Chapitre 2: Les Listes chainées

1
 Introduction(1/2)

Jusqu’à maintenant, pour mémoriser une lise des

étudiants ou des employées, on utilise les tableaux. Ces
derniers sont des structures statiques dont la taille est
fixé au début , ne varie pas.
D’autre part de point de vue mémoire si on déclare un
tableau de 15 entiers, le compilateur doit trouver une
quinzane de cases mémoires successives de taille un
entier

2
 Introduction(2/2)

Une liste chaînée permet de stocker un ensemble de valeur du

même type, comme un tableau. Contrairement au tableau, la
taille de la liste chaînée peut varier au cours du temps. En effet,
contrairement au tableau, la liste n’est pas allouée en une seule
fois, mais chaque élément est alloué indépendamment, sous la
forme d’une cellule. Le compilateur n’est pas obligé de trouver
des cases successives vides dans la mémoire. Ces cases peuvent
être éparpillées dans toute la mémoire qui constitue un gain
considérable.

3
 Notion de liste chainée
 Dans une liste chaînée, chaque élément pointe, à l'aide d’un
pointeur (suivant) vers l'élément suivant dans la liste; le dernier
élément, par définition ,n’a pas de suivant, donc son pointeur
suivant vaut nil.

 Pour manipuler une liste chaînée, nous manipulons un pointeur

sur le premier élément; comme chaque élément «connaît»
l'élément suivant, on peut ainsi accéder à tous les éléments de la
liste. Notons enfin que si le pointeur premier vaut nil, on
considérera naturellement que la liste est vide(elle ne contient
aucun élément). Le premier maillon de la liste est appelé tête, le
dernier maillon de la liste est appelé queue. 4
 Différents types de listes

Liste chaînée simple constituée d'éléments reliés entre eux

par des pointeurs.
Liste chaînée ordonnée où l'élément suivant est plus grand
que le précédent. L'insertion et la suppression d'élément se
font de façon à ce que la liste reste triée.
Liste doublement chaînée où chaque élément dispose non
plus d'un mais de deux pointeurs pointant respectivement
sur l'élément précédent et l'élément suivant. Ceci permet de
lire la liste dans les deux sens, du premier vers le dernier
élément ou inversement.
Liste circulaire où le dernier élément pointe sur le premier
élément de la liste. S'il s'agit d'une liste doublement chaînée
alors de premier élément pointe également sur le dernier.
5
Ces différents types peuvent être mixés selon les besoins.
 Définition
Un élément d'une liste est l'ensemble (ou structure) formé :
 d'une donnée ou information,
 d'unpointeur
La variable pointeurPnommé
pointe surSuivant indiquant
l'espace mémoire la position
P^ de
d'adressel'élément
3. Cettelecellule
suivant dans la contient
mémoire liste. la valeur "Essai"
Un pointeur
dans le champ est
Infoune variable
et la valeur dont la valeur
spéciale est le
Nil dans une adresse
champ
mémoire
Suivant. Ce. champ
Un pointeur,
serviranoté P, pointe
à indiquer surest
quel unel’élément
variable
dynamique
suivant notée
lorsque P^. fera partie d’une liste. La valeur Nil
la cellule
Le typequ’il
indique de base
n’y a est
pasled'élément
type de lasuivant.
variableP^pointée.
est l'objet dont
Le type est
l'adresse du rangée
pointeur est P.l'ensemble des adresses des
dans
variables pointées du type de base. Il est représenté par le
symbole ^ suivi de l'identificateur du type de base.

6
 Implémentation (1/2)

Définir le type des éléments de liste :

Type Cellule= Structure
Info : variant( entier,
chaine …)
Suivant : Liste
fin Structure

Définir le type du pointeur :

Type Liste = ^Cellule

Déclarer une variable pointeur de type Liste

Var P : Liste

7
 Implémentation (2/2)

Allouer une cellule mémoire qui réserve un espace en

mémoire et donne à P la valeur de l'adresse de l'espace
mémoire P^ : Allouer(P)

Affecter des valeurs à l'espace mémoire P^:

P^.Info  "Essai" ;
P^.SuivantNil ;

Initialisation d’une liste à Nil

P  Nil

8
Traitements de base d'utilisation d'une
liste chaînée simple
Les traitements des listes sont les suivants :

 Créer une liste.

 Ajouter un élément.
 Supprimer un élément.
 Modifier un élément.
 Parcourir une liste.
 Rechercher une valeur dans une liste.

9 5
 Créer une liste(1/3)

Créer une liste chaînée composée de 2 éléments de

type chaîne de caractères
Déclarations des types pour la liste :
Type Liste = ^Element
Type Element = Structure
Info : chaîne de caractères
Suivant : Liste
Fin structure

10 5
 Créer une liste(2/3)

Algorithme CréationListe2Elements
Tete, P : Liste
NombreElt : entier
DEBUT
Tete  Nil /*1 pour l'instant la liste est vide*/
Allouer(P) /*2 réserve un espace mémoire pour le premier élément */
Lire(P^.Info) /* 3 stocke dans l'Info de l'élément pointé par P la valeur
saisie */
P^.Suivant <- Nil /*4 il n'y a pas d'élément suivant */
Tete P /*5 le pointeur Tete pointe maintenant sur P */
/* Il faut maintenant ajouter le 2e élément, ce qui revient à insérer un
élément en tête de liste */
Allouer(P) /* 6 réserve un espace mémoire pour le second élément */
Lire(P^.Info) /*7 stocke dans l'Info de l'élément pointé par P la valeur
saisie */
P^.Suivant Tete /*8 élément inséré en tête de liste */
Tete P /*9 */ 11 5
FIN
Créer une liste(3/3)

12 5
 Exercice (1/3)

1- Ecrire un algorithme qui permet de créer une liste

chaînée contenant un nombre d'éléments à préciser
par l'utilisateur
2-Ecrire une procédure qui permet d’afficher une liste

10 minutes 13 6
 Exercice (2/3)

1- Ecrire un algorithme qui permet de créer une liste chaînée contenant un

nombre d'éléments à préciser par l'utilisateur:

14 6
 Exercice (3/3)

2-Ecrire une procédure qui permet d’afficher une liste

15 6
Rechercher un élément dans une liste
Procedure RechercherValeurListe (Entrée Tete : Liste, Val : variant)
Variables locales P : Liste /* pointeur de parcours de la liste */
Trouve : booléen /* indicateur de succès de la recherche */
DEBUT
SI Tete <> Nil ALORS /* la liste n'est pas vide on peut donc y chercher une valeur */
P  Tete
Trouve Faux
TANTQUE P <> Nil ET Non Trouve FAIRE
SI P^.Info = Val ALORS /* L'élément recherché est l'élément courant */
Trouve Vrai
SINON /* L'élément courant n'est pas l'élément recherché */
P  P^.Suivant /* on passe à l'élément suivant dans la liste */
FINSI
FIN TANT QUE
SI Trouve ALORS
Ecrire (" La valeur ", Val, " est dans la liste")
SINON
Ecrire (" La valeur ", Val, " n'est pas dans la liste")
FINSI
SINON
Ecrire("La liste est vide")
FINSI
FIN
16 6
Supprimer le premier élément d'une liste
/* Supprime le premier élément de la liste dont le pointeur de tête est passé en paramètre */
Procedure SupprimerPremierElement (Entrée/Sortie Tete : Liste)
Variables locales P : Liste /* pointeur sur l'élément à supprimer */
DEBUT
SI Tete <> Nil ALORS /* la liste n'est pas vide on peut donc supprimer le premier élément */

P Tete /* P pointe sur le 1er élément de la liste */

Tete  P^.Suivant /* la tête de liste doit pointer sur le deuxième 'élément */
Desallouer(P) /* libération de l'espace mémoire qu'occupait le premier élément */
SINON
Ecrire("La liste est vide")
FINSI
FIN

17 6
Supprimer d'une liste un élément portant une valeur donné(1/3)

Principe :
- traiter à part la suppression du premier élément car
il faut modifier le pointeur de tête,
- trouver l'adresse P de l'élément à supprimer,
- sauvegarder l'adresse Prec de l'élément précédant
l'élément pointé par P pour connaître l'adresse de
l'élément précédant l'élément à supprimer, puis
faire pointer l'élément précédent sur l'élément
suivant l'élément à supprimer,
- -Libérer l'espace mémoire occupé par l'élément
supprimé.

18 6
Supprimer d'une liste un élément portant une valeur donné(2/3)

L'exemple considère que l'on souhaite supprimer

l'élément contenant la valeur "liste" de la liste
cidessus.

19 6
Supprimer d'une liste un élément portant une valeur donné(2/3)
Procedure SupprimerElement (Entrée/Sortie Tete : Liste, Val : variant)
/* Supprime l'élément dont la valeur est passée en paramètre */
Variables locales P : Liste /* pointeur sur l'élément à supprimer */
Prec : Liste /* pointeur sur l'élément précédant l'élément à supprimer */
Trouvé : Liste /* indique si l'élément à supprimer a été trouvé */
DEBUT
SI Tete <> Nil ALORS /* la liste n'est pas vide on peut donc y chercher une valeur à supprimer */
SI Tete^.info = Val ALORS /* l'élément à supprimer est le premier */
P Tete
Tete Tete^Suivant Desallouer(P)
SINON /* l'élément à supprimer n'est pas le premier */
Trouve Faux
Prec Tete /* pointeur précédent */
P Tete^.Suivant /* pointeur courant */
TANTQUE P <> Nil ET Non Trouve FAIRE
SI P^.Info = Val ALORS /* L'élément recherché est l'élément courant */
Trouve Vrai
SINON /* L'élément courant n'est pas l'élément cherché */
Prec  P /* on garde la position du précédent */
P P^.Suivant /* on passe à l'élément suivant dans la liste */
FINSI
FIN TANT QUE
SI Trouve ALORS
Prec^.Suivant  P^.Suivant /* on "saute" l'élément à supprimer "/
Desallouer(P)
SINON Ecrire ("La valeur ", Val, " n'est pas dans la liste") FINSI FINSI SINON Ecrire("La liste est vide")
FINSI FIN

20 6
21
 Exercice (1/4)

1- Ecrire une procédure qui permet d’insérer une

valeur à la fin de la liste
2-Ecrire une procédure qui permet d’insérer une
valeur à une position k de la liste

10 minutes 22 6
Exercice (2/4): Insertion à la fin de la liste (Queue)

PROCEDURE InsertQueue(var premier: liste, val : variant)

Variable
P,Der: liste
Debut
Allouer(P)
P^.Info<-val
P^.Suivant <- Nil
si(premier=Nil) alors
PremierP
Sinon // il sera le dernier élément de la liste
Der premier
tantque(Der<>Nil et Der^.suivant<>Nil) faire
DerDer^.suivant
Fintantque
Der^.suivantP
Finsi
Fin
23 6
Exercice (3/4):Insertion à une position k

PROCEDURE Ajoutk (VAR Tete  : Liste, e : variant, k : entier)

VAR
P : Liste, Prec : Liste
DEBUT
SI k = 1 ALORS
Tete  Nil /* Le code en bleu est l’insertion à tête de la liste*/
Allouer(P)
P^.Info  e
P^.Suivant <- Nil
Tete P
SINON
Prec <― Accesk (Tete , k-1)
SI prec <> NIL ALORS
Allouer(P)
P^.Info  e
P^.Suivant <- prec^.suivant
prec^.suivantp
FIN SI
FIN SI
FIN

24 6
Exercice (4/4):accès au k iéme élément d’une liste

FONCTION Accesk (L : Liste, k : entier) : Liste

VAR
P: Liste
I: entier
DEBUT
P <― L
I <― 1
TANT QUE (I <k) et (p<> NIL) FAIRE
I <― I+1
P <― p^.suivant
FIN FAIRE
RETOURNER (p)
FIN

25 6
 Exercice

Une société de transport veut informatiser la liste de ses véhicules. Pour

chaque Véhicule on enregistre la date de mise en circulation, la puissance,
la marque et L’immatriculation
1- Déclarer le type enregistrement de vehicule qui comporte les champs
DateMC, PuissanceCV, Marque, IMM
2- Déclarer un type cellule, qui comporte 2 champs, l’un contient la
structure véhicule et l’autre un pointeur sur la cellule suivante.
3- Ecrire une procédure CreatLV qui prend en parametres le nombre de
cellules et la tête L et permet de remplir la liste avec n véhicules,
4- Ecrire une fonction Nb_PCH qui retourne le nombre de véhicules dont la
puissance est supérieur à 5 chevaux.

26 6