Discussion :

[Kenshin01]

Bonjour,

je vous contacte car je bloque sur ce code au niveau des enfiler et defiler. Voici la question

Dans un premier temps, vous utilisez votre code manipulant des listes doublement chaînées comme file d’attente. La terminologie : enfiler correspond à insérer (à vous de choisir la place) et défiler à supprimer de la liste tout en récupérant la valeur de la cellule (le numéro x du sommet).

Mon code :

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
 
// Procédure qui recherche le plus court chemin depuis un sommet de référence 
    // Paramètres : 
    // adjacence : matrice d’adjacence du graphe
    // ordre : nombre de sommets
    // s : numéro de sommet de référence 
    // l : tableau dynamique alloué des longueurs minimales des sommets depuis s
    // pred : tableau dynamique alloué des prédécesseurs des sommets 
 
    void plusCourtChemin (int**adjacence, int ordre, int s, int *l, int *pred) { // Variables locales
        int *marques ;
        int x, y ; 
        t_file *f ;
 
        // Allouer le tableau marques de taille « ordre »
            *p = malloc(sizeof(int) * ordre);
 
        // Initialiser les marquages et les longueurs minimales à 0
        for (x=0 ; x<ordre ; x++) {
            marques[x] = 0 ;
            l[x] = 0 ;
        }
 
        // Marquer le sommet s à 1
            marques[s] = 1 ;
 
        // Créer (allouer) la file f et enfiler s dans f
            ... (pas trouvé)
 
        while (…) { // Tant que la file f n’est pas vide
        … // Défiler le premier sommet x de la file f (PAS TROUVé)
 
        // Pour tous les sommets y adjacents à x et non marqués 
            for (y=0 ; y<ordre ; y++)
                if (adjacence[x][y] && !marques[y]) {
                    marques[y] = 1 ; // marquer le sommet y
                    … (PAS TROUVE) // enfiler le sommet y dans f 
                    pred[y] = x ; // x est le prédécesseur de y
                    l[y] = l[x]+1 ; // incrémenter la longueur de y
            }
        }
}

Et connaitre sa complexité mémoire.

Je bloque un peu la dessus.

Je ne sais pas ici si mon malloc a bien été utilisé ?

Voilà voilà en espérant que vous puissiez m'éclairer

[WhiteCrow]

Bonjour,

je vous contacte car je bloque sur ce code au niveau des enfiler et defiler. [...]

La meilleure des façons de ne pas bloquer sur ça est de créer une structure de données à part que tu pourras tester et appeler à volonté sans avoir besoin de tout réimplémenter à chaque fois que tu en auras besoin,.

[Kenshin01]

C'est a dire structure de donnée je n'ai pas très bien compris ?

[WhiteCrow]

Ton morceau devrait ressembler à :

Code :

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

1
2
3
4
5
6
7
8
 
// Créer (allouer) la file f et enfiler s dans f
file_t *file=file_creer();
file = file_enfiler(file, s);
 
while (! file_est_vide(file) ) { // Tant que la file f n’est pas vide
   sommet = file_defiler(file);
   …

où c'est à ta charge de créer la structure de donnée file_t qui est une simple file d'entiers, ainsi que toutes les primitives et fonctions d'accès …

[Kenshin01]

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
 
// Procédure qui recherche le plus court chemin depuis un sommet de référence
// Paramètres :
// adjacence : matrice d’adjacence du graphe
// ordre : nombre de sommets
// s : numéro de sommet de référence
// l : tableau dynamique alloué des longueurs minimales des sommets depuis s
// pred : tableau dynamique alloué des prédécesseurs des sommets
 
void plusCourtChemin (int**adjacence, int ordre, int s, int *l, int *pred) { // Variables locales
       int *marques ;
       int x, y ;
       t_file *f ;
 
      // Allouer le tableau marques de taille « ordre »
      *p = malloc(sizeof(int) * ordre);
 
      // Initialiser les marquages et les longueurs minimales à 0
      for (x=0 ; x<ordre ; x++) {
      marques[x] = 0 ;
      l[x] = 0 ;
      }
 
     // Marquer le sommet s à 1
     marques[s] = 1 ;
 
     // Créer (allouer) la file f et enfiler s dans f
     t_file *file=file_creer();
     file = file_enfiler(file, s);
 
     while (! file_est_vide(file)) { // Tant que la file f n’est pas vide
              sommet = file_defiler(file)// Défiler le premier sommet x de la file f
 
     // Pour tous les sommets y adjacents à x et non marqués
      for (y=0 ; y<ordre ; y++)
              if (adjacence[x][y] && !marques[y]) {
              marques[y] = 1 ; // marquer le sommet y
              file_enfiler(file, y) // enfiler le sommet y dans f
              pred[y] = x ; // x est le prédécesseur de y
              l[y] = l[x]+1 ; // incrémenter la longueur de y
             }
      }
}

Est ce que cette fois c'est bon au niveau de la structure ? Je pense avoir compléter le code mais je ne sais pas ?

Merci d'avance

[WhiteCrow]

Commence par écrire ta structure de données file … teste la … seulement ensuite tu pourras l'utiliser dans ton implémentation d'algo.

[Kenshin01]

Quand vous dites structure de données vous parler de créer une fonction file c'est ça?

[Kenshin01]

Commence par écrire ta structure de données file … teste la … seulement ensuite tu pourras l'utiliser dans ton implémentation d'algo.

Je n'arrive pas a effectuer une structure de données avec file. Je ne vois pas ce que je peux mettre pour que cela fonctionne?

[Kenshin01]

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
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
#include <stdio.h>
 
// Procédure qui recherche le plus court chemin depuis un sommet de référence 
    // Paramètres : 
    // adjacence : matrice d’adjacence du graphe
    // ordre : nombre de sommets
    // s : numéro de sommet de référence 
    // l : tableau dynamique alloué des longueurs minimales des sommets depuis s
    // pred : tableau dynamique alloué des prédécesseurs des sommets 
 
    typedef struct Element Element;
    struct Element
    {
        int nombre;
        Element *suivant;
    };
 
    typedef struct File File;
    struct File
    {
        Element *premier;
    };
 
    void file_enfiler(File *file, int nvNombre) {
        Element *nouveau = malloc(sizeof(*nouveau));
        if (file == NULL || nouveau == NULL) {
        exit(EXIT_FAILURE);
        }
 
        nouveau->nombre = nvNombre;
        nouveau->suivant = NULL;
 
        if (file->premier != NULL) { /* La file n'est pas vide */
 
            /* On se positionne à la fin de la file */
            Element *elementActuel = file->premier;
            while (elementActuel->suivant != NULL) {
                elementActuel = elementActuel->suivant;
            }
            elementActuel->suivant = nouveau;
        }
        else {/* La file est vide, notre élément est le premier */
            file->premier = nouveau;
        }
    }
 
    int file_defiler(File *file) {
        if (file == NULL) {
            exit(EXIT_FAILURE);
        }
 
        int nombreDefile = 0;
 
        /* On vérifie s'il y a quelque chose à défiler */
        if (file->premier != NULL) {
            Element *elementDefile = file->premier;
 
            nombreDefile = elementDefile->nombre;
            file->premier = elementDefile->suivant;
            free(elementDefile);
        }
 
        return nombreDefile;
 
    }
 
    void plusCourtChemin (int**adjacence, int ordre, int s, int *l, int *pred) { // Variables locales
        int *marques ; // tableau dynamique indiquant si les sommets sont marqués ou non
        int x, y ; // numéros de sommets intermédiaires
        t_file *f ; // file d’attente de sommets à créer en s’inspirant des listes doublement chaïnée avec un .h et un .c dédié
 
        // Allouer le tableau marques de taille « ordre »
            *p = malloc(sizeof(int) * ordre);
 
        // Initialiser les marquages et les longueurs minimales à 0
        for (x=0 ; x<ordre ; x++) {
            marques[x] = 0 ;
            l[x] = 0 ;
        }
 
        // Marquer le sommet s à 1
            marques[s] = 1 ;
 
        // Créer (allouer) la file f et enfiler s dans f
            t_file *file=file_creer();
            file = file_enfiler(file, s);
 
        while (! file_est_vide(file)) { // Tant que la file f n’est pas vide
                sommet = file_defiler(file); // Défiler le premier sommet x de la file f
        }
 
        // Pour tous les sommets y adjacents à x et non marqués 
            for (y=0 ; y<ordre ; y++)
                if (adjacence[x][y] && !marques[y]) {
                    marques[y] = 1 ; // marquer le sommet y
                    file_enfiler(file, y); // enfiler le sommet y dans f 
                    pred[y] = x ; // x est le prédécesseur de y
                    l[y] = l[x]+1 ; // incrémenter la longueur de y
                }
            }  
    }
 
int main() {
 
    return 0;
}

Rebonsoir ,voici mon code avec la structure file, je ne sais pas is c'est bon ou si il y a moyen de simplifier? maintenant j'aimerais savoir comment pouvoir tester cela car j'ai l'impression que cela ne marche pas?

En espérant que vous pourriez m'aider.

Cordialement.

[Kenshin01]

J'ai encore cherché ce matin pour le code mais je n'arrive toujours pas a le faire fonctionner..

[Galet]

Bonjour,

Je ne programme pas en C donc je ne peux te donner de code mais quelques explications sur ce que te conseille WhiteCrow :

Commence par écrire ta structure de données file … teste la … seulement ensuite tu pourras l'utiliser dans ton implémentation d'algo.

Tu dois remplir File_t avec des valeurs connues, un échantillon, au départ simple, des données que tu souhaites traiter.
Cet échantillon te servira à initialiser la File que tu souhaites traiter et à vérifier que ton "conteneur" (la structure de données) stocke correctement tes données (pas de mélange ou de perte d'info et accessibilité aux données correcte)

De cette manière, tu pourras
- gagner du temps car tes données serons initialisées automatiquement à chaque test de ton programme
- vérifier l'état de tes données avant et après chaque traitement que tu suspectes de contenir des erreurs
- vérifier que le bon résultat est ateint de manière répétable et stable.

Si tu as besoin d'aide, tu pourras aussi donner des indications sur le type de défaut rencontré pour être plus précis que "Ca ne marche pas". Il sera possible, sur le forum, de travailler avec les mêmes données que toi.

Une fois que ton programme fonctionnera sur ton échantillon simple, tu pourras facilement le tester en ajoutant des données, puis en validant les valeurs et nombres limites de données qui doivent être pris en compte (Ces valeurs sont souvent celles qui génèrent des défauts).
Tu pourras aussi, facilement, "blinder" ton programme en lui donnant des données incorrectes (pour simuler les erreurs de comportement de l'utilisateur). Il te faut aussi tester ton application avec une liste vide. Le but étant de signaler les erreurs plutôt que de laisser ton programme se "planter lamentablement".

Une fois que ton programme fonctionnera correctement, tu pourras continuer à utiliser ton ou tes échantillons représentatifs, à chaque modification, pour vérifier que tes modifications n'ont pas d'incidence sur le coeur de ton programme, et, pour finir, si tu confies ton programme à d'autres, tu pourras facilement trouver les solutions aux problèmes qu'ils pourront te remonter.

Voilà, ce conseil est utile pour tous les cas de traitement de données.

Bonne journée et bon courage,