Aller au contenu

DS 5 — Listes chaînées

MP2I, année scolaire 2022-2023, devoir surveillé du 11 mars 2023. Durée totale 4h.

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.

L'introduction et l'utilisation de fonctions auxiliaires est autorisée, et même encouragée, d'autant plus si cela améliore la lisibilité et la compréhension. Les fonctions auxiliaires doivent être précédées de leur type (en OCaml) et commentées.

Lorsque l'on pose des hypothèses sur les arguments, il n'est pas nécessaire dans vos fonctions de le vérifier ni de prévoir le comportement si l'hypothèse est violée.

De nombreuses questions comportent une sous-question sur la complexité. On prendra garde à ne pas lire trop vite l'énoncé et à ne pas ainsi oublier de répondre à une partie de la question.

Le sujet comporte un premier exercice de reprise du cours et un problème découpé en plusieurs parties relativement indépendantes.

Attention : on rédigera chaque partie sur des copies séparées pour bien différencier les numéros des questions.

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 *);

Q.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;
}

Q.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;
}

Q.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;
}

Q.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;
}

Q.5 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)\), on s'en sert donc respectivement pour les opérations push et pop.