Discussion :

[guipe]

Bonjour,j'ai trouvé un paragraphe d'explications sur les listes chainées,cependant je n'arrive pas à modéliser le fonctionnement dans ma tête,notamment pour l'ajout d'un premier élément.

Voici le paragraphe :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
Ajout d'un premier élément

Une fois la structure et les pointeurs définis, il est possible d'ajouter un premier maillon à la liste chaînée, puis de l'affecter au pointeur Tete. Pour cela il est nécessaire :

d'allouer la mémoire nécessaire au nouveau maillon grâce à la fonction malloc, selon la syntaxe suivante :
Nouveau = (Liste*)malloc(sizeof(struct Liste));
d'assigner au champ « pointeur » du nouveau maillon, la valeur du pointeur vers le maillon de tête :
Nouveau->pSuivant = Tete;
définir le nouveau maillon comme maillon de tête :
Tete = Nouveau;

L'allocation dynamique de mémoire je la comprends,ce que je n'arrive pas à comprendre c'est pourquoi par exemple on doit faire pointer le nouveau maillon vers le maillon de tête et pourquoi ensuite on fait Tete=Nouveau ?

Si une personne arrivait à me l'expliquer avec un petit schéma ou avec des termes plus faciles ce serait super.Merci beaucoup !

[jeroman]

Salut

Tu peux trouver un cours de listes chainées ici : http://chgi.developpez.com/pile/

[Invité]

Bonjour,
Rien de tel qu'un petit échange.
Le principe d'une liste chainée simple est qu'un élément de la liste possède au moins 2 valeurs
1- l'information sur l'élément lui-même
2- un pointeur sur l'élément suivant.
L'information sur l'élément lui-même peut être n'importe quoi, par exemple un pointeur sur une structure qui décrit l'élément.
L'élément suivant est forcément du type "élément". S'il n'y a pas de suivant, parce que c'est le dernier et UNIQUEMENT dans ce cas là, le pointeur est NULL.

Lorsqu'on insère le premier élément dans la liste, le pointeur "suiv" est mis à NULL. A partir de ce moment quel est le premier élément ?, c'est à dire quel est celui qui servira à parcourir la liste depuis de début, justement celui qu'on vient de créer, donc, on le mémorise soigneusement.

Il faut savoir qu'une liste peut être parcourue dans le sens où on a inséré les différents éléments, ou dans le sens inverse Dans le cas que vous décrivez, la liste sera parcourue dans le même sens que vous l'avez créée. Mais on peut aussi la parcourir dans le sens inverse. Dans ce cas, le premier élément à conserver pour parcourir la liste est le dernier inséré. Mais gardez ce paragraphe pour plus tard.

[diogene]

Si une personne arrivait à me l'expliquer avec un petit schéma

Voici un schéma expliquant au fur et à mesure de l'exécution du code la situation en mémoire (j'ai numéroté les éléments pour bien les différencier) :
Au départ, la liste est vide :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

struct Liste * Tete --> NULL

insertion du premier élément :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Nouveau = malloc(sizeof(struct Liste))
      Tete --> NULL
                ----------
               | psuivant |--> ???
   Nouveau --> |  ..1..   |
                ----------

Nouveau->pSuivant = Tete;
       Tete -->NULL
                ----------
               | psuivant |--> NULL
   Nouveau --> |  ..1..   |
                ----------

Tete = Nouveau;
                ----------
       Tete -->| psuivant |--> NULL
               |  ..1..   |
                ----------

Insertion du suivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Nouveau = malloc(sizeof(struct Liste));
                ----------
       Tete -->| psuivant |--> NULL
               |  ..1..   |
                ----------
                ----------
               | psuivant |--> ???
   Nouveau --> |  ..2..   |
                ----------

Nouveau->pSuivant = Tete;
                ----------
       Tete -->| psuivant |--> NULL
               |  ..1..   |<-
                ----------   |
                ----------   |
               | psuivant |--
   Nouveau --> |  ..2..   | 
                ----------

Tete = Nouveau;
                ----------
               | psuivant |--> NULL
               |  ..1..   |<-
                ----------   |
                ----------   |
               | psuivant |--
      Tete --> |  ..2..   | 
                ----------

etc...

[guipe]

Merci beaucoup !

[SofEvans]

Comme quoi l'ASCII art permet de faire des merveilles.

[Invité]

En choisissant bien sa table de caractère aussi.