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);
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);
p
e q
, e devolve como
valor da função a soma de p
e q
.Polinomio subtrai(Polinomio p, Polinomio q);
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);
p
e q
, e devolve como
valor da função o produto de p
e q
.Polinomio deriva(Polinomio p);
p
e devolve como valor da função o
polinômio que é a derivada de p
.double calcula(Polinomio p, double x);
p
e um real x
e devolve o
valor do polinômio p
em x
.void imprime(Polinomio p, FILE *arq);
p
e o imprime no arquivo
arq
. O parâmetro arq
deve ser um arquivo
aberto para escrita.void libera(Polinomio p);
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 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
, multiplica
e
deriva
criam novos polinômios.
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
|
|
|
|
|
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
|
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; static Termo *lista_livre = NULL;
A estrutura Termo
é usada para as células dos polinômios. Em
outras palavras, cada polinômio é uma lista encadeada de Termo
s.
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.
A lista livre
Sua implementação deve manter uma lista livre, com os Termo
s
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 cria_monomio
devolve um Polinomio
constituído por uma célula recém retirada
da lista livre ou recém alocada via malloc
. (Ela obtém essa
célula por meio de uma chamada à função aloca_termo
, descrita
abaixo.) A função libera
insere na lista livre todas as células
do polinômio referenciado por p
. (Ela faz isso mediante chamadas
à função libera_termo
, descrita abaixo.)
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.
Sua biblioteca deve conter duas funções auxiliares com os seguintes protótipos:
static Termo *aloca_termo();
static void libera_termo(Termo *p);
Essas são funções de manipulação da lista livre. Todo acesso à lista livre é
feito por meio de chamadas a aloca_termo
ou a
libera_termo
. A função aloca_termo
devolve o
endereço de um Termo
retirado da lista livre ou (caso essa lista
esteja vazia) alocado diretamente via malloc
. A função
libera_termo
insere na lista livre o Termo
cujo
endereço é recebido como parâmetro. Opcionalmente você pode fazer com que
libera_termo
examine o comprimento da lista livre antes de
inserir um Termo
na lista. Se esse comprimento for menor que um
valor pré-fixado, a função insere o Termo
na lista livre. Caso
contrário libera_termo
faz uma chamada a free
para
devolver ao sistema a memória ocupada pelo Termo
. Esse esquema
evita que a lista livre cresça indefinidamente.
Note que as demais partes da biblioteca nunca precisarão chamar
malloc
ou free
para alocar ou liberar termos. A
motivação para se usar uma lista livre é precisamente a economia nas chamadas
a malloc
e free
, pois essas funções são mais
demoradas que as funções aloca_termo
e libera_termo
.
(Por que malloc
e free
não podem ser tão eficientes
quanto aloca_termo
e libera_termo
?)
Requisitos adicionais sobre a implementação da biblioteca
soma
e subtrai
deve ser eficiente, ou seja, os polinômios de
entrada devem ser percorridos apenas uma vez.
static Polinomio multiplica_por_monomio(Polinomio p, double coef, int exp)
Essa função devolve o produto do polinômio p
pelo monomio cujo
coeficiente é coef
e cujo expoente é exp
. O
polinômio devolvido é alocado dinâmicamente e deve ser liberado (mediante
chamada à funcão libera
) quando não tiver mais utilidade para
quem chamou multiplica_por_monomio
.
Note que multiplica_por_monomio
é uma função interna da
biblioteca. Por esse motivo ela é declarada com static
e não
aparece no arquivo polinomio.h
.multiplica
deve obrigatoriamente
usar a função multiplica_por_monomio
. (O cumprimento desse
requisito facilita bastante a tarefa de escrever a função
multiplica
.)
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
u=t'
u(x) = -8x + 3x^2 - 4x^3 - 45x^4 + 12x^5 + 35x^6 + 32x^7 + 108x^8
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
", ou da forma "v=s'
" atribui à
variável v
o polinômio resultado de uma operação (soma,
subtração, multiplicação ou derivação) aplicada aos polinômios associados às
variáveis s
e t
(nos três primeiros casos) ou ao
polinômio associado à variável s
(no caso da derivação). 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.
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
var[0]
seja o Polinomio
associado à variável cujo
identificador é a
,var[1]
seja o Polinomio
associado à variável cujo
identificador é b
,var[2]
seja o Polinomio
associado à variável cujo
identificador é c
, etc.
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 ":
"!
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:
arq-entrada
é o nome do arquivo de
entrada.arq-saida
é o nome do arquivo de saída.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:
gcc
ou o
Code::Blocks
(que na verdade chama o gcc
para
fazer a compilação). Caso você use diretamente o gcc
, passe
ao compilador (na linha de comando) as seguintes opções:
-Wall -ansi -pedantic -O2 -U_FORTIFY_SOURCECaso você use o
Code::Blocks
, entre em
Settings -> Compiler and debugger... -> Compiler settings -> Compiler Flags,
selecione as quatro opcões correspondentes a -Wall
,
-ansi
, -pedantic
e -O2
, e clique
em OK. Entre também em
Settings -> Compiler and debugger... -> Compiler settings -> Other options,
digite -U_FORTIFY_SOURCE
na caixa de texto
Other options e clique OK.
ep1-<seu-número-USP>.tar.gz
ou
ep1-<seu-número-USP>.zip
.
Por exemplo: ep1-12345678.zip
..tar.gz
ou .zip
. (Exemplo:
ep1-12345678
.) Todos os arquivos desempacotados devem
estar dentro desse diretório.polinomio.h
com a interface da sua
biblioteca. O conteúdo desse arquivo deve ser o especificado
neste enunciado.polinomio.c
com a implementação da sua
biblioteca.cliente.c
com o programa cliente que
faz chamadas às funções da sua biblioteca. (É nesse arquivo que
está a função main
.).h
ou .c
que você utilizar para funções auxiliares compiladas
separadamente. Por exemplo, se você tiver um módulo compilado
separadamente contendo apenas a função mallocX
,
então você deverá entregar os arquivos mallocx.h
e
mallocx.c
..h
ou .c
devem ter
um cabeçalho como o seguinte:
/**************************************************************/ /* Aluno: Fulano de Tal */ /* Número USP: 12345678 */ /* Curso: ... */ /* Exercicio-Programa 1 -- Manipulação de Polinômios Esparsos */ /* MAC0122 -- 2010 -- POLI/Eletrica (PSI), -- Prof. Reverbel */ /* Compilador: ... (gcc ou Code::Blocks) versão ... */ /* Sistema Operacional: ... */ /**************************************************************/