Primeiro Exercício-Programa

Manipulação de Polinômios Esparsos

Entrega: 22 de setembro

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 "polinomio". 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);

void soma(Polinomio p, Polinomio q);

void subtrai(Polinomio p, Polinomio q);

void multiplica(Polinomio p, Polinomio q);

Polinomio deriva(Polinomio p);

int grau(Polinomio p);

double calcula(Polinomio p, double x);

Polinomio duplica(Polinomio p);

void imprime(Polinomio p);

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.)

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

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 forem ser mais utilizados. Por exemplo: se uma variável v referenciar um Polinomio, é um erro deixar que v saia de escopo sem antes executar libera(v).

As funções soma, subtrai e multiplica destroem o Polinomio originalmente referenciado pelo primeiro parâmetro (o polinômio p) e liberam a memória ocupada por aquele polinômio. Caso seja necessário preservar uma cópia desse polinômio, tal cópia deve ser obtida com uma chamada à função duplica: 

    Polinomio p, q, p_salvo;
    p = ...;
    q = ...;
    p_salvo = duplica(p);
    soma(p, q); /* destrói o valor original de p */

É 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, deriva e duplica criam novos polinômios. No caso da função duplica, o Polinomio criado é uma "cópia funda" (deep copy) de um já existente.

Implementação da Biblioteca

Cada polinômio é armazenado em uma lista ligada com cabeça de lista (para facilitar a manipulação). 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)=-x5+2x3+5x2-7 fica armazenado em uma lista de acordo com a seguinte figura.

prox
-7 0 prox
5 2 prox
2 3 prox
-1 5 NULL

onde prox representa um apontador para a célula seguinte na figura e a primeira célula é a cabeça da lista. Note a ausência dos termos correspondentes a x4 e x, que neste polinômio têm coeficientes nulos.

Exemplo 2: O polinômio nulo p(x)=0 é representado por uma lista como a que aparece na figura abaixo.

NULL

Note que essa lista contém somente a cabeça de lista, pois o polinômio p(x)=0 não possui nehum termo com coeficiente não nulo.

A implementação da biblioteca (o arquivo polinomio.c) deve incluir as seguintes declarações: 

#include <stdlib.h>
#include "polinomio.h"

typedef struct termo {
    double coef;
    int exp;
    struct termo *prox;
} Termo;

static Termo *lista_livre = NULL;

Sua implementação deve manter uma lista livre, com os Termos alocados via malloc mas disponíveis no momento. O apontador lista_livre aponta para o início dessa lista. Um novo Termo deve ser alocado através da função malloc apenas quando a lista livre estiver vazia. A função Polinomio cria_monomio(double coef, int exp) devolve um Polinomio constituído por duas células recém-retiradas da lista livre (ou alocadas diretamente via malloc): a cabeça de lista (um Termo dummy, que existe apenas por conveniência) e o "verdadeiro Termo" do monômio, termo este já preenchido com coef, exp e NULL. A função void libera(Polinomio p) insere na lista livre todas as células do polinômio referenciado por p.

Não deixe sua implementação vazar memória, ou seja, inclua na lista livre todas as células que não estiverem em um polinômio no momento.

Programa Cliente

Além da implementação das funções da biblioteca, você deverá entregar um programa principal que teste essas funções. O programa principal deve ler de um arquivo uma seqüência de polinômios e operações e mostrar o resultado da execução de cada uma destas operações sobre os polinômios dados.

As operações de soma, subtração, multiplicação, derivação, grau, cópia e calcula valor são codificadas por '+', '-', '*', 'd', 'g', 'c' e 'v' respectivamente. Cada linha do arquivo contem ou um polinômio, dado por um inteiro k e uma seqüência de k pares de números (cada par representando um termo), ou uma operação. No caso do polinômio, suponha que os termos são dados em ordem crescente de expoente, para facilitar. No caso da operação calcula, a letra 'v' vem seguida de um valor real. Uma operação se refere sempre ao último polinômio manipulado e, caso a operação seja binária, ao próximo polinômio no arquivo. Tome cuidado com a manipulação do arquivo de entrada. Em C, vários problemas podem acontecer na leitura. Assim, numa primeira etapa, implemente a leitura dos dados e a impressão de um polinômio. Apenas depois que essa parte estiver funcionando bem, passe a escrever e testar as demais funções de manipulação de polinômios. Teste cada função separadamente, para não se atrapalhar.

Após a leitura de cada polinômio do arquivo de entrada, o seu programa deve imprimir o polinômio lido. Também após o processamento de cada operação, o seu programa deve imprimir o resultado da operação.

Abaixo mostramos um exemplo de arquivo de entrada. 

3 1 2 -1 3 4 5
+
4 -1 0 2 2 1 3 3 4
g
-
4 -1 0 2 2 1 3 3 4
*
1 1 1
d
*
2 1 1 -1 2

A saída para tal exemplo poderia ser algo como: 

(x^2-x^3+4x^5) + (-1+2x^2+x^3+3x^4) = -1+3x^2+3x^4+4x^5 
O grau de -1+3x^2+3x^4+4x^5 e' 5.
(-1+3x^2+3x^4+4x^5) - (-1+2x^2+x^3+3x^4) = x^2-x^3+4x^5
(x^2-x^3+4x^5) * (x) = x^3-x^4+4x^6
A derivada de x^3-x^4+4x^6 e' 3x^2-4x^3+24x^5.
(3x^2-4x^3+24x^5) * (x-x^2) = 3x^3-7x^4+4x^5+24x^6-24x^7

Avisos

Este trabalho deve ser entregue até 22/09, através do sistema Paca/Moodle.

Valid CSS! Valid XHTML 1.0! Last modified: Thu Oct 9 17:25:25 BRT 2008