Polinomios Esparsos

Primeiro Exercício-Programa

Manipulação de Polinômios Esparsos

Entrega: 25 de abril

Dúvidas sobre este EP devem ser enviadas para o Fórum de Discussão de MAC0122

Polinômios esparsos podem ser representados eficientemente por meio de listas encadeadas. Neste exercício-programa você escreverá uma biblioteca que usa listas encadeadas para implementar o tipo abstrato de dados "polinômio". A interface da sua biblioteca deve ser o arquivo polinomio.h, cujo conteúdo é o seguinte:

typedef struct termo *Polinomio;

Polinomio cria_monomio(double coef, int exp);

Polinomio soma(Polinomio p, Polinomio q);

Polinomio subtrai(Polinomio p, Polinomio q);

Polinomio multiplica(Polinomio p, Polinomio q);

Polinomio deriva(Polinomio p);

double calcula(Polinomio p, double x);

void imprime(Polinomio p, FILE *arq);

void libera(Polinomio p);

Note que o arquivo polinomio.h especifica o que se pode fazer com um Polinomio (isto é, as operações sobre polinômios), mas não informa como um Polinomio é implementado. O tipo Polinomio é definido como um apontador para uma estrutura cuja definição não é parte da interface da biblioteca. (A definição da estrutura termo não aparece no arquivo polinomio.h.) Isso faz com que o tipo Polinomio seja abstrato. Note, ainda, que esse tipo também é de primeira classe, pois podemos ter múltiplos polinômios e podemos armazenar esses polinômios em variáveis do tipo Polinomio.

Abaixo descrevemos o que deve fazer cada uma das funções da biblioteca:

* Polinomio cria_monomio(double coef, int exp);

Cria um novo monômio (um polinômio com um só termo) cujo coeficiente é coef e cujo expoente é exp e devolve o monômio criado. Caso o parâmetro coef seja igual a zero, esta função cria um polinômio nulo (um polinômio que não possui nenhum termo com coeficiente não nulo) e devolve o polinômio nulo criado.

* Polinomio soma(Polinomio p, Polinomio q);

Recebe dois polinômios, p e q, e devolve como valor da função a soma de p e q.

* Polinomio subtrai(Polinomio p, Polinomio q);

Recebe dois polinômios, p e q, e devolve como valor da função a diferença entre p e q, ou seja, p-q.

* Polinomio multiplica(Polinomio p, Polinomio q);

Recebe dois polinômios, p e q, e devolve como valor da função o produto de p e q.

* Polinomio deriva(Polinomio p);

Recebe um polinômio p e devolve como valor da função o polinômio que é a derivada de p.

* double calcula(Polinomio p, double x);

Recebe um polinômio p e um real x e devolve o valor do polinômio p em x.

* void imprime(Polinomio p, FILE *arq);

Recebe um polinômio p e o imprime no arquivo arq. O parâmetro arq deve ser um arquivo aberto para escrita.

* void libera(Polinomio p);

Libera a memória ocupada pelo polinômio p.

Exceto pela função libera, nenhuma das funções acima modifica algum polinômio recebido como parâmetro. Todos os polinômios devolvidos por essas funções são alocados dinâmicamente e devem ser liberados (mediante chamadas à funcão libera) quando não tiverem mais utilidade para o cliente da biblioteca. Por exemplo: se uma variável v referenciar um Polinomio, é um erro deixar que v saia de escopo sem antes executarlibera(v). Também é um erro atribuir outro Polinomio a v sem antes executar libera(v). Considere o seguinte exemplo, que imprime a soma e o produto de dois polinômios dados:

Polinomio p, q, r;

p = ...; /* inicializa p com algum polinômio */

q = ...; /* inicializa q com outro polinômio */

v = soma(p, q); /* inicializa v com o polinômio soma p+q */

imprime(v, stdout); /* imprime o polinômio soma */

libera(v); /* libera o polinômio soma <<<<< */

v = multiplica(p, q); /* atribui a v o polinômio produto p*q */

imprime(v, stdout); /* imprime o polinômio produto */

O fragmento de código acima estaria errado sem a chamada libera(v). O fragmento a seguir também está errado, pois os polinômios devolvidos pelas chamadas às funções soma e multiplica são passados diretamente à função imprime, sem serem liberados:

Polinomio p, q, r;

p = ...; /* inicializa p com algum polinômio */

q = ...; /* inicializa q com outro polinômio */

imprime(soma(p, q), stdout); /* imprime o polinômio soma p+q */

imprime(multiplica(p, q), stdout); /* imprime o polinômio produto p*q */

É importante entender que um cliente da biblioteca precisa chamar funções da biblioteca para obter polinômios. O cliente não tem como "fabricar" polinômios diretamente. As funções cria_monomio, soma, subtrai,multiplica e deriva criam novos polinômios.

Implementação da Biblioteca

Cada polinômio é armazenado em uma lista ligada sem cabeça. Cada célula da lista é do tipo struct termo e armazena os dados de um dos termos do polinômio: o coeficiente e o expoente, além do apontador para o próximo termo. Apenas termos com coeficiente não-nulo devem estar na lista e, para que a manipulação seja mais eficiente, os termos devem aparecer na lista em ordem crescente do expoente.

Exemplo 1: O polinômio p(x)=-7+5x2+2x3-x5 fica armazenado em uma lista de acordo com a seguinte figura.

inicio |

|