Précision sur les listes chaînées

Bonsoir,

j'aimerais quelques précisions sur les listes chaînées :

D'après ce que j'ai compris du sujet (corrigez moi si je me trompe!), une liste liste chaînée est composée de n structures contenant une partie données (entier,chaîne de caractères, structure, etc)et d'un pointeur pointant vers l'élément suivant (avec cas particulier pour premier et dernier éléments).

L'avantage d'une liste chaînée est donc de pouvoir insérer et créer autant d'éléments que l'on souhaite, sans savoir à l'origine combien il y en aura ( car si l'on sait combien on aura d'éléments, autant créer un tableau c'est bien plus simple non ?).

Mais au début du programme, il faut bien déclarer chaque les éléments ? Alors comment est-ce possible vu que l'on n'en connait pas a priori le nombre ?

C'estpour cela qu'il me semble que l'on ne déclare que 3 structures,

où la strucure en question est par exemple

Code:

---

1 2 3 4 5 6

typedef struct noeud{   char info; struct noeud *next;   }node;

---

node *tete,p*,q*;
(tete est le premier element dela liste)
et p et q sont utilisés lors d'opérations telles que insérer, déplacer, supprimer(etc.) un élément et modifient les pointeurs sur la structure pour indiquer le nouveau chemin vers l'élément suivant.

Donc je pense qu'on ne connait pas explicitement l'adresse du i-ème élément, mais qu'on y accède à partir de l'adresse du premier élément.

Mais alors comment acceder concrètement à cet i-ème élément en pratique ?
Par exemple pour afficher à l'écran le contenu de sa partie information ?

En utilisant une boucle.

Tu entends quoi par utiliser une boucle ?

pour un tableau aucun soucis, on accède à l'élément i par tab[i] puisque tous les éléments sont stockés de façon contigüe.

mais pour une liste chaînée je vois pas comment une boucle permet de faire ça.
Ou plutôt, je ne vos pas sur quoi doit agir cette boucle...

Citation:

---

Envoyé par Von22

Tu entends quoi par utiliser une boucle ?

pour un tableau aucun soucis, on accède à l'élément i par tab[i] puisque tous les éléments sont stockés de façon contigüe.

mais pour une liste chaînée je vois pas comment une boucle permet de faire ça.
Ou plutôt, je ne vos pas sur quoi doit agir cette boucle...

---

Ben tu récupères un pointeur "p" qui pointe donc sur un élément de la liste (le premier ou un autre ça n'a pas d'importance)
1) tu affiches le contenu de cet élément
2) tu regardes si "p->next" n'est pas nul et si c'est le cas tu affectes "p->next" à "p" et tu retournes en "1" => c'est la boucle (bien entendu quand tu crées un nouvel élément pour ta liste tu mets "NULL" dans le membre "next" de ce nouvel élément quitte à le modifier ensuite lorsque cet élément sera inséré au milieu des autres ; comme ça tu es certain que le dernier élément de ta liste aura bien ce "NULL" que tu cherches en "2")

Petit détail: on n'utilise une liste chaînée que si on a besoin d'insérer des éléments au milieu (par exemple parce qu'ils sont dans un certain ordre qu'on désire conserver). Si on n'a pas besoin de cette possibilité, alors vaut mieux utiliser un tableau dynamique (alloué puis réalloué quand on a besoin de l'agrandir)

Autre détail => il peut être utile aussi de créer une structure pour y ranger "tete", "p" et "q". Cela permet d'y mettre d'autres infos utiles (comme par exemple le nombre d'éléments, l'adresse du dernier, etc...). Ensuite, chaque fonction qui a besoin de manipuler la liste reçoit un pointeur sur cette structure et grace à ce pointeur ladite fonction peut accéder à toutes les infos et tous les outils de la liste...

Ah au temps pour moi.

Est ce quelque chose de ce genre conviendrait pour insérer un élément?

Code:

---

1 2 3 4 5 6 7 8 9 10 11

p=(node)*malloc(sizeof(node)); p->info=... ; q=tete; while(q->info!=...){   q=q->next;   } p->next=q->next; q->next=p; ...

---

Citation:

---

Envoyé par Von22

Ah au temps pour moi.

Est ce quelque chose de ce genre conviendrait pour insérer un élément?

Code:

---

1 2 3 4 5 6 7 8 9 10 11

p=(node*)malloc(sizeof(node)); p->info=... ; q=tete; while(q->info!=...){ q=q->next; } p->next=q->next; q->next=p; ...

---

---

Exactement ça. T'as fait une erreur sur le cast qui est d'ailleurs inutile mais sinon c'est bon. Ensuite on préfère découper cet algo en deux fonctions
1) fonction de création (qui alloue et remplit le contenu)
2) fonction d'insertion (qui se charge d'insérer là où il faut)
Ca rend les choses plus modulaires (les règles d'insertion peuvent changer par exemple...)

ok ok.
En tout cas merci beaucoup!

Citation:

---

Envoyé par Von22

ok ok.
En tout cas merci beaucoup!

---

Gaffe quand-même à ton "while(q->info != ...)". Si la condition n'est jamais trouvée, tu balayes toute ta liste, ton pointeur "q" finit par recevoir "NULL" (fin de la liste") et tu vas taper dans "q->info" => Plantation de bug !!!

Si t'es sûr que la condition est trouvée ça va, sinon vaut mieux y rajouter un test sur q->next => "while (q->info != ... && q->next != NULL)"