Element de didacticiel comportant plusieurs Applets pour
montrer une liste
chaînée et le résultat des ajouts ou suppressions dans
une telle liste.
Une liste est un ensemble de valeurs stockées dans la mémoire
de manière non contigüe, les valeurs étant reliées
entre elles par des liens. La liste peut être vue de manière
itérative, comme une suite de cellules ou maillons reliés
entre eux par des liens, ou de manière récursive comme une
valeur suivie d'une sous-liste.
Dans la liste présentée ici, les valeurs (numériques)
sont liées les unes aux autres de manière à être
découvertes par ordre croissant.
Au départ, la liste est composée de 5 valeurs aléatoires...
Algorithme d'ajout :
-
contrôle de pré-requis éventuel : vérification que la liste
est bien ordonnée, en cas d'échec, levée d'exception
-
si la valeur à ajouter est inférieure ou égale à
la valeur située en tête de liste, retour d'une nouvelle liste
avec la valeur à ajouter et la liste de départ comme sous-liste
-
si la valeur à ajouter est supérieure à la valeur
située en tête de liste, modification de la liste donnée
pour que sa nouvelle sous-liste soit le résultat de l'appel récursif
de la méthode d'ajout sur l'ancienne sous-liste
-
contrôle de post-requis éventuel : vérification que la liste résultat
est bien ordonnée et levée d'exception en cas d'échec.
Algorithme de retrait :
-
contrôle de pré-requis éventuel : vérification que la liste
est bien ordonnée, en cas d'échec, levée d'exception
-
si la valeur à enlever est égale à la valeur de tête
de liste, élimination de cette valeur et retour de la sous-liste,
-
si elle est inférieure à la valeur de tête de liste,
c'est qu'elle n'est pas dans la liste. Deux politiques possibles dans
ce
cas : soit considérer que c'est normal, ne rien faire et retourner
la liste donnée, soit considérer que c'est le signal d'une
anomalie et lever une exception...
-
si la valeur à ajouter est supérieure à la valeur
située en tête de liste, retour du résultat de l'appel
récursif sur la sous-liste.
-
contrôle de post-requis éventuel : vérification que la liste résultat
est bien ordonnée et levée d'exception en cas d'échec.
La première applet présente la liste :
La seconde applet permet de la modifier...
Les fichiers sources des deux applets : MontreListe.java et Gestion.java