Discussion :

[guipe]

Bonjour dans le cadre d'un programme je dois réaliser un tableau de pointeur vers une structure pile.

Je définis donc ma structure pile et un pointeur vers cette structure.

J'ai créé une fonction afin d'initialiser mon tableau.

Cependant à chaque fois que je lance mon programme, j'ai une erreur qui est la suivante:

Code :

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

1
2
3
4
5
Invalid write of size 8
==2296==    at 0x401D22: init_pile (fc.c:17)
==2296==    by 0x402271: forwardChecking (fc.c:192)
==2296==    by 0x4007AF: main (main.c:9)
==2296==  Address 0x0 is not stack'd, malloc'd or (recently) free'd

J'ai souligné la ligne correspondante dans le code.
Pourtant il me semble bien n'avoir oublié aucun malloc.
Enfin j'espère que vous pourrez m'aider.

Voici le code:


Ma structure pile :

Code :

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

1
2
3
4
5
typedef struct 
{
	liste* domaines;
	int* instanciation;
} *pile;

Ma fonction d'initialisation:

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
void init_pile(int n, pile* p, int taille)
{
	int i,j;
	
	p= (pile*) malloc(taille*sizeof(pile));
	for (i=0; i< taille; i++)
	{
			p[i] = NULL;
	}
	
	
	for(i=0; i<taille; i++)
	{
		p[i]->domaines= (liste*)malloc(n*sizeof(liste));
		for (j=0; j< n; j++)
		{
			p[i]->domaines[j] = NULL;
		}
		p[i]->instanciation = (int*) malloc(n*sizeof(int));
		for (j=0; j< n; j++)
		{
			p[i]->instanciation[j] = -1;
		}
	}

}

Appel à la fonction:

Code :

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

1
2
3
4
 
 
pile *p=NULL;
init_pile(csp->n_variables, p, 100);

[supersnail]

Bonjour,
Pourrais-tu nous mettre le code complet? (le bug peut provenir d'un autre bout du programme, que l'on ne voit pas...)

[guipe]

Structures:

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
typedef struct _liste_couple_int
{
	int val1, val2;
	struct _liste_couple_int* suiv;
} Couple;
typedef Couple* relation;
 
typedef struct _liste_int
{
	int val;
	int use;
	struct _liste_int* suiv;
} liste_int;
typedef liste_int* liste;
 
typedef struct 
{
	liste* domaines;
	int* instanciation;
} *pile;
 
typedef struct
{
	int n_variables;
	int* instanciation; 
	liste* domaines;
	relation** contraintes;
} CSP;

Fonctions:

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
#include "types.h"
#include "fonctions.h"
 
void init_pile(int n, pile* p, int taille)
{
	int i,j;
 
	p= (pile*) malloc(taille*sizeof(pile));
	for (i=0; i< taille; i++)
	{
			p[i] = NULL;
	}
 
	for(i=0; i<taille; i++)
	{
		p[i]->domaines= (liste*)malloc(n*sizeof(liste));
		for (j=0; j< n; j++)
		{
			p[i]->domaines[j] = NULL;
		}
		p[i]->instanciation = (int*) malloc(n*sizeof(int));
		for (j=0; j< n; j++)
		{
			p[i]->instanciation[j] = -1;
		}
	}
 
}
 
int var_precedente(int place, int* place_instanciation, int taille)
{
	int i;
	int var;
 
	for(i=0; i < taille; i++)
	{
		if(place_instanciation[i] == --place)
		{
			var = i;
			break;
		}
	}
	return var;	
}
 
int valeur_possible(int var1, int val1, int* instanciation, CSP* csp)
{
	int i=0;
	relation r,r2;
	int ok=1;
	int ins;
 
	while( (i < csp->n_variables) && ok)
	{
		if(i != var1 && csp->contraintes[var1][i] != NULL)
		{
			r= csp->contraintes[var1][i];
			r2= csp->contraintes[i][var1];
			while(r && ok)
			{
				if(r->val1 == val1)
				{
					if((ins = instanciation[i]) != -1)
					{
						while(!((r2->val2 == val1) && (r2->val1 == ins )))
						{
							r2=r2->suiv;
						}
						if(r2 == NULL)
							ok=-1;	
					}
					else
					{
						while(!(r2->val2 == val1))
						{
							r2=r2->suiv;
						}
						if(r2 == NULL)
							ok=-1;
					}
				}
				r=r->suiv;
			}
		}
		i++;
	}
	return ok;
}
 
int supprime_val_domaine(liste* tete, int val)
{
 
	while( (*tete != NULL) && ((*tete)->val != val))
		*tete= (*tete)->suiv;
 
	if( (*tete == NULL) )
		return -1;
	else
	{
		(*tete)->val = -1; //la valeur du domaine est mise à -1(annulée)
		return 1;
	}
 
}
 
void copyList(liste cpy, liste tab)
{
	while(tab)
	{
		ajout_liste(&(cpy), tab->val);
		tab = tab -> suiv;
		cpy = cpy->suiv;
	}
}
 
void copyTab(liste* cpy, liste* tab, int min, int max)
{
	int i;
 
	for (i = min; i < max; i++)
	{
		while(tab[i])
		{
			ajout_liste(&(cpy[i]), tab[i]->val);
			//printf("%d",cpy[i]->val);
			cpy[i] = cpy[i] -> suiv;
			tab[i] = tab[i] -> suiv;
		}
	}
}
void copyTab2(int* cpy, int* tab, int min, int max)
{
	int i;
 
	for (i = min; i < max; i++)
		cpy[i] = tab[i];
}
 
int taille_domaine(liste domaine)
{
	int taille=0;
	while(domaine)
	{
		taille++;
		domaine = domaine-> suiv;
	}
	return taille;
}
 
int MinDomain(CSP* csp, int* marquage)
{
	int min= 1000;
	int tmp;
	int var;
	liste l;
	int i;
 
	if(csp->n_variables == 0)
	{
		perror("Aucune variable à choisir");
		return -1;
	}
	else
	{
		for(i=0; i< csp-> n_variables; i++)
		{
			l = csp -> domaines[i];
			tmp = taille_domaine(l);
			if( tmp < min && ! marquage[i])
			{
				min = tmp;
				var = i;
			}
		}
		marquage[var]=1;
		return var;
	}	
}
 
void forwardChecking(CSP* csp)
{
	pile *p=NULL;
	liste l;
	relation r;
	int i;
	int var_instanciees=0;
	int var_cour=0;
	int version=0;
	int ok,ok2;
 
	init_pile(csp->n_variables, p, 100);
	copyTab(p[version]->domaines, csp->domaines, 0, csp->n_variables);
 
	while(var_instanciees < csp->n_variables)
	{
		l=p[version]->domaines[var_cour];
 
		/*if(l == NULL)
			printf("null");*/
 
		while(l)
		{
			printf("$%d$\n",l->val);
			l=l->suiv;
		}
 
		/*while(l && !valeur_possible(var_cour,l->val, p[version].instanciation, csp) && l->use != 1)
		{
			//printf("OK");
			l=l->suiv;
		}*/
 
		if(l != NULL && l->val != -1)
		{
			ok=0;
			l->use=1;
			p[version]->instanciation[var_cour]= l->val;
			for(i=0; i <csp->n_variables; i++)
			{
				if(var_cour != i && csp->contraintes[var_cour][i] != NULL)
				{
					r= csp->contraintes[i][var_cour];
					while(r)
					{
						if(r->val2 != l->val)
						{
							if(!ok)
							{
								version++;
								ok = 1;
							}
 
							copyList(p[version]->domaines[i], p[version-1]->domaines[i]);
							supprime_val_domaine(&(p[version]->domaines[i]), r->val1);
						}	
						r=r->suiv;	
					}
				}
			}	
			var_instanciees++;
			var_cour++;
			printf("var cour:%d",var_cour);
			if(var_instanciees == csp->n_variables)
			{
				printf("Oui");
				copyTab2(csp->instanciation, p[version]->instanciation, 0, csp->n_variables);
				break;
			}
		}
		else
		{
			if(var_cour > 0)
			{
				var_cour--;
				ok2=0;
				for(i=0; i<csp->n_variables; i++)
				{
					if(csp->contraintes[var_cour][i] != NULL)
					{
						if(!ok2)
						{
							version--;
							ok2 = 1;
						}
					}
				}
			}
			else
			{
				printf("Non");
				break;
			}
 
		}
 
	}
	printf("var instanciees:%d\n",var_instanciees);
}
 
/*void forwardCheckingMD(CSP* csp)
{
	pile p[100];
	liste l;
	relation r;
	int i;
	int var_instanciees=0;
	int var_cour;
	int version=1;
	int ok,ok2;
	int place=0;
	int place_instanciation[csp->n_variables];
	int marquage[csp-> n_variables];
 
	init_pile(csp->n_variables, p, 100);
	copyTab((p+version-1)->domaines, csp->domaines, 0, csp->n_variables);
 
	while(var_instanciees < csp->n_variables)
	{
		var_cour = MinDomain(csp,marquage);
 
		l=(p+version-1)->domaines[var_cour];
 
		while(l && !valeur_possible(var_cour,l->val, (p+version-1)->instanciation, csp) && l->use != 1)
		{
			l=l->suiv;
		}
 
		if(l != NULL && l->val != -1)
		{
			ok=0;
			l->use=1;
			(p+version-1)->instanciation[var_cour]= l->val;
			place_instanciation[var_cour]= place++;
			for(i=0; i <csp->n_variables; i++)
			{
				if(var_cour != i && csp->contraintes[var_cour][i] != NULL)
				{
					r= csp->contraintes[i][var_cour];
					while(r)
					{
						if(r->val2 != l->val)
						{
							if(!ok)
							{
								version++;
								ok = 1;
							}
							copyList((p+version-1)->domaines[i], (p+version-2)->domaines[i]);
							supprime_val_domaine(&((p+version-1)->domaines[i]), r->val1);
						}	
						r=r->suiv;	
					}
				}
			}	
			var_instanciees++;
			if(var_instanciees == csp->n_variables)
			{
				printf("Oui");
				copyTab2(csp->instanciation, (p+version-1)->instanciation, 0, csp->n_variables);
				break;
			}
		}
		else
		{
			if(place_instanciation[var_cour] > 0)
			{
				marquage[var_cour] =0;
				var_cour = var_precedente(place_instanciation[var_cour], place_instanciation, csp->n_variables);
 
				ok2=0;
				for(i=0; i<csp->n_variables; i++)
				{
					if(csp->contraintes[var_cour][i] != NULL)
					{
						if(!ok2)
						{
							version--;
							ok2 = 1;
						}
					}
				}
			}
			else
			{
				printf("Non");
				break;
			}
		}
	}
}*/

[diogene]

C'est normal qu'il ne soit pas d'accord ici

Code :

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

p[i]->domaines= (liste*)malloc(n*sizeof(liste));

puisque p[i] == NULL.

Code :

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

p= (pile*) malloc(taille*sizeof(pile));

p est une variable locale non retournée par la fonction. Comment la fonction appelante va-t-elle récupéré cette valeur.

Ceci étant, le code est difficile à suivre à cause de cette définition de pile comme un pointeur et c'est sans doute la source de ces erreurs.

Tu veux faire
- un tableau contenant des pointeurs sur des structures. (C'est ce que fait ton code. Mais il faut aussi créer les structures ce que ton code ne fait pas)
- ou un tableau de structure
?

[guipe]

Juste un tableau de structure. Tu as raison je vais supprimer le pointeur pile, ce n'est pas ce que je veux !

Mais ce que je ne comprends pas c'est que je passe un pointeur en argument(pointeur qui représentera mon futur tableau une fois le malloc effectué). Je ne comprends donc pas bien ton histoire de variable locale. p n'est pas locale à "init_pile" c'est un pointeur que je passe en paramètre.

Si je me trompe, dans ce cas comment récupérer p ?

Merci de tes explications.

PS: Voici mon code actualisé :

Structure pile:

Code :

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

1
2
3
4
5
typedef struct 
{
	liste* domaines;
	int* instanciation;
}pile;

Fonction init_pile:

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
void init_pile(int n, pile* p, int taille)
{
	int i,j;
 
	p= (pile*) malloc(taille*sizeof(pile));
 
	for(i=0; i<taille; i++)
	{
		p[i].domaines= (liste*)malloc(n*sizeof(liste));
		for (j=0; j< n; j++)
		{
			p[i].domaines[j] = NULL;
		}
		p[i].instanciation = (int*) malloc(n*sizeof(int));
		for (j=0; j< n; j++)
		{
			p[i].instanciation[j] = -1;
		}
	}
 
}

[diogene]

Je ne comprends donc pas bien ton histoire de variable locale. p n'est pas locale à "init_pile" c'est un pointeur que je passe en paramètre

Un paramètre est une variable locale. La seule différence avec une variable locale "ordinaire" est qu'elle est initialisée par la valeur passée en argument.

Si je me trompe, dans ce cas comment récupérer p ?

Le plus simple est d'utiliser la valeur de retour :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
pile* init_pile(int n, int taille)
{
	int i,j;
 
	pile * p=  malloc(taille*sizeof *p);
        if(p != NULL)
        {
          ...
        }
        return p;
}

[guipe]

Je n'ai à présent plus d'erreurs de segmentation. Mais mon problème est lorsque j'essaie de copier le tableau, de récupérer la liste, je fais le test pour voir si ma liste est nulle, et elle l'est or elle ne doit pas l'être si ma fonction de copie a marché. Je pense donc que mon problème vient de ma fonction copyTab :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
p= (pile*) malloc(100*sizeof(pile));
	
	init_pile(csp->n_variables, p, 100);
	copyTab(p[version].domaines, csp->domaines, 0, csp->n_variables);
	
	while(var_instanciees < csp->n_variables)
	{
		l=p[version].domaines[var_cour];
		
		if(l == NULL)
			printf("null");..........
..........
..........

Voici ma fonction copyTab:

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
void copyTab(liste* cpy, liste* tab, int min, int max)
{
	int i;
 
	for (i = min; i < max; i++)
	{
		while(tab[i])
		{
			ajout_liste(&(cpy[i]), tab[i]->val);
			//printf("%d",cpy[i]->val);
			cpy[i] = cpy[i] -> suiv;
			tab[i] = tab[i] -> suiv;
		}
	}
}

Une fois de plus je ne comprends pas mon erreur, je passe en argument un tableau de liste(tab) déjà rempli et un autre(cpy) qui a été "malloc" dans ma fonction init_pile. Je fais la copie des listes. Puis quand je veux récupérer une liste de ma copie de tableau dans ma fonction principale, elle est nulle. POurtant dans le printf de ma fonction copy, le printf m'indique le contraire. Je passe des tableaux en paramètre, donc des pointeurs, donc je ne comprends pas pourquoi ça ne fonctionne pas !

J'ai déjà passé des tableaux en paramètre et ça marchait très bien mais la non lol

[diogene]

Mais mon problème est lorsque j'essaie de copier le tableau, de récupérer la liste, je fais le test pour voir si ma liste est nulle, et elle l'est or elle ne doit pas l'être si ma fonction de copie a marché. Je pense donc que mon problème vient de ma fonction copyTab

Tu parles ici de choses que tu n'as pas décrites et comme on n'est pas dans ta tête...
Ton code utilise des types liste qu'on ne connait pas et, de toute façon, on ne sait pas ce que tu veux faire.

[guipe]

Je veux simplement copier un tableau de liste avec ma fonction copyTab. Mais apparemment cela ne fonctionne pas, comme j'ai pu le voir avec mon test ! J'ai déjà donné mes structures dans un post précédent.

PS: La fonction ajout_liste marche très bien ce n'est pas là d'ou vient le problème.

Je viens de faire un test dans ma fonction copytab qui me surprend. J'ai testé pour voir si mon tableau copié était nul après ma boucle "while(tab[i])" et il l'est... Alors que le printf dans la boucle while m'indique bien que la valeur avait bien été ajouté..

Je ne comprends pas !

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
void copyTab(liste* cpy, liste* tab, int min, int max)
{
	int i,j;
 
	for (i = min; i < max; i++)
	{
		while(tab[i])
		{
			ajout_liste(&(cpy[i]), tab[i]->val);
			//printf("%d",cpy[i]->val); // printf affiche les bonnes valeurs
			cpy[i] = cpy[i] -> suiv;
			tab[i] = tab[i] -> suiv;
		}
	}
	for(j=min; j <max; j++)
	{
		while(cpy[j])
		{
			printf("%d",cpy[j]->val); // printf n'affiche rien ici
			cpy[j]=cpy[j]->suiv;
		}
	}
 
}

Mon printf ici n'affiche rien ce qui prouve que l'ajout n'a pas marché !

[diogene]

Tu parles ici de choses que tu n'as pas décrites et comme on n'est pas dans ta tête...
Ton code utilise des types liste qu'on ne connait pas et, de toute façon, on ne sait pas ce que tu veux faire.

Tu ne réponds pas à cette remarque.
Il faut apporter des précisions sur ce qu'est le type liste, éventuellement le code de ajout_liste() et surtout ce que tu veux faire, parce que

Code :

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

1
2
3
4
5
6
7
8
9
ajout_liste(&(cpy[i]), tab[i]->val);
//printf("%d",cpy[i]->val); // printf affiche les bonnes valeurs
cpy[i] = cpy[i] -> suiv;
tab[i] = tab[i] -> suiv;
....
while(cpy[j])
{
  printf("%d",cpy[j]->val); // printf n'affiche rien ici
  cpy[j]=cpy[j]->suiv;}

me semble bizarre (pourquoi modifier ainsi les tableaux cpy et tab ?)

[guipe]

D'accord, je n'ai peut etre pas été clair. Je veux programmer un algorithme de forward checking. J'ai donc un tableau de pointeur vers des listes nommé csp->domaines qui a déjà été initialisé et qui représente les domaines de mes variables.

Ce que je veux faire dans un premier temps est créer un tableau de piles pour pouvoir avoir différentes versions(au cours du forward checking) de mon tableau de domaines, la structure pile contenant aussi un tableau de pointeur vers des listes.

Je veux donc simplement effectuer la copie du tableau csp->domaines dans p[0].domaines pour l'instant. Cependant cela ne semble pas marcher.

Ajout liste:

Code :

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

1
2
3
4
5
6
7
void ajout_liste(liste* tete, int val)
{
	liste nouveau =(liste) malloc(sizeof(liste_int));
	nouveau -> val = val;
	nouveau -> suiv = *tete;
	*tete = nouveau;
}

Structures:

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 
{
	liste* domaines;
	int* instanciation;
}pile;
 
typedef struct
{
	int n_variables;
	int* instanciation; 
	liste* domaines;
	relation** contraintes;
} CSP;

Edit: J'ai trouvé mon problème, il venait de ces lignes de code:

Code :

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

1
2
cpy[i] = cpy[i] -> suiv;
tab[i] = tab[i] -> suiv;

Forcément mon tableau était NULL à la fin, bref ! Merci !