Les Listes Chaînées

Les listes chaînées simple

XII.2.1 Définitions

XII.2.1.1 Définition d'un pointeur

Une variable de type pointeur est une variable susceptible de contenir l’adresse d’une autre variable d’un type défini. Elle est déclarée de la manière suivante.



Var Identificateur_variable_pointeur : ^ Type_élément_pointé



Exemple



VAR Adresse : ^ entier



L’entier pointé par la variable Adresse est désigné par



Adresse^.



Adresse^ joue le rôle d’une variable. On peut ainsi l’utiliser dans toute action d’un algorithme. Ainsi, après l’action



Adresse^ ß 2003



la variable adresse contiendra l’adresse d’un espace mémoire associé à un entier. Cet espace va contenir la valeur 2004.

Un pointeur peut aussi pointer sur un type enregistrement.



Exemple



Type Etudiant = Enregistrement

Nom : Chaîne

Prénom : Chaîne

CIN : entier

Adresse : Chaîne

Fin



VAR ptr_Etudiant : ^Etudiant



L’espace mémoire associé à l’enregistrement est désigné par : ptr_Etudiant^. D’une façon générale, un champ d’un enregistrement pointé par Ptr_enregistrement est désigné par Ptr_enregistrement^.Nom_champ

Par exemple, le champ CIN est accessible par : ptr_Etudiant^.CIN

Une liste chaînée simple est pointée par un pointeur sur liste qui contient l’adresse du premier élément de la liste si cette dernière n’est pas vide. Dans le cas contraire, il contient la valeur NIL.


Les listes chaînées doubles

XII.3.1 Définition
Une liste chaînée double est une liste d’éléments où à partir d’un élément on peut accéder aussi bien à son suivant qu’à son précédent. C’est une liste à chaînage double. A chaque élément de la liste est associé, en mémoire, un emplacement mémoire représentant un enregistrement à trois champs où le premier contient l’élément, le deuxième contient l’adresse de l’emplacement mémoire de l’élément précédent et le troisième contient l’adresse de l’emplacement mémoire de l’élément suivant. Les deux derniers champs sont des pointeurs sur des enregistrements de même type. En l’absence d’un élément suivant ou précédent, le champ pointeur correspondant contiendra la constante NIL.

En mémoire, une liste chaînée double a la représentation suivante :



La déclaration de cette structure est la suivante

Type LD = ^Cellule

Cellule = Enregistrement

valeur : Type_élément

précédent : LD

suivant : LD

Fin Enregistrement

Var Liste : LS



Un nouveau type LD est définit. C’est un pointeur sur une cellule où une cellule est un enregistrement à trois champs. Le premier contient un élément de la liste, le deuxième contient l’adresse d’une cellule précédente si elle existe si non la valeur NIL et le troisième contient l’adresse d’une cellule suivante si elle existe si non la valeur NIL.

L’adresse de la première cellule de la liste est sauvegardée dans une variable Liste. Cette variable est donc de type pointeur sur une cellule.



Si q est un pointeur sur une cellule de la liste déclaré par :



Var q :LD

Alors

q^.précédent désigne l’adresse de la cellule précédente.

q^.suivant désigne l’adresse de la cellule suivante