Terceiro Exercício-Programa

Manipulação de Polinômios Esparsos

Entrega: 24 de novembro

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

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

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

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 executar libera(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 e multiplica 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
 
 
-7 0 prox
 
5 2 prox
 
2 3 prox
 
-1 5 NULL

Em cada uma das células acima, o campo prox representa um apontador para a célula seguinte na figura. O retângulo mais à esquerda é a variável que contém o início (o endereço da primeira célula) 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.

inicio
NULL

Note que essa lista é vazia, pois o polinômio p(x)=0 não possui nenhum termo com coeficiente não nulo. Como a lista não possui nenhuma célula, a variável que indica o início da lista contém NULL.

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

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

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

A estrutura Termo é usada para as células dos polinômios. Em outras palavras, cada polinômio é uma lista encadeada de Termos. Note, entretanto, que os programas que forem usar a sua biblioteca de polinômios (os clientes da biblioteca) não precisam saber nada disso. Esses programas não precisam conhecer a estrutura Termo, nem saber que internamente a biblioteca implementa polinômios como listas encadeadas sem cabeça. Para escrever um cliente é suficiente conhecer a interface da biblioteca (o arquivo polinomio.h) e saber o que fazem as funções dessa interface.

Requisitos adicionais sobre a implementação da biblioteca

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 é uma calculadora que mantém um conjunto de 23 variáveis identificadas pelas letras minúsculas de 'a' a 'w'. Os valores dessas variáveis são polinômios. O usuário da calculadora pode efetuar operações envolvendo essas variáveis.

Este é um exemplo de uso da calculadora:

a?
a(x) = 0 
p? 
p(x) = 0 
p: 3 1 2 -1 3 4 5 
p(x) = x^2 - x^3 + 4x^5 
q: 4 3 4 -1 0 1 3 2 2 
q(x) = -1 + 2x^2 + x^3 + 3x^4 
r=p+q 
r(x) = -1 + 3x^2 + 3x^4 + 4x^5 
s=p*q 
s(x) = -x^2 + x^3 + 2x^4 - 5x^5 + 2x^6 + 5x^7 + 4x^8 + 12x^9 
t=s-r 
t(x) = 1 - 4x^2 + x^3 - x^4 - 9x^5 + 2x^6 + 5x^7 + 4x^8 + 12x^9 
t(1) 
t(1) = 11 
t(123.456) 
t(123.456) = 8.0163e+19 
p=p*p 
p(x) = x^4 - 2x^5 + x^6 + 8x^7 - 8x^8 + 16x^10 
p(2) 
p(2) = 15376 
p=p*p 
p(x) = x^8 - 4x^9 + 6x^10 + 12x^11 - 47x^12 + 48x^13 + 80x^14 - 192x^15 + 96x^16 + 256x^17 - 256x^18 + 256x^20 
p(2) 
p(2) = 2.36421e+08 

As linhas em negrito pertencem ao arquivo de entrada (ou podem ter sido digitadas pelo usuário, de modo interativo). As demais linhas são geradas pela calculadora e formam a saída do programa.

Cada linha da entrada contém um comando para a calculadora. Todo comando começa com uma letra minúscula de 'a' a 'w'. Essa letra identifica uma variável da calculadora. O comando "v?" (uma varíavel da calculadora seguida do caractere "?") é um comando de consulta que imprime o polinômio associado à variável especificada. No início da sua execução, a calculadora inicializa com polinômios nulos todas as variáveis de 'a' a 'w'. (Seu programa deve fazer isso!) Por esse motivo, a consulta "a?" imprime a informação "a(x) = 0" (a é um polinômio nulo). A primeira das consultas "p?" imprime informação análoga.

Um comando da forma "v: n <lista de n pares>" atribui à variável v o polinômio cujos termos não nulos são especificados por uma lista de n pares de números. Em cada um desses pares de números, o primeiro elemento é o coeficiente do termo (um número real) e o segundo elemento é o expoente do termo (um número inteiro não negativo). Assim, o comando "p: 3 1 2 -1 3 4 5" atribui à variável p um polinômio com três termos não nulos (o polinômio x2 - x3 + 4x5). Em resposta a esse comando, a calculadora imprime o polinômio atribuído à variável p (a informação p(x) = x^2 - x^3 + 4x^5). Note que a lista de pares não precisa ser fornecida em ordem crescente de expoente. No comando "q: 4 3 4 -1 0 1 3 2 2" os pares são fornecidos numa ordem arbitrária, mas os termos do polinômio atribuído à variável q aparecem em ordem crescente de expoente (q(x) = -1 + 2x^2 + x^3 + 3x^4).

Um comando da forma "v=s+t", ou da forma "v=s-t", ou da forma "v=s*t" atribui à variável v o polinômio resultado de uma operação (soma, subtração ou multiplicação) aplicada aos polinômios associados às variáveis s e t. Em resposta a um comando assim, a calculadora imprime o polinômio atribuído à variável v. O exemplo acima contém vários comandos desse tipo. Note que a mesma variável pode aparecer nos dois lados da atribuição ("p=p*p").

Finalmente, um comando da forma "v(<um número real>)" faz a calculadora imprimir o valor do polinômio v (mais precisamente, o valor do polinômio associado à variável v) sobre o número real especificado. Em outras palavras, o programa calcula e imprime v(x) para o valor de x especificado.

Implementação do Programa Cliente

Note que o segundo caractere de cada comando ('?', ':', '=' ou '(') define o tipo do comando. O primeiro caractere especifica a variável afetada pelo comando. Você pode usar esses fatos para simplificar a implementação do seu programa cliente.

Para implementar as variáveis da calculadora, utilize um vetor com 23 posições (uma para cada letra minúscula de 'a' a 'w'), que contenha em cada posição uma referência para um polinômio.

Mais especificamente, seu programa cliente deve manter um vetor

    Polinomio var[23]; /* O tipo Polinomio é o definido pela biblioteca. */

de modo que

Em outras palavras, as 23 variáveis da calculadora (a, b, c, ..., w) são implementadas pelas 23 posições do vetor var (var[0], var[1], var[2], ..., var[22]). Dessa forma pode-se ter acesso a um polinômio de modo bem eficiente, a partir da letra minúscula que identifica o polinômio.

No início da execução do programa, todas as posições do vetor var devem ser inicializadas com polinômios nulos. Para obter polinômios nulos, faça chamadas à função cria_monomio passando o valor zero no parâmetro coef.

Tome o seguinte cuidado com a leitura dos dados no seu programa cliente: leia cada linha da entrada até o último caractere da linha (o caractere '\n' que termina toda linha), incluindo esse caractere. Se você não fizer isso, quando você estiver querendo ler o primeiro caractere da próxima linha você acabará pegando o '\n' da linha anterior (ou até mesmo algum caractere que apareceu antes desse '\n', como por exemplo um espaço presente ao final da linha anterior). Para não ter esse tipo de problema, faça seu cliente ler toda linha até o fim, passando para a linha seguinte só depois de ler um '\n'!

Este esqueleto de programa cliente inclui uma função auxiliar (descarta_resto_da_linha) que lê e descarta todos os caracteres ainda não lidos da linha atual. Ele contém também um fragmento da função main com o laço de leitura da entrada. Esse fragmento mostra uma chamada a descarta_resto_da_linha, efetuada quando o cliente encontra uma linha cujo primeiro caractere não é uma variável válida. Faça o seu programa cliente chamar descarta_resto_da_linha no tratamento de todo comando da calculadora: depois de ler o último caractere útil de um comando, descarte o resto da linha da entrada.

Note que o nosso esqueleto de programa cliente tem mais uma função auxiliar (le_polinomio), esta ainda não implementada. Implemente a função le_polinomio e use-a no tratamento do comando ":"!

Argumentos na Linha de Comando

Seu programa cliente deve tratar os seguintes argumentos na linha de comando: 

    ./cliente [arq-entrada] [arq-saida]
A linha de comando acima pressupõe que o nome do arquivo executável é cliente.

Os argumentos aceitos pelo programa têm estes significados:

Exemplo: 

    ./cliente entrada.txt saida.txt

O tratamento dado a cada argumento é determinado pela posição do argumento na linha de comando. O primeiro argumento é o arq-entrada e o segundo é o arq-saida. Pode ocorrer omissão de argumentos:

Observações

Last modified: Mon Nov 9 16:53:43 BRST 2009