Discussion :

[letopdutop]

Bonjours a tous !

je travail depuis quelques temps a un projet utilisant Dijkstra sur des reseaux ferroviaires, or j'ai un souci de segmentation que je n'arrive pas a m'expliquer.
Voila mes structures pour le reseau :

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
typedef struct Passage {
	int horaire;		// l'horaire de passage du train
	int destination;	// le destination de ce train
	int index_destination;	// l'index du passage du train a la destination
 
	int ligne;
} Passage;
 
typedef struct Coordonne {
	int abcisse, ordonnee;
} Coordonne;
 
 
typedef struct Ville {
	Coordonne coord;
 
	int nb_passages;
	Passage* passages;
} Ville;	
 
typedef struct Reseau {
	int nb_villes;
	Ville* villes;
} Reseau;
 
 
Reseau* Create_Reseau ( );
void Destroy_Reseau ( );
 
void Add_Ville (Reseau* reseau, int abcisse, int ordonnee);
int Add_Passage (Reseau* reseau, int ville, int horaire, int ligne);	// terminus par defaut. Sinon, regarder dans Add_Ligne.
void Add_Ligne (Reseau* reseau, int* villes, int* horaires, int size, int ligne);

voila les fonctions utilisés :

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
#include "Reseau.h"
 
#define format(a,b) ((a)*60 + (b))
#define heure(a) ((a)/60)
#define minute(a) ((a)%60)
 
#define TERM	-1		//TERM pour terminus, il n'y a pas de prochain arret
 
int By_Horaire_Then_Line (const void*, const void*);
 
Reseau* Create_Reseau ( ) {
	Reseau* reseau = malloc (sizeof(Reseau));
	reseau->nb_villes = 0;
	reseau->villes = NULL;
 
	return reseau;
}
 
void Destroy_Reseau (Reseau* reseau) {
	for (unsigned int i=0; i<reseau->nb_villes; i++) {
		free (reseau->villes[i].passages);
	}
	free (reseau->villes);
	free (reseau);
}
 
 
 
void Add_Ville (Reseau* reseau, int abcisse, int ordonnee) {
	reseau->nb_villes++;
	reseau->villes = realloc (reseau->villes, reseau->nb_villes * sizeof (Ville));
 
	int created = reseau->nb_villes - 1;
 
	reseau->villes[created].coord.abcisse = abcisse;
	reseau->villes[created].coord.ordonnee = ordonnee;
 
	reseau->villes[created].nb_passages = 0;
	reseau->villes[created].passages = NULL;
}
 
 
int Add_Passage (Reseau* reseau, int ville, int horaire, int ligne) {
	Passage created;
			created.horaire = horaire;
			created.ligne = ligne;
			created.destination = TERM;
			created.index_destination = TERM;
 
	int rang = ORInsert (reseau->villes[ville].passages, &created, reseau->villes[ville].nb_passages,
						 sizeof (Passage), By_Horaire_Then_Line);
	reseau->villes[ville].nb_passages ++;
 
	return rang;
}
 
 
 
void Add_Ligne (Reseau* reseau, int* villes, int* horaires, int lenght, int ligne) {
	int* indexes = malloc (lenght * sizeof (int));
 
	for (int i=0; i<lenght; i++) {
		indexes[i] = Add_Passage (reseau, villes[i], horaires[i], ligne);
		printf ("%d %d\n", indexes[i], villes[i]);
	}
 
	for (int i=0; i<lenght-1; i++) {
		reseau->villes[villes[i]].passages[indexes[i]].destination = villes[i+1];
		reseau->villes[villes[i]].passages[indexes[i]].index_destination = indexes[i+1];
	}
 
	free (indexes);
}
 
 
int By_Horaire_Then_Line (const void* a, const void* b) {
	Passage* A = a;
	Passage* B = b;
 
	return (A->horaire - B->horaire != 0 ? A->horaire - B->horaire : A->ligne - B->ligne);
}

et voila la fonction ORInsert (qui fait une insertion dans un tableau en respectant l'ordre)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
int ORInsert (void* array, void* x, int lenght, size_t size, int Compare (const void*, const void*)) {
	array = realloc (array, (lenght+1) * size);
	int i = lenght - 1;
		while (i > 0 && (Compare(array + (i*size), x) > 0)) {
			memcpy (array + ((i+1)*size), array + (i*size), size);
			i--;
		}
		if (i < 0) i = 0;
		memcpy(array + (i*size), x, size);
	return i;
}

le problème se trouve dans la fonction Add_Ligne(), sur la ligne
reseau->villes[villes[i]].passages[indexes[i]].destination = villes[i + 1] : il me le marque en segfault,
pourtant j'ai beau faire des printf, passer et repasser cette ligne, la regarder avec gdb je ne trouve absolument pas ce qui peut provoquer cette erreur, une idée ?

[Obsidian]

Bonjour,

le problème se trouve dans la fonction Add_Ligne(), sur la ligne
reseau->villes[villes[i]].passages[indexes[i]].destination = villes[i + 1] : il me le marque en segfault,
pourtant j'ai beau faire des printf, passer et repasser cette ligne, la regarder avec gdb je ne trouve absolument pas ce qui peut provoquer cette erreur, une idée ?

Impossible d'être catégorique sans voir le reste de ton programme, mais il y a beaucoup de points qui peuvent poser problème en une seule ligne :

• Un pointeur « reseau » mal initialisé ;
• Un pointeur « villes » mal initialisé ;
• Une variable « lenght » (qui devrait être écrite « length ») mal initialisée, ou à la valeur trop élevée par rapport à celle du réseau parcourue ;
• Un tableau pointé par « ville » trop court ou mal initialisé : si les valeurs contenues dans les entiers pointées sont incorrectes, ce ne sera pas un problème en soi mais ça le deviendra si ces entiers servent d'index à un autre tableau ;
• Un pointeur « indexes » mal initialisé (si malloc() échoue. Peu probable mais pas impossible) ;

Si tu utilises des printf, il faut donc en mettre un juste avant la ligne concernée (avec un retour à la ligne) qui mette en évidence le contenu de tous les points cités ci-dessus, à commencer par la valeur de « i » elle-même, pour savoir si la ligne plante systématiquement ou après plusieurs tours de boucle, voire au dernier.

Ensuite, décompose (au moins temporairement) ta ligne unique en plusieurs lignes distinctes, quitte à utiliser des variables intermédiaires, de façon à pouvoir les visualiser plus facilement avec gdb.

Enfin, n'oublie pas d'activer tous les warnings de GCC (au moins « -W -Wall » et éventuellement « -Wextra ») : il y a beaucoup de cas « acceptables » qui deviennent vicieux dès qu'un programme gagne en complexité.

[diogene]

Dans la fonction ORInsert(), tu fais un realloc() qui peut changer l'adresse mémoire.
Cette éventuelle nouvelle adresse n'est pas répercutée dans la fonction appelante Add_Passage() et reseau->villes[ville].passages est alors devenue une adresse illégale.