DS 4 (MP2I 2021-2022) — Listes chaînées en C¶

Devoir surveillé · MP2I · 2021-2022 · partie I du DS 4 (3 h au total)

Autres parties : II. Pavages par dominos et placement des espaces

Consignes

Tout document interdit. Tout dispositif électronique interdit.

On vous demande d'écrire lisiblement et de bien présenter. Les programmes en particulier doivent être bien indentés et lisibles. Utilisez de préférence plusieurs couleurs. Commentez votre code dès que ce qu'il fait n'est pas évident.

Avant chaque fonction compliquée à écrire, ou quand vous n'y arrivez pas, indiquez avec des phrases ce que vous voulez faire. Cela permet de vous donner éventuellement des points si l'idée était bonne ou si vous y êtes presque.

A link to a past TP¶

On va reprendre le type des listes chaînées en C :

struct maillon {
    int valeur;
    struct maillon *suivant;
};

typedef struct maillon maillon;

struct liste {
    maillon *debut;
    maillon *fin;
};

typedef struct liste liste;

Dans un maillon, soit suivant pointe vers le maillon suivant de la chaîne ou vaut NULL.
La liste vide aura la valeur NULL pour debut et fin.
Dans une liste non vide, debut pointe sur le premier maillon et fin sur le dernier.

On suppose définies des fonctions

// cree un maillon
maillon *creer_maillon(int valeur, maillon *suivant);
// supprime un maillon
void suppr_maillon(maillon *);
// cree une liste vide
liste *creer_liste(void);
// supprime une liste
void suppr_liste(liste *);

Question 1

Écrire une fonction de prototype

int longueur(liste *);

qui renvoie la longueur d'une liste.

Corrigé

int longueur(liste *l)
{
    int n = 0;
    maillon *m = l->debut;
    while(m != NULL)
    {
        n++;
        m = m->suivant;
    }
    return n;
}

Question 2

Écrire une fonction de prototype

int somme(liste *);

qui renvoie la somme des valeurs des éléments d'une liste.

Corrigé

int somme(liste *l)
{
    int s = 0;
    maillon *m = l->debut;
    while(m != NULL)
    {
        s = s + m->valeur;
        m = m->suivant;
    }
    return s;
}

Question 3

Écrire une fonction de prototype

void liste_ajout_en_tete(liste *l, int valeur);

qui ajoute un maillon en tête de la liste passée en paramètre en \(O(1)\).

On fera attention au cas où la liste est vide.

Corrigé

void liste_ajout_en_tete(liste *l, int valeur)
{
    l->debut = creer_maillon(valeur, l->debut);
    if (l->fin == NULL)
        l->fin = l->debut;
}

Question 4

Écrire une fonction de prototype

maillon *liste_cherche_maillon(liste *l, int valeur);

qui renvoie un pointeur sur le premier maillon de valeur valeur ou renvoie NULL s'il n'y en a pas.

Corrigé

maillon *liste_cherche_maillon(liste *l, int valeur)
{
    maillon *m = l->debut;
    while(m != NULL && m->valeur != valeur)
    {
        m = m->suivant;
    }
    return m;
}

Question 5

Écrire une fonction de prototype

void liste_ajout_maillon_apres(liste *l, maillon *m, int valeur);

qui insère en \(O(1)\) un maillon après le maillon m. On fera en sorte que l'insertion soit valide même si m est le dernier maillon de la liste.

Corrigé

void liste_ajout_maillon_apres(liste *l, maillon *m, int valeur)
{
    m->suivant = creer_maillon(valeur, m->suivant);
    if (l->fin == m)
        l->fin = m->suivant;
}

Question 6

Expliquer comment cette structure permet d'implémenter une pile et donner les différentes complexités des opérations de la structure liste.

Corrigé

L'ajout et la suppression en tête sont en \(O(1)\).