Corrigé Mines-Ponts 2026 Informatique II MPI — Partie 2 (2.1 et 2.2) (Q6 à Q19) : Le monde en mémoire : listes chaînées et représentation CSR

Tous les programmes de cette partie ont été compilés (gcc -Wall -Wextra -std=c99, sans avertissement) et exécutés : on a construit en listes chaînées le monde de Q12, vérifié degrés, somme des degrés ($7$) et coût total ($23$) dans les deux représentations, et contrôlé que monde_vers_CSR redonne exactement les trois tableaux de l'énoncé ; cas limites : monde de $0$ salle, salles sans passage. L'outil leaks ne signale aucune fuite.

Q6. Trois niveaux d'allocation : la structure monde, le tableau de n pointeurs, puis chacune des n salles, dont on initialise les deux champs.

monde* monde_init(int n) {
    assert(n >= 0);
    monde* m = malloc(sizeof(monde));
    assert(m != NULL);
    m->taille = n;
    m->salles = malloc(n * sizeof(salle*));
    assert(n == 0 || m->salles != NULL);
    for (int i = 0; i < n; i++) {
        m->salles[i] = malloc(sizeof(salle));
        assert(m->salles[i] != NULL);
        m->salles[i]->id = i;           /* id = indice dans le tableau */
        m->salles[i]->passages = NULL;  /* liste de passages vide */
    }
    return m;
}

Le tableau contient des salle*, d'où sizeof(salle*) ; chaque salle est une salle, d'où sizeof(salle). L'identifiant vaut l'indice, comme l'exige l'énoncé. (Le test n == 0 dans l'assertion tient compte de ce que malloc(0) peut renvoyer NULL.) Coût : $n+2$ allocations, $O(n)$.

Ce que le correcteur attend : l'allocation individuelle de chaque salle et la mise à NULL des listes ; le jury a relevé l'oubli de l'une ou l'autre, et la confusion entre la taille d'une structure et celle d'un pointeur.

Q7. Parcours de la liste en suivant le champ suivant :

int monde_degre(monde* m, int s) {
    assert(m != NULL && 0 <= s && s < m->taille);
    int d = 0;
    for (passage* p = m->salles[s]->passages; p != NULL; p = p->suivant) {
        d++;
    }
    return d;
}

Invariant : d est le nombre de maillons déjà dépassés, ceux qui précèdent p. La boucle s'arrête quand p vaut NULL, donc après le dernier maillon : d est la longueur de la liste. Elle termine car la liste, construite par des allocations successives, est finie et acyclique. Coût $O(\mathrm{deg}s)$. La condition p->suivant != NULL oublierait le dernier maillon (et déréférencerait NULL sur une liste vide).

Q8. On réutilise monde_degre, comme demandé :

int monde_sommeDegres(monde* m) {
    assert(m != NULL);
    int total = 0;
    for (int s = 0; s < m->taille; s++) {
        total += monde_degre(m, s);
    }
    return total;
}

Chaque passage appartient à la liste de sa salle d'entrée et à elle seule : la somme des degrés sortants est le nombre de passages. Coût $O(ns+np)$.

Q9. Double boucle : sur les salles, puis sur la liste de chacune.

int monde_coutTotal(monde* m) {
    assert(m != NULL);
    int total = 0;
    for (int s = 0; s < m->taille; s++) {
        for (passage* p = m->salles[s]->passages; p != NULL; p = p->suivant) {
            total += p->cout;
        }
    }
    return total;
}

Chaque passage est vu une fois exactement (même argument qu'en Q8) ; coût $O(ns+np)$.