INF1007 - Programação II

Lab 8 - Listas Encadeadas

Suponha uma aplicação matemática que manipule polinômios da forma

p(x) = c₁x^e₁ + c₂x^e₂ + ...  + c_nx^e_n

Podemos representar um polinômio desse tipo através de uma lista encadeada, onde cada elemento tem três campos: o coeficiente c_n, o expoente e_n e um ponteiro para o próximo elemento. Podemos definir este elemento usando a estrutura


struct no {
  int coef;
  int exp;
  struct no *prox;
};
typedef struct no No;

Nosso ponto de partida é o programa lab8.c, que usa como entrada de dados os arquivos polinomio1.txt, polinomio2.txt e polinomio3.txt. Cada um desses arquivos tem os dados de um polinômio, isto é, cada linha tem o coeficiente e o expoente de um elemento do polinômio.

Nosso programa (isto é, sua função main):

Lê os arquivos de entrada para montar duas listas encadeadas (p1, p2 e p3) que representam os três polinômios.
- Para montar as listas, ele usa a função insereElemento, que recebe como parâmetros o primeiro nó da lista atual e o coeficiente e expoente do elemento a inserir.
- O novo elemento é inserido no início da lista, e a função retorna o novo início da lista (isto é, o ponteiro para o novo nó inserido).
Depois de criar as listas que representam os polinômios, nosso programa calcula a derivada do primeiro polinômio (uma lista criada pela função derivadaPolinomio) e exibe o polinômio e sua derivada (usando a função imprimePolinomio).
Em seguida, usando a função comparaPolinomios, o programa compara o primeiro polinômio com ele mesmo, o primeiro polinômio com o segundo e o primeiro polinômio com o terceiro, exibindo os resultados.
Depois, o programa calcula o polinômio soma dos dois primeiros polinômios, e exibe os dois polinômios e sua soma.
Ao final, nosso programa libera as listas que representam os polinômios, a derivada e o polinômio soma, usando a função liberaPolinomio.

Mas as funções derivadaPolinomio, comparaPolinomios e somaPolinomios ainda não estão prontas. Por enquanto nosso programa vai imprimir:


Polinomio1: 1x<15> - 5x<10> + 2x<7> - 4x<5> + 1x<2> - 7x<1>
Derivada: <VAZIO>
Polinomio p1 NAO IGUAL a p1
Polinomio p1 NAO IGUAL a p2
Polinomio p1 NAO IGUAL a p3
Polinomio1: 1x<15> - 5x<10> + 2x<7> - 4x<5> + 1x<2> - 7x<1>
Polinomio2: 2x<15> + 6x<10> - 5x<6> + 1x<5> - 8x<4> + 5x<0>
Soma dos polinomios: <VAZIO>

Exercícios

Implemente a função derivadaPolinomio (note que o arquivo lab8.c já tem essa função, mas por enquanto ela apenas retorna NULL).
A função derivadaPolinomio recebe como parâmetro uma lista encadeada que representa um polinômio (isto é, um ponteiro para o primeiro nó desta lista) e retorna um novo polinômio (uma nova lista) que é a derivada do polinômio original.
```
No *derivadaPolinomio(No *p);
```
A derivada de um polinômio é um polinômio cujos elementos são as derivadas de cada um dos elementos do polinômio original. A derivada de um elemento c_nx^e_n é e_nc_nx^e_n-1. Por exemplo, a derivada do polinômio 3x² - 2x¹ + 1 é 6x¹- 2 (note que não representamos um elemento cujo coeficiente é 0!)
Para inserir cada elemento no novo polinômio derivada, sua função deve usar a função insereElemento.
A saída esperada para o nosso programa agora é:
```
Polinomio1: 1x<15> - 5x<10> + 2x<7> - 4x<5> + 1x<2> - 7x<1>
Derivada:  - 7x<0> + 2x<1> - 20x<4> + 14x<6> - 50x<9> + 15x<14>
Polinomio p1 NAO IGUAL a p1
Polinomio p1 NAO IGUAL a p2
Polinomio p1 NAO IGUAL a p3
Polinomio1: 1x<15> - 5x<10> + 2x<7> - 4x<5> + 1x<2> - 7x<1>
Polinomio2: 2x<15> + 6x<10> - 5x<6> + 1x<5> - 8x<4> + 5x<0>
Soma dos polinomios: <VAZIO>
```
Você deve ter reparado que a lista que representa a derivada do primeiro polinômio têm seus elementos na ordem inversa dos elementos correspondentes do polinômio original... Isto aconteceu porque inserimos cada novo elemento gerado para a derivada no início da lista que a representa!
Podemos melhorar nosso programa implementando a função, insereNoFinal. Assim como insereElemento, essa função recebe como parâmetros o primeiro nó da lista atual e o coeficiente e expoente do elemento a inserir:
```
No *insereNoFinal(No *p, int coef, int exp);
```
Porém o novo elemento deve ser inserido no final da lista (ou seja, após o último elemento da lista original). Se a lista original estiver vazia, a função retorna um ponteiro para o novo elemento. Caso contrário, após inserir o novo elemento no final da lista, ela retorna o ponteiro para o primeiro elemento da lista.
Novamente, o arquivo lab8.c já tem essa função. Substitua a implementação "dummy" corrente por sua implementação.
Depois de implementar essa nova função, substitua em derivadaPolinomio a chamada a insereElemento por uma chamada a insereNoFinal. Com isso, a nova saída do programa deverá ser
```
Polinomio1: 1x<15> - 5x<10> + 2x<7> - 4x<5> + 1x<2> - 7x<1>
Derivada1: 15x<14> - 50x<9> + 14x<6> - 20x<4> + 2x<1> - 7x<0>
Polinomio p1 NAO IGUAL a p1
Polinomio p1 NAO IGUAL a p2
Polinomio p1 NAO IGUAL a p3
Polinomio1: 1x<15> - 5x<10> + 2x<7> - 4x<5> + 1x<2> - 7x<1>
Polinomio2: 2x<15> + 6x<10> - 5x<6> + 1x<5> - 8x<4> + 5x<0>
Soma dos polinomios: <VAZIO>
```
Implemente agora a função comparaPolinomios. Note que o arquivo lab8.c já tem essa função, mas por enquanto ela retorna sempre 0 (falso).
A função comparaPolinomios recebe como parâmetros dois polinômios e retorna 1 de os polinômios são iguais e 0 caso contrário.
```
int comparaPolinomios(No *p1, No* p2);
```
Assuma que os dois polinômios de entrada estão ordenados decrescentemente por expoente e que não há num polinômio dois elementos com o mesmo expoente.
Dois polinômios com as características acima serão considerados iguais se tiverem os mesmos elementos (isto é, elementos com o mesmo coeficiente e o mesmo expoente) na mesma ordem.
Atenção! Sua função deve estar preparada para receber polinômios de entrada de tamanho (número de elementos) diferente!
Se sua função estiver correta, a nova saída do programa deverá ser
```
Polinomio1: 1x<15> - 5x<10> + 2x<7> - 4x<5> + 1x<2> - 7x<1>
Derivada1: 15x<14> - 50x<9> + 14x<6> - 20x<4> + 2x<1> - 7x<0>
Polinomio p1 IGUAL a p1
Polinomio p1 NAO IGUAL a p2
Polinomio p1 NAO IGUAL a p3
Polinomio1: 1x<15> - 5x<10> + 2x<7> - 4x<5> + 1x<2> - 7x<1>
Polinomio2: 2x<15> + 6x<10> - 5x<6> + 1x<5> - 8x<4> + 5x<0>
Soma dos polinomios: <VAZIO>
```
Finalmente, implemente a função somaPolinomios (note que o arquivo lab8.c já tem essa função, mas por enquanto ela apenas retorna NULL).
A função somaPolinomios recebe como parâmetros dois polinômios e retorna um novo polinômio (uma nova lista) que é a soma desses dois polinômios.
```
No *somaPolinomios(No *p1, No* p2);
```
Para somar dois polinômios:
- se ambos os polinômios contém um elemento com um mesmo expoente, o polinômio soma deverá conter um elemento que tem este expoente e um coeficiente igual à soma dos coeficientes dos elementos com este expoente em cada polinômio
- se um dos polinômios contém um elemento com um dado par coeficiente/expoente e o outro polinômio não contém nenhum elemento com este expoente, o polinômio soma deverá conter um elemento que tem este par coeficiente/expoente.
Por exemplo, a soma dos polinômios 3x² - 2x¹ + 1 e 6x¹- 2 é 3x² + 4x¹ - 1
Novamente, sua função pode considerar que os elementos dos dois polinômios estão ordenados decrescentemente por expoente e que não há num polinômio dois elementos com o mesmo expoente.
Atenção! O polinômio soma também deverá ter seus elementos ordenados decrescentemente por expoente.
Se sua função estiver correta, a saída do nosso programa agora é:
```
Polinomio1: 1x<15> - 5x<10> + 2x<7> - 4x<5> + 1x<2> - 7x<1>
Derivada: 15x<14> - 50x<9> + 14x<6> - 20x<4> + 2x<1> - 7x<0>
Polinomio p1 IGUAL a p1
Polinomio p1 NAO IGUAL a p2
Polinomio p1 NAO IGUAL a p3
Polinomio1: 1x<15> - 5x<10> + 2x<7> - 4x<5> + 1x<2> - 7x<1>
Polinomio2: 2x<15> + 6x<10> - 5x<6> + 1x<5> - 8x<4> + 5x<0>
Soma dos polinomios: 3x<15> + 1x<10> + 2x<7> - 5x<6> - 3x<5> - 8x<4> + 1x<2> - 7x<1> + 5x<0>
```