Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Généralités sur les listes chainées Lorsque vous créez un algorithme utilisant

Généralités sur les listes chainées Lorsque vous créez un algorithme utilisant des conteneurs, il existe différentes manières de les implémenter, la façon la plus courante étant les tableaux, que vous connaissez tous. Lorsque vous créez un tableau, les éléments de celui-ci sont placés de façon contiguë en mémoire. Pour pouvoir le créer, il vous faut connaître sa taille. Si vous voulez supprimer un élément au milieu du tableau, il vous faut recopier les éléments temporairement, ré-allouer de la mémoire pour le tableau, puis le remplir à partir de l'élément supprimé. En bref, ce sont beaucoup de manipulations coûteuses en ressources. Une liste chaînée est différente dans le sens où les éléments de votre liste sont répartis dans la mémoire et reliés entre eux par des pointeurs. Vous pouvez ajouter et enlever des éléments d'une liste chaînée à n'importe quel endroit, à n'importe quel instant, sans devoir recréer la liste entière. Nous allons essayer de voir ceci plus en détail sur ces schémas : Vous avez sur ce schéma la représentation que l'on pourrait faire d'un tableau et d'une liste chaînée. Chacune de ces représentations possède ses avantages et inconvénients. C'est lors de l'écriture de votre programme que vous devez vous poser la question de savoir laquelle des deux méthodes est la plus intéressante.  Dans un tableau, la taille est connue, l'adresse du premier élément aussi. Lorsque vous déclarez un tableau, la variable contiendra l'adresse du premier élément de votre tableau. Comme le stockage est contigu, et la taille de chacun des éléments connue, il est possible d'atteindre directement la case i d'un tableau.  Pour déclarer un tableau, il faut connaître sa taille.  Pour supprimer ou ajouter un élément à un tableau, il faut créer un nouveau tableau et supprimer l'ancien. Ce n'est en général pas visible par l'utilisateur, mais c'est ce que realloc va souvent faire. L'adresse du premier élément d'un tableau peut changer après un realloc, ce qui est tout à fait logique puisque realloc n'aura pas forcement la possibilité de trouver en mémoire la place nécessaire et contiguë pour allouer votre nouveau tableau. realloc va donc chercher une place suffisante, recopier votre tableau, et supprimer l'ancien.  Dans une liste chaînée, la taille est inconnue au départ, la liste peut avoir autant d'éléments que votre mémoire le permet. Il est en revanche impossible d'accéder directement à l'élément i de la liste chainée. Pour ce faire, il vous faudra traverser les i-1 éléments précédents de la liste.  Pour déclarer une liste chaînée, il suffit de créer le pointeur qui va pointer sur le premier élément de votre liste chaînée, aucune taille n'est donc à spécifier.  Il est possible d'ajouter, de supprimer, d'intervertir des éléments d'une liste chaînée sans avoir à recréer la liste en entier, mais en manipulant simplement leurs pointeurs. Chaque élément d'une liste chaînée est composé de deux parties :  la valeur que vous voulez stocker,  l'adresse de l'élément suivant, s'il existe. S'il n'y a plus d'élément suivant, alors l'adresse sera NULL, et désignera le bout de la chaîne. Voilà deux schémas pour expliquer comment se passent l'ajout et la suppression d'un élément d'une liste chaînée. Remarquez le symbole en bout de chaîne qui signifie que l'adresse de l'élément suivant ne pointe sur rien, c'est-à-dire sur NULL. Comme vous vous en doutez certainement maintenant, la liste chaînée est un type structuré. Nous en avons terminé avec ces quelques généralités, nous allons pouvoir passer à la définition d'une structure de données nous permettant de créer cette fameuse liste ! Vous pouvez essayer d'imaginer à quoi va ressembler la structure liste_chainee : si vous avez compris le principe, vous en êtes capables. Je vous invite donc à écrire sur un papier vos idées que vous pourrez ensuite comparer au résultat que je vais fournir un peu plus bas ! Retour en haut Déclaration en C d'une liste chainée Vous vous demandez sûrement de quel type sera l'élément de la liste chaînée. A ceci je ne peux répondre que... à vous de voir. En effet, vous pouvez créer des listes chaînées de n'importe quel type d'éléments : entiers, caractères, structures, tableaux, voir même d'autres listes chaînées... Il vous est même possible de combiner plusieurs types dans une même liste. Allez : vous avez assez patienté, voici la déclaration d'une liste simplement chaînée d'entiers : Code : C - Sélectionner 1 2 3 4 5 6 7 8 9 10 #include <stdlib.h> typedef struct element element; struct element { int val; struct element *nxt; }; typedef element* llist; On crée le type element qui est une structure contenant un entier (val) et un pointeur sur élément (nxt), qui contiendra l'adresse de l'élément suivant. Ensuite, il nous faut créer le type llist (pour linked list = liste chaînée) qui est en fait un pointeur sur le type element. Lorsque nous allons déclarer la liste chaînée, nous devrons déclarer un pointeur sur element, l'initialiser à NULL, pour pouvoir ensuite allouer le premier élément. N'oubliez pas d'inclure stdlib.h afin de pouvoir utiliser la macro NULL. Comme vous allez le constater, nous avons juste crée le type llist afin de simplifier la déclaration. Voilà comment déclarer une liste chaînée (vide pour l'instant) : Code : C - Sélectionner 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <stdlib.h> typedef struct element element; struct element { int val; struct element *nxt; }; typedef element* llist; int main(int argc, char **argv) { /* Déclarons 3 listes chaînées de façons différentes mais équivalentes */ llist ma_liste1 = NULL; element *ma_liste2 = NULL; struct element *ma_liste3 = NULL; return 0; } Il est important de toujours initialiser la liste chaînée à NULL. Le cas échéant, elle sera considérée comme contenant au moins un élément. C'est une erreur fréquente. A garder en mémoire donc. De manière générale, il est plus sage de toujours initialiser vos pointeurs. Retour en haut Manipuler les listes chainées (1/2) Maintenant que nous savons comment déclarer une liste chaînée, il serait intéressant d'apprendre à ajouter des éléments dans cette liste, ainsi que de lire ce qu'elle contient. C'est ce que nous allons étudier dans cette première partie sur la manipulation des listes chaînées. Je vous invite à essayer par vous-mêmes de programmer ces quelques fonctions basiques permettant de manipuler les listes. Dans tous les cas (ou presque), nous renverrons la nouvelle liste, c'est-à-dire un pointeur sur element contenant l'adresse du premier élément de la liste. Ajouter un élément Lorsque nous voulons ajouter un élément dans une liste chaînée, il faut savoir où l'insérer. Les deux ajouts génériques des listes chaînées sont les ajouts en tête, et les ajouts en fin de liste. Nous allons étudier ces deux moyens d'ajouter un élément à une liste. Ajouter en tête Lors d'un ajout en tête, nous allons créer un élément, lui assigner la valeur que l'on veut ajouter, puis pour terminer, raccorder cet élément à la liste passée en paramètre. Lors d'un ajout en tête, on devra donc assigner à nxt l'adresse du premier élément de la liste passé en paramètre. Visualisons tout ceci sur un schéma : Code : C - Sélectionner 1 2 3 4 5 6 llist ajouterEnTete(llist liste, int valeur) { /* On crée un nouvel élément */ element* nouvelElement = malloc(sizeof(element)); /* On assigne la valeur au nouvel élément */ 7 8 9 10 11 12 13 14 nouvelElement->val = valeur; /* On assigne l'adresse de l'élément suivant au nouvel élément */ nouvelElement->nxt = liste; /* On retourne la nouvelle liste, i.e. le pointeur sur le premier élément */ return nouvelElement; } C'est l'ajout le plus simple des deux. Il suffit de créer un nouvel élément puis de le relier au début de la liste originale. Si l'original est , (vide) c'est NULL qui sera assigne au champ nxt du nouvel element. La liste contiendra dans ce cas-là un seul élément. Ajouter en fin de liste Cette fois-ci, c'est un peu plus compliqué. Il nous faut tout d'abord créer un nouvel élément, lui assigner sa valeur, et mettre l'adresse de l'élément suivant à NULL. En effet,, comme cet élément va terminer la liste nous devons signaler qu'il n'y a plus d'élément suivant. Ensuite, il faut faire pointer le dernier élément de liste originale sur le nouvel élément que nous venons de créer. Pour ce faire, il faut créer un pointeur temporaire sur element qui va se déplacer d'élément en élément, et regarder si cet élément est le dernier de la liste. Un élément sera forcément le dernier de la liste si NULL est assigné à son champ nxt. Code : C - Sélectionner 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 llist ajouterEnFin(llist liste, int valeur) { /* On crée un nouvel élément */ element* nouvelElement = malloc(sizeof(element)); /* On assigne la valeur au nouvel élément */ nouvelElement->val = valeur; /* On ajoute en fin, donc aucun élément ne va suivre */ nouvelElement->nxt = NULL; uploads/Geographie/ generalites-sur-les-listes-chainees.pdf