vecteur de structures

Salut, alors voilà : je bosse sur un projet où je dois pour le problème du voyageur de commerce, tester tous les chemins possibles à travers plusieures villes et renvoyer le plus court. Pour celà je dois utiliser un vecteur.

J'utilise donc un vecteur contenant des structures contenant elle même une structure.
Mon problème est que j'ai l'impression de faire des erreurs sur la structure de donnée (définition et accès aux données).

J'utilise donc un module vext, crée précédemment en cours :
struct vext (et toutes les fonctions d'accès, de création etc définies dans vext.c)

(la struct vext juste en dessous est dans vext.c, le code ensuite est le vext.h)

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
struct vext 
{
    void **vecteur;
    unsigned int taille_physique;
    unsigned int taille_rallongement;
    unsigned int nombre_d_elements;
    void (*liberer)(void *);
    void (*afficher)(void *);
};
 
#ifndef VEXT_H
#define VEXT_H
 
typedef struct vext *vext;
 
extern vext vext_creer(void);
extern void vext_liberer(vext self);
extern unsigned int vext_nombre_d_elements(vext self);
extern void *vext_lire(vext self, int i);
extern void vext_ecrire(vext self, int i, void *valeur);
extern void vext_ajouter(vext self, void *valeur);
extern void vext_iterer(vext self, void (*fonction)(void *));
extern void vext_iterer_jusqua(vext self, void (*fonction)(void *), int n);
extern void vext_afficher(vext self);
extern void vext_definir_affichage(vext self, void (*afficher)());
extern void vext_definir_liberation(vext self, void (*liberer)());
 
#endif  /* VEXT_H */

En passant je précise mon arborescence et le makefile que j'utilise :
3 dossier include, lib et src
lib contenant la bibliothèque lvext.a et lbcb.a (contenant des fonctions tel mémoire_liberer).
include contenant tous les .h sauf versionperso.h
et src contenant versionperso.c .h et voyager.c et le makefile un dossier disterre contenant disterre.c et .h

donc le makefile en question :

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
CC 	= gcc
PREFIX	=../
INCDIR = $(PREFIX)/include
LIBDIR = $(PREFIX)/lib
BINDIR = $(PREFIX)/bin
CFLAGS  = -g -Wall -Werror -std=c99
CPPFLAGS = -I$(INCDIR)
LDFLAGS = -L$(LIBDIR)
 
LDLIBS = -lbcb -lvext
 
all: voyager
 
voyager: voyager.o disterre/disterre.o versionperso.o
	${CC} voyager.o versionperso.o ${CFLAGS} disterre/disterre.o ${LDFLAGS} -o voyager
 
 
versionperso.o: versionperso.c versionperso.h disterre.h
disterre.o: disterre/disterre.c disterre/disterre.h
voyager.o: voyager.c versionperso.h disterre/disterre.h
 
clean:
	for j in ${FPATH} ; do\
		rm -f *.o;\
	done

un fichier disterre.h et .c qui se charge de la gestion des coordonnées géographiques

disterre.c :

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
#include "disterre.h"
#include <math.h>
 
struct coordonnee
{
  int degre;
  int minute;
  int seconde;
  point_cardinal cardinalite;
};
 
struct position_terrestre
{
  char *nom_ville;
  coordonnee latitude;
  coordonnee longitude;
};
 
const double rayon_terrestre=6371.0; 
 
static double 
deg2rad(coordonnee c)
{
  const double un_degre = atan(1.0) / 45.0; 
 
  return c.cardinalite * 
    (c.degre + c.minute / 60.0 + c.seconde / 3600.0) * un_degre;
}
 
 
double disterre_distance(position_terrestre x, position_terrestre y)
{
 
  double latx = deg2rad(x.latitude);
  double lonx = deg2rad(x.longitude);
  double laty = deg2rad(y.latitude);
  double lony = deg2rad(y.longitude);
 
 
  return  rayon_terrestre * 
   acos((cos(latx)*cos(laty)*cos(lony - lonx))+sin(latx)*sin(laty));
}

disterre.h :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#ifndef DISTERRE_H
#define DISTERRE_H
 
 
typedef enum {N=1, S=-1, E=1, O=-1} point_cardinal;
 
typedef struct coordonnee *coordonnee;
 
typedef struct position_terrestre *position_terrestre;
 
 
double disterre_distance(position_terrestre x, position_terrestre y);
 
 
#endif

un fichier versionperso.c qui contient les fonctions de gestion des possibilités de parcours etc

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
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
#include "versionperso.h"
#include <disterre.h>
#include <stdio.h>
#include <stdlib.h>
 
 
double
distance_parcours(vext self)
{
  double distance =0;
  for (int i=0 ; i < vext_nombre_d_elements(self) ; i++)
    distance += disterre_distance(self->vecteur[i],self->vecteur[i+1]);
  return distance;
}
 
int
factorielle(int n)
{
  if (n ==1)
    return 1;
  else
    return n * factorielle(n-1);
}
 
void
echange(position_terrestre a, position_terrestre b)
{
  position_terrestre tmp = memoire_allouer(sizeof(position_terrestre));
  tmp = a;
  a = b;
  b = tmp;
}
 
vext
echange3elements(vext self,int cpt)
{
  int n=vext_nombre_d_elements(self)-1;
  echange(self->vecteur[n-1-cpt], self->vecteur[n-cpt]);
  (cpt+=1)%2;
  return self;
}
 
void
cas3(vext self,int nb, double distance)
{
  vext vext_recup2 = vext_creer();
  while(nr_cas < factorielle(3))
    {
      vext_recup2 = echange3elements(self,compt);
      nr_cas +=1;
      double distance2 = distance_parcours(self);
      if (distance2 < distance)
	{
	  distance = distance2;
	  vext_iterer(self, memoire_liberer(self->vecteur));
	  vext_iterer(self, vext_ajouter(self, vext_recup2->vecteur));
	}
    }
  vext_liberer(vext_recup2);
}
 
 
 
double
parcours(vext self)
{
 
  double distance_tot = distance_parcours(self);
  int compt = 0;
  int n = vext_nombre_d_elements(self);
  int nr_cas = 0;
  vext vext_recup = vext_creer();
  int factorielle = factorielle(n);
  vext_iterer(vext_recup, vext_ajouter(vext_recup, self->vecteur));
 
 
  if (vext_nombre_d_elements(self) == 3)
    {
      cas3(self, nr_cas, distance_tot);
 
      /* while(nr_cas < factorielle(3))
	 {
	 vext_recup = echange3elements(self,compt);
	 nr_cas +=1;
	 double distance2 = distance_parcours(self);
	 if (distance2 < distance_tot)
	 distance_tot = distance2;
	 }*/
    }
 
 
  //plus de 3 elements
  if (vext_nombre_d_elements(self) > 3)
    {
      int a = 0;
      while(a < factorielle)
	{
	  int j=1;
	  for (int i= 0 ; i< (factorielle / n) ; i++)
 
	    {
	      cas3(self, nr_cas, distance_tot);
	      vext_ajouter(self,self->vecteur[n-3-j]);
	      memoire_liberer(self->vecteur[n-3-j]);
	      j++;
	      a+=6;
 
	    }
	  vext_ajouter(self, self->vecteur[0]);
	  memoire_liberer(self->vecteur[0]);
	}
 
 
    }
 
  return distance_tot;
}
 
coordonnee
creer_coordonnee(void)
{
  coordonnee cor = memoire_allouer(sizeof(coordonnee));
  cor->degre=0;
  cor->minute=0;
  cor->seconde=0;
  cor->cardinalite="";
  return cor;
}
 
position_terrestre
creer_position_terrestre(void)
{
  position_terrestre pt = memoire_allouer(sizeof(position_terrestre));
  coordonnee latitude = creer_coordonnee();//memoire_allouer(sizeof(coordonnee));
  coordonnee longitude = creer_coordonnee();//memoire_allouer(sizeof(coordonnee));
  pt->nom_ville = "";
  pt->latitude = latitude;
  pt->longitude = longitude;
  return pt;
}

le versionperso.h :
j'ai du remettre la définition de la structure vext et coordonnee et position_terrestre sinon à la compilation j'avais un message du type : utilisation implicite de vext (apparament malgré que j'inclue le vext.h dans versionperso.h il n'avais pas vraiment accès à la structure vext?)

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
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
#ifndef VERSIONPERSO_H
 
#define VERSIONPERSO_H
 
 
 
#include <memoire.h>
 
#include <vext.h>
 
#include <disterre.h>
 
 
 
struct vext 
 
{
 
    void **vecteur;
 
    unsigned int taille_physique;
 
    unsigned int taille_rallongement;
 
    unsigned int nombre_d_elements;
 
    void (*liberer)(void *);
 
    void (*afficher)(void *);
 
}; 
 
 
 
struct coordonnee
 
{
 
  int degre;
 
  int minute;
 
  int seconde;
 
  point_cardinal cardinalite;
 
};
 
 
 
struct position_terrestre
 
{
 
  char *nom_ville;
 
  coordonnee latitude;
 
  coordonnee longitude;
 
};
 
 
 
extern position_terrestre creer_position_terrestre(void);
 
extern double distance_parcours(vext self);
 
static int factorielle(int n);
 
extern void echange(position_terrestre a, position_terrestre b);
 
extern vext echange3elements(vext self,int cpt);
 
extern void cas3(vext self,int nb, double distance);
 
extern double parcours(vext self);
 
 
 
#endif /*VERSIONPERSO_H*/

enfin le fichier voyager.c qui contient le main et gère le remplissage du vecteur à partir d'un fichier .txt contenant des coordonnées.
j'ai redéfinis certaines fonctions tel vext_liberer mais si ma structure de donnée était juste celà je pense devrait fonctionner avec celle du module vext.

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
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
#include <stdio.h>
 
#include <stdlib.h>
 
 
 
#include "versionperso.h"
 
#include "disterre.h"
 
 
 
#define CHEMIN /home/jerome/enseignement/Projet2/coordonnees.txt
 
 
 
void
 
usage (char* s)
 
{
 
  fprintf(stderr,"Usage : %s <nom_fichier_texte>.txt",s);
 
  exit(EXIT_FAILURE);
 
}
 
 
 
 
 
void
 
affichage_villes(vext self)
 
{
 
  for (int i = 0 ; i< vext_nombre_d_elements(self) ; i++)
 
    printf(" %p ", self->vecteur[i].nom_ville);
 
  printf("\n");
 
}
 
 
 
// à modifier et déplacer!
 
void
 
liberation_vext(vext self)
 
{
 
  unsigned int n = vext_nombre_d_elements(self);
 
  for (int i=0; i < n; i++)
 
    { 
 
      if (self->liberer != NULL)
 
	{
 
	  if (self->vecteur[i] != NULL)
 
	    { 
 
	      self->liberer(self->vecteur[i].latitude);
 
	      self->liberer(self->vecteur[i].longitude); 
 
	      self->liberer(self->vecteur[i]);
 
	    }
 
	}
 
      memoire_liberer(self->vecteur);
 
      memoire_liberer(self);
 
    }
 
}
 
 
 
 
 
vext
 
faire_vext()
 
{
 
  vext self = vext_creer();
 
 
 
  vext_definir_affichage(self, affichage_villes);
 
  vext_definir_liberation(self, memoire_liberer);
 
 
 
  return self;
 
}
 
 
 
 
 
 
 
 
 
void
 
remplir_vext_depuis_fichier(vext self)
 
{
 
  int nb_lignes=0;
 
  FILE *flot = memoire_allouer(sizeof(*flot));
 
  flot = fopen("CHEMIN", "r");//erreur si mauvais chemin / pas de fichier à mettre.
 
  while (flot != 0)
 
    {
 
      position_terrestre pt = creer_position_terrestre();
 
 
 
      int lat1, lat2, lat3, lon1, lon2, lon3;
 
      char lat, lon;
 
      char *s;
 
 
 
      fscanf(flot, " %s %d %d %d %c %d %d %d %c \n", s, &lat1, &lat2, &lat3, &lat, &lon1, &lon2, &lon3, &lon);
 
 
 
      pt->nom_ville = s;
 
      pt->latitude->degre = lat1;
 
      pt->latitude->minute = lat2;
 
      pt->latitude->seconde = lat3;
 
      pt->latitude->cardinalite = lat;
 
 
 
      pt->longitude->degre = lon1;
 
      pt->longitude->minute = lon2;
 
      pt->longitude->seconde = lon3;
 
      pt->longitude->cardinalite = lon;
 
 
 
      vext_ajouter(self, pt);
 
 
 
      nb_lignes++; 
 
    }
 
  fclose(flot);
 
}
 
 
 
 
 
int
 
main(int argc, char *argv[])
 
{
 
  vext self = faire_vext();
 
 
 
  remplir_vext_depuis_fichier(self);
 
 
 
  double distance = parcours(self);
 
 
 
 
 
  printf("Voici un parcours minimal de longueur %f : ", distance);
 
  vext_afficher(self);
 
 
 
  vext_liberer(self);
 
  return EXIT_SUCCESS;
 
 
 
}

En conclusion j'ai :
vext.c et vext.h (définis en cour)
disterre.c et disterre.h gère l'utilisation des coordonnées géographiques
versionperso.c versionperso.h gère les possibilités de chemins etc
voyager.c le main et le remplissage du vecteur à partir d'un fichier de coordonnées.

Beaucoup de choses sont définies sans y avoir passé trop de temps, là par contre où j'ai pas mal cherché sans trouver de solution c'est le point que je ne comprends pas bien :

comment je dois définir / gérer / libérer le vecteur de structures?

Si vous pouviez m'aider ce serait super ^^ je sais que j'ai tout mis un peu en vrac dans ce post et que ça fais long, mais peut-être que celà est plus compréhensible, d'autre part en passant je n'attends pas bien sûr que l'on me fasse mon projet juste que l'on m'explique les points précédents ;)

enfin je poste les erreurs de compilations restantes :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
-*- mode: compilation; default-directory: "~/Bureau/Projet2/src/" -*-
Compilation started at Sun Mar 16 22:03:31
 
make
gcc -g -Wall -Werror -std=c99 -I..//include  -c -o voyager.o voyager.c
voyager.c: In function «affichage_villes":
voyager.c:21: erreur: request for member «nom_ville" in something not a structure or union
voyager.c: In function «liberation_vext":
voyager.c:36: erreur: request for member «latitude" in something not a structure or union
voyager.c:37: erreur: request for member «longitude" in something not a structure or union
make: *** [voyager.o] Erreur 1
 
Compilation exited abnormally with code 2 at Sun Mar 16 22:03:31

dernière précision : notamment dans la fonction de remplissage du vecteur dans voyager.c ne trouvant pas de solution aux erreurs de compilation j'ai un peu expérimenté pour voir le résultat d'où peut-être certaines lignes pas cohérentes mais je peux ainsi voir les erreurs que ça provoque en espérant comrpendre le problème.
Voilà = )

vecteur est un tableau de pointeurs génériques, donc vecteur[i] est un pointeur générique.

Pour moi, la fonction affichage_villes() ne devrait appeler le pointeur de fonction afficher() sur chaque ville, et non essayer d'afficher elle-même la ville...

En tant que débutant je te conseille vivement d'éviter au maximum d'utiliser des pointeurs "void*". C'est une source d'em.... perpétuels quand on ne sait pas bien les utiliser. Dans tes exemples tu devrais pouvoir t'en passer. En plus tu auras des messages d'erreur plus compréhensibles à la compilation.

Le C est un langage fortement typé, et utiliser des pointeurs non typés (void*) doit être réservé à un usage exceptionnel.

La structure vext semble évidemment décrire un vecteur générique, donc void* est tout-à-fait approprié ici...

Citation:

Envoyé par garfieldkat

J'utilise donc un module vext, crée précédemment en cours :
struct vext (et toutes les fonctions d'accès, de création etc définies dans vext.c)

J'avais râté ça ... Mieux vaut effectivement ne pas toucher à ce qui fonctionne déjà. Donc oubli ma recommandation sur l'utilisation de void*.

D'accord sur l'appel du pointeur de fonction void (*afficher)(void *).

déja merci pour vos réponses je vais éssayer ^^

Par contre je ne saisis pas très bien comment est faite au final la structure :

pour accèder à un élément i du vexteur je dois faire :
self->vecteur[i] qui pointe donc sur l'élément i du vecteur.

si c'est une structure donc avec un champ disons int a je devrait faire :
self->vecteur[i].a ou self->vecteur[i]->a?
et que change le fait de déclarer soit :
typedef struct position_terrestre position_terrestre ou bien
typedef struct position_terrestre *position_terrestre
physiquement et pour l'accès à une donnée dans position_terrestre?

si ensuite j'ai dans position_terrestre le champ latitude qui est une autre structure contenant le champ degre aurais-je :
self->vecteur[i]->latitude->degre?

j'ai l'impression d'être approximatif sur tous ces points ^^

Citation:

pour accèder à un élément i du vexteur je dois faire :
self->vecteur[i] qui pointe donc sur l'élément i du vecteur.

D'après la syntaxe, on peut dire que :
Self est un pointeur sur une structure. Cette structure comporte un champ vecteur. Ce champ vecteur est soit un tableau soit un pointeur (contenant l'adresse de début d'un tableau).

Citation:

self->vecteur[i].a

Le tableau vecteur est un tableau de structures comportant un champ a

Citation:

self->vecteur[i]->a?

Le tableau vecteur est un tableau de pointeurs sur des structures comportant un champ a

Citation:

typedef struct position_terrestre position_terrestre

position_terrestre est un type struct position_terrestre. Si position_terrestre p; l'acces à un champ a de la structure sera fait par p.a

Citation:

typedef struct position_terrestre *position_terrestre

position_terrestre est un type pointeur sur struct position_terrestre
Si position_terrestre p; (et p initialisé avec l'adresse d'une struct position_terrestre) l'acces à un champ a de cette structure sera fait par p->a

Citation:

si ensuite j'ai dans position_terrestre le champ latitude qui est une autre structure contenant le champ degre aurais-je :
self->vecteur[i]->latitude->degre?

Ceci correspond, par exemple, à une structure de ce type :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 struct y { .... degre; }; struct x { struct y * latitude }; struct z { struct x * vecteur[N]; }; struct z * self;
Si on a self->vecteur[i]->latitude.degre, on aurait la structure :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 struct y { .... degre; }; struct x { struct y latitude }; struct z { struct x * vecteur[N]; }; struct z * self;

Citation:

Envoyé par garfieldkat

si c'est une structure donc avec un champ disons int a je devrait faire :
self->vecteur[i].a ou self->vecteur[i]->a?

Citation:

Envoyé par diogene

D'après la syntaxe, on peut dire que :
Self est un pointeur sur une structure. Cette structure comporte un champ vecteur. Ce champ vecteur est soit un tableau soit un pointeur (contenant l'adresse de début d'un tableau).

Code:

self->vecteur[i].a

Le tableau vecteur est un tableau de structures comportant un champ a

Code:

self->vecteur[i]->a?

Le tableau vecteur est un tableau de pointeurs sur des structures comportant un champ a

C'est presque ça, mais comme vect->vecteur est déclaré comme étant un tableau de pointeurs de type inconnu (void) :
Code:

1 2 3 4 struct vext { void **vecteur; ...
Tu dois faire une conversion de type explicite (cast) ou implicite (affectation typée) avant de pouvoir accéder à un membre "a" (si on remplace a par nom_ville par exemple).
Code:

1 2 3 4 5 6 typedef struct position_terrestre *position_terrestre; position_terrestre p; p = self.vecteur[i]; printf("nom = %s", p->nom_ville);
Nécessaire car le type de "self.vecteur[i]" est "void*". Et que "void*" n'est pas un pointeur de structure, et n'a donc pas de membre a. Alors que p, oui.
Code:

1 2 printf("nom = %s", ((position_terrestre) self.vecteur[i])->nom_ville);

super merci beaucoup je comprends déja bien mieux:king:
je vais éssayer de continuer ça devrait bien m'aider ^^