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 ?