TD1 2 MIC guillerm@laas.fr Romaric GUILLERM Algo-Prog en Ada

TD12 MIC

guillerm@laas.fr

Romaric GUILLERM

Algo-Progen Ada

http://romaric.guillerm.free.fr

TD1Pointeurs et Listes chaînées

Listes simplement chaînées :

TD1 Exercice 1 : Listes identiques

On considère des listes simplement chaînées.

Deux listes sont dites identiques si elles sont toutes les deux vides ou si elles contiennent les mêmes valeurs dans le même ordre.

Ecrire une fonction booléenne récursive qui teste si 2 listes données sont identiques.

TD1 Exercice 2 : Suppression des occurrences multiples dans une

listeOn considère toujours des listes simplement chaînées.

Ecrire un sous-programme supprimant d'une liste toutes les occurrences multiples de chaque valeur (on obtient donc une liste contenant une seule occurrence de chaque valeur).

TD1 Exercice 2

itératif

TD1 Exercice 2

itératif

TD1 Exercice 2

récursif

TD1 Exercice 2

récursif

TD1 Exercice 3 : Insertions et suppressions dans une liste

doublement chaînéeOn considère des listes doublement chaînées.

3.1.a Quel est l'intérêt essentiel d'une liste doublement chaînée par rapport à une liste simplement chaînée ?

Parcours possible dans les deux sens !

3.1.b On désire construire une liste doublement chaînée à l'aide de 2 sous‐programmes d'insertion permettant respectivement : d'insérer un nouvel élément en début de liste ; d'insérer un nouvel élément en fin de liste.

Proposer une structure de données permettant de modéliser une liste d'entiers doublement chaînée et telle que les algorithmes d'insertion en début et en fin n'effectuent aucun parcours de la liste.

TD1 Exercice 3 : Insertions et suppressions dans une liste

doublement chaînée

3.2 Identifier les différents cas à prendre en compte pour l'insertion d'un nouvel élément en début de liste,puis écrire le sous‐programme d'insertion en début de liste.

TD1 Exercice 3 : Insertions et suppressions dans une liste

doublement chaînée

3.2 Identifier les différents cas à prendre en compte pour l'insertion d'un nouvel élément en début de liste,puis écrire le sous‐programme d'insertion en début de liste.

TD1 Exercice 3 : Insertions et suppressions dans une liste

doublement chaînée

3.3 Même question pour le sous‐programme d'insertion en fin de liste.

TD1 Exercice 3 : Insertions et suppressions dans une liste

doublement chaînée

3.4 Identifier les différents cas à prendre en compte pour la suppression du premier élément d'une liste,puis écrire le sous‐programme de suppression.

TD1 Exercice 3 : Insertions et suppressions dans une liste

doublement chaînée

3.5 Même question pour le sous‐programme de suppression du dernier élément d'une liste.

TD1 Exercice 3 : Insertions et suppressions dans une liste

doublement chaînée

3.6 Ecrire un sous‐programme de suppression d'un entier donné dans une liste. Ce sous‐programme doit lever une exception Element_Inexistant si l'entier à supprimer n'appartient pas à la liste.

TD1 Exercice 3 : Insertions et suppressions dans une liste

doublement chaînée

3.7 Concevoir un scenario permettant d'effectuer tous les cas de tests des sous‐programmes d'insertion et de suppression réalisés précédemment.

Travailler à la maison !avec Windows

Compilateur Ada GNAT :

http://romaric.guillerm.free.fr

Pour écrire le programme (fichier.adb):

Bloc Note, Emacs… ou : Notepad++

Pour compiler et exécuter :