Note ajoutée depuis : un exercice de cours en Delphi/Pascal — le texte mentionne d'ailleurs « comme demandé par l'énoncé ». C'est le plus ancien billet technique de ces archives, et le seul en Pascal.
Il est intéressant de se pencher sur des cas réels pour comprendre l'utilité algorithmique. Cela nous parle beaucoup mieux avec un cas concret.
Je vous propose le cas suivant :
Imaginons un petit utilitaire qui permet de détecter les fichiers dupliqués sur votre ordinateur. 2 fichiers seront considérés comme dupliqués s'ils possèdent les mêmes noms et extensions, la même taille et la même date. Comment allez-vous gérer cela ? Étant donné que votre ordinateur a plusieurs milliers de fichiers à mettre en mémoire…
Une structure avec une table de hachage et une liste simplement chaînée semble être un bon compromis. Le projet de ce sujet est réalisé en application fenêtrée. TDirectoryOutline pour sélectionner le dossier dans lequel doit démarrer la recherche.
Découpage du projet
Ci-dessous un exemple de logiciel réalisé en Delphi.
UTABLE — L'unité UTable (U pour unité et Table pour table) gère les tableaux. Cette unité crée et introduit dans une liste (selon la clef du hachage).
UNIT2 — L'unité Unit2 est l'unité de la fenêtre 2 du programme. Cette fenêtre consiste à demander un message de confirmation lorsqu'on quitte la fenêtre par le menu. C'est du Delphi pur.
ULISTE — L'unité UListe gère les listes chaînées. Permet de créer, d'ajouter un élément dans une liste, vérifier si la liste est vide. Une fonction importante dans cette unité : l'affichage de la liste chaînée dans affiche_liste ! Qui affiche le résultat dans un TMemo (assez simple mais réellement pratique et rapide).
UCOEUR — L'unité UCoeur est requise au bon fonctionnement du programme, c'est le cœur du logiciel : parcourt un répertoire, prend les informations (taille, date, etc.) et les envoie aux fonctions (UTable) pour être mises dans la structure de données.
UCLEF — L'unité UClef gère la transformation de la clef de hachage et ses opérations. Une opération peut être de vérifier si les valeurs des clefs sont identiques (utile pour la structure d'une table de hachage) et ainsi ajouter dans la table ou juste afficher.
UATTRIBUT — L'unité UAttribut régit les informations des attributs et ses opérations. Identiquement à UClef mais aux attributs (chemin, déjà affiché). Contrairement à UClef, la méthode égale n'existe pas (il n'y a pas besoin de savoir si les valeurs des attributs sont égales).
MAIN — L'unité main a été conçue entièrement avec l'éditeur TextPad en langage Pascal. L'unité main.pas n'est pas employée dans l'interface graphique. Cette unité fonctionne uniquement en mode console.
FINDUP — L'unité Findup a été générée (en partie) par Delphi. On y retrouve la fenêtre graphique du programme principal. C'est-à-dire le TMemo, les boutons et les affichages divers.
UCoeur.pas
function nomcomplet(chemin, nom : string):string;
function taille(const chemin : String):int64;La fonction mémoire permet de parcourir les répertoires (sélectionnés par l'utilisateur) et d'envoyer les informations (clefs et attributs) dans l'unité UTable. On utilise d'autres procédures et fonctions qui transforment les attributs d'une clef ou d'un attribut en record.
function memoire(const chemin: string):int64;
const attr : Integer = faAnyFile - faVolumeID;
var SearchRec : TSearchRec;
encore : boolean;
compteur : integer;
begin
result := 0;
encore := findfirst(NomComplet(Chemin, '*.*'), attr, SearchRec) = 0;
compteur := 1;
while ((encore) and (compteur <= N)) do begin
if (SearchRec.attr and faDirectory) > 0 then begin
if (SearchRec.Name <> '.') and (SearchRec.Name <> '..') then
inc(Result, memoire(nomComplet(chemin, SearchRec.Name)));
end
else
Utable.ajouter(UClef.transforme_clef(SearchRec.Name, SearchRec.Size, SearchRec.Time),
UAttribut.transforme_attr(nomcomplet(chemin, SearchRec.Name), false), t);
encore := findnext(SearchRec) = 0;
end;
findclose(SearchRec);
end;UListe.pas
procedure creer(out l:liste);
function liste_vide(l:liste):boolean;La procédure affiche_liste permet d'afficher le résultat d'une liste simplement chaînée avec la condition de la vérification que les champs deja_affiche sont à false. Si le champ est à true, on n'affiche pas le résultat.
procedure affiche_liste (const l : liste);
var courant : liste;
begin
if (liste_vide(l)) then
else begin
courant := l;
while (courant <> nil) do
begin
if (not courant^.attribut.deja_affiche) then
Form1.Memo1.Lines.Add(courant^.clef.nom + ' ' + SizeToStr(courant^.clef.taille) + ' ' + DateToStr(FileDateToDateTime(courant^.clef.time)) + ' ' + courant^.attribut.chemin);
courant := courant^.svt;
end;
end;
end;La procédure ajouter_simple permet d'ajouter simplement une valeur dans une liste chaînée, si la liste n'existe pas (c'est-à-dire qu'elle est automatiquement vide). Si la liste existe, on n'insère pas l'élément (comme demandé par l'énoncé) mais on affiche le résultat directement. On informe la structure que ce résultat a déjà été affiché afin qu'on ne le réaffiche plus par la suite. On peut constater que j'utilise les différentes unités pour voir si une clef est égale ou non, pour la copie d'une clef ou d'un attribut. J'utilise la récursivité pour ajouter un élément dans une liste.
procedure ajouter_simple(const c:Tclef; a:Tattribut; var l:liste);
begin
if liste_vide(l) then
begin
new(l);
Uclef.copier(l^.clef, c);
Uattribut.copier(l^.attribut, a);
l^.svt := nil;
end
else if (UClef.egale(c, l^.clef)) then
begin
affiche_liste(l);
l^.attribut.deja_affiche := true;
Form1.Memo1.Lines.Add(c.nom + ' ' + SizeToStr(c.taille) + ' ' + DateToStr(FileDateToDateTime(c.time)) + ' ' + a.chemin);
end
else
begin
ajouter_simple(c, a, l^.svt);
end;
end;UTable.pas
procedure creer(out t : table);
function hachage(c : tclef):cardinal;
procedure ajouter(c:tclef; a:tattribut; var t:table);
begin
Uliste.ajouter_simple(c, a, T[hachage(c)]);
end;UClef.pas
procedure copier(var c:Tclef; d:Tclef);
function egale(c,d : Tclef):boolean;
function SizeToStr(const Size : int64) : string;Un exemple de fonction qui transforme une clef en record.
function transforme_clef (nom:string; taille:integer; ttime:integer) : Tclef;
var a : tclef;
begin
a.nom := nom;
a.taille := taille;
a.time := ttime;
result := a;
end;La fonction de hachage qui utilise le nom, la taille et la date du fichier.
function clef(c:Tclef):cardinal;
var k : integer;
begin
Result := 0;
for k := 1 to length(c.nom) do
inc(Result, Ord(c.Nom[k]));
inc(Result, c.Taille);
inc(Result, c.Time);
end;UAttribut.pas
function transforme_attr (chemin:string; deja_affiche:boolean):Tattribut;
procedure copier(var a: Tattribut; b:Tattribut);Findup.pas
procedure TForm1.DirectoryListBox1Click(Sender: TObject);
procedure TForm1.DriveComboBox1Change(Sender: TObject);
procedure TForm1.DirectoryListBox1Change(Sender: TObject);La procédure Button1Click est générée par Delphi. Après une édition afin d'envoyer les paramètres au cœur afin que cette unité puisse traiter les données.
procedure TForm1.Button1Click(Sender: TObject);
begin
ProgressBar1.Visible := true;
Button1.Enabled := false;
UTable.creer(t);
ProgressBar1.Position := 1;
Ucoeur.memoire(DirectoryListBox1.Directory);
ProgressBar1.Position := 50;
Button1.Enabled := true;
ProgressBar1.Position := 100;
showmessage('La recherche est terminée !');
end;À noter que c'est un exemple de logiciel simpliste pour que tout le monde puisse comprendre.
Pour les perfectionnistes, la table de hachage n'est pas du tout parfaite. Elle donnera énormément de doublons et cela prendra beaucoup plus de temps à parcourir la liste chaînée !