cast et listes chaînées

Version imprimable

Bonjour,

J'ai quelques difficultés à comprendre le programme d'exemple de listes chaînées fourni par mon professeur.
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 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include <stdio.h> #include <stdlib.h> typedef struct liste { struct liste *suivant; int valeur; } LISTE; void affichage (LISTE *debut) { LISTE *p; p = debut; while (p != NULL) { printf("%d\n", p->valeur); p = p->suivant; } } LISTE *insertion (int valeur, LISTE *p) { LISTE *nouveau; nouveau = malloc(sizeof(LISTE));// allocation nouvel élément p->suivant = nouveau; // chaînage à partir du précédent nouveau->suivant = NULL; // pas encore de successeur nouveau->valeur = valeur; // stockage de la valeur return nouveau; } int main () { int i, n; LISTE *tete, *p; printf ("Taille de la liste: "); scanf ("%d", &n); p = (LISTE *) &tete; for (i=1; i<=n; i++) p = insertion(i*i, p); affichage(tete); }
Le principe de la liste chaînée en lui même ne me pose pas de problèmes, je n'arrive simplement pas à comprendre le cast (si c'en est bien un) dans le main.

Code:

p = (LISTE *) &tete;

Je ne trouve pas son utilisation ici, très intuitive.

Il s'agit, si je ne m'abuse, d'attribuer à p de type LISTE* l'adresse de tete également de type LISTE*. L'adresse de tete est logiquement de type LISTE** d'où la présence du cast, qui va permettre cette affectation.
J'arrive bien à concevoir ce qu'il se passe au niveau de p, mais j'ai beaucoup plus de mal en revanche au niveau de *p.

*p doit être de type LISTE, et donc être une structure comportant deux éléments, p->suivant et p->valeur.
Or p pointe désormais sur tete qui est un simple pointeur et non une structure... la valeur de tete va-t-elle se placer dans p->suivant?
A quoi est égal p->valeur?

Pourquoi ne pas tout simplement initialiser p à p = tete?

Merci d'avance pour vos réponses!

C'est une absurdité totale qui masque une erreur de programmation :roll:
Pour pouvoir faire ça correctement il aurait fallu déclarer p en tant que LISTE**.

J'ai modifié ton code pour que ce soit correct (il manque une fonction pour libérer tout ce qui a été alloué avec malloc) :
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 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include <stdio.h> #include <stdlib.h> typedef struct liste { struct liste *suivant; int valeur; } LISTE; void affichage (LISTE *debut) { LISTE *p; p = debut; while (p != NULL) { printf("%d\n", p->valeur); p = p->suivant; } } LISTE *insertion (int valeur, LISTE **p) { LISTE *nouveau; nouveau = malloc(sizeof(LISTE)); // allocation nouvel élément if (*p == NULL) { *p = nouveau; nouveau->suivant = NULL; } else nouveau->suivant = *p; nouveau->valeur = valeur; // stockage de la valeur return nouveau; } int main (void) { int i, n; LISTE *tete = NULL, **p = NULL; printf ("Taille de la liste: "); scanf ("%d", &n); p = &tete; for (i = 1; i <= n; i++) *p = insertion(i*i, p); affichage(tete); return 0; }
Si l'ajout n'est pas celui que tu voulais il faut que tu modifies la fonction pour insérer en fin de liste et pas en début ;)

Merci pour ces explications, ça me paraît déjà plus clair, mais quelques zones d'ombre demeurent.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 LISTE *insertion (int valeur, LISTE **p) { LISTE *nouveau; nouveau = malloc(sizeof(LISTE)); // allocation nouvel élément if (*p == NULL) { *p = nouveau; nouveau->suivant = NULL; } else nouveau->suivant = *p; nouveau->valeur = valeur; // stockage de la valeur return nouveau;
Pourquoi avoir recours à un double pointeur LISTE** ici alors qu'on return nouveau?
Ne s'agit-il pas à présent d'une pile puisque tu chaînes le nouvel élément avec le précédent, et non le précédent avec le nouveau?

En effet moi j'aurais mis :
Code:

1 2 3 4 5 6 7 8 9 else { p->suivant = nouveau; nouveau->suivant = NULL; } nouveau->valeur = valeur; // stockage de la valeur return nouveau;
Qu'en penses-tu?

11/01/2010, 12h59
diogene
Citation:

Envoyé par onodi

....
Le principe de la liste chaînée en lui même ne me pose pas de problèmes, je n'arrive simplement pas à comprendre le cast (si c'en est bien un) dans le main.

Code:

p = (LISTE *) &tete;

Je ne trouve pas son utilisation ici, très intuitive.

Il s'agit, si je ne m'abuse, d'attribuer à p de type LISTE* l'adresse de tete également de type LISTE*. L'adresse de tete est logiquement de type LISTE** d'où la présence du cast, qui va permettre cette affectation.
J'arrive bien à concevoir ce qu'il se passe au niveau de p, mais j'ai beaucoup plus de mal en revanche au niveau de *p.
....

Code tenant plus de la bidouille que de la programmation.

Pourquoi ça marche ?
A la première entrée dans insertion(), p est l'adresse du pointeur tete, présenté (artificiellement à cause de ce cast) comme l'adresse d'une structure LISTE hypothétique qui en fait n'existe pas. p->suivant étant le premier élément de cette structure LISTE hypothétique a pour adresse la même que celle de la structure Liste hypothétique et donc son adresse est bien celle du pointeur tete.
Pour faire planter le programme, il suffit sans changer autrement une seule ligne de code de modifier l'ordre des champs de LISTE de façon à ce que suivant ne soit plus le premier :
Code:

1 2 3 4 5 typedef struct liste { int valeur; struct liste *suivant; } LISTE;
Un tel "style" de programmation n'est pas à mon sens admissible même si on aboutit à un code d'apparence plus simple que par un traitement sérieux.

@ Pouet_forever :
Ton code répond à un autre problème puisqu'il réalise une insertion en tête de liste et non en queue.
11/01/2010, 13h58
onodi

Merci Diogène, c'est précisément l'explication que j'attendais.

C'était plus de la curiosité finalement, comprendre dans le détail ce qui se passait à la première entrée dans la fonction insertion().

J'avais bien le sentiment de toute façon que ça relevait plus de la bidouille que d'un code propre (ce qui, au passage est regrettable quand on sait que ça figure dans un poly de cours...)

Mon problème est résolu, merci à vous deux.