3MMALG11 Soutien S07

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.