Discussion :

[onodi]

Bonjour,

J'ai quelques difficultés à comprendre le programme d'exemple de listes chaînées fourni par mon professeur.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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!

[Pouet_forever]

C'est une absurdité totale qui masque une erreur de programmation
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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[onodi]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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?

[diogene]

....
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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[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.