Liste chainée

Bonjour,

Dans ce code suivant, je ne comprends pas la ligne :

Code:

typedef element* llist;

.
Je ne comprends pas non plus, pourquoi on utilise struct dans la ligne de code

Code:

struct element *nxt;

Merci.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <stdlib.h> typedef struct element element; struct element { int val; struct element *nxt; }; typedef element* llist; int main(int argc, char **argv) { /* Déclarons 3 listes chaînées de façons différentes mais équivalentes */ llist ma_liste1 = NULL; element *ma_liste2 = NULL; struct element *ma_liste3 = NULL; return 0; }

Parce que c'est un code C et non C++. Quand tu déclares une struct element {}; tu déclares un type struct element et non un type element.
Après cette première ligne tu peux utiliser llist comme type pour faire référence à un struct element*.

Citation:

Envoyé par calito

Dans ce code suivant, je ne comprends pas la ligne :

Code:

typedef element* llist;

.

J'ajoute que ce que tu nous présentes est malheureusement une pratique aussi répandue que décriée : cacher un pointeur dans un typedef.

Presque toutes les écoles d'ingénieur, depuis au moins dix ans et probablement beaucoup plus, proposent un exercice similaire (listes chaînées en C avec « pseudo-typage » de la sorte, censée rendre la chose plus facilement abordable). À croire parfois que c'est imposé par la commission des titres…

Bref : typedef signifie « Type Definition » et sert officiellement à définir un nouveau type de donnée. En réalité, il s'agit plutôt de définir un alias sur un nom de type, généralement compliqué, pour s'y référer plus facilement.

Ce qu'expliquait Bousk au commentaire précédent est que les structures nommées du C permettent implicitement de faire de la programmation orientée objet et d'utiliser le concept de classe, ce que les programmeurs de tous horizons ont fait dès le départ. Pour définir puis ré-invoquer une structure en C, on écrit struct [nomdelastructure] (le nom est même facultatif, en fait, mais c'est compliqué de faire sans). De là, il est très tentant d'utiliser typedef pour définir cette structure comme un nom de type à part entière dans un formalisme orientée objet. C'est une pratique très répandue et cela a même été normalisé ensuite dans le C++.

Détail important : les structures disposent de leur propre namespace. Tout identifiant qui suit le mot-clé struct y sera automatiquement classé et n'entreront pas en conflit avec les identifiants déclarés au niveau global. Ainsi struct element et element peuvent tout-à-fait cohabiter et désigner des choses distinctes même si, en l'occurrence, le second est un alias du premier. C'est d'ailleurs ce qui nous permet de faire du renommage à la C++ comme expliqué ci-dessus.

Donc, désigner par element une structure qui donne le détail du contenu d'un élément de ta chaîne est une bonne chose en soi.

Ensuite, comme chaque élément contient une référence vers le suivant, cela forme automatiquement une liste, puisqu'on peut alors passer facilement d'un élément au suivant. Par conséquent, référencer une liste chaînée se fait exactement comme parcourir une chaîne de caractères : il suffit qu'on nous indique où se trouve le début.

Par contre (et c'est là que le bât blesse) il devient très tentant, dès lors, de définir un « pointeur vers un élément » (en principe le premier d'une liste, mais pas forcément) comme étant « une liste » à part entière. Et là où ça devient vicieux, c'est lorsqu'on inclut le pointeur « * » dans l'alias : il disparaît alors du reste du code MAIS le programmeur doit quand même se souvenir qu'il est là et il doit l'utiliser comme tel.

Citation:

Je ne comprends pas non plus, pourquoi on utilise struct dans la ligne de code

Code:

struct element *nxt;

Justement parce qu'au moment où cette ligne apparaît, le type struct element n'est pas encore complet puisque ce champ est déclaré au sein même de cette structure. Donc, en principe, on définit d'abord le type en entier, et seulement ensuite on lui adjoint un alias.

Mais le C reste suffisamment bien conçu pour te permettre de faire des déclarations partielles, entre autres pour les cas de références croisées (B référence A et A référence B). Et les typedef en bénéficient.