Informatique T.D 4 Exercices sur les pointeurs : polynômes creux Marie-Pierre Béal et Laurent Moll

Dans ce TP, on va manipuler des polynômes creux, c’est-à-dire des polynômes qui admettent un petit nombre de coefficients non nuls par rapport à leur degré. De plus le degré n’est pas borné à l’avance. On représente un polynôme par une liste chaînee de boites qui sont des structures représentant un monôme. On définit les types suivants pour manipuler ces listes chaînées :

type Polynome = ↑ Boite; Boite = record

coef : integer; degre : integer; suiv : Polynome; end;

Exercice 1.— Quelques fonctions de base

• Ecrire une fonction est_vide de type booléen qui prend un pointeur en paramètre et rend vrai si ce pointeur est nil.

• Ecrire une procédure creer_monome de paramètres deux entiers x et n et un pointeur p passé par adresse, qui crée un monôme pointé par p de champ coef égal à x, de champ degre égal à n et de champ suiv égal à nil.

• Ecrire une procédure afficher qui affiche un polynôme dans la fenêtre Text.

• Ecrire une procédure inserer_debut_pol de paramètres deux entiers x et n, et un pointeur p passé par adresse, qui insère un nouveau monôme en début de liste. Elle fera appel

à creer_monome.

• Ecrire une procédure creation_polynome qui crée un polynôme dont les champs degre et coef sont entrés au clavier par degrés croissants pour être en ordre décroissant dans la liste.

Exercice 2.— Retournement d’une liste

• Ecrire une procédure retourne_pol_surplace récursive qui renverse une liste en modifiant uniquement les champs suiv, donc sans créer de nouvelles boites.

Exercice 3.— Une addition

• Ecrire une procédure additionner qui prend en paramètres deux polynômes p et q et renvoie un pointeur sur une liste représentant le polynôme p + q. On supposera que p et q sont données par des listes triées suivant le degré et le résultat sera aussi une liste triée suivant le degré. On fera ceci sans créer de nouvelles boites, les polynômes p et q étant alors perdus.

Exercice 4.— Tri fusion : cette procédure sera utilisée pour trier suivant le degré une liste non triée représentant un polynôme.

• Ecrire une fonction milieu_inf qui renvoie un pointeur sur la boite ”milieu” de la liste. Plus exactement, si la liste comprend n boites, le pointeur devra pointer sur la boite n/2 si n est pair et sur la boite (n + 1)/2 si n est impair.

• Ecrire une fonction récursive fusionner qui prend en paramètre deux listes triées suivant le degré et renvoie un pointeur sur une liste triée dont les boites sont celles des deux listes initiales.(On ne créera pas de nouvelles boites, les listes initiales étant donc perdues).

• Ecrire une procédure tri_fusion qui trie une liste. On commence par couper la liste en deux moitiés, on applique le tri (par un appel récursif) sur chaque moitié et on fusionne enfin les deux parties triées.

Exercice 5.— Evaluer la complexité de chacune de vos procédures ou fonctions.

Exercice 6.— Ajouter des fonctions supplémentaires de manipulation de polynômes comme la multiplication par une constante, la multiplication d’un polynôme par un monôme, la soustraction et la multiplication de deux polynômes.