3MMALG11 Soutien S08

Correction des procédures SupprimerPremOcc et InsererTriee

On utilise dans ces procédures la technique de l'élément fictif en tête de liste, qui permet d'éviter de dissocier des cas particuliers (liste vide et gestion du premier élément de la liste).

   --  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
      Prec: Liste;
      Fictif: Liste;
      Tmp: Liste;
   begin
      Fictif := new Cellule; Fictif.Suiv := L;
      Prec := Fictif;
      while Prec.Suiv /= null and then Prec.Suiv.Val /= V loop
         Prec := Prec.Suiv;
      end loop;
      if Prec.Suiv /= null then
         Tmp := Prec.Suiv;
         Prec.Suiv := Prec.Suiv.Suiv;
         Liberer(Tmp);
      end if;
      L := Fictif.Suiv;
      Liberer(Fictif);
   end SupprimerPremOcc;

   --  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
      Prec: Liste;
      Fictif: Liste;
   begin
      Fictif := new Cellule; Fictif.Suiv := L;
      Prec := Fictif;
      while Prec.Suiv /= null and then Prec.Suiv.Val <= V loop
         Prec := Prec.Suiv;
      end loop;
      Prec.Suiv := new Cellule'(V, Prec.Suiv);
      L := Fictif.Suiv;
      Liberer(Fictif);
   end InsererTriee;

Tri de listes chainées

On va travailler aujourd'hui sur l'implantation de deux algorithmes de tri classiques sur les listes chainées.

Pour tester les procédures, on pourra utiliser le programme suivant (à copier-coller dans un fichier s08_e1.adb :

with Ada.Text_IO, Ada.Unchecked_Deallocation, Ada.Numerics.Discrete_Random;
use Ada.Text_IO;

procedure S08_E1 is

   type Cellule;
   type Liste is access Cellule;
   type Cellule is record
      Val: Character;
      Suiv: Liste;
   end record;

   Taille_Max: constant Natural := 5;
   subtype Indice is Integer range 1 .. Taille_Max;
   package Aleatoire is new Ada.Numerics.Discrete_Random(Indice);
   use Aleatoire;
   G: Generator;

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

   procedure Creer(S: String; L: out Liste) is
   begin
      L := null;
      for I in reverse S'Range loop
         L := new Cellule'(S(I), L);
      end loop;
   end Creer;

   procedure Detruire(L: in out Liste) is
      Suiv: Liste;
   begin
      while L /= null loop
         Suiv := L.Suiv;
         Liberer(L);
         L := Suiv;
      end loop;
   end Detruire;

   procedure Afficher(L: Liste) is
      Cour: Liste;
   begin
      Cour := L;
      while Cour /= null loop
         Put(Cour.Val & " -> ");
         Cour := Cour.Suiv;
      end loop;
      Put_Line("FIN");
   end Afficher;

   procedure Trier_Max(L: in out Liste) is
   begin
      null; --  A COMPLETER !
   end Trier_Max;

   procedure Trier_Ins(L: in out Liste) is
   begin
      null; -- A COMPLETER !
   end Trier_Ins;

   procedure Test(Taille: Natural; Max: Boolean) is
      S: String(1 .. Taille);
      L: Liste;
   begin
      for N in 0 .. Taille loop
         for I in S'Range loop
            S(I) := Character'Val(Character'Pos('A') + Random(G) - 1);
         end loop;
         Creer(S, L); Afficher(L);
         if Max then
            Trier_Max(L);
         else
            Trier_Ins(L);
         end if;
         Afficher(L); New_Line;
         Detruire(L);
      end loop;
   end Test;

begin
   Reset(G);
   Put_Line("-- Tri par recherche du maximum --");
   for I in 0 .. 5 loop
      Test(I, True);
   end loop;
   New_Line; New_Line;
   Put_Line("-- Tri par insertion en place --");
   for I in 0 .. 5 loop
      Test(I, False);
   end loop;
end S08_E1;

Tri par recherche du maximum

On va travailler dans cet exercice sur un tri simple, le tri par recherche du maximum, qu'on va appliquer à des listes chaînées de caractères.

On veut trier la liste par ordre croissant (la relation d'ordre sera simplement l'ordre alphabétique sur les caractères).

Indication : il faut réfléchir en considérant qu'on va à chaque tour de boucle :

• rechercher l'élément maximum de la liste ;
• le supprimer de la liste source et l'insérer en tête de la liste destination.

Bien sûr, on doit faire cela sans allouer de cellule (à part éventuellement un fictif en tête) ni recopier le contenu des cellules.

Tri par insertion en place

On va maintenant trier la liste selon l'algorithme du tri par insertion.

On veut cette fois trier la liste par ordre décroissant.

Indication : il faut réfléchir en considérant qu'on va à chaque tour de boucle :

• rechercher l'endroit où insérer l'élément courant dans la liste destination ;
• insérer l'élément courant à sa place dans la liste destination en l'enlevant au passage de la liste source.