ASDC 20 21 Partie4
ASDC 20 21 Partie4
ASDC 20 21 Partie4
Déclaration du maillon
type
maillon = Enregistrement
valeur : type
suivant : ^maillon
Fin maillon
Les listes chaînées
Autre modélisation du type liste chaînée
Un maillon est composé de deux champs :
Un champ de type enregistrement contenant les champs de données
Un pointeur vers le maillon suivant
Déclaration du maillon
type
data = Enregisterment
val1 : type
val2 : type
…
Fin data
maillon = Enregistrement
champ: data
suivant : ^maillon
Fin maillon
Les listes chaînées
Définition du type liste
type
liste : maillon
Déclaration d’une variable de type liste
Une fois le type liste est défini on peut déclarer une variable de
type pointeur sur liste de la manière suivante
p : ^liste
Accès aux champs d’un maillon d’une liste
Si p est un pointeur sur une variable de type liste, p^ est la
variable pointée par p. cette variable est un enregistrement, pour
accéder à ses champs on utilise l’opérateur ". "
p^. valeur
p^. suivant
Les listes chaînées
Initialisation d’une liste à Nil
Une liste est vide si le pointeur du premier maillon vaut Nil
p ← Nil
Insertion d’une valeur en tête d’une liste
Ecrire la procédure InsertTete qui permet d’insérer une
valeur val en tête d’une liste chaînée donnée par
l’adresse de son premier élément (premier).
Notons qu’après l’insertion la valeur du premier
sera changée, donc le passage doit se faire par
adresse.
Les listes chaînées
Principe
1. Créer un maillon d’adresse p1 contenant la valeur val
p1 ← nouveau(^liste)
p1^.valeur ← val
2. Créer un lien entre le nouveau maillon et la tête de la liste de telle sorte
que p soit le suivant de p1
p1^.suivant ← premier
3. Le maillon p1 devient le premier maillon de liste p
premier ← p1
Les listes chaînées
Algorithmique
PROCEDURE InsertTete(var premier : ^liste, val : entier)
var
type
nouvElt: ^liste maillon = Enregistrement
valeur : entier
Début suivant : ^maillon
nouvElt ← nouveau(^liste) Fin maillon
Principe
Le dernier élément de la liste s’il existe est un maillon qui ne
possède pas de suivant.
On fait le parcours de liste du premier élément jusqu’à trouver
un maillon dont le suivant vaut Nil.
L’adresse de ce maillon est renvoyée par la fonction.
Les listes chaînées
Algorithmique
Fonction Dernier( premier : ^liste) : ^liste
Debut
Tantque(premier <>Nil et premier ^.suivant<>Nil) faire
premier ← premier ^.suivant
FinTantque
Retourner premier
Fin