Exercice 1 On représente la poche par une structure contenant un seul champ, la liste chaînée des objets. Création d'une poche : poche créer-poche() renvoyer allouer-poche(NIL) Les autres opérations (Exercice 1a) : booléen vide?(poche p) renvoyer liste(p) = NIL booléen membre?(poche p, objet obj) l <- liste(p) tant que l != NIL faire si données(l) = obj alors renvoyer vrai renvoyer faux insérer(poche p, objet obj) assert(!membre?(p, obj)) liste(p) <- allouer-cellule(obj, liste(p)) obj supprimer(poche p) assert(!vide?(p)) obj <- données(liste(p)) liste(p) <- suiv(liste(p)) renvoyer obj Complexité (Exercice 1b) : opération complexité justification vide? O(1) nombre constant d'opérations membre? O(n) il faut parcourir la liste insérer O(n) il faut appeler membre? supprimer O(1) nombre constant d'opérations Avec un dictionnaire (Exercice 1c) : Création d'une poche : poche créer-poche() renvoyer allouer-poche(NIL, créer-dictionnaire()) Les autres opérations (Exercice 1a) : booléen vide?(poche p) renvoyer liste(p) = NIL booléen membre?(poche p, objet obj) renvoyer membre(dictionnaire(p), obj) insérer(poche p, objet obj) assert(!membre?(p, obj)) liste(p) <- allouer-cellule(obj, liste(p)) insérer(dictionnaire(p), obj) obj supprimer(poche p) assert(!vide?(p)) obj <- données(liste(p)) liste(p) <- suiv(liste(p)) supprimer(dictionnaire(p), obj) renvoyer obj Exercice 2 a. Il suffit de créer un sommet 2 qui devient la nouvelle racine de l'arbre, et qui contiendra les deux autres arbres comme fils. arbre concaténer-même-hauteur(arbre a1, arbre a2) renvoyer allouer-sommet2(a1, a2) séquence concaténer-même-hauteur(séquence s1, séquence s2) allouer-séquence(concaténer-même-hauteur(arbre(s1), arbre(s2))) b. Pour calculer la hauteur d'un arbre, descendre jusqu'à une feuille (toutes les feuille sont à la même hauteur). On ne traite pas le cas d'un arbre vide, car on n'en a pas besoin. entier hauteur(arbre a) hauteur <- 0 tant que !feuille?(a) faire hauteur <- hauteur + 1 a <- gauche(a) renvoyer hauteur L'algorithme de concaténation est similaire à l'algorithme d'insertion traité en cours, avec la différence que l'on n'insère pas dans les feuille mais dans un sommet ayant la même hauteur que l'autre arbre. arbre, arbre concaténer-aux(arbre a1, entier h1, arbre a2, entier h2) si h1 = h2 alors renvoyer a1, a2 sinon si h1 < h2 aa1, aa2 <- concaténer-aux(a1, h1, gauche(a2), h2 - 1) si aa2 = NIL alors gauche(a2) <- aa1 renvoyer a2, NIL sinon si sommet-2?(a2) alors renvoyer allouer-sommet-3(aa1, aa2, droite(a2)) sinon g <- allouer-sommet-2(aa1, aa2) d <- allouer-sommet-2(milieu(a2), droite(a2)) renvoyer g, d sinon // h1 > h2 aa1, aa2 <- concaténer-aux(droite(a1), h1 - 1, a2, h2) si aa2 = NIL alors droite(a1) <- aa1 renvoyer a1, NIL sinon si sommet-2?(a1) alors renvoyer allouer-sommet-3(gauche(a1), aa1, aa2) sinon g <- allouer-sommet-2(gauche(a1), milieu(a1)) d <- allouer-sommet-2(aa1, aa2) renvoyer g, d arbre, arbre concaténer(arbre a1, arbre a2) si a1 = NIL alors renvoyer a2 sinon si a2 = NIL alors renvoyer a1 sinon h1 <- hauteur(a1) h2 <- hauteur(a2) renvoyer concaténer-aux(a1, h1, a2, h2) séquence concaténer(séquence s1, séquence s2) aa1, aa2 <- concaténer(arbre(s1), arbre(s2)) si aa2 = NIL alors renvoyer allouer-séquence(aa1) sinon renvoyer allouer-séquence(allouer-sommet-2(aa1, aa2)) c. La complexité est O(log n) où n est le nombre d'objets dans la séquence la plus longue entre les deux (ou équivalent, où n est la somme du nombre d'objets dans chacune des deux séquences. Justification : à chaque appel récursif, hauteur de l'arbre le plus haut diminue. Le nombre d'appels récursifs est donc proportionnel à la hauteur de l'arbre le plus haut, soit log n, où n est le nombre d'objets dans cet arbre.