Chapitre 11:Les listes chainée
2021-2022 SAHAR TRIGUI 193
Introduction
Une liste chaînée est une structure linéaire d’éléments (ou bien nœuds, cellule,
…) de même type et qui n'a pas de dimension fixe à sa création.
les éléments d’une liste chaînée sont éparpillés dans la mémoire et reliés entre
eux par des pointeurs.
Une liste chaînée est accessible uniquement par sa tête de liste c’est-à-dire son
premier élément.
chaque élément indique l'emplacement de l'élément suivant. Le dernier
élément de la liste ne pointe sur rien (NULL).
194
Introduction
Exemple d’une liste chaînée: ll=(t1,t2,t3,t4)
cellule
premier
t1 t2 t3 t4
adresse du
information
suivant
premier est une variable de type pointeur (adresse du premier élément)
Si premier est null alors alors on constate que la liste est vide
195
Introduction
La longueur d’une liste est le nombre de ses éléments.
Elle est nulle si la liste est vide
Elle augmente de 1 lors de l’ajout d’un élément
Elle diminue de 1 lors de la suppression d’un élément
2021-2022 SAHAR TRIGUI 196
Les types de listes chaînées
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.
2021-2022 SAHAR TRIGUI 197
Opérations sur les listes
creer_liste_vide: créer une liste vide => opération de création
liste_vide: vérifier si une liste est vide ou non Opérations de
chercher: chercher un élément donné dans une liste consultation
ajouter: ajouter un élément dans une liste
supprimer: supprimer un élément donné d’une liste Opérations de
modification
visiter: visiter les éléments et appliquer un traitement donné
198
Déclaration d’une liste
Une cellule d’une liste chaînée est constitué d’un champs qui contient une information ou
donnée et d’un autre champ qui contient un pointeur vers une autre cellule de même structure.
Une liste chaînée est définie comme suit:
struct cellule
{
element information;
struct cellule *suivant;
};
typedef struct cellule cellule;
Le type « element » de « information » dépend des valeurs contenues dans la liste : entier,
chaîne de caractères, etc.
199
Déclaration d’une liste
La déclaration d’une liste chaînée consiste à définir son premier élément.
La déclaration d’un pointeur vers le premier élément de la liste est :
cellule *premier;
L’initialisation d’une liste vide:
premier = NULL.
premier NULL
On peut créer une fonction creer_liste qui permet de créer une liste vide:
void creer_liste_vide(cellule *premier)
{ premier = NULL ; }
200
Ajout du premier élément
Après la déclaration et la création de la liste, on peut ajouter un élément.
Allocation de la mémoire pour le nouveau élément.
nouveau = (cellule *) malloc(sizeof(cellule));
Lecture de l’information, par saisie, affectation, …
Le champ « suivant » de « nouveau » prend comme valeur celui de la cellule premier.
nouveau -> suivant = NULL;// nouveau -> suivant = premier;
La nouvelle cellule devient le premier (tête) de la liste
premier = nouveau; // le pointeur premier pointe maintenant sur p
premier
t1
201
Création d’une liste
La création de n entiers dans une liste consiste à allouer n espaces mémoires, saisir les
n informations et lier les éléments.
202
Affichage d’une liste
L’affichage d’une liste consiste à afficher l’information contenue dans le champ
information de chaque cellule. L’opération s ’arrête lorsque le champ suivant pointe vers
le NULL.
203
Ajouter au début d’une liste
premier
t1 t2 t3 t4
t5
204
Ajouter à la fin d’une liste
premier
t1 t2 t3
t4
t5
205
Ajouter à une position
206
Supprimer le premier élément d’une liste
2021-2022 SAHAR TRIGUI 207
Supprimer le dernier élément
2021-2022 SAHAR TRIGUI 208
Supprimer à une position
2021-2022 SAHAR TRIGUI 209
Vérifier l’existence d’un élément dans
une liste
2021-2022 SAHAR TRIGUI 210
Vider une liste
2021-2022 SAHAR TRIGUI 211
Chapitre 12:Les piles
2021-2022 SAHAR TRIGUI 212
Introduction
Une pile est une structure de données de taille variable, initialement vide, sur
laquelle plusieurs opérations sont applicables.
Une pile regroupe plusieurs éléments et obéie à la loi « dernier rentré,
premier sorti » ou « Last In, First Out (LIFO) ».
Les opérations applicables sur une structure de données pile sont:
Opérations de consultation: Obtenir des renseignement sur l’état de la pile (vide et
dernier)
Opérations de modification: Modifier l’état d’une pile (empiler et dépiler)
Opérations de création: Créer la structure de données pile (créer_pile)
2021-2022 SAHAR TRIGUI 213
Introduction
Les éléments qui forment une pile sont repérés par un point d’accès appelé
sommet.
Pour gérer une pile, on n’utilise que son sommet.
Un élément ne peut être inséré qu'au sommet de la pile,
Un élément ne peut être supprimé que du sommet de la pile.
Exemple: Empiler ‘b’ Dépiler ‘b’
sommet
sommet
‘b’
‘a’ ‘a’
2021-2022 SAHAR TRIGUI 214
Opérations sur une pile
pile creer_pile(): créer une pile vide.
int vide (pile p): vérifier si la pile est vide ou non.
element dernier (pile p): afficher le dernier élément empiler.
pile empiler (pile p, element e): ajouter un élément à la pile
pile depiler (pile p): supprimer le dernier élément empiler dans la pile
Remarques:
Un empilement suivit immédiatement d’un dépilement laisse la pile inchangée
Un dépilement suivit immédiatement de l’empilement de l’élément dépilé laisse la
pile inchangée.
L’opération de dépilement suppose que la pile est non vide.
2021-2022 SAHAR TRIGUI 215
Représentation physique d‘une pile
Représentation contiguë
Elle permet de mémoriser les éléments d’une pile dans un espace contiguë (sous
forme d’un tableau).
n #define n 100
struct pile
Partie non utilisée entre sommet+1 et n {
element information[n];
int sommet;
‘b’ };
Partie utilisée entre 1 et sommet (=2)
1 ‘a’ typedef struct pile pile;
NB: Le type « element » de « information » dépend des valeurs contenues dans la liste : entier, réel, etc.
2021-2022 SAHAR TRIGUI 216
Représentation physique d‘une pile
Représentation chainée
Elle permet de mémoriser les éléments d’une pile dans des endroits quelconques en
mémoire centrale mais reliés entre eux.
Elle comporte un ensemble de nœuds où chacun se compose de deux champs:
information: contient un élément de la pile.
suivant: mémorise un pointeur sur l’élément précédemment empilé.
L’accès aux éléments d’une pile se fait à l’aide du point d’accès sommet qui
initialement pointe vers le NULL.
sommet
‘b’ ‘a’
2021-2022 SAHAR TRIGUI 217
Représentation physique d‘une pile
struct cellule
{
element information;
struct cellule *suivant;
};
typedef struct cellule cellule;
NB: Le type « element » de « information » dépend des valeurs contenues dans la liste : entier,
réel, etc.
2021-2022 SAHAR TRIGUI 218
Matérialisation d’une pile
Représentation contiguë
2021-2022 SAHAR TRIGUI 219
Matérialisation d’une pile
2021-2022 SAHAR TRIGUI 220
Matérialisation d’une pile
2021-2022 SAHAR TRIGUI 221
Matérialisation d’une pile
Représentation chainée
2021-2022 SAHAR TRIGUI 222
Matérialisation d’une pile
2021-2022 SAHAR TRIGUI 223
Matérialisation d’une pile
2021-2022 SAHAR TRIGUI 224
Exercice
Ecrire un programme en C qui permet de lire une expression avec des
parenthèses supposée valide (câd nombre de parenthèses ouvrantes = nombre
de parenthèses fermantes) et d’afficher toutes les sous-expressions entre
parenthèses en commençant par la plus interne.
Par exemple, si l’expression saisie est: a+((b*c)-d) alors le programme doit
afficher
(b*c)
((b*c)-d)
2021-2022 SAHAR TRIGUI 225
