Les listes chaînées
Année universitaire :2019-2020
1
Plan
• Introduction & motivation
1
• Définition
2
• Caractéristiques d’une liste simplement chaînée
3
• Déclaration
4
• Opérations élémentaires sur les listes
5
• Synthèse
6
2
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Structure de données
• Une structure de données est une manière d’organiser et de stocker l’information.
• Une structure de données spécifie la façon de représenter les données d’un problème à
résoudre en décrivant:
✔ la manière d’attribuer une certaine quantité de mémoire à cette structure, (allocation
statique ou dynamique).
✔ la façon d’accéder aux données qu’elle contient.
3
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Structure de données déjà vue
❖ Les tableaux forment une suite de variables de même type associées à des emplacements consécutifs dans la
mémoire.
🡺 Problème: On peut avoir suffisamment d'espace mais qui n'est pas forcement contiguë!
❖ Les opérations d'insertion ou de suppression d'une case dans un tableau ne sont pas coûteuses dans le cas où elles
sont effectuées à la fin. Par contre, l'insertion ou la suppression d'un élément au début ou au milieu nécessitent
un décalage du contenu de plusieurs cases
🡺 Problème: un traitement coûteux en terme de temps d'exécution d'un programme.
❖ Lorsqu’il n’y a pas assez de place dans le tableau, il est nécessaire d’effectuer une réallocation afin de l’agrandir
🡺 Problème: il est possible qu’une zone entièrement différente soit réservée, ce qui implique de recopier
l’intégralité du tableau dans une nouvelle zone mémoire et de libérer l'ancienne zone.
4
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Structure de données déjà vue
Afin de contourner les difficultés liées aux tableaux, il faut adopter une structure de données:
⮚ qui n'exige pas une contiguïté des éléments à stocker en mémoire
⮚ dont les opérations d'ajout et de suppression sont moins coûteuses en terme de temps par rapport aux tableaux.
C’est le but des listes chaînées.
5
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Définition
• Une liste chaînée est une structure de données linéaire qui permet de stocker une suite d’éléments
de même type qui sont chaînés entre eux.
• L’élément de base d’une liste chaînée s’appelle maillon, cellule ou nœud
• Chaque cellule de la liste est constitué de deux parties:
✔ Un champ de données.
✔ un pointeur vers une structure de même type (l’élément suivant de la liste).
Pointeur Pointeur
Données vers le Données vers le …
maillon 2 maillon 3
maillon1 maillon2
6
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Définition
• Le champ pointeur vers un maillon pointe vers le maillon suivant de la liste.
• S’il n’y a pas de maillon suivant, le pointeur vaut NULL.
• Une liste vide est une liste qui ne contient pas de maillon. Elle a donc la valeur NULL.
• La terminologie suivante est généralement employée :
✔ L’adresse du premier maillon de la liste est appelé tête ;
✔ L’adresse du dernier maillon de la liste est appelé queue.
• Une liste est représentée par sa tête. Accédant à la tête, on peut accéder à tous les autres éléments .
7
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Représentation graphique
queue
• Chaque maillon de cette liste est une structure contenant des données et un pointeur vers l’élément suivant.
8
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Liste chaînée: Caractéristiques
▪ Une liste chaînée est une structure linéaire qui n’a pas de dimension fixée à sa création.
▪ Ses éléments de même type sont éparpillés dans la mémoire et reliés entre eux par des pointeurs.
Par exemple: Le premier élément de la liste peut se trouver à l’adresse 1024, le second à l’adresse 256, le
troisième en 532, le quatrième en 2084, etc.
▪ La liste est accessible uniquement par sa tête indiquant l'adresse de son premier élément.
▪ La fin de la liste est caractérisée par un pointeur NULL.
▪ Le dernier élément existant, son champ suivant vaut NULL.
9
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Déclaration
Syntaxe :
struct Nom_cellule
{ Données
Data D; Les données à stocker
struct Nom_cellule * suivant ; Pointeur sur l’élément suivant
};
10
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Exemple: une liste d'entiers
typedef struct Cellule Cellule;
struct Cellule struct Cellule
{ {
int valeur ; // Donnée int valeur ; // Donnée
struct Cellule * suivant ; // pointeur sur Ou bien Cellule * suivant ; // pointeur
l’élément suivant sur l’élément suivant
}; };
typedef struct Cellule * liste; typedef Cellule * liste;
Ces instructions déclarent une structure Cellule composée de :
1. Un premier champ contenant la donnée (un entier dans ce cas).
2. Un second champ indiquant le pointeur sur la cellule suivante.
3. Pour des raisons pratiques de facilité de manipulation, on définit le nouveau type liste comme étant
un pointeur sur une cellule. 11
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Exemple:
• Le 1er élément de la liste vaut 12 et se trouve à l'adresse 3, début de la liste.
• Le 2e élément de la liste vaut 14 et se trouve à l'adresse 4 (car le suivant de la cellule d’adresse 3 est égal à 4)
Tête: liste
@: 3 @: 4 @: 2 @: 1
14 24 10
12
4 NULL
2 1
12
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Opérations élémentaires sur les listes
1. Liste vide: savoir si une liste est vide ou pas.
2. Parcourir : passer chaque élément de la liste dans l'ordre du début vers la fin.
3. Ajouter une cellule à la liste, soit au début, soit à la fin, soit à une position donnée.
4. Supprimer : enlever une cellule de la liste.
5. Détruire une liste : libérer tous les maillons de la liste
13
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Liste vide
• Si la tête pointe vers NULL c'est que la liste est vide.
• Eventuellement on peut implémenter une fonction qui retourne 1 ou 0 indiquant si la liste est vide ou pas.
• Une liste est représentée par l'adresse de son premier élément, à partir duquel on accède à tous les
autres éléments par chainage. Ce premier élément est un pointeur qui vaut initialement NULL.
Déclaration de la liste
struct Cellule Liste vide
{ int liste_vide(liste l)
int valeur ; {
struct Cellule * suivant ; return (l==NULL);
}; }
typedef struct Cellule * liste;
int main{
liste l=NULL; // déclaration et initialisation de la liste
}
14
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Parcours d’une liste
⮚Parcourir une liste c’est-à-dire aller d’un bout à l’autre de la liste en traitant chaque élément consécutivement.
Pour cela, l’approche standard consiste:
• à utiliser un pointeur temporaire, que nous noterons tmp, et qui ne sera utilisé que pour cette tâche de
parcours.
• Le pointeur tmp est initialisé au début de la liste à la tête, et est modifié dans une boucle en lui
affectant à chaque fois l'adresse de la cellule suivante.
15
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Exemple : Afficher le contenu du champ de donnée:
Parcours
void parcourir(liste l)
{
struct cellule* tmp=l;
Cas tête if(l==NULL)
Null printf("la liste est vide");
else
{
while (tmp!=NULL)
{
Cas tête printf("%d",tmp->valeur);
Non Null tmp=tmp->suivant;
}
}
}
16
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Ajout d’un élément :
au début de la liste - à la fin de la liste – au milieu avant critère
Ajouter un élément suppose:
1.L'initialisation du champ de données.
2.L'initialisation du champ indiquant l'adresse de son suivant.
3.Décider où l’élément sera ajouté :
• Au début
• A la fin
• Au milieu, avant un critère donné.
17
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Ajout d’un élément :
au début de la liste - à la fin de la liste – au milieu avant critère
1. Créer une nouvelle cellule (Allocation et initialisation du champs de donnée)
SI la création fut un succès alors
2. On fait pointer la nouvelle cellule vers le 3. On fait pointer la tête de liste sur le
premier élément de la liste. nouveau nœud.
tête 34 12
26
18
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Ajout d’un élément :
au début de la liste - à la fin de la liste – au milieu avant critère
Ajout au début de la liste
liste ajouter_deb(liste l, int val)
{
Déclaration struct Cellule* nouv;
Allocation dynamique nouv = (struct Cellule*) malloc(sizeof(struct Cellule));
Et remplissage d’une nouv->valeur=val;
nouvelle cellule nouv->suivant=NULL;
Le suivant de la nouv->suivant=l;
nouvelle cellule
est l’ancienne tête
La nouvelle tête est
l’adresse de la l=nouv;
nouvelle cellule
l’adresse de la première
cellule a changé return(l);
-->elle doit être retournée }
19
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Ajout d’un élément :
au début de la liste - à la fin de la liste – au milieu avant critère
1. Allouer dynamiquement une nouvelle cellule .
2. Initialiser le champs de donnée et le pointeur suivant à NULL
SI la création fut un succès ALORS
3. La tête est l’adresse de la nouvelle cellule
4. On parcours la liste jusqu’à atteindre l’adresse de la dernière cellule.
5. On fait pointer la dernière cellule sur la nouvelle cellule
tête 34 12 26
20
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Ajout d’un élément :
au début de la liste - à la fin de la liste – au milieu avant critère
liste ajouter_Fin(liste l, int val)
{
Déclaration struct Cellule * nouv, *parc;
Création nouv = (struct Cellule*) malloc(sizeof(struct Cellule));
nouvelle nouv->valeur=val;
cellule nouv->suivant=NULL;
if(l==NULL)
Cas tête
{
==Null
l=nouv;
}
else
{
Cas tête parc=l;
!=Null while(parc->suivant!=NULL)
parc=parc->suivant;
parc->suivant = nouv;
}
Fin return(l);
} 21
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Ajout d’un élément :
au début de la liste - à la fin de la liste – au milieu avant critère
⮚ Il s’agit d’ajouter une cellule avant une cellule qui vérifie un certain critère.
⮚ Il existe 3 différents scenarios:
1) La liste est vide ou toutes les cellules ne vérifient pas le critère d’insertion: pas d’insertion
2) Le critère est vérifié pour la première cellule : changement de la tête
3) Le critère est vérifié pour une cellule autre que la tête : changement du chainage
22
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Ajout d’un élément :
au début de la liste - à la fin de la liste – au milieu avant critère
Par exemple, insérer 12 avant la cellule qui contient la valeur 15
Liste initiale
6 @C2 10 @C3 15 NULL
@ C1
@C1 @C2 @C3
tête
Liste résultat
6 @C2 10 @C3 15 NULL
@C1 @C2 @C3
@ C1
tête
@nouv 12 @C3
nouv @nouv
23
Introduction & Motivation Définition Caractéristiques Déclaration Opérations élémentaires
Ajout d’un élément :
au début de la liste - à la fin de la liste – au milieu avant critère
liste ajoutmilieu (liste l , int val, int critere)
{
Déclaration struct Cellule* nouv=NULL, *precedent=NULL,*courant=l;
while (courant!=NULL && courant->valeur !=critere)
Recherche de la cellule
{ precedent=courant;
vérifiant le critère et de la
courant=courant->suivant;
cellule qui la précède
}
if(courant==NULL)//liste vide ou critère non vérifié dans toutes les
Pas d’insertion cellules.
printf(«critère non vérifié »);
else //critère vérifiée
{
Allocation et remplissage
nouv=(struct Cellule*)malloc(sizeof(struct Cellule));
d’une nouvelle cellule
nouv->valeur=val;
nouv->suivant=courant;
Changement de la tête If(courant==l)
l=nouv;
Changement du else
chainage precedent->suivant=nouv;
}
Ne pas perdre la nouvelle return l; } 24
tête