Scéance machine n°2

Listes simplement chaînées

Copiez chez vous le fichier listes.adb (changez le ~/ADA si besoin) :

cp ~debunne/Ada/listes.adb ~/ADA

Etudiez le programme. Ajoutez :

Une fonction EstTriee(L:Liste) return Boolean qui renvoie vrai si et seulement si les valeurs de la liste sont classées dans l'ordre croissant.
Une procédure SupprimeDoublets(L : ?? Liste) qui prend en entrée une liste triée et supprime les éléments dont la valeur apparait plus d'une fois (1 2 2 3 4 4 4 4 5 5 devient 1 2 3 4 5).

Testez vos méthodes sur des exemples en essayant bien les cas particuliers.

Utilisation du paquetage arbre

Copiez chez vous les fichiers du paquetage arbre :

cp ~debunne/Ada/type_arbre.ad? ~/ADA
cp ~debunne/Ada/essai_arbre.adb ~/ADA

Étudiez le code du paquetage générique ainsi que l'exemple essai_arbre.adb. Dessinez l'arbre qui est fourni dans l'exemple, pour pouvoir vérifier vos résultats. Partez de ce programme et ajoutez :

Une fonction NombreDeNoeuds (A : Arbre)
Une fonction Hauteur (A : Arbre) (Conseil : Integer'Max(a,b), un arbre vide a une hauteur de 0).
Une procédure AfficherFeuilles (A : Arbre) qui affiche la suite des valeurs des feuilles d'un arbre.

Chacune de ces méthodes peut être récursive ou non. La version récursive est souvent plus simple. S'il vous reste du temps, codez l'autre version.