Polinômios - LIstas Encadeadas

Prévia do material em texto

Estruturas de Dados - Turma F
Listas Encadeadas
Prof. Marcos F. Caetano - 2017/1
Matr´ıcula Nome
1. Um bom exemplo da utilizac¸a˜o de estruturas de dados dinaˆmicas do tipo lista e´ a repre-
sentac¸a˜o de polinoˆmios. Seja o seguinte polinoˆmio:
P (X) = CnX
n + Cn−1Xn−1 + . . . + CkXk + . . . + C3X3 + C2X2 + C1X1 + C0 (1)
Um polinoˆmio pode ser representado por um conjunto de pares que associam para um dado
X o correspondente coeficiente e poteˆncia. Ou seja, para P (X) = 4X5 − 11X3 + 3X2 − 4
seria representado pelos pares {(4, 5), (−11, 3), (3, 2), (−4, 0)}. Para cada par, o primeiro
elemento representa o coeficiente de X, e o segundo elemento representa o valor da poteˆncia
de X.
Uma lista ordenada crescente pode representar, de forma adequada, um polinoˆmio, se con-
siderarmos que na˜o existem repetic¸o˜es da mesma poteˆncia de X na lista. Essa considerac¸a˜o
faz com que seja poss´ıvel usar a pro´pria poteˆncia de X como a chave de ordenac¸a˜o.
Ao usar a poteˆncia de X para ordenar a lista, o exemplo apresentado anteriormente seria
escrito da seguinte forma: P : {(−4, 0), (3, 2), (−11, 3), (4, 5)}. Observe, na sequencia, a
ordenac¸a˜o crescente dos pares presentes em P , levando em considerac¸a˜o o valor da poteˆncia
de X.
Sejam as seguintes representac¸o˜es ba´sicas dos componentes que formam um polinoˆmio e
suas respectivas func¸o˜es de acesso:
typedef struct nodo{
float coeficiente;
int expoente;
struct nodo* proximo;
} p_nodo;
typedef struct polinomio{
p_nodo* primeiro;
} l_polinomio;
/*
Func¸~ao retorna um nodo do polinomio inicializado
com zero e ponteiro NULL.
*/
p_nodo* getNodo();
/*
Func¸~ao retorna a estrutura do polinomio com
ponteiro NULL.
*/
l_polinomio * getPolinomio();
/*
Func¸~ao adiciona um termo a um polino^mio.
*/
void inserir_nodo(l_polinomio* pol, float coef, int expo );
/*
Func¸~ao imprime um polino^mio segundo especificac¸~ao.
*/
void imprime_polinomio(l_polinomio* pol, char n);
/*
Func¸~ao realiza o ca´lculo do polino^mio dado um valor de X.
*/
float calcula_polinomio(l_polinomio* pol, float x);
As func¸o˜es acima sa˜o utilizadas das seguinte forma:
#include "polinomio.h"
int main(){
l_polinomio* polinomio = getPolinomio();
float s;
inserir_nodo(polinomio, 10, 2);
inserir_nodo(polinomio, 6, 1);
inserir_nodo(polinomio, -1, 0);
inserir_nodo(polinomio, -2, 2);
imprime_polinomio(polinomio, ’p’);
s = calcula_polinomio(polinomio, 4);
printf("Polino^mio calculado: %.2f \n", s);
}
Como resultado, as seguinte sa´ıda e´ apresentada no terminal:
p ( X ) = - 1.00 + 6.00*X^1 + 8.00*X^2
Polino^mio calculado: 151.00
Implemente as func¸o˜es apresentadas acima de acordo com a especificac¸a˜o. Por
fim, em sua implementac¸a˜o, considere os seguintes pontos.
0.1 Inserc¸a˜o de um termo no polinoˆmio
Representada pela func¸a˜o inserir nodo(), sera´ responsa´vel pela inserc¸a˜o de um novo termo
com um coeficiente e uma poteˆncia quaisquer. Entretanto, se durante a inserc¸a˜o for obser-
vada a pre-existeˆncia de um termo com a mesma poteˆncia, havera´ a soma dos coeficientes.
Isso garante que em um polinoˆmio na˜o exista dois termos com o mesmo valor de poteˆncia,
facilitando a tarefa de desenvolvimento da representac¸a˜o de um polinoˆmio usando a lista
encadeada ordenada.
A considerac¸a˜o de que todo polinoˆmio tem pelo menos o termo de expoente zero garante
uma facilidade na criac¸a˜o da func¸a˜o inserir nodo() porque, ao incluir um novo elemento
na lista, na˜o e´ mais necessa´rio pensarmos no tratamento que seria preciso para incluir um
elemento no in´ıcio da lista, pois la´ estara´ pelo menos o termo de expoente zero.
Considerando o polinoˆmio P (X) = 10X2 + 6X − 1, caso seja realizada a inserc¸a˜o do termo
−2X2, obtemos como resultado P (X) = 8X2 + 6X − 1. Neste caso, assume-se que na˜o se
pode existir mais de um termo com a mesma poteˆncia de X. Neste caso, a rotina de inserc¸a˜o
soma automaticamente os termos de mesma poteˆncia; sendo assim, 10X2 − 2X2 = 8X2
resultando em P (X) = 8X2 + 6X − 1.
0.2 Apresentac¸a˜o do Polinoˆmio
Apenas os termos com o coeficiente diferente de zero sera˜o impressos na tela. Se o expoente
for nulo, o termo tambe´m na˜o sera´ impresso. Como a func¸a˜o imprime polinomio() tem a
responsabilidade de exibir o sinal ’+’ ou ’-’, recomenda-se o uso da func¸a˜o abs para sempre
exibir os valores absolutos dos nu´meros.
Supondo que o polinoˆmio P (X) = 10X2 + 6X − 1 precise ser mostrado, a execuc¸a˜o da
func¸a˜o imprime polinomio() produzira´ como resultado:
p(X) = -1.00 + 6.00*X^1 + 10.00*X^2
0.3 Resolvendo um polinoˆmio
A func¸a˜o calcula polinomio() calcula o valor do polinoˆmio para um X qualquer, ou seja,
realiza o somato´rio de cada termo no polinoˆmio, considerando um certo valor para X.
A func¸a˜o pow(), da biblioteca math.h pode ser utilizada para o ca´lculo da operac¸a˜o de
exponenciac¸a˜o. Lembrando que, para o seu uso, e´ necessa´rio linkar o co´digo da biblioteca
atrave´s do paraˆmetro −lm fornecido na linha de compilac¸a˜o do programa.