QuickSort

Segundo Trabalho de Implementa¸ao c˜ Algoritmos e Estrutura de Dados II

O objetivo deste trabalho ´ implementar uma biblioteca de opera¸˜es matem´tica sobre e co a polinˆmios. A implementa¸˜o deve usar necessariamente listas encadeadas. As opera¸˜es a o ca co serem implementadas s˜o soma, subtra¸˜o, produto, derivada, integral (primitiva) e avalia¸˜o a ca ca em um ponto.

Estrutura de Dados
Cada polinˆmio ser´ representado por uma referˆncia (ponteiro) para uma lista encadeada, como o a e definido no arquivo polinomio.h: typedef lista *polinomio;
Os n´s est˜o ordenados em ordem crescente de grau. Todos os termos do polinˆmio s˜o o a o a reprentados na lista, mesmo os termos com coeficientes igual a zero. Assim, por exemplo, o polinˆmio 2x3 + 3x − 4 teria a poss´ o ıvel representa¸˜o gr´fica: ca a

Opera¸˜es co A biblioteca das opera¸˜es est´ definida no arquivo polinomio.h. As opera¸˜es s˜o as seguintes: co a co a polinomio soma(polinomio p, polinomio q) : soma dois polinˆmios, devolvendo o resulo tado em outro polinˆmio. o polinomio subtrai(polinomio p, polinomio q) : subtrai dois polinˆmios, devolvendo o reo sultado em outro polinˆmio. Note que a subtra¸˜o, diferente da soma, n˜o ´ comutativa. o ca a e polinomio multiplica(polinomio p, polinomio q) : multiplica dois polinˆmios, devolvendo o o resultado em outro polinˆmio. o polinomio derivada(polinomio p) : calcula a derivada de um polinˆmio, devolvendo o reo sultado em outro polinˆmio. o polinomio integra(polinomio p) : calcula a integral (primitiva) de um polinˆmio, devolo vendo o resultado em outro polinˆmio. o Ap´s calcular a integral, o termo de menor grau do resultado ´ uma constante c arbitr´ria. o e a Para fins de corre¸˜o do trabalho, assuma que c = 0 (Aten¸˜o: c = 0 pode levar ` corre¸˜o ca ca a ca incorreta do trabalho). float avalia(polinomio p, float x) : avalia¸˜o o polinˆmio p em um ponto x, ou seja, ca o devolve p(x).
1