3MMALG11 Soutien S09

De Ensiwiki
Aller à : navigation, rechercher
AttentionCette 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 sur l'implantation d'une table de hachage. On donne le programme ci-dessous (à copier-coller dans un fichier s09_e1.adb :

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

procedure S09_E1 is

   subtype Valeur is Integer range 1 .. 9;
   package Aleat is new Ada.Numerics.Discrete_Random(Valeur); use Aleat;

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

   type Entree is record
      Nbr: Natural;
      Tete: Liste;
   end record;

   subtype Indice is Integer range 0 .. 3;
   type TableH is array(Indice) of Entree;
   type TableHachage is record
      Nbr: Natural;
      Table: TableH;
   end record;

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

   procedure Afficher(T: TableHachage) is
      procedure Afficher(L: Liste) is
         Cour: Liste;
      begin
         Cour := L;
         while Cour /= null loop
            Put(Cour.Val, Width=>0); Put(" -> ");
            Cour := Cour.Suiv;
         end loop;
         Put_Line("FIN");
      end Afficher;
   begin
      Put("Taille = "); Put(T.Nbr, Width=>0); New_Line;
      for I in T.Table'Range loop
         Put("["); Put(I, Width=>0); Put("] (");
         Put(T.Table(I).Nbr, Width=>0); Put(") : ");
         Afficher(T.Table(I).Tete.Suiv);
      end loop;
   end Afficher;

   function Hash(V: Valeur) return Indice is
   begin
      return (V mod (Indice'Last - Indice'First + 1)) + Indice'First;
   end Hash;

   procedure Init(T: in out TableHachage) is
   begin
      T.Nbr := 0;
      for I in T.Table'Range loop
         T.Table(I).Nbr := 0;
         T.Table(I).Tete := new Cellule;
         T.Table(I).Tete.Suiv := null;
      end loop;
   end Init;

   procedure Inserer(T: in out TableHachage; V: Valeur) is
   begin
      null; --  A COMPLETER !
   end Inserer;

   procedure Supprimer(T: in out TableHachage; V: Valeur) is
   begin
      null; --  A COMPLETER !
   end Supprimer;

   procedure Detruire(T: in out TableHachage) is
   begin
      null; --  A COMPLETER !
   end Detruire;

   G: Generator;
   T: TableHachage;
   X, Y: Natural;

begin
   Reset(G); Init(T);
   for I in 1 .. 15 loop
      Inserer(T, Random(G));
   end loop;
   Afficher(T); New_Line;
   while T.Nbr /= 0 loop
      X := T.Nbr; Y := Random(G);
      Supprimer(T, Y);
      if X /= T.Nbr then
         Put("Suppression : "); Put(Y, Width=>0); New_Line;
         Afficher(T); New_Line;
      end if;
   end loop;
   Detruire(T);
end S09_E1;

En lisant ce programme et notamment les déclarations de types et la procédure Init, dessinez la structure de la table de hachage manipulée dans ce programme.

Implantez ensuite les procédures d'insertion et de suppression dans la table, ainsi que la procédure de destruction de la table.