problème creation graphe avec un fichier txt

Version imprimable

23/02/2010, 16h05
ALeX850

problème creation graphe avec un fichier txt

Bonjour,
J'aimerais créer un graphe avec des listes chaînées.
Pour cela j'ai fait un txt avec toutes les informations pour le chaîner.
Il y a 57 sommet dans mon graphe.
Il y a un for de 0 à 57 qui permet de chaîner ses successeurs à chacun des 57 sommets.
Mon problème c'est qu'au bout de 33 itérations, il ne se passe plus rien...
Les 33 premières se déroulent sans souci, j'ai vérifié par des printf si toutes les informations avaient bien été stockées.
D'après mes tests, à la 33ème fois, il ne se passe plus rien après :
fscanf(fichier_graphe, "%d", &nb_succ);
qui permet de stocker le nombre de successeurs du sommet en cours de traitement.
Ma question c'est : y a-t-il une taille maximale de fichier ? (en caractères ?)
Car je ne vois aucune raison pour qu'il ne se passe plus rien, mais je n'y connais pas grand chose non plus. Quand je dis ça, en fait il se passe que le curseur de la console clignote et c'est tout.
Merci pour votre aide
23/02/2010, 16h18
diogene

Il y a une erreur dans ton code (ou/et dans ton fichier), mais comme tu ne le montres pas ...

Citation:

Ma question c'est : y a-t-il une taille maximale de fichier ? (en caractères ?)

Certainement, mais la valeur depend de ton système. De toute façon, tu dois être (très) loin du compte.
23/02/2010, 17h15
ALeX850

Rebonjour,
en fait quelqu'un a testé mon programme, et chez lui ça marche jusqu'au bout ... étrange..
Je programme avec code blocks 8.02
Auriez-vous une idée du pourquoi du comment ?
Merci
23/02/2010, 17h35
Obsidian

Citation:

Envoyé par ALeX850

Ma question c'est : y a-t-il une taille maximale de fichier ? (en caractères ?) Car je ne vois aucune raison pour qu'il ne se passe plus rien, mais je n'y connais pas grand chose non plus. Quand je dis ça, en fait il se passe que le curseur de la console clignote et c'est tout. Merci pour votre aide

Pour compléter ce que dit Diogène, il y a souvent un maximum de 2 Go par fichier, quoi que cette limite est en train d'être levée sur les systèmes de fichiers récents.

Citation:

Envoyé par ALeX850

Rebonjour, en fait quelqu'un a testé mon programme, et chez lui ça marche jusqu'au bout ... étrange.. Je programme avec code blocks 8.02 Auriez-vous une idée du pourquoi du comment ? Merci

C'est un bug intermittent. Il peut être dû à n'importe quoi mais, comme ça, je parierais sur un dépassement de tampon qui doit aller écraser les variables d'à côté, lesquelles sont probablement les indices de ta boucle.

Poste ton code ici (avec les balises [ CODE ]), et on tâchera de t'aider.

Voilà donc cette fonction permet de construire le graphe. Elle n'est pas commentée mais je pense qu'elle est facile à comprendre : on ouvre le fichier, il lit l'ordre du graphe, puis on fait autant d'itérations que l'ordre, il lit le nombre de successeurs du sommet i, puis on chaîne les successeurs...
(sinon j'aimerais savoir, quand je tronque mes double, il m'affiche quelque chose du genre : XX.XX0000, comment enlever ces 0 ?)

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
 
T_sommet **Construction_Graphe(T_sommet **Graphe, int *ordre){
    FILE *fichier_graphe;
    T_sommet *temp = NULL;
    double vitesse_temp;
    int nb_succ = 0;
    int i, j;
 
    fichier_graphe = fopen(".\\graphe.txt", "r");
    if (fichier_graphe == NULL) printf("Probleme d'ouverture fichier");
    else{
        fscanf(fichier_graphe, "%d", ordre);
 
        Graphe = (T_sommet**)malloc(sizeof(T_sommet*));
 
        for(i=0 ; i<(*ordre) ; i++){
            Graphe[i] = (T_sommet*)malloc(sizeof(T_sommet));
            Graphe[i] = NULL;
 
            fscanf(fichier_graphe, "%d", &nb_succ);
 
            if(nb_succ != 0){
                for(j=0 ; j<nb_succ ; j++){
                    temp = (T_sommet*)malloc(sizeof(T_sommet));
                    fscanf(fichier_graphe, "%d %d %d", &(temp->id), &(temp->distance), &(temp->vitessemax));
                    vitesse_temp = Conversion_kmh_ms(temp->vitessemax);
                    temp->temps = Tronquer_Centieme((temp->distance)/vitesse_temp);
                    temp->vitesse = temp->vitessemax;
                    temp->densitemax = ((temp->distance)/(((temp->vitessemax)/10)+2));
                    temp->densite = 0;
                    Graphe[i] = Ajouter_Sommet(Graphe[i], temp);
                }
            }
        }
        fclose(fichier_graphe);
        return Graphe;
    }
}

Merci

23/02/2010, 22h27
Obsidian
Bonsoir,

Citation:

Envoyé par ALeX850

Voilà donc cette fonction permet de construire le graphe. Elle n'est pas commentée mais je pense qu'elle est facile à comprendre : on ouvre le fichier, il lit l'ordre du graphe, puis on fait autant d'itérations que l'ordre, il lit le nombre de successeurs du sommet i, puis on chaîne les successeurs...

Il nous faudrait le code des autres fonctions (celles qui sont appelées dans celle-ci), et surtout la définition de T_sommet mais, à vue de nez, il y a déjà pas mal d'incohérences dans ton programme :
Code:

1 2 3 4 5 T_sommet **Construction_Graphe(T_sommet **Graphe, int *ordre) { … Graphe = (T_sommet**)malloc(sizeof(T_sommet*));
D'une part, tu demandes à la fonction appelante de te passer un pointeur sur ce que je pense être un tableau de sommets, mais tu écrases le contenu de ce pointeur à la première utilisation par un malloc(). À quoi cela te sert-il de passer un argument ?
Code:

1 2 3 for(i=0 ; i<(*ordre) ; i++){ Graphe[i] = (T_sommet*)malloc(sizeof(T_sommet)); Graphe[i] = NULL;
D'un pointeur sur un tableau, tu fais un tableau de pointeurs. Soit. Mais, en l'occurrence, tu n'as alloué de la place que pour un seul pointeur (dans le paragraphe au dessus). une boucle de 0 à « ordre » va donc forcément sortir de la mémoire allouée. On a donc déjà le dépassement de tableau que l'on subodorait.

D'autre part, tu alloues un sommet et tu écrases immédiatement le pointeur retourné avec NULL. Mise à part la fuite de mémoire que cela engendre, pourquoi fais-tu cela ?
Code:

1 2 if(nb_succ != 0){ for(j=0 ; j<nb_succ ; j++){
Puisque ton « if » ne contient rien d'autre que la boucle, il ne sert à rien, ici. La boucle ne tournera pas du tout si « nb_succ » est nul ou négatif.

Code:

Graphe[i] = Ajouter_Sommet(Graphe[i], temp);

Ceci est probablement faux, également, mais on ne peut l'affirmer sans avoir vu le contenu de Ajouter_Sommet.

Tout d'abord, merci pour ta réponse. Mais il y a plusieurs points que je ne comprends pas, comme tu dois le voir je ne maîtrise pas vraiment les pointeurs..
Pour plus de clarté, voilà mes autres fonctions, le main et le header :

header :

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
 
#ifndef GRAPHE_H_INCLUDED
#define GRAPHE_H_INCLUDED
 
#include <stdio.h>
#include <stdlib.h>
#include <float.h>
#include <math.h>
 
typedef struct sommet{
    unsigned int id;
	double temps;
    unsigned int distance;
    unsigned int vitesse;
    unsigned int vitessemax;
	unsigned int densite;
	unsigned int densitemax;
    struct sommet *suiv;
}T_sommet;
 
T_sommet **Construction_Graphe(T_sommet **Graphe, int *ordre);
T_sommet *Ajouter_Sommet(T_sommet *ancre, T_sommet *nv_sommet);
double Conversion_kmh_ms(int nombre);
double Tronquer_Centieme(double nombre);
 
#endif // GRAPHE_H_INCLUDED

main :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
#include "graphe.h"
 
int main(int argc, char** argv)
{
    T_sommet **Graphe;
    int ordre = 0;
 
    Graphe = Construction_Graphe(Graphe, &ordre);
 
    return 0;
}

la fonction de tout à l'heure :

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
 
/**Fonction qui construit le graphe en mémoire**/
T_sommet **Construction_Graphe(T_sommet **Graphe, int *ordre){
    FILE *fichier_graphe;
    T_sommet *temp = NULL;
    double vitesse_temp;
    int nb_succ = 0;
    int i, j;
 
    fichier_graphe = fopen(".\\graphe.txt", "r");
    if (fichier_graphe == NULL) printf("Probleme d'ouverture fichier");
    else{
        fscanf(fichier_graphe, "%d", ordre);
        printf("ordre = %d\n", *ordre);
 
        Graphe = (T_sommet**)malloc(sizeof(T_sommet*));
 
        for(i=0 ; i<(*ordre) ; i++){
            printf("sommet %d\n", i);
            Graphe[i] = (T_sommet*)malloc(sizeof(T_sommet));
            Graphe[i] = NULL;
 
            fscanf(fichier_graphe, "%d", &nb_succ);
            printf("nb_succ = %d\n", nb_succ);
 
            if(nb_succ != 0){
                for(j=0 ; j<nb_succ ; j++){
                    temp = (T_sommet*)malloc(sizeof(T_sommet));
                    fscanf(fichier_graphe, "%d %d %d", &(temp->id), &(temp->distance), &(temp->vitessemax));
                    vitesse_temp = Conversion_kmh_ms(temp->vitessemax); //On convertit les km/h en m/s avec 2 chiffres après la virgule
                    temp->temps = Tronquer_Centieme((temp->distance)/vitesse_temp);
                    temp->vitesse = temp->vitessemax;
                    temp->densitemax = ((temp->distance)/(((temp->vitessemax)/10)+2));
                    temp->densite = 0;
                    printf("id = %d, dist = %dm, vit = %lfm/s, tmps = %lfs, densmx = %d\n", (temp->id), (temp->distance), vitesse_temp, (temp->temps), (temp->densitemax));
                    Graphe[i] = Ajouter_Sommet(Graphe[i], temp);
                }
            }
        }
        fclose(fichier_graphe);
        return Graphe;
    }
}

fonction qui chaine le successeur :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
T_sommet *Ajouter_Sommet(T_sommet *ancre, T_sommet *nv_sommet){
    if(ancre == NULL){
        ancre = nv_sommet;
        ancre -> suiv = NULL;
    }
    else{
        nv_sommet -> suiv = ancre;
        ancre = nv_sommet;
    }
    return ancre;
}

fonction qui convertit en m/s

Code:

1
2
3
4
5
6
7
8
 
double Conversion_kmh_ms(int nombre){
    double nv_nombre = nombre;
    int temp;
    nv_nombre = (nv_nombre*1000)/3600;
    nv_nombre = Tronquer_Centieme(nv_nombre);
    return nv_nombre;
}

fonction qui tronque au centieme :

Code:

1
2
3
4
5
6
 
double Tronquer_Centieme(double nombre){
    int temp = 100*nombre;
    nombre = (double)temp/100;
    return nombre;
}

et en bonus voilà mon fichier texte :

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
 
57
1 1 1000 30
4 0 1000 30 3 3000 80 31 2500 80 33 2800 30
1 3 700 50
4 1 3000 80 2 700 50 5 900 80 35 1700 50
1 5 600 80
3 3 900 80 4 600 80 7 1500 80
1 7 800 80
3 5 1500 80 6 800 80 9 800 80
1 9 800 30
4 7 800 80 8 800 30 11 2000 80 37 2500 30
1 11 1600 80
4 9 2000 80 10 1600 80 13 3000 80 38 2900 80
1 13 800 30
4 11 3000 80 12 800 30 15 2000 80 40 1300 30
1 15 1300 80
3 13 2000 80 14 1300 80 17 1600 80
1 17 800 50
4 15 1600 80 16 800 50 19 3000 80 41 2500 50
1 19 500 50
4 17 3000 80 18 500 50 20 2000 80 42 2500 50
1 21 400 80
3 19 2000 80 20 400 80 23 1200 80
1 23 400 30
4 21 1200 80 22 400 30 25 3500 80 43 1800 30
1 25 600 50
4 23 3500 80 24 600 50 27 2000 80 44 1600 50
1 27 1000 50
4 25 2000 80 26 1000 50 29 4000 80 45 1100 50
1 29 1000 80
3 27 4000 80 28 1000 80 31 1300 80
1 31 700 50
4 1 2500 80 29 1300 80 30 700 50 32 3200 50
3 31 3200 50 33 2900 50 46 2500 50
4 1 2800 30 32 2900 50 34 800 50 48 500 30
4 33 800 50 35 500 50 36 600 50 48 600 50
3 3 1700 50 34 500 50 36 600 50
4 34 600 50 35 600 50 37 1200 50 49 1400 50
4 9 2500 30 36 1200 50 38 1500 50 50 1500 30
4 11 2900 80 37 1500 50 39 1000 30 51 700 50
5 38 1000 30 40 2000 30 51 500 50 53 1500 50 55 1800 30
3 13 1300 30 39 2000 30 41 3000 30
4 17 2500 50 40 3000 30 42 1700 30 55 1100 50
4 19 2500 50 41 1700 30 43 1400 30 56 1400 50
4 23 1800 30 42 1400 30 44 4000 30 56 1200 30
2 25 1600 50 45 400 50
3 27 1100 50 44 400 50 46 1900 50
4 32 2500 50 45 1900 50 47 1000 50 52 2000 50
3 46 1000 50 48 1100 50 49 1400 50
3 33 500 30 34 600 50 47 1100 50
4 36 1400 50 47 1400 50 50 500 50 52 700 50
3 37 1500 30 49 500 50 51 1000 50
3 39 500 50 50 1000 50 52 1300 50
2 49 700 50 53 200 50
4 39 1500 50 46 2000 50 52 200 50 54 800 50
3 53 800 50 55 1100 50 56 1500 50
3 39 1800 30 41 1100 50 54 1100 50
4 42 1400 50 43 1200 30 54 1500 50 55 800 30

Donc le dans le fichier texte, on retrouve d'abord l'ordre du graphe, puis chaque ligne représente un sommet : on a d'abord son nombre de successeurs, puis l'identifiant du successeur 1, deux informations (distance et vitesse), puis successeur 2 etc..

Donc voilà mon problème avec ça, c'est qu'à i = 33, mon programme n'affiche plus rien, alors que ce n'est pas le cas sur un autre pc.

24/02/2010, 04h02
Obsidian

Citation:

Envoyé par ALeX850

Tout d'abord, merci pour ta réponse. Mais il y a plusieurs points que je ne comprends pas

Lesquels ?

Citation:

comme tu dois le voir je ne maîtrise pas vraiment les pointeurs..

Ce n'est pas une fatalité. Un pointeur est avant tout une variable comme une autre et s'utilise de la même façon. Son contenu est la représentation d'une adresse en mémoire, soit l'emplacement de quelque chose d'autre.

Citation:

Donc voilà mon problème avec ça, c'est qu'à i = 33, mon programme n'affiche plus rien, alors que ce n'est pas le cas sur un autre pc.

C'est tout-à-fait fortuit et intermittent. Il peut se passer n'importe quoi. Sur ma machine, par exemple, la boucle fait bien ses 57 tours, mais le programme plante juste après. Il se peut tout-à-fait que le débordement de ton tableau fasse que tu ailles écrire directement dans les variables qui servent à contrôler ta boucle.

D'ailleurs, quels outils utilises-tu pour savoir que ton programme bloque à 33 tours ? Je ne vois aucun print dans ton programme hormis celui qui sert à l'ouverture du fichier.

D'autre part, il y a beaucoup de malloc() dans ton code, mais aucun free() pour le moment…
24/02/2010, 12h08
diogene
Des incohérences :
1-
Code:

1 2 3 4 5 6 int main(int argc, char** argv) { T_sommet **Graphe; int ordre = 0; Graphe = Construction_Graphe(Graphe, &ordre); .....
Lors de l'appel à Construction_Graphe(), Graphe n'est pas initialisé. Ou il ne sert à rien de passer Graphe à la fonction, ou ça va planter !

2-
Code:

1 2 3 T_sommet **Construction_Graphe(T_sommet **Graphe, int *ordre){ .... Graphe = (T_sommet**)malloc(sizeof(T_sommet*));
Réponse à la question précédente : le paramètre Graphe ne sert à rien (puisque la valeur transmise n'est pas utilisée mais écrasée) et devrait être une variable locale;

3-
Code:

1 2 3 4 for(i=0 ; i<(*ordre) ; i++){ printf("sommet %d\n", i); Graphe[i] = (T_sommet*)malloc(sizeof(T_sommet)); Graphe[i] = NULL;
Le malloc ne sert à rien d'autre que faire une fuite de mémoire puisque Graphe[i] est aussitôt écrabouillé par NULL