QCM Listes C

De Ensiwiki
Aller à : navigation, rechercher

Pour ce QCM, on considère une structure de liste chainée définie par :

struct cell {
    int val;
    struct cell *next;
};

Une « liste » est de type struct cellule *, la liste vide est représentée par NULL

1. Pour insérer un élément en tête de liste, on considère les fonctions suivantes :

void push_front_1(struct cell *l, int val) {
    struct cell *first = malloc(sizeof(struct cell));
    first->val = val;
    first->next = l;
    l = first;

}

void push_front_2(struct cell **l, int val) {
    struct cell *first = malloc(sizeof(struct cell));
    first->val = val;
    first->next = *l;
    *l = first;

}

void push_front_3(struct cell **l, int val) {
    if (*l != NULL) {
        struct cell *first = malloc(sizeof(struct cell));
        first->val = val;
        first->next = *l;
        *l = first;

    }
}

struct cell * push_front_4(struct cell *l, int val) {
    struct cell *first = malloc(sizeof(struct cell));
    first->val = val;
    first->next = l;
    return first;

}

void push_front_5(struct cell **l, int val) {
    struct cell first;
    first.val = val;
    first.next = *l;
    *l = &first;

}

Cocher la ou les implémentation(s) correcte(s).

push_front_1
Non, cette fonction modifie l localement (dans la fonction), mais la liste passée en argument par l'appelant n'est pas modifiée.
push_front_2
Oui, la double indirection est nécessaire pour matérialiser le faitqu'on passe un pointeur par adresse.
push_front_3
Non, le test sur la liste vide n'est pas nécessaire (un cas particulier ou une sentinelle serait nécessaire pour une insertion en fin de liste), et même incorrect: avec cette version, on n'ajoute pas la valeur si la liste était vide au départ.
push_front_4
C'est une solution un peu détournée, mais cette version ajoute une cellule en tête de l sans modifier l, puis renvoie la nouvelle liste. On peut l'utiliser avec
liste = push_front_4(liste, 42);
push_front_5
Surtout pas. Cette version va bien modifier la liste, mais la cellule ajoutée est allouée sur la pile, et sera donc écrasée au prochain appel de fonction !

2. Pour libérer la mémoire allouée par une liste, on considère les fonctions suivantes :

void free_list_1(struct cell *l) {
    free(l);

}

void free_list_2(struct cell *l) {
    free(l->next);
    free(l->val);

}

void free_list_3(struct cell *l) {
    for (; l != NULL; l = l->next) {
        free(l);

    }
}

void free_list_4(struct cell *l) {
    while (l != NULL) {
        struct cell *next = l->next;
        free(l);
        l = next;

    }
}

void free_list_5(struct cell *l) {
    while (l != NULL) {
        struct cell *tmp = l;
        l = l->next;
        free(tmp);

    }
}

Cocher la ou les implémentation(s) correcte(s).

free_list_1
Non, cette fonction ne désalloue que la première cellule.
free_list_2
Cette version n'a aucun sens : la fonction free doit être appelée sur un pointeur, on ne peut pas l'appeler sur list->val qui n'en est pas un.
free_list_3
Presque, mais cette version fait un « use-after-free » : on appelle free(l) pour libérer la mémoire pointée par l, puis on exécute l = l->next qui fait un accès à l->next, qui vient d'être libérée.
free_list_4
Oui, c'est la solution classique : on stocke la valeur de
free_list_5
Variante correcte de free_list_4. Peut-être un peu moins lisible.

Votre pointage est 0 / 0