Structure de donnée
Travaux Pratiques 1
Exercice 1 :
Nous souhaitons écrire un programme manipulant des polynômes (Exemple : 3X4 - 1.2X2 + 5X -
4.5). Un polynôme sera codé en une liste doublement chaînée où chaque élément est un terme (ou
monôme) caractérisé par un coefficient réel et un degré entier. (Exemple -1.2X2 est un terme de
degré 2 et de coefficient -1.2). Les termes sont triés par ordre croissant de degré et les termes de
coefficient 0 ne sont pas représentés.
1) Définir les types terme représentant un monôme et polynome celui d’un polynôme.
2) Écrire les fonctions suivantes :
• void afficher(polynome p) : afficher un polynôme à l’écran.
• void ajouterTerme(terme t, polynome *p) : qui ajoute un terme au polynôme référencé par
p.
• int degre(polynome p) : retourne le degré d’un polynôme.
• polynome add(polynome p, polynome q) : retourne la somme des polynômes p et q.
• polynome prod(polynome p, polynome q) : retourne la produit des polynômes p et q.
• polynome div(polynome p, polynome q) : retourne le quotient de la division du polynôme
p par q.
• polynome tabToPoly(double *tab, int n) : retourne le polynôme construit à partir du
tableau tab tel que tab[i] correspond au coefficient du monôme Xi . Exemple : si tab={2,-
5,0,1.6} le polynôme correspondant est : 1.6X3 -5X+2.
• double *polyToTab(polynome p) : effectue l’opération inverse de la fonction précédente.
3) Écrire un programme pour tester ces opérations.
1
Exercice 2 :
Une association de bénévolat compte parmi ses membres des personnes avec des tranches
d’âge très variées. Afin d’optimiser son temps de travail et de faciliter la répartition de ses
tâches, l’association a fait appel à vous pour structurer les informations de ses bénévoles.
Du fait que des tâches spécifiques peuvent être affectées selon l’âge des personnes,
l’association a décidé de répartir ses bénévoles selon des tranches d’âges de 16-20 ans, 21-
25 ans, 26-30 ans et ainsi de suite. En bon programmeur, vous décidez de structurer les
bénévoles en forme d’Arbre Binaire de Recherche (ABR), où chaque nœud est la borne
supérieure d’une tranche d’âge donnée. Par exemple, le nœud 25 représente la liste des
bénévoles qui font partie de la tranche d’âge 21-25ans. Fonctions:
1. Initialiser un arbre
2. Ajouter une Tranche
3. Ajouter un bénévole dans une tranche d’âge
4. Afficher les tranches d’âge d’un ABR
5. Afficher les bénévoles d’une tranche d’âge
6. Supprimer un bénévole
7. Supprimer une tranche
8. Afficher le nombre total de bénévoles
Exercice 3 :
typedef struct noeud{
int valeur;
struct noeud* gauche;
struct noeud* droit;
} arbre;
Partie 1 :
Créez l’Arbre et définissez les fonctions équivalentes à cette dernière :
1) Arbre * CreerNoeud(Arbre * Racine,int valeur) : pour ajouter un nœud
2) AfficherArbre(Arbre * Racine) : permettant d’afficher l'arbre
3) AfficherArbreCroissant(Arbre * Racine) : Pour afficher l'arbre dans l'ordre croissant
4) AfficherArbreDecroissant(Arbre * Racine) : Pour afficher l'arbre dans l'ordre decroissant
5) int Somme(Arbre * Racine) : Retourne la somme des nœuds
6) int CompteNoeud(Arbre * Racine) : Retourne le nombre de nœuds
7) Arbre * RechercheNoeud(Arbre * Racine, int valeur) : Rechercher un nœud dans l’arbre
8) Arbre * OterNoeud(Arbre * Racine, int valeur) : Enlever un nœud d’un arbre.
2
Partie 2 :
1) Ecrire une fonction qui teste si un ABR est un AVL
2) Implémenter les rotations gauche et droite
a. Donner la fonction d’insertion dans un arbre AVL
b. Donner la fonction de suppression dans un arbre AVL
c. Donner la fonction de recherche dans un arbre AVL
Exercice 4 :
Créez l’Arbre et définissez les fonctions équivalentes à cette dernière :
1) Les fonctions permettant de naviguer dans l’arbre
• noeud* parent(noeud* n) : qui retourne le père d’un noeud
• noeud* grandparent(noeud* n) : qui retourne le grand père d’un noeud
• noeud* frere(noeud* n) : qui retourne le frere d’un noeud
• noeud* oncle(noeud* enfant) : qui retourne l’oncle d’un nœud
2) Les fonctions de rotation
• void rotation_droite(noeud *x)
• void rotation_gauche(noeud *x)
3) La fonction de recherche d’un élément : noeud *recherche(noeud *n, value_t x)
4) La fonction d’insertion : noeud *insertion(noeud *racine, noeud *n)
