Discussion :

[Amnael]

Bonjour, j'ai grand besoin d'aide pour débugguer mon programme; si quelqun pouvait m'aider ce serait sympas; voilà les erreurs

arbre.c: In function ‘empile’:
arbre.c:72:5: error: dereferencing pointer to incomplete type
tmp->feuille = feuille;
^
arbre.c:73:5: error: dereferencing pointer to incomplete type
tmp->suivant = p;
^
arbre.c: In function ‘depile’:
arbre.c:79:21: error: dereferencing pointer to incomplete type
GRD *feuille = (*p)->feuille;
^
arbre.c:82:11: error: dereferencing pointer to incomplete type
*p = (*p)->suivant;
^
unit_test_itArbre.c: In function ‘triIteratifGRD’:
unit_test_itArbre.c:12:4: warning: assignment from incompatible pointer type [enabled by default]
a=(depile(&p));
^
unit_test_itArbre.c:17:9: error: incompatible types when assigning to type ‘struct unfeuille’ from type ‘struct unfeuille **’
(*a)=depile(&p);

Voici mes prototypes

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct unfeuille {
	int val;
	struct unfeuille *gauche;
	struct unfeuille *droite;
}feuille;
typedef struct unfeuille * GRD;
 
typedef struct elpile {
  GRD* feuille;
  struct elpile* suivant; //pointeur sur la feuille suivante
 }pile;
 
typedef struct pile* PILE;

A partir de ça, voici mon algo de tri itératif

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
void triIteratifGRD(GRD a)
{
	PILE p=initpile();
	while(!pilevide(p))
	{
		a=(depile(&p));
		if(estVideGRD(a))
		{
			if(!pilevide(p))
			{
				(*a)=depile(&p);
				printf("%d\n",(a)->val);
			}
		}
		else
		{
			p=empile(p,&((a)->gauche));
			p=empile(p,&(a));
			p=empile(p,&((a)->droite));
		}
	}
}

Ainsi que les fonctions pour empiler/depiler

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
PILE empile(PILE p, GRD *feuille)
{
	PILE tmp = malloc(sizeof(&tmp));
 
	if (tmp == NULL)
	{
		puts("pb memoire");
		exit(0);
	}
	tmp->feuille = feuille;
	tmp->suivant = p;
	return tmp;
}
 
GRD* depile(PILE *p)
{
	GRD *feuille = (*p)->feuille;
 
	PILE tmp = *p;
	*p = (*p)->suivant;
	free(tmp);
 
	return feuille;
}

Malheureusement je n'arrive toujours pas à compiler et je ne vois pas quelle solution adopter. Un tri de manière récursif est pourtant si simple

J'ai grand besoin d'aide là dessus; merci à tous !

[Sve@r]

Code :

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

PILE tmp = malloc(sizeof(&tmp));

Bonjour
T'es sûr de ta syntaxe ???

A part ça je te rappelle qu'on t'a déjà dit que c'était une mauvaise pratique de masquer les pointeurs derrière des types... surtout quand ensuite tu as quand-même des pointeurs sur ces types en question. Exemple dans la structure elpile, feuille est un pointeur sur un pointeur. Idem pour le paramètre p de la fonction depile(). Et donc là aussi j'ai un gros doute sur la réussite du truc (ne serait-ce que pour le relire j'ai dû faire vingt fois l'aller-retour)...

[Amnael]

Bonjour, merci pour ta réponse.

Oui je sais que c'est mal; malheureusement ça fait partie des exigences de tp à respecter donc...le tout c'est d'être conscient que c'est un pointeur.


Et non je suis pas sûr de ma syntaxe

[Sve@r]

Bonjour

Une fois par topic suffit. Comme dans la vraie vie quand tu discutes avec quelqu'un, tu ne répètes pas "bonjour" à chaque phrase... si ???

Oui je sais que c'est mal; malheureusement ça fait partie des exigences de tp à respecter donc...le tout c'est d'être conscient que c'est un pointeur.

Oui mais justement, la manipulation de listes et d'arbres nécessite des pointeurs sur les éléments, pas des pointeurs sur les pointeurs d'éléments. Va voir ton autre topic où j'expliquais la structure de liste et son utilité...

Et non je suis pas sûr de ma syntaxe

Bah, c'est juste un peu de logique. L'allocation de n éléments a besoin de n fois la taille d'un élément. Si tu as un <type> *pt, alors un élément est représenté par *pt. Donc tu alloueras n * sizeof(*pt). Ou bien n * sizeof(type) au choix...

[Médinoc]

Oui mais justement, la manipulation de listes et d'arbres nécessite des pointeurs sur les éléments, pas des pointeurs sur les pointeurs d'éléments.

Là, je ne suis pas d'accord. Une fonction d'insertion/ajout dans une liste simplement chaînée tend à très bien marcher avec des pointeurs de pointeur (y compris en argument, un pointeur sur le pointeur vers le premier élément):

Code C :

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
int InsertionEnTete(Chainon **ppPremier, Chainon *pNouveau)
{
	assert(ppPremier != NULL);
	if(pNouveau == NULL || pNouveau->pSuivant!=NULL)
		return -1;
	pNouveau->pSuivant = *ppPremier;
	*ppPremier = pNouveau;
	return 0;
}
 
int InsertionEnQueue(Chainon **ppPremier, Chainon *pNouveau)
{
	Chainon **ppCourant;
	assert(ppPremier != NULL);
	if(pNouveau == NULL || pNouveau->pSuivant!=NULL)
		return -1;
	for(ppCourant=ppPremier ; *ppCourant!=NULL ; ppCourant = &((*ppCourant)->pSuivant))
	{ }
	assert(*ppCourant == NULL);
	*ppCourant = pNouveau;
	return 0;
}

[Sve@r]

Là, je ne suis pas d'accord. Une fonction d'insertion/ajout dans une liste simplement chaînée tend à très bien marcher avec des pointeurs de pointeur (y compris en argument, un pointeur sur le pointeur vers le premier élément):

Pas lorsque tu as une structure dédiée à la manipulation de la liste elle-même. Cette structure contient un pointeur sur le premier élément et la fonction d'insertion reçoit un pointeur sur cette structure. Elle a donc tout loisir de modifier le premier élément sans pour cela recevoir l'adresse de ce pointeur...

Code c :

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

1
2
3
4
5
6
7
8
typedef struct s_elem {
	char nom[20];
	struct s_elem *pSuivant;
} t_elem;
 
typedef struct {
	t_elem *ppPremier;
} t_liste;

Code C :

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
int InsertionEnTete(Chainon **ppPremier, Chainon *pNouveau)
{
	assert(ppPremier != NULL);
	if(pNouveau == NULL || pNouveau->pSuivant!=NULL)
		return -1;
	pNouveau->pSuivant = *ppPremier;
	*ppPremier = pNouveau;
	return 0;
}
 
int InsertionEnQueue(Chainon **ppPremier, Chainon *pNouveau)
{
	Chainon **ppCourant;
	assert(ppPremier != NULL);
	if(pNouveau == NULL || pNouveau->pSuivant!=NULL)
		return -1;
	for(ppCourant=ppPremier ; *ppCourant!=NULL ; ppCourant = &((*ppCourant)->pSuivant))
	{ }
	assert(*ppCourant == NULL);
	*ppCourant = pNouveau;
	return 0;
}

Code c :

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
int InsertionEnTete(t_liste *liste, t_elem *pNouveau)
{
	assert (liste != NULL);
	if (pNouveau == NULL || pNouveau->pSuivant!=NULL) return -1;
	pNouveau->pSuivant = ppPremier;
	liste->ppPremier = pNouveau;
	return 0;
}
 
int InsertionEnQueue(t_liste *liste, t_elem *pNouveau)
{
	t_elem *ppCourant;
	assert (liste != NULL);
	if (pNouveau == NULL || pNouveau->pSuivant != NULL) return -1;
	if (liste->ppPremier == NULL)
	{
		liste->ppPremier=pNouveau;
		return 0;
	}
	for (ppCourant=liste->ppPremier ; ppCourant->pSuivant != NULL ; ppCourant = ppCourant->pSuivant);
	assert (ppCourant->pSuivant == NULL);
	ppCourant->pSuivant = pNouveau;
	return 0;
}

N'est-ce pas plus lisible que ce &((*ppCourant)->pSuivant) ??? Sans compter que tu peux rajouter différents éléments de gestion dans t_liste (nb d'éléments, pointeur vers le dernier, etc).

Là où j'ai mal regardé effectivement, c'est que je croyais avoir vu un équivalent de cette structure de liste dans les prototypes d'Amnael mais je viens de revoir son code et il n'en a pas créé. Donc effectivement sans ça lui il a besoin de passer un pointeur de pointeur s'il veut modifier son pointeur premier...

[Médinoc]

Pourquoi préfixes-tu par pp des pointeurs à un seul niveau?

Ignorant ça, la raison pour laquelle je préfère ma méthode est que je n'ai pas à faire de cas séparé pour l'ajout en queue du premier élément. Ou pour l'insertion avant n'importe quel élément.

N'est-ce pas plus lisible que ce &((*ppCourant)->pSuivant) ???

Probablement, pour être honnête. C'est pourquoi le plus souvent, j'en fais une fonction:

Code C :

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

1
2
3
4
5
6
7
8
9
10
t_elem ** GetPtrSuiv(t_elem **ppElem)
{
	if(ppElem == NULL || *ppElem == NULL)
		return NULL;
	{
		t_elem *pElem = *ppElem;
		t_elem **ppSuivant = &(pElem->pSuivant); //Il me semble que les parenthèses ne sont pas nécessaires, mais je trouve qu'ici elles rendent plus lisible
		return ppSuivant;
	}
}

Ce genre de parcours est aussi très utile pour supprimer un ou plusieurs éléments de la liste.

[Sve@r]

Pourquoi préfixes-tu par pp des pointeurs à un seul niveau?

J'ai bêtement recopié ta fonction puis l'ai adaptée à mes structures sans réfléchir au sens de "pp"...

Ignorant ça, la raison pour laquelle je préfère ma méthode est que je n'ai pas à faire de cas séparé pour l'ajout en queue du premier élément. Ou pour l'insertion avant n'importe quel élément.

Rien n'interdit toutefois un double pointeur de travail dans la fonction

Code c :

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

1
2
3
4
5
6
7
8
9
10
int InsertionEnQueue(t_liste *pListe, t_elem *pNouveau)
{
	t_elem **ppCourant;
	assert(pListe != NULL);
	if(pNouveau == NULL || pNouveau->pSuivant!=NULL) return -1;
	for (ppCourant=&pListe->pPremier ; *ppCourant!=NULL ; ppCourant = &((*ppCourant)->pSuivant));
	assert(*ppCourant == NULL);
	*ppCourant = pNouveau;
	return 0;
}

Je n'ai rien contre le double pointeur mais en fait ce que je trouve dommage, c'est de se dire "une liste c'est juste un pointeur vers le premier" alors que ça peut être beaucoup plus que cela. Ca peut être aussi un pointeur vers le premier plus un autre vers le dernier; ça peut-être aussi en plus le nombre d'éléments; ça peut-être aussi en plus un pointeur vers une fonction de callback pour trier deux éléments, bref plein de possibilités. D'où ma fameuse structure "t_liste" qui embarque bien évidemment le premier mais qui laisse le champ libre à tout le reste si on veut faire évoluer. Un petit pas vers l'objet en somme. Je dis souvent "les chemises on peut les tenir par le col mais c'est mieux si on les met sur un cintre"...

Et (est-ce un but inconscient ou juste une simple conséquence ?), on en revient à ma toute première phrase qui a déclenché cet intéressant débat, fatalement la fonction qui insère un élément n'a plus besoin de recevoir un double pointeur sur l'adresse du premier mais un simple pointeur sur la liste. Surtout si on replace cette discussion dans le contexte du code d'origine qui tente de masquer les pointeurs derrière des types mais qui en laisse tout de même apparaitre certains ce qui devient encore pire question compréhension ("ah oui, GRD c'est un pointeur donc GRD *feuille, malgré sa simple étoile, c'est un pointeur sur un pointeur..." => horrible !!!)...

[Médinoc]

Rien n'interdit toutefois un double pointeur de travail dans la fonction
<snip>

Je n'ai rien contre le double pointeur mais en fait ce que je trouve dommage, c'est de se dire "une liste c'est juste un pointeur vers le premier" alors que ça peut être beaucoup plus que cela. Ca peut être aussi un pointeur vers le premier plus un autre vers le dernier; ça peut-être aussi en plus le nombre d'éléments; ça peut-être aussi en plus un pointeur vers une fonction de callback pour trier deux éléments, bref plein de possibilités. D'où ma fameuse structure "t_liste" qui embarque bien évidemment le premier mais qui laisse le champ libre à tout le reste si on veut faire évoluer. Un petit pas vers l'objet en somme. Je dis souvent "les chemises on peut les tenir par le col mais c'est mieux si on les met sur un cintre"...

Là on en revient plus à ce que j'ai l'habitude de faire. Une structure liste, et des fonctions qui utilisent en interne des double pointeurs.

Surtout si on replace cette discussion dans le contexte du code d'origine qui tente de masquer les pointeurs derrière des types mais qui en laisse tout de même apparaitre certains ce qui devient encore pire question compréhension ("ah oui, GRD c'est un pointeur donc GRD *feuille, malgré sa simple étoile, c'est un pointeur sur un pointeur..." => horrible !!!)...

Tout à fait d'accord.