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.