STRUCTURES DE DONNEES

DYNAMIQUES

CHAP:8
Année Universitaire 2022/2023 –
Semestre 1

1
Objectif

maitriser la définition et la manipulation de certains

structures de données dynamiques.
I. Introduction
Le but de cette leçon c’est de gérer un ensemble fini
d'éléments dont le nombre varie au cours de l'exécution du
programme. Les éléments de cet ensemble peuvent être de
différentes sortes: nombres entiers ou réel, chaine de
caractères ou des objets informatiques plus complexes
comme les identificateurs de processus ou les expressions
arithmétiques.
On ne s’intéressera pas aux éléments de l'ensemble de
question mais aux opérations que l'on autoriser sur un
ensemble E sont le suivantes:
I. Introduction

• tester si l'ensemble E est vide.

• ajouter l'élément x à l'ensemble E.
• vérifier si l'élément x appartient à l'ensemble E
• supprimer l'élément x de l'ensemble E.
Cette gestion des ensembles doit, pour être efficace,
répondre à deux critères parfois contradictoires: un minimum
d'espace mémoire utilisé et un minimum d’instructions pour
réaliser une opération.
II. Les variables dynamiques
jusqu‘ici, nous avons utilisé des variables dites «statiques»
Une variable statique est caractérisée par les
propriétés suivantes:
- elle est déclarée en tête du bloc ou elle est utilisée.
II. Les variables dynamiques

-elle occupe un espace mémoire dont la taille est fixée dés

le début pour qu'on y place ses valeurs.
L‘accès à la valeur se fait par le nom de la variable.
Au contraire, une variable dynamique est caractérisée par
les propriétés suivantes:
-elle peut être crée et détruite au cours de l'exécution du
bloc dans laquelle elle est déclarée.
-l'espace mémoire rendu libre peut être récupéré.
-l‘accès à la valeur se fait par un pointeur
II.1-Variable pointeur et variable pointée
Un pointeur P est une variable statique dont les valeurs sont
des adresses. Une variable dynamique pointé P sera noté P^
-Le type de la variable pointé est appelée type de base.
II. Les variables dynamiques
Exemple

43 "Tunis"

P
La variable
P^ pointeur P à pour valeur 43. Elle pointe sur l’espace
mémoire P^ d'adresse 43 dont le contenu est la chaine" Tunis"
L'algorithme suivant permet de créer et initialiser un pointeur P:
Algorithme Pteur
types
Pointeur = ^Chaine
Var
P : Pointeur
Début
Allouer(P) (*création du pointeur
P*) P ^  " Tunis"
Fin.
II. Les variables dynamiques
II.2-Opérations sur les pointeurs
Il ne faut pas confondre les opérations sur les pointeurs avec
les opérations
"Tunis" "Tunis" "Sousse"

P P^ P P^ P P^
"Sousse" "Sousse" "Sousse"

Q Q^ Q Q^ Q Q^
A B C
PQ Par contre, si l'instruction
P^ = Q^ = "Sousse" P^  Q^
si l'on modifie la valeur de Q^, P^ P^ = Q^ = "Sousse"
sera également modifié et si l'on modifie la valeur de Q^, P^ ne
restera égal à Q^. sera pas modifié.
III. Les listes linéaire chainées

La structure de liste est utilisée pour représenter un ensemble

d'élément contenus chacun dans une cellule. Celle-ci contient
en plus de l‘élément, l'adresse de l‘élément suivant appelée
pointeur. La référence vers la première cellule est contenue
dans un pointeur nommé tête de liste. Une liste chainé est
accessible uniquement par sa tête.
Tête de liste

Fin de
@ e1 @ e2 @ e3 @
liste (Nil)

Nil est une constante prédéfinie qui indique la fin de la liste

En supposant que les éléments de la liste sont des entiers,
celle-ci se déclare de la façon suivante:
III. Les listes linéaire chainées
types
Liste = ^Cellule
Cellule =
Struct
Elem:
entier
Suiv:
Liste
(*point
eur de
Liste*)
FinStruct
Var
L: Liste
(*pointeur
de Liste*)
III. Les listes linéaire chainées

Début
Allouer(Tête)
Ecrire("Entrer l'élément de tête:") Lire(Tête^.Elem)
Tête^.Suiv  Nil
L  Tête
Pour i de 2 à n Faire
Allouer(P)
Ecrire("Entrer un entier:") Lire (P^.Elem)
P^.Suiv  Nil
L^.Suiv  P
LP
FinPour
L  Tête
Fin
III. Les listes linéaire chainées

III.2 Parcours d'une liste chainée

La procédure itérative suivante permet de parcourir
et afficher les éléments d'une liste chainée.
Procédure AffichListe_itér( L: liste)
Var
P : Liste
Début
PL
TantQue (P <> Nil) Faire
Ecrire(P^.Elem)
P  P^.Suiv
FinTQ
Fin
Le parcours peut se faire
également de façon récursive:
III. Les listes linéaire chainées

Procédure AffichListe_récur(L:liste)
Début
Si (L <> Nil) Alors
Ecrire(L^.Elem)
Affich_list_récur(L^.Suiv)
FinSi
Fin
III.3 Insertion d'un élément en
tête de liste
Tête Fin de
@ e1 @ e2 @ e3 @
liste
(Nil)
III. Les listes linéaire chainées

Procédure AffichListe_récur(L:liste)
Début
Si (L <> Nil) Alors
Ecrire(L^.Elem)
Affich_list_récur(L^.Suiv)
FinSi
Fin
III.3 Insertion d'un élément en
tête de liste
Tête Fin de
@ e1 @ e2 @ e3 @
liste
(Nil)

e0 @
III. Les listes linéaire chainées
On suppos que la liste initiale contient au moins une cellule.
Procédure InsertTéte (Var L: Liste)
Var
P : Liste
Début
Allo
uer(P)
Ecrire("Entrer un entier:")
Lire(P^.Elem) P^.Suiv L
LP
Fin
III.3 Recherche d'un élément dans une liste
chainée
On veut une fonction recherche (x: Entier;
III. Les listes linéaire chainées
a- Version itérative
Fonction recherche(x: Entier; L: Liste):booléen
Var
P : Liste
trouve : Booléen
Début
trouve faux
PL
TantQue (P <>
Nil)
Et(trouve=fa
ux) Faire
trouve  (P^.Elem = x) P
 P^.Suiv
III. Les listes linéaire chainées
b- Version récursive
Fonction recherche(x : Entier; L: Liste):Booléen
Début
Si(L = Nil) Alors
rechercheFaux
Sinon
Si(L^.Elem = x )Alors
rechercheVrai
Sinon
rechercherecherche(x, L^.Suiv)
FinSi
FinSi
Fin
III. Les listes linéaire chainées
III.5 Suppression d'un élément d'une liste chainée
En supposant que la valeur x existe une seule fois dans la
liste, supprimer x revient à mettre à jour les liens de façon
que le successeur du prédécesseur de x devient le
successeur
traitement particulier doit être fait si l'élément à supprimer
est le premier élément de la liste.
Tête
Fin de
e1 e2 e3
liste
(Nil)
Têt
e
Fin de
e1 e2 e3
liste (Nil)
III. Les listes linéaire chainées

Procédure TantQue(Q<>Nil) Et
supprimer(x:Entier;Var L:Liste) (Q^.Elem<>x) Faire
Var PQ
P, Q: Liste Q  Q^.Suiv
Début FinTQ
Si (L <> Nil) Alors Si(Q <> Nil) Alors
PL P^.suiv  Q^.Suiv
Si (L^.Elem=x) Alors Libérer(Q)
L  L^.Suiv FinSi
Libérer(P) FinSi
Sinon
Q  L^.Suiv Finsi
Fin
III. Les listes linéaire chainées
L'instruction Libérer(P) permet de rendre disponible l'espace
occupé par P.
Exercice : Longueur d'une liste
Ecrire une fonction récursive qui retourne le
nombre d'élément d'une liste chainée.
Solution
Fonction Longueur(L: Liste):Entier
Début
Si (L = Nil) Alors
Longueur 0
Sinon
Longueur  1 + Longueur(L^.Suiv)
FinSi
Fin
III. Les listes linéaire chainées
Remarque:
une liste chainé circulaire est une liste particulière dans
laquelle le dernier élément pointe sur le premier élément de
la liste.
Tête
Fin de
e1 e2 e3
liste
(Nil)

IV. Les listes à chainage double

Ce sont des listes chainées avec, en plus, un pointeur vers
l'élément précédent de chaque cellule. Cette structure
permet de parcourir la liste dans les 2 sens et d'accélérer la
recherche d'un élément:
IV. Les listes à chainage double
Tête

Nil e1 e2 e3 Nil

Queue
en supposant que les élément de la liste sont des entiers,
celle-
ci se déclare de la façon suivante:
Type
liste = ^Cellule
Cellule = Struct
Pred : Liste
Elem :
Entier
Suiv : Liste
FinStruct
IV. Les listes à chainage double
IV.1 Création d'une liste à chainage double
La procédure suivante permet de créer une liste à chainage
double qui contient n éléments de types entier:
Procédure CréatListe (n; Entier ;Var L,Queue : Liste)
Var
Tête, P: liste
i : Entier
Début
Allouer
(Tête)
Ecrire("Entrer un entier:") Lire(Tête^.Elem)
Tête^.Pred  Nil
Tête^.Suiv  Nil
LTête
IV. Les listes à chainage double
Pour i de 2 à n Faire
Allouer(P)
Ecrire("Entrer un entier:") Lire (P^.Elem)
P^.Pred  L
P^.Suiv Nil
L^.Suiv  P
LP
FinPour
Queue  P
L  Tête
Fin
IV.2. Parcours
inverse d'une
liste à chainage
double
IV. Les listes à chainage double
Procedure AffichListe(Queue : Liste)
Var
P: Liste
Début
P  Queue
TantQue (P <> Nil) Faire
Ecrire (P^.Elem)
P  P^.Pred
FinTQ
Fin
V. les piles
1. présentation
Une pile est une suite des cellules allouées dynamiquement
(liste chainée) où l’insertion et la suppression d’un élément se
font toujours en tête de la liste.
PILE ET FILE

2
4
V. les piles
L’image intuitive d’une pile par une pile d’assiette ou une pile
de dossier a condition de supposer qu’on prend un seul
élément à la fois (celui de sommet). On peut résumer la
contrainte d’accès par le principe « dernier arrivé, premier
sorti » qui se traduit en anglais par : Last In First Out.
Sommet

e1 e2 e3 Nil

la structure d’un objet en pile s’impose lorsqu’on a des

informations qui devront être traitées dans l’ordre inverse de
leur arrivé. C’est le cas, par exemple, de la gestion des adresses
de retour dans l’exécution d’un programme récursif.
En supposant que les éléments de la pile sont des entiers,
celle-ci se déclare de la façon suivante :
V. les piles
Types
Pile =^Cellule
Cellule = struct
Elem : Entier
Suiv : Pile
FinStruct
Var
P : Pile
V.2. Manipulation d’une
pile
Du point de vu manipulation les contrainte d’accès
sont matérialisées par les procédures et les fonctions suivantes
: Procédure Initialiser (var P : Pile) : crée une Pile vide P.
Fonction Pile_Vide (P : Pile) booléen : renvoi la valeur vrai si la
V. les piles
Procédure Empiler (x : Entier ; Var P : Pile) : ajouté l’élément x
au sommet de la pile.
Procédure Dépiler (Var x : Entier ; Var P : Pile) : Dépiler le
sommet de la pile et le met dans le variable x.

Procédure Initialiser (var P : Pile) Procédure Empiler (x : Entier ; Var

Début P : Pile)
P Nil Var
Fin Q : Liste
Fonction Pile_Vide (P : Pile) Début
Début Allouer (Q)
Pile_Vide  (P = Nil) Q^.Elem  x
Fin Q^.Suiv  P
PQ
Fin
V. les piles
Procédure Dépiler (Var x : Entier ; Var P : Pile)
Début
Si NON (Pile_Vide(P)) Alors
x  P^.Elem
QP
P  P^.Suiv
Libérer (Q)
Sinon
Ecrire
("impossibl
e, la pile est
vide")
FinSI
Fin
V. les files
1. prése
ntati
V. les files
- On ne peut ajouter un élément qu’en dernier rang de la suite
- On ne peut supprimer que le premier élément
L’image intuitive d’une fille peut être donnée par la queue
devant le guichet lorsqu’il n’y a pas de resquilleurs. On peut
résumer les contraintes par le principe « premier arrivé
premier sorti » qui se traduit en anglais par : First In First Out.

Sommet Queue

e1 e2 e3 Nil

La d’un objet en file s’impose en

structure
lorsqu’une ressource
particulierdoit être protégée par plusieurs
utilisateurs : il y a formation d’une file d’attente.
V. les
files
Un exemple est donné par le spooler d’impression qui est un
programme qui reçoit, traite, planifie et distribue les
documents à imprimer dans un système multiprogrammé.
En supposant que les éléments de la file sont des entiers, celle-
ci se déclare de la façon suivante :
Types
Liste =^Cellule
Cellule=
strcut
Elem : Entier
Suiv : Liste
Finstruct
File = Struct
Tête : Liste
Queue : Liste
FinStruct
Var
V. les files
VI .2. Manipulation d’une file
Du point de vu manipulation, les contraintes d’accès
sont matérialisées pars les procédures et les fonctions
suivantes : Procédure Initialiser (var F : File) : crée une File
vide F. Procédure Ajouter (x : Entier ; Var F : File) : ajouté
l’élément x à la fin de la File.
Procédure Extraire (Var x : Entier ; Var F : File) : extrait le
sommet de la file et le met dans le variable x.
Procédure Initialiser (var F : File)
Début
F.Tête  Nil
F.Queue  Nil
Fin
V. les files
Procédure Ajouter (x : Entier ; Var F : File)
Var
P : Liste
Début
Allouer (P)
P^.Elem  x
Q^.Suiv  Nil
Si (F.Queue
<>

Nil) Alors
F.Que
ue^.S
uiv 
V. les
files
Dans le cas où la file est vide, comme la queue, la tête de la file
doit également pointer vers le nouvel élément.
Procédure Extraire (Var x : Entier ; Var P : Pile)
Var
P : Liste
Début
Si (F.Tête = Nil) Alors
Ecrire ("impossible, la file est vide")
Sinon
P  F.Tête
x  F.Tête^.Elem
F.Tête 
F.Tête^.Suiv Libérer
(P)
FinSI
V. les
files
Remarque
Dans les langages qui n’offre pas de type pointeur, les
structures de liste pile ou file peuvent être implanté sous
forme de tableaux.
Ainsi une liste chainée d’entier peut être déclaré de la façon
suivante :
Cons
N = 100
Types
Indice : 1..N
Cellule = struct
Elem : Entier
Suiv : Indice
Liste = Tableau [Indice] de cellule
Var
L : Liste