Les listes chaînées PDF

Les listes chaînées 3/30 1. Introduction : Objectif et Motivation En langage C, il existe un grand nombre de structure de données : Exemple : les tableaux les structures, les listes chaı̂nées, les piles, les files, les arbres binaires... L’objectif d...

Les listes chaînées 3/30 1. Introduction : Objectif et Motivation En langage C, il existe un grand nombre de structure de données : Exemple : les tableaux les structures, les listes chaı̂nées, les piles, les files, les arbres binaires... L’objectif de ce chapitre est d’introduire quelques structures de données très utilisées en programmation, notamment en langage C et qui ont pour but la gestion d’un ensemble fini d’éléments dont le nombre n’est pas fixé. Exemple : listes chaı̂nées, les piles, les files, les arbres binaires, les graphes. Les éléments de cet ensemble peuvent être de différentes types : nombres entiers ou réels, chaı̂nes de caractères,... On ne s’intéressera pas aux éléments de l’ensemble en question mais aux opérations que l’on effectue sur cet ensemble, indépendamment de la nature de ses éléments. En programmation informatique, ces ensembles sont considérés comme des objets dynamiques. En effet, le nombre de leurs éléments varie au cours de l’exécution du programme, puisqu’on peut y ajouter et supprimer des éléments en cours de traitement. Plus précisément les opérations que l’on s’autorise sur les ensembles sont les suivantes : tester si un ensemble est vide. ajouter un élément à un ensemble. supprimer un élément à un ensemble. rechercher un élément dans un ensemble. Cette gestion des ensembles doit, pour être efficace, répondre à deux critères : un minimum de place mémoire utilisée, et un minimum d’instructions élémentaires pour réaliser une opération. Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C 4/30 1. Introduction : Objectif et Motivation Notons que la structure de données la plus utilisée pour manipuler des données sont les tableaux. Mais, dans certains cas, les tableaux ne constituent pas la meilleure solution pour stocker et manipuler les données. En effet, Si on veut supprimer un élément au milieu d’un tableau, il faut recopier les éléments temporairement, réallouer le tableau, puis le remplir à partir de l’élément supprimé. Ces manipulations sont coûteuses en ressources. En langage C, les listes chaı̂nées (ou tout simplement les listes) peuvent être considérées comme des structures de données très pratiques pour manipuler des éléments d’un ensemble d’objets dynamiques. En effet, une liste chaı̂née est différente par rapport à un tableau dans le sens où ses éléments sont répartis dans la mémoire et reliés entre eux par des pointeurs. Ceci permet d’ajouter et de supprimer des éléments d’une liste à n’importe quel endroit, sans modifier la liste entière. Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C 5/30 2. Les listes chaı̂nées Une liste chaı̂née est une structure de base de la programmation informatique. C’est une structure de données dans laquelle les objets sont stockés de manière ordonnée (l’ordre signifie que chaque objet possède une position dans la liste). Cependant, contrairement au tableau, pour lequel l’ordre est déterminé par les indices, l’ordre d’une liste chaı̂née est déterminé par un pointeur dans chaque objet. Les listes chaı̂nées sont des structures dynamiques capables, d’accueillir un nombre infini d’éléments, et de supporter toutes les opérations sur les ensembles dynamiques (insertion, suppression, recherche,...). Dans la suite du chapitre, on utilise la liste chaı̂née pour représenter un ensemble d’éléments. Chaque élément est contenu dans une cellule (appelée aussi maillon), et chaque cellule est composée d’une partie contenant l’information et d’au moins un pointeur. Pointeur vers le prochain élément Information Représentation d’une cellule avec un seul pointeur. Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C 6/30 2. Les listes chaı̂nées Chaque élément est accessible par celui qui le précède grâce au pointeur. Une liste chaı̂née est donc une succession de cellules, dont le dernier porte une adresse de fin (le pointeur NULL). La première cellule de la liste est appelée tête et la dernière cellule est appelée queue. L’accès à la liste chaı̂née se fait par un pointeur vers le premier élément. Pour atteindre un des éléments de la liste, on est obligé de parcourir la liste depuis le début. A partir d’un élément quelconque, on ne peut atteindre que le suivant. Une liste chaı̂née peut prendre différentes formes : Elle peut être simple (dite aussi simplement chaı̂née) : chaque cellule est composé de l’information et d’un seul pointeur (pointe sur l’adresse de la cellule suivante). Ou doublement chaı̂née : chaque cellule est composé de l’information et de deux pointeurs (l’un pointe sur l’adresse de la cellule suivante et l’autre sur celle de la cellule précédente). Ou circulaire : la tête pointe sur la queue de la liste, et la queue pointe sur la tête de la liste. Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C 7/30 2. Les listes chaı̂nées : 2.1 Les listes simplement chaı̂nées Rappelons qu’une liste simplement chaı̂née est une liste où chaque cellules contient des informations accessibles et modifiables par l’utilisateur ainsi qu’un pointeur vers la cellule suivante. Valeur 1 Valeur 2 Valeur 3 Valeur 4 NULL Tête Queue Comme les listes simplement chaı̂nées sont une structure de données importante en programmation informatique, il est fondamental de s’intéresser à la manière de les implanter en vue de leurs manipulations informatique. Deux modes de d’implantation peuvent être envisagés : Implantation par pointeur. Implantation par tableau. Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C 8/30 2.1 Les listes simplement chaı̂nées : Implantation par pointeur Déclaration Le langage C permet de réaliser des listes chaı̂nées à l’aide des structures (le type structure en C qui est créée par le mot clé struct). En effet, les cellules sont des objets constitués : d’un champ de données, d’un pointeur vers la cellule suivante. La déclaration correspondante est la suivante, où l’on suppose ici que les valeurs stockées dans chaque cellule sont de type entier. Code en C typedef int element; struct cellule { element valeur; struct cellule * suivant; }; typedef struct cellule cellule, * liste; Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C 9/30 2.1 Les listes simplement chaı̂nées : Implantation par pointeur Remarque 1: Notons qu’on peut créer des listes chaı̂nées contenant des valeurs qui sont : de différents type, c-à-d des entiers, des réels, des caractères, des tableaux, des structures, une combinaison de plusieurs types, ou des listes chaı̂nées. Exemple : typedef float element; struct cellule { element valeur; struct cellule * suivant; }; typedef struct cellule cellule, * liste; Remarque 2: Les instructions suivantes permettent de déclarer, de façons différentes mais équivalentes, une liste chaı̂née : liste liste1; cellule *liste2; struct cellule *liste3; Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C 10/30 2.1 Les listes simplement chaı̂nées : Implantation par pointeur Création et initialisation Pour créer une liste chaı̂née, on doit l’initialiser à NULL (macro de stdlib.h), cela va nous permettre d’allouer la première cellule. L’initialisation d’une liste chaı̂née, ou la création d’une liste vide, est généralement faite par la fonction suivante : liste creerListeVide( ) { return NULL; } Pour tester si une liste est vide, on utilise la fonction suivante : int ListeVide(liste l) { return l==NULL; } Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C 11/30 2.1 Les listes simplement chaı̂nées : Implantation par pointeur Insertion d’une cellule (Ajout d’une valeur dans une liste) : Il est toujours possible d’insérer des cellules (ajouter des valeurs) à une liste chaı̂née donnée. En effet, il y a deux façons d’ajouter des cellules dans des listes chaı̂nées : ajouter une nouvelle cellule en tête de la liste, ajouter une nouvelle cellule à la fin de la liste. Ainsi, les fonctions ajouterElementTeteListe () et ajouterElementFinListe () permettent respectivement l’ajout d’un élément en tête et à la fin d’une liste. Ajout d’un élément en tête de la liste liste ajouterElementTeteListe(element val, liste l) { liste ln; ln=malloc(sizeof(cellule)); ln->valeur=val; ln->suivant=l; return ln; } Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C 12/30 2.1 Les listes simplement chaı̂nées : Implantation par pointeur Insertion d’une cellule (Ajout d’une valeur dans une liste) : Ajout d’un élément à la fin de la liste liste ajouterElementFinListe(element val, liste l) { liste ln,lp; ln=malloc(sizeof(cellule)); ln->valeur=val; ln->suivant=NULL; if(l==NULL) return ln; else { lp=l; while(lp->suivant != NULL) { lp= lp->suivant; } lp->suivant =ln; return l; } } Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C 13/30 2.1 Les listes simplement chaı̂nées : Implantation par pointeur Suppression d’une cellule (supprimer une valeur dans une liste) : Il est possible également de supprimer des cellules (des valeurs) dans une liste chaı̂née donnée. En effet, il y a trois façons de supprimer des cellules dans des listes chaı̂nées : supprimer une cellule en tête de la liste, supprimer une cellule à la fin de la liste, supprimer une cellule quelconque dans une liste. Suppression d’un élément en tête de la liste liste supprimerElementTeteListe(liste l) { liste lp; if(l==NULL) return NULL; else { lp=l->suivant; free(l); return lp; } } Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C 14/30 2.1 Les listes simplement chaı̂nées : Implantation par pointeur Suppression d’une cellule (supprimer une valeur dans une liste) : Suppression d’un élément à la fin de la liste liste supprimerElementFinListe(liste l) { liste lp1,lp2; if(l==NULL) return NULL; if(l->suivant==NULL) { free(l); return NULL; } lp1=l; while(lp1->suivant->suivant!=NULL) { lp1=lp1->suivant; } lp2=lp1->suivant; lp1->suivant=NULL; free(lp2); return l; } Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C 15/30 2.1 Les listes simplement chaı̂nées : Implantation par pointeur Suppression d’une cellule (supprimer une valeur dans une liste) : Suppression d’un élément quelconque dans la liste (Méthode itérative) liste supprimerItertiveElementListe(element val, liste l) { liste lp1,lp2; if(l!=NULL) if(l->valeur==val) { lp1=l; l=l->suivant; free(lp1); } else { lp2=l; while(lp2->suivant!=NULL && lp2->suivant->valeur!=val) lp2=lp2->suivant; if(lp2->suivant!=NULL) { lp1=lp2->suivant; lp2->suivant=lp2->suivant->suivant; free(lp1); } } return l; } Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C 16/30 2.1 Les listes simplement chaı̂nées : Implantation par pointeur Suppression d’une cellule (supprimer une valeur dans une liste) : Suppression d’un élément quelconque dans la liste (Méthode récurrente) liste supprimerRecurrenteElementListe(element val, liste l) { liste lp; if(l!=NULL) if(l->valeur==val) { lp=l; l=l->suivant; free(lp); } else l->suivant=supprimerRecurrenteElementListe(val, l->suivant); return l; } Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C 17/30 2.1 Les listes simplement chaı̂nées : Implantation par pointeur Recherche dans une liste : Étant donnée une liste chaı̂née liste et une valeur val, l’objectif ici est d’effectue un parcours de liste pour rechercher la valeur val dans liste. Pour ceci, on peut envisager deux types de fonction : une fonction qui teste si la valeur recherchée val figure dans la liste liste. une fonction qui renvoie l’adresse de la cellule contenant la valeur recherchée val. fonctions qui testent si val figure dans liste Recherche dans une liste (Méthode itérative) Recherche dans une liste (Méthode récurrente) int rechercherIterListe(element val, liste L) int rechercherRecListe(element val, liste L) { { while(L!=NULL) if(L==NULL) { return 0; if(L->valeur==val) else if(L->valeur==val) return 1; return 1; L=L->suivant; else } return rechercherRecListe(val, L->suivant); return 0; } } Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C 18/30 2.1 Les listes simplement chaı̂nées : Implantation par pointeur Recherche dans une liste : fonctions qui renvoient l’adresse de la cellule contenant val Recherche dans une liste (Méthode itérative) Recherche dans une liste (Méthode récurrente) liste rechercherLIter(element val, liste L) liste rechercherLRec(element val, liste L) { { while(L!=NULL) if(L==NULL) { return NULL; if(L->valeur==val) else if(L->valeur==val) return L; return L; L=L->suivant; else } return rechercherLRec(val, L->suivant); return NULL; } } Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C 19/30 2.1 Les listes simplement chaı̂nées : Implantation par pointeur Affichage d’une liste : La fonction suivante permet d’afficher les valeurs stockée d’une liste. Affichage d’une liste void afficherListe(liste l) { while(l!=NULL) { printf("%d ",l->valeur); l=l->suivant; } printf("\n"); } Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C 20/30 2.1 Les listes simplement chaı̂nées : Implantation par pointeur Exercice : Écrire un programme complet en langage C qui permet de construire une liste chaı̂née, afficher une liste chaı̂née, calculer la longueur d’une liste chaı̂née, rechercher une valeur dans la liste et de retourner sa position dans la liste. effectuer les manipulations suivantes : supprimer une valeur quelconque de la liste, supprimer une valeur en début de liste, supprimer une valeur en fin de liste, supprimer une valeur à une position donnée dans la liste, supprimer une valeur avant ou après une position donnée dans la liste. Filière SMI/SMA 2008-2009 Informatique 3 : Structures de données en C