Listes chaînées - initialisation d'une liste

Bonjour,

Lorsque j'initialise une liste chaînée, pourquoi dois-je utiliser un double pointeur dans la fonction suivant ?

Fonction :

Code:

---

1 2 3

void initListe (typeElt **ptPrem) { *ptPrem = NULL; }

---

Exemple d'utilisation de la fonction :

Code:

---

initListe (&premier);

---

Merci pour votre aide.

Bonjour,

Parce que la variable que tu veux initialiser à NULL est un pointeur. Il faut donc que tu passes l'adresse de ce pointeur pour que l'on puisse écrire dedans. Et par conséquent, cette adresse est… « un pointeur sur un pointeur ».

Merci beaucoup pour la réponse et pour votre aide. Autre question, lorsque j'écris une fonction de création d'un élément de ce type de structure :

Code:

---

1 2 3 4

typedef struct elt { typeDonnee val; struct elt *suivant; } typeElt;

---

Pourquoi dois-je mettre un astérisque devant l'intitulé de la fonction "creerElt" comme ceci ? :

Code:

---

typeElt *creerElt(typeDonnee valeur);

---

Citation:

---

Envoyé par wallace27

Pourquoi dois-je mettre un astérisque devant l'intitulé de la fonction "creerElt" comme ceci ? :

Code:

---

typeElt *creerElt(typeDonnee valeur);

---

---

Parce que l'astérisque s'applique en fait à ce qui précède et donne « typeElt * ». Ta fonction renvoie en fait un pointeur vers une instance de typeElt, probablement parce qu'elle a alloué elle-même l'espace avec malloc() et procédé ensuite à quelques initialisations pour que cette instance soit utilisable.

Ça ressemble aux questions d'un devoir. Est-ce le cas ?

Les question c'est moi qui me les crée et qui me les pose. Et c'est effectivement pour préparer un examen. Mille mercis pour votre aide. Merci de laisser le fil ouvert au cas où j'ai d'autres questions svp.

@wallace27: Je pense qu'il vaudrait mieux que tu passes ce sujet en résolu et que tu ouvres d'autres topics si tu as d'autres questions.

Pardon, mais voici une question de la même catégorie que la première.

Ici :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

void detruireElt(typeElt **ptPrem, typeElt *courant){ typeElt *elt;   if (courant == NULL) { elt = *ptPrem; *ptPrem = elt->suivant; } else { elt = courant->suivant; courant->suivant = elt->suivant; } free(elt); }

---

Est-ce qu'on peut considérer que "courant" soit l'équivalent du dernier élément de la liste ?

Citation:

---

Envoyé par wallace27

Pardon, mais voici une question de la même catégorie que la première.

Ici :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

void detruireElt(typeElt **ptPrem, typeElt *courant){ typeElt *elt;   if (courant == NULL) { elt = *ptPrem; *ptPrem = elt->suivant; } else { elt = courant->suivant; courant->suivant = elt->suivant; } free(elt); }

---

Est-ce qu'on peut considérer que "courant" soit l'équivalent du dernier élément de la liste ?

---

Non. courant pointe sur l'élément précédent celui à détruire. S'il est nul, c'est le premier élément de la liste qui est supprimé.
Il n'a donc rien à voir avec le dernier élément de la liste.

Est-ce que mon illustration de la première hypothèse selon laquelle courant est NULL est juste ?

Pièce jointe 168764



Et est-ce que mon illustration selon l'hypothèse où courant n'est pas NULL est juste ?


Pièce jointe 168770

Ces deux illustrations me semblent correctes à part un détail : pour le cas ou courant est NULL, il ne faudrait pas de flèche entre courant et un élément de la liste.

Citation:

---

Envoyé par wallace27

Lorsque j'initialise une liste chaînée, pourquoi dois-je utiliser un double pointeur dans la fonction suivant ?

Fonction :

Code:

---

1 2 3

void initListe (typeElt **ptPrem) { *ptPrem = NULL; }

---

Exemple d'utilisation de la fonction :

Code:

---

initListe (&premier);

---

---

Bonjour

Quand on manipule des listes chainées, il peut-être intéressant de créer un type pour la liste elle-même. Et accessoirement, nommer ses types "t_xxx" apporte le même avantage que le nommer "typeXXX" mais en plus court.
Exemple

Code:

---

1 2 3 4 5 6 7 8

typedef struct s_elt { typeDonnee val; struct s_elt *suivant; } t_elt;   typedef struct { t_elt *ptPremier; } t_liste;

---

Ca semble tout bête de créer un type ne contenant qu'un seul objet interne mais ça amène ensuite beaucoup d'avantages

1. les fonctions ayant besoin de modifier le premier élément n'ont plus besoin de recevoir un double pointeur. Un simple pointeur sur la liste permet d'accéder à son premier élément. On ne se bat plus avec ces étoiles à tout moment du code.
   
   Code:

   ---

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

   void initListe(t_liste *l) { l->ptPremier=NULL; }   int main() { t_liste liste; initListe(&liste); }   void detruireElt(t_liste *l, t_elt *courant){ t_elt *elt;   if (courant == NULL) { elt = l->ptPrem; l->ptPrem = elt->suivant; } else { elt = courant->suivant; if (elt) courant->suivant = elt->suivant; } free(elt); }

   ---

2. Si ensuite on veut rajouter d'autres éléments de gestion, comme par exemple le nombre d'éléments, un pointeur sur le dernier ou autre, suffit de le rajouter dans le type initial et toutes les fonctions y ont alors immédiatement accès.
   
   Code:

   ---

   1 2 3 4 5 6 7 8 9 10

   typedef struct { t_elt *ptPremier; size_t nbElem; } t_liste;   void initListe(t_liste *l) { l->ptPremier=NULL; l->nbElem=0; }

   ---

Est-ce que les schémas de cette fonction sont justes ? :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

void insereElt(typeElt **ptPrem, typeElt *courant, typeElt *nouveau) {   if (courant == NULL) { nouveau->suivant = *ptPrem; *ptPrem = nouveau; } else { nouveau->suivant = courant->suivant; courant->suivant = nouveau; } }

---

Pour l'insertion avec courant == NUL :

Pièce jointe 168804

Pour l'insertion avec courant non NULL :

Pièce jointe 168805

Oui
Mais perso je pense que tu devrais faire des schémas avec des éléments entiers, à mon avis tu gagnerais en lisibilité...

Exemple
La liste contient les maillons 0x10, 0x20, 0x30

• Maillon 0x10: Jean, 0x20
• Maillon 0x20: Paul, 0x30
• Maillon 0x30: Pierre, NULL
• (*ptPrem)=0x10

Et arrivée du maillon 0x40 (Luc)

Insertion avec courant=NULL

• nouveau->suivant=(*ptPrem)=0x10
• (*ptPrem)=nouveau=0x40

La liste contient maintenant les maillons 0x40, 0x10, 0x20, 0x30

• Maillon 0x40: Luc, 0x10
• Maillon 0x10: Jean, 0x20
• Maillon 0x20: Paul, 0x30
• Maillon 0x30: Pierre, NULL
• (*ptPrem)=0x40

Insertion avec courant=0x20 (le milieu)

• nouveau->suivant=courant->suivant=0x30
• courant->suivant=nouveau=0x40

La liste contient maintenant les maillons 0x10, 0x20, 0x40, 0x30

• Maillon 0x10: Jean, 0x20
• Maillon 0x20: Paul, 0x40
• Maillon 0x40: Luc, 0x30
• Maillon 0x30: Pierre, NULL
• (*ptPrem)=0x10

Dans insertion avec courant == NULL, je suis inquiet de voir que dans mon schéma, à la fin l'élément nouveau pointe en fait vers lui-même... Est-ce possible ? et est-ce juste ?

Citation:

---

Envoyé par wallace27

Dans insertion avec courant == NULL, je suis inquiet de voir que dans mon schéma, à la fin l'élément nouveau pointe en fait vers lui-même... Est-ce possible ? et est-ce juste ?

---

Dans le cas "courant == NULL", ton code écrit nouveau->suivant = *ptPrem;. Donc nouveau ne peut pas pointer vers lui-même. Et dans mon schéma ce n'est pas le cas...

Oui c'est vrai, merci pour la réponse.

Juste une petite chose, quelle est la différence entre un programme "compilable" et un programme "exécutable" et comment puis-je constater la différence avec par exemple Visual Studio ?

Un "programme" est compilable quand l'ensemble de son code source est légal au sens du traité normatif du C++
(ou plus simplement, au sens où le compilateur l'accepte)

Il est alors possible de le compiler en un programme (du binaire).

Ce programme est exécutable s'il est possible de l'exécuter sans qu'il se plante.
Un programme qui plante avant que l'utilisateur n'intervienne n'est pas "exécutable". S'il plante après, il n'est que buggé.

Bonjour,

Pour parcourir une liste chaînée du premier au dernier c'est facile, je fais :

Code:

---

1 2	while courant != NULL courant = courant->suivant

---

Mais comment faire pour parcourir cette même liste dans le sens inverse, c'est-à-dire du dernier (qui vaut NULL) au premier élément de la liste ?



Merci pour votre aide.

et bien, à chaque itération, tu reparcours tout, mais en te souvenant de l'adresse du dernier élément visité. Ainsi, quand celui-là sera le prochain, alors c'est que tu es arrivé.

C'est possible d'avoir un code qui exemplifie cela ?

Citation:

---

Envoyé par wallace27

Bonjour,

---

Non, une fois suffit. Tu es entré dns le forum comme tu entres dans une pièce, tu as dit bonjour en entrant comme quand tu entres dans une pièce, tu ne redis pas ensuite "bonjour" à chaque fois que tu interviens dans une discussion si ???

Citation:

---

Envoyé par wallace27

Pour parcourir une liste chaînée du premier au dernier c'est facile, je fais :

Code:

---

1 2	while courant != NULL courant = courant->suivant

---

---

Moui. Ou bien avec un for

Code:

---

1 2 3 4

for (courant=(*ptPrem); courant != NULL; courant=courant->suivant) { ... (traitement du courant)... }

---

Citation:

---

Envoyé par wallace27

Mais comment faire pour parcourir cette même liste dans le sens inverse, c'est-à-dire du dernier (qui vaut NULL) au premier élément de la liste ?

---

Tu rajoutes à chaque maillon un pointeur vers le précédent que tu gères dans l'insertion et la suppression. Et tu rajoutes à ton "t_liste" un pointeur vers le dernier élément. Ah zut, c'est vrai que tu n'as pas suivi mes conseils et que tu n'as pas créé de type dédié à la liste elle-même...:bug:

Dans ce qui m'est demandé à l'examen, je ne dois pas créer de liste dédiée.

Et bien, comment ferais-tu?

Tu sais:

• te mettre au début de la file.
• voir qui est le suivant.
• que NULL est le vide qui suit le dernier.
• changer de place vers un élément que tu connais.

Je t'ai répondu, mais je ne coderai pas.
Après tout, c'est ton exercice, pas le mien :mrgreen:

Montre nous ton code, et nous te corrigerons volontiers

Citation:

---

Envoyé par wallace27

Dans ce qui m'est demandé à l'examen, je ne dois pas créer de liste dédiée.

---

Ca m'étonne. C'est explicitement écrit ? Il est écrit textuellement "voici ce que vous devez utiliser et rien d'autre" ???
Il ne faut pas confondre "directives/aides/conseils" et "interdits". Si on te dit "vous pouvez faire ceci" rien n'interdit de faire "ceci+cela"...

Ceci dit tu peux très bien te passer du type "t_liste". Son rôle est d'embarquer dans une seule entité tous les outils dédiés à la gestion de la liste comme le pointeur sur le premier, le nombre d'éléments, le pointeur sur le dernier etc ce qui simplifie ensuite la manipulation (avec une seule variable tu as tous ces outils à disposition). Mais rien n'empêche d'avoir ces éléments de façon individuelle. Tu as créé une variable "ptPrem" contenant le premier élément de ta liste, rien ne t'interdit donc de créer une variable "ptDern" contenant le dernier élément, une variable "nbElem" contenant le nombre d'éléments etc. Simplement faudra ensuite penser à bien passer toutes ces variables aux fonctions de gestion (insertion/suppression/etc)...

Sinon ben c'est comme le dit Leternel. Tu places un drapeau sur le dernier élément et à chaque itération tu pars du début jusqu'à cet élément marqué en mémorisant bien entendu le courant et celui juste avant. Quand ton courant est arrivé à l'élément marqué du drapeau, tu affiches le précédent puis tu déplaces ton drapeau sur ce précédent et tu recommences la boucle. Et tu arrêtes tout ce micmac quand ton drapeau est arrivé au premier élément...

Un collègue me signale qu'il y a franchement mieux:

construire la liste inverse (en insérant en toujours en tête d'une autre liste), et parcourir celle-ci.

Oui c'est vrai, il faut "inverser" la direction que prennent les pointeurs d'un élément à l'autre de manière à ce qu'on parte du dernier, que le dernier pointe vers l'avant dernier, etc.

Merci en tout cas !