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