ASD2 – Les Structures Dynamiques Séquentielles LFSI-1
CHAPITRE 1 Les Structures Dynamiques
Séquentielles
I. Introduction
Les structures de données linéaires ( séquentielles) permettent de stocker un certain nombre de
données de types identiques. L'exemple le plus simple est le type tableau.
Seulement, utiliser un tableau implique généralement qu'on doit définir le nombre maximal de
ses éléments.
En combinant l'utilisant des pointeurs et autres types, on peut arriver à créer une structure
linéaire extensible. Un élément est ajouté au début ( ou à la fin) de la liste chaque fois qu'on en a
besoin en utilisant la fonction allouer.
II. Les Listes Chainées
II.1 Définition
Une liste chainée est une structure linéaire qui n'a pas de dimension fixée à sa création. Ses
éléments sont reliés entre eux par leurs adresses mémoire. La liste est accessible uniquement par
sa tête de liste c'est-à-dire le premier élément.
Le dernier élément de la liste pointe sur "rien" ou la valeur nil.
On accède à un élément de la liste en parcourant tous les éléments qui le précèdent.
II.2 Représentation en mémoire
Dans le jeu de bowling, le joueur lance la boule un certain nombre de fois et obtient chaque fois
un score. Le joueur peut décider d'arrêter de jouer à tout moment de ce fait, le nombre de lancers
est inconnu, nous allons alors représenter les scores d'un joueur par une liste chainée :
Tête 1198
4 1232
8 4567
@ = 1198 3 5643
@ = 1232 @ = 4567 9 2564
@ = 5643 9 NIL
@ = 2564
Tête : c'est un pointeur qui contient l'adresse du premier élément de la liste
Chaque élément de la liste contient deux informations :
4 : score obtenu
1232 : adresse de l'élément suivant de la liste
La structure de donnée qui permet de représenter en même temps le score et l'adresse est le type
Enregistrement.
Type LesScores = Enregistrement
score : entier
suivant : Pointeur sur LesScores
Fin Enregistrement
On dit que le LesScores est un type récursif.
Pour ajouter, supprimer ou déplacer un élément de la liste, nous aurons besoin d'utiliser la fonction
Allouer et la procédure Libérer.
https://drive.google.com/open?id=0B4vjsH8LiCDsbDdDYWVZbWVVbzA Page 1
ASD2 – Les Structures Dynamiques Séquentielles LFSI-1
II.3 Les Types de Listes Chainées
On distingue
a) La liste chaînée simple
Exemple : voir exemple précédent
b) La liste chaînée doublement chaînée
Tête 1198
NIL 4 1232
@ 1198 1198 3 5643
@ 1232 5643 9 2564
@ 5643 5643 9 NIL
@ 2564
c) La liste chaînée circulaire
C'est une liste chaînée simple mais avec en plus un lien du dernier élément vers le premier
ainsi qu'un pointeur queue qui pointe vers le dernier élément de la liste.
Tête 1198 Queue 2564
4 1232
8 4567
3 5643
9 2564
9 1198
d) La Pile
C'est une liste chaînée simple où l'insertion et la suppression d'éléments se fait uniquement
en tête de liste (LIFO).
e) La File
C'est une liste chaînée simple où l'insertion d'éléments se fait à la fin de la liste (Queue) alors
que la suppression se fait à partir de la tête de liste
En plus du pointeur tête, un pointeur Queue sera utile pour éviter de parcourir la liste chaque
fois qu'il y a besoin d'insérer un élément.
II.4 Traitements de base sur les listes chaînées
Remarque
Dans ce qui suit, nous allons s'intéresser seulement aux listes chaînées simples
a) Créer (construire) la liste
Commençant par créer le premier élément de la liste, pour cela nous avons besoin de
déclarer le pointeur Tête, d'allouer un espace mémoire puis de saisir un score pour le
premier élément de la liste.
https://drive.google.com/open?id=0B4vjsH8LiCDsbDdDYWVZbWVVbzA Page 2
ASD2 – Les Structures Dynamiques Séquentielles LFSI-1
Rappelons le type que nous avons déjà crée :
Type LesScores = Enregistrement
score : entier
suivant : Pointeur sur LesScores
Fin Enregistrement
Pour simplifier la déclaration des objets, nous allons définir le type Liste telque :
Type Listes = Pointeur sur LesScores
Procédure CréationListe (var tête : Listes)
Var
ElemListe: Listes
Début
ElemListe Allouer ()
Tête ElemListe
Ecrire ("donnez le score obtenu au premier lancer :")
Lire (*ElemListe.score)
*ElemListe.suivant nil
Fin créationListe
Procédure RemplirListe (var tête : Listes) /* ajout en tête de liste
Var
Nouvelem : Listes
nouvScore : entier
Début
Ecrire ("donnez le score, 0 pour terminer ")
Lire (nouvscore)
TantQue (nouvscore > 0) Faire
Nouvelem allouer ()
*Nouvelem.suivant tête
*Nouvelem.score nouvscore
Tête Nouvelem
Ecrire ("donnez le score, 0 pour terminer ")
Lire (nouvscore)
FinTantQue
Fin Ajoutelems
b) Déterminer la longueur d'une liste chaînée simple.
Fonction detLongueur ( tête : listes ) : entier
Var
ne : entier
Elemparcour : listes
début
ne 0
Elemparcour tête
tantque ( Elemparcour <> nil ) Faire
ne ne + 1
Elemparcour *Elemparcour.suivant
FinTantQue
detLongueur ne
Fin detLongueur
https://drive.google.com/open?id=0B4vjsH8LiCDsbDdDYWVZbWVVbzA Page 3
