Aller au contenu

Implémentation de structures de données en C++ : listes chaînées, piles et files

Fiche de révision · Numérique et sciences informatiques · Term

L'essentiel du cours

  1. Chapitre 1 : Structures linéaires et pointeurs en C++

    Un pointeur permet de relier dynamiquement des éléments en mémoire.

  2. Chapitre 2 : Implémenter une liste chaînée

    L'insertion et la suppression en tête d'une liste chaînée se font en temps constant O(1).

  3. Chapitre 3 : Implémenter une pile

    Dans une pile, toutes les opérations se font au sommet, en O(1) avec une liste chaînée.

  4. Chapitre 4 : Implémenter une file

    Une file utilise deux pointeurs (tête et queue) pour des opérations en O(1).

Teste-toi · 8 questions

  1. 1.Quelle structure suit le principe LIFO ?

    Voir la réponse

    Réponse : Pile

    Une pile est LIFO (Last In, First Out) : le dernier élément inséré est le premier retiré.

  2. 2.Dans une liste chaînée simple, que contient le champ suivant du dernier nœud ?

    1. A.nullptr
    2. B.rien
    3. C.zéro
    4. D.l'adresse de la tête
    Voir la réponse

    Réponse A : nullptr

    Le dernier nœud pointe vers nullptr pour indiquer la fin de la liste.

  3. 3.Quelle opération n'est pas une opération de pile ?

    Voir la réponse

    Réponse : enqueue

    enqueue (enfiler) est une opération de file, pas de pile. Les opérations de pile sont push, pop et top.

  4. 4.Pour une file implémentée avec une liste chaînée, quels pointeurs sont nécessaires ?

    Voir la réponse

    Réponse : tête et queue

    Il faut un pointeur vers la tête pour défiler et un pointeur vers la queue pour enfiler en O(1).

  5. 5.L'insertion en tête d'une liste chaînée est en ?

    Voir la réponse

    Réponse : O(1)

    On modifie seulement deux pointeurs, indépendamment de la taille de la liste, donc complexité constante O(1).

  6. 6.Quel mot-clé C++ alloue dynamiquement un objet ?

    Voir la réponse

    Réponse : new

    En C++, l'opérateur new alloue dynamiquement de la mémoire et appelle le constructeur si nécessaire. malloc est du C.

  7. 7.Que se passe-t-il si on dépile une pile vide ?

    Voir la réponse

    Réponse : erreur ou comportement indéfini

    Dépiler une pile vide revient à déréférencer un pointeur nul ou accéder hors limites, ce qui provoque une erreur ou un comportement indéfini.

  8. 8.Quelle structure est adaptée pour un historique de navigation (bouton retour) ?

    Voir la réponse

    Réponse : Pile

    Le bouton retour revient à la page précédente, c'est-à-dire la dernière visitée : comportement LIFO d'une pile.