3MMALG11 Soutien S07

Cette page est maintenue uniquement par les enseignants. Afin de ne pas perturber le déroulement des cours, elle n'a pas vocation à être modifiée par les élèves. Mais si vous avez des modifications à proposer, merci d'en discuter ou d'envoyer un e-mail aux auteurs de la page (cf. historique)

On va travailler pendant cette séance sur des exercices de base sur les listes chaînées. On testera les procédures demandées grâce au programme principal suivant (à copier-coller dans un fichier s07_e1.adb) :

with Ada.Text_IO, Ada.Integer_Text_IO, Ada.Unchecked_Deallocation;
use Ada.Text_IO, Ada.Integer_Text_IO;

procedure S07_E1 is

    type Cellule;
    --  Une liste est definie comme un pointeur sur la premiere cellule
    type Liste is access Cellule;
    type Cellule is record
        Val: Natural;
        Suiv: Liste;
    end record;

    procedure Liberer is new Ada.Unchecked_Deallocation(Cellule, Liste);

    -- Affiche les valeurs des cellules de la liste
    procedure Afficher(L: Liste) is
    begin
        null; -- a completer !
    end;

    -- Insere en tete de la liste une cellule contenant la valeur passee
    --   en parametre
    procedure InsererTete(L: in out Liste; V: Natural) is
    begin
        null; -- a completer !
    end;

    -- Inserer en queue de la liste une cellule contenant la valeur
    --   passee en parametre
    procedure InsererQueue(L: in out Liste; V: Natural) is
    begin
        null; -- a completer !
    end;

    -- Detruit chaque cellule de la liste passee en parametre et
    --   affecte le pointeur L a null
    procedure Vider(L: in out Liste) is
    begin
        null; -- a completer !
    end;

    -- Inverse la liste passee en parametre
    procedure Inverser(L: in out Liste) is
    begin
        null; -- a completer !
    end;

    -- Supprime la premiere cellule trouvee contenant la valeur
    --   passee en parametre. Ne change rien si la liste ne contient
    --   aucune cellule ayant cette valeur
    procedure SupprimerPremOcc(L: in out Liste; V: Natural) is
    begin
        null; -- a completer !
    end;

    -- Insere une cellule contenant la valeur passee en parametre a
    --   sa place dans une liste triee par ordre croissant
    procedure InsererTriee(L: in out Liste; V: Natural) is
    begin
        null; -- a completer !
    end;    

    L: Liste;

begin
    L := null; Afficher(L); Inverser(L); Afficher(L);
    InsererTete(L, 3); Afficher(L); Inverser(L); Afficher(L);
    InsererQueue(L, 4); Afficher(L); Inverser(L); Afficher(L);
    InsererTete(L, 5); Afficher(L); InsererQueue(L, 2); Afficher(L);
    Inverser(L); Afficher(L); InsererTete(L, 1); Afficher(L);
    SupprimerPremOcc(L, 3); Afficher(L); SupprimerPremOcc(L, 10); Afficher(L);
    SupprimerPremOcc(L, 1); Afficher(L); SupprimerPremOcc(L, 5); Afficher(L);
    SupprimerPremOcc(L, 2); Afficher(L);
    InsererTriee(L, 3); Afficher(L); InsererTriee(L, 1); Afficher(L);
    InsererTriee(L, 5); Afficher(L); InsererTriee(L, 2); Afficher(L);
    Vider(L); Afficher(L);
    InsererTriee(L, 0); Afficher(L); SupprimerPremOcc(L, 0); Afficher(L);
end;

Même lorsque ce n'est pas précisé dans l'énoncé, on considèrera qu'on a toujours les contraintes suivantes quand on travaille sur des listes chaînées :

• on doit travailler en place, c'est à dire sans allouer de nouvelle cellule (sauf si l'exercice le demande), à part un éventuel élément fictif en tête de liste, servant à éviter de dissocier le cas de la liste vide, et qu'on détruira toujours à la fin de la procédure ;
• on travaillera toujours par manipulation de pointeurs, sans recopier le contenu des champs contenant les valeurs des cellules ;
• on doit toujours garantir que les procédures écrites fonctionnent même si la liste est vide (c'est à dire si on passe un pointeur valant null ;
• on doit chercher à effectuer le moins de parcours possibles de la liste initiale.

Il est impératif de faire des dessins pour bien aborder les problèmes sur les listes chaînées : sur une copie d'examen, un dessin illustrant les manipulations de pointeurs sera valorisé, et pourra même compenser des erreurs d'inattention dans l'écriture du code.