Struct liste chainée et pointeur

Bonsoir,

J'ai un petit problème de compréhension sur une structure :

Code:

---

1 2 3 4 5 6 7 8 9 10

typedef struct EPOINT EPOINT;   struct EPOINT { double x; double y; struct EPOINT *next; };   typedef EPOINT *PLISTE;

---

Alors je connais le principe des listes chainées, mais c'est juste au niveau des "typedef" que j'ai du mal à comprendre.

Quelle est la différence entre "typedef struct EPOINT EPOINT; " et "typedef EPOINT *PLISTE;" ?

Est-ce qu'avec PLISTE je peux accéder aux différents éléments avec des indices comme un tableau ?

Merci.

Bonjour,

Citation:

---

Envoyé par hotman1313

Alors je connais le principe des listes chainées, mais c'est juste au niveau des "typedef" que j'ai du mal à comprendre.

Quelle est la différence entre "typedef struct EPOINT EPOINT; " et "typedef EPOINT *PLISTE;" ?

---

Il faut d'abord savoir qu'une liste chaînée n'est pas un type natif en soi, mais une structure de données, c'est-à-dire une manière de les organiser, au même titre qu'une pile ou un buffer.

En fait, c'est plus clair présenté ainsi :

Code:

---

1 2	typedef struct EPOINT EPOINT; typedef EPOINT * PLISTE;

---

Autrement dit, « struct EPOINT » est renommé (ou plutôt bénéficie d'un alias) en « EPOINT » tout court, puis « PLISTE » devient équivalent à « EPOINT * ». Ça veut dire que le pointeur est caché derrière son alias mais qu'il existe toujours en tant que tel.

C'est une très mauvaise pratique mais elle est malheureusement extrêmement répandue dans les cours d'algorithmique quand on étudie ces structures là.

Citation:

---

Est-ce qu'avec PLISTE je peux accéder aux différents éléments avec des indices comme un tableau ?

---

Non. C'est d'ailleurs le principe de la liste chaînée, (sauf foncteurs et assimilés dans d'autres langages). Chaque élément (les maillons de la chaîne) contient une donnée utile et une référence vers le prochain maillon (en C, sous forme de pointeur). Ça te permet d'insérer et de supprimer très facilement des éléments, voire des morceaux de chaîne entiers mais en contrepartie, tu perds l'accès aléatoire : il redevient séquentiel et tu es obligé de parcourir la liste pour retrouver un élément donné. Tu peux cependant optimiser la chose en conservant les références vers les maillons utiles.

J'ajoute qu'il faut bien comprendre que les typedef ne correspondent pas à des instructions exécutables et qu'il n'ont aucune incidence sur le code généré. C'est une fonctionnalité offerte au programmeur pour s'éviter de retaper des noms de types fastidieux et/ou pour améliorer la lisibilité de son code.

Citation:

---

Envoyé par Obsidian

puis « PLISTE » devient équivalent à « EPOINT * ». Ça veut dire que le pointeur est caché derrière son alias mais qu'il existe toujours en tant que tel.

C'est une très mauvaise pratique mais elle est malheureusement extrêmement répandue dans les cours d'algorithmique

---

+1 c'est vraiment dégueulasse.. :no:

Bien, merci pour ta réponse très clair.

Dans le header qu'on nous a donné, il y a une déclaration de fonction assez ambigüe :

Code:

---

1 2 3 4 5 6 7

/*  * Initialisation avec un point  * INPUT: coordonnees du point  * OUTPUT: pointeur sur liste creee  */ PLISTE init_liste(double xx, double yy);

---

D'après le commentaire, la fonction doit retournée un pointeur. Soit l'étoile a été oubliée, soit j'ai mal compris.
Du coup, voici mon code tel que je l'ai compris :

Code:

---

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

/*  * Initialisation avec un point  * INPUT: coordonnees du point  * OUTPUT: pointeur sur liste creee  */ PLISTE *init_liste(double xx, double yy){ //inits PLISTE *uneListeP; EPOINT *p;   //allocation uneListeP = malloc(sizeof(PLISTE)); p = create_point(xx, yy, NULL);   //affectations uneListeP[0] = p;   return uneListeP; }

---

J'ai également ajouté l'étoile dans le header. En effet, cela me paraissait plus logique, mais je pense avoir mal compris.

Merci.

typedef EPOINT *PLISTE; : cette ligne informe l'analyseur lexical que chaque fois qu'il rencontre le terme PLISTE, il doit le remplacer par EPOINT * (pas EPOINT). Tu peux voir cela comme un « #define amélioré ». C'est complètement équivalent à :

• typedef EPOINT* PLISTE;
• typedef EPOINT * PLISTE;
• typedef EPOINT <whitespace> * <moar whitespace..> PLISTE ;
• etc...

Ici PLISTE « implique » donc déjà l'astérisque, c'est un type pointeur. Si tu ajoutes une astérisque, tu transformes ce type en EPOINT **.

Cette incompréhension est ce pourquoi nous écrivions avec Obsidian qu'il ne faut jamais définir d'alias sur un type pointeur, en particulier lorsque l'on s'adresse à des débutants.

Merci je comprends mieux.
Oui j'imagine que cette syntaxe n'est pas bonne, mais elle nous a été donnée tel quelle est.

Je passe en résolu. ;)

La syntaxe est bonne, puisque ca compile. Par contre, c'est un piège pour l'humain qui doit développer, car il y a une étoile cachée

D'un autre côté, ça peut rester intéressant pour donner un type opaque à l'utilisateur (ex: tous les Hxxxxx de Windows).
Mais en revenant du premier côté, on peut très bien faire ça sans supprimer le pointeur (ex: les FILE* du C).