Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

LSb1.3 - Algorithmique et structures de données – Table arborescente binaire Ma

LSb1.3 - Algorithmique et structures de données – Table arborescente binaire Manipulation d’arbres binaires, tables, récursivité et itération Guillaume Revy Séances du 22 et 23 janvier 2009 Objectif du TD6 - Gestion d’un annuaire téléphonique. On veut gérer un annuaire té- léphonique sous la forme d’une table <nom,numéro>. Pour cela on choisit une structure de données adaptée et on écrit les fonctions d’accés nécessaires. 1 Utilisation de la classe map de la STL Exercice 1. On utilisera la classe map de la STL. Déﬁnir les types de données Table et IterTable corres- pondant à l’annuaire. typedef string Cle; typedef int Info; typedef map<Cle,Info> Table; typedef map<Cle,Info>::iterator IterTable; Un objet de type Table est une map qui associe un objet de type Info (entier) à un objet de type Cle (string). Un objet de type Table peut être vu comme un tableau indicé par une Cle. Exercice 2. Écrire une fonction inserer(Cle,Info,Table) pour insérer une entrée dans la table. Traiter le problème de l’entrée déjà présente dans la table. bool inserer(Table& table, Cle cle, Info info) { pair<IterTable,bool> code_retour = table.insert(make_pair(cle,info)); return code_retour.second; } Une entrée dans la table correspond à une paire <Cle,Info>. La fonction insert renvoie une paire contenant un itérateur sur l’élément inséré et un booléen indiquant si la clé existait déjà dans la table (et donc si l’entrée a été insérée). Exercice 3. Écrire une fonction chercher(Cle,Table) qui rend le numéro associé à un nom. Traiter le cas d’une absence d’une entrée dans la table. #define nullInfo -1 // definition d’une constante nullInfo = -1 Info chercher(Table& table, Cle cle) { IterTable info = table.find(cle); // retourne un iterateur sur l’element trouve return info==table.end()?nullInfo:info->second; } Si le nom n’est pas trouvé, on retourne un numéro égal à −1 (nullInfo). La syntaxe return info==table.end()?nullInfo:info->second; LSb1.3 - Éléments de correction du TD6. 1 est équivalente à if( info == table.end() ) return nullInfo; else return info->second; De plus, la table est passée par référence pour éviter de la dupliquer à chaque appel. Exercice 4. Écrire une fonction afﬁcher(Table) qui afﬁche sur l’écran le contenu de la table. void afficher(Table& table) { IterTable info; for( info = table.begin() ; info != table.end() ; info++ ){ cout << "-------------------------------------------" << endl; cout << " Nom " << setw(10) << info->first << endl; cout << " Numero " << setw(4) << info->second << endl; } } Exercice 5. Écrire une fonction modiﬁer(Cle,Info,Table) qui modiﬁe le numéro correspondant à un nom situé dans la table. void modifier(Table& table, Cle c, Info info) { table[c] = info; // si l’entree n’existe pas, elle est creee } Si la clé c n’existe pas, l’entrée <c,info> est créée. Sinon le numéro associé à la clé c est modiﬁé par info. Exercice 6. Écrire une fonction supprimer(Cle,Table) qui supprime une entrée de la table. bool supprimer(Table& table, Cle c) { IterTable it = table.find(c); if( it == table.end() ) return false; // la cle c n’a pas ete trouvee dans // la table table.erase(it); return true; } Si la clé c est trouvée, on supprime l’entrée associée. 2 Arbre Binaire Ordonné Horizontalement (ABOH) On utilise maintenant une table arborescente binaire ordonnée horizontalement. Chaque nœud de l’arbre contiendra une chaîne de caractères correspondant au nom et un entier correspon- dant au numéro de téléphone. On rappelle qu’un arbre binaire ordonné horizontalement (ABOH) est un arbre binaire tel que : pour chaque nœud racine d’un sous-arbre – la valeur du nœud est supérieure aux valeurs des nœuds de son sous-arbre gauche, – la valeur du nœud est inférieure aux valeurs des nœuds de son sous-arbre droit. Exercice 1. Donner une représentation graphique d’un exemple d’annuaire limité à 4 ou 5 entrée. Bob Jean Marc Sam Luc 3321 3398 3356 3354 3367 SAG SAD Toutes les valeurs du SAG sont inférieures à Luc et toutes les valeurs du SAD sont supérieures. LSb1.3 - Éléments de correction du TD6. 2 Exercice 2. On veut représenter l’arbre binaire de manière dispersée dans une zone de stockage gérée par l’utilisateur sous la forme d’un grand vecteur. Donner la déﬁnition C d’un nœud de l’arbre. Déﬁnir la zone de stockage sous la forme d’un vecteur de 100 nœuds, une telle zone pourra contenir plusieurs arbres. typedef string Cle; typedef int Info; typedef int & Arbre; typedef int RefNoeud; struct Noeud { Cle cle; Info info; RefNoeud g,d; }; typedef vector<Noeud> Stockage; #define nullInfo -1 // Variables globales Stockage s(100); int libre; // indice dans le tableau de la // prochaine place libre Cle Info g d 0 “vide” 0 1 -1 1 “vide” 0 2 -1 2 “vide” 0 3 -1 · · · · · · · · · · · · · · · 99 “vide” 0 -1 -1 Un nœud contient une clé, une info (numéro) et l’indice dans la zone de stockage de son ﬁls droit (d) et son ﬁls gauche (g). Exercice 3. Écrire une fonction init_stockage() qui initialise la zone de stockage sous la forme d’une liste chaînée de nœuds (liste de places disponibles). void init_stockage() { libre = 0; int i, taille = s.size(); for( i = 0 ; i < taille-1 ; i++ ){ s[i].cle = "vide"; s[i].info = 0; s[i].g = i+1; s[i].d = -1; } s[i].cle = "vide"; s[i].info = 0; s[i].g = -1; s[i].d = -1; } Exercice 4. Écrire les fonctions de base permettant de gérer la zone de stockage : trace() pour visualiser l’état de la zone de stockage, saturation() pour savoir si il reste de la place dans la zone de stockage, prendNoeud() qui prend de la place pour un nœud et libereNoeud() qui libère un nœud en rendand la place disponible. bool saturation() { return libre == -1; } RefNoeud prendNoeud() { RefNoeud r; if( ! saturation() ){ r = libre; // on reserve la prochaine place libre libre = s[libre].g; // la place libre suivante sera le SAG // du prochain noeud libre }else r = -1; // si il y a saturation, on retourne -1 return r; // on retourne le place reservee } void libereNoeud(RefNoeud r) { s[r].d = -1; s[r].d = libre; // s[r].g : place libre apres le prochain ajout // d’un noeud en indice r LSb1.3 - Éléments de correction du TD6. 3 libre = r; // comme on libere le noeud en indice r, la // nouvelle place libre est r } void trace() { int i; for( i = 0 ; i < s.size() ; i++ ){ cout << "-------------------------------------------" << endl; cout << setw(20) << s[i].cle << " "; cout << setw(4) << s[i].info << " "; cout << setw(2) << s[i].g << " "; cout << setw(2) << s[i].d << endl; } cout << "libre = " << libre << endl; } Exercice 5. Écrire une fonction vide(Arbre) qui dtéermine si un arbre est vide. bool vide(Arbre a) { return a == -1; } Exercice 6. Écrire une fonction récursive d’insertion d’une entrée dans la table arborescente binaire. bool inserer_r(Arbre a, Cle c, Info i) { if( saturation() ) return false; // si il y a saturation, on ne peut pas // inserer une nouvelle entree if( vide(a) ){ // si l’arbre est vide a = prendNoeud(); // on reserve un noeud racine s[a].cle = c; s[a].info = i; s[a].g = s[a].d = -1; // on modifie les informations du noeud return true; } if( c < s[a].cle ) // si la cle qu’on veut inserer est // inferieure a la cle du noeud d’indice a, // on retourne le resultat de l’insertion // dans le SAG return inserer_r(s[a].g,c,i); else return inserer_r(s[a].d,c,i); // sinon on retourne le resultat de l’insertion // dans le SAD } Comme le type Arbre est une référence sur un entier, lorsque l’on crée un noeud car le sous- arbre courant est vide, l’information est également modiﬁé dans le noeud père appelant. Exercice 7. Écrire une fonction itérative d’insertion d’une entrée dans la table arborescente binaire. bool inserer_i(Arbre a, Cle c, Info i) { if( saturation() ) return false; // si il y a saturation, on ne peut pas // inserer une nouvelle entree RefNoeud x,np; np = prendNoeud(); // on reserve un noeud et on modifie les s[a].cle = c; // informations du noeud s[a].info = i; s[a].g = s[a].d = -1; if( vide(a) ) { a = np; return true; } x = a; while( true ) // boucle infinie : attention a explicitement { // terminer la boucle if( c < s[x].cle ){ // insertion dans le SAG if( ! vide(s[x].g) ) // si le SAG n’est pas vide, on insert l’entree x = s[x].g; // dans le SAG else{ LSb1.3 - Éléments de correction du TD6. 4 s[x].g = np; return true; } }else{ // insertion dans le SAG if( ! vide(s[x].d) ) // si le SAD n’est pas vide, on insert l’entree x = s[x].d; // dans le SAD else{ s[x].d = np; return true; } } } } Exercice 8. Écrire une fonction récursive de recherche de l’information associée uploads/Science et Technologie/ corrige-td6.pdf