Corrigé 6. Enoncé
1. Une version du chaînage séparé
Structures de données
TYPE S = STRUCTURE
Val : Typeqq
Suiv : POINTEUR(S)
FIN
TYPE TYPE_Elément = STRUCTURE
Elément : Typeqq
Pt : POINTEUR(S)
FIN
VAR T : TABLEAU(0..M-1) DE TYPE_Elément
Etape d'initialisation
Soit Vide une valeur particulière désignant le vide.
POUR I = 0, M-1
T(I) := ( Vide, NIL )
FINPOUR
Ecriture des modules R, I, S
Soient Val(I) , Liste(I) , Aff_Val(I, Val) et Aff_Liste(I, L) des opérations définies
comme suit :
Val(I)
: Val := T(I).élément
Liste(I)
: Liste := T(I).Pt
Aff_Val(I, Val) : T(I).élément := Val
Aff_Liste(I, L) : T(I).Pt := L
Module R
I := H(Donnée) { H désigne la fonction de hachage}
SI Val (I) = Vide :
Rech := FAUX
SINON
SI Val(I) = Donnée :
Rech := VRAI
SINON
L := Liste(I)
Rech := FAUX
(1)
TANTQUE NON Rech ET L
<> NIL : (3)
SI Valeur(L) = Donnée : (4)
Rech := VRAI
SINON L := Suivant(L) FSI (2)
FINTANTQUE
FSI
FSI
Module I
Le module R positionne Rech à VRAI si Donnée existe, FAUX sinon. I désigne la classe de
l'élément recherché.
R( Donnée, Rech, I) :
SI Rech :
" La Donnée existe "
SINON
SI Val(I) = Vide:
Aff_Val(I, Donnée)
SINON { Insertion au début }
(1)
Allouer (Q,S)
Aff_Val(Q, Donnée)
Aff_Adr(Q, Liste(I))
Aff_Liste(I, Q)
FSI
FSI
Module S
Le module R positionne Rech à VRAI si Donnée existe, FAUX sinon. I désigne la classe de
l'élément recherché. L désigne le pointeur du maillon à supprimer et Prec son
précédent.
Pour avoir Prec, il suffit de faire " Prec := L " avant (1) et (2) dans le
module Recherche.
R(Donnée, Rech, I, L, Prec) :
SI NON Rech :
" La Donnée n'existe pas "
SINON
SI Val(I) = Donnée
SI Liste(I) = NIL :
Aff_Val(I, Vide)
SINON
Q := Liste(I)
Aff_Val(I, Valeur(Liste(I)) )
Aff_Liste(I, Suivant(Liste(I)) )
Libérer (Q)
FSI
SINON {L est le pointeur de la donnée à
supprimer}
SI Prec = Liste(I)
Aff_Liste(I, Suivant(L) )
SINON
Aff_Adr(Prec, Suivant(L) )
FSI
Libérer (L)
FSI
FSI
Modifications sur les algorithmes R, I et S si on désire maintenir
la liste des débordements triée
Module R'
Il suffit de remplacer (3) par
TANTQUE L <> NIL ET NON Trouv ET NON Arret
avec Arret initialisée à FAUX.
et l'alternative (4) par
SI Valeur(L) = Donnée :
Trouv := VRAI
SINON
SI Valeur(L) > Donnée { Liste ordonnée
croissante }
Arret := FAUX
SINON L := Suivant(L) FSI
FSI
Module I'
Le module R positionne Rech à VRAI si Donnée existe, FAUX sinon. I désigne la classe de
l'élément recherché. Dans le cas o� Rech est FAUX, L désigne le pointeur du maillon
dont la valeur est supérieure à Donnée et Prec son précédent.
L'appel se fera par R'(Donnée, Rech, I, L, Prec)
Remplacer la partie Sinon (1) dans le module I par
SINON
Allouer (Q, S)
Aff_Val(Q, Donnée)
SI Prec = Liste(I)
Aff_Adr(Q, Liste(I))
Aff_Liste(I,Q)
SINON
Aff_Adr(Q,L)
Aff_Adr(Prec,Q)
FSI
Module S'
Reste inchangé.
Ecriture des modules R", I" et S"
Pour plus de commodité, remplaçons Liste(i) par Arbre(i) et Aff_Liste(I, L) par
Aff_Arbre(I, L).
Module R''
I := H(Donnée)
SI Val (I) = Vide :
Rech := FAUX
SINON
SI Val(I) = Donnée :
Rech := VRAI
SINON
L := Arbre(I)
Rech := FAUX
TANTQUE NON Rech ET L
<> NIL :
SI Info(L) = Donnée :
Rech := VRAI
SINON
SI Donnée < Info (L)
L := Fg(L)
SINON
L := Fd(L)
FSI
FSI
FINTANTQUE
FSI
FSI
Module I"
Prec désigne la dernière valeur de L <> NIL dans le cas o� Donnée n'existe pas.
Dans R", il suffit de sauvegarder dans Prec la valeur de L avant les affectations
"L:=Fg(L)" et "L:=Fd(L)".
R"( Donnée, Rech, I, L, Prec)
SI Rech :
" La Donnée existe "
SINON
SI Val(I) = Vide:
Aff_Val(I, Donnée)
SINON
{Prec est le maillon
pour lequel on a créé un fils}
{ Existe-t-il un arbre
de débordement ? }
SI Arbre(I) = NIL :
Aff_Arbre(I,Créernoeud(Donnée)
SINON
SI Donnée < Info(Prec)
Aff_Fg(Prec,Créernoeud(Donnée) )
SINON
Aff_Fd(Prec,Créernoeud(Donnée))
FSI
FSI
FSI
FSI
Module S"
R"(Donnée, Rech, I, L, Prec)
SI NON Rech :
" La Donnée n'existe pas "
SINON
SI Val(I) = Donnée
SI Arbre(I) = NIL :
Aff_Val(I, Vide)
SINON
Aff_Val(I, Info(Arbre(I))
Supprimer (I, Arbre(I),Prec, Racine )
SI Racine = NIL : Aff_Arbre(I, NIL) FSI
FSI
SINON
Supprimer(I, L, Prec,
Racine)
SI Racine = NIL :
Aff_Arbre(I, NIL) FSI
FSI
FSI
Le module Supprimer (I, L, Prec, Racine ) est défini comme suit :
I désigne la classe de l'élément à supprimer, L le nœud à supprimer et Prec son
père si L n'est pas la racine. Ce module rend dans Racine la valeur NIL si après
suppression l'arbre devient vide.
Q := L { Pour la libération du maillon supprimé}
SI Fg(L)=NIL ET Fd(L)=NIL
SI Prec = NIL
Racine := NIL
SINON
SI Fg(Prec) = L :
Aff_Fg(Prec, NIL)
SINON Aff_Fd(Prec, NIL)
FSI
FSI
SINON
SI Fg(L) = NIL
SI Prec = NIL :
Racine := Fd(L)
SINON
SI Fg(Prec) = L : Aff_Fg(Prec, Fd(L))
SINON Aff_Fd(Prec, Fd(L)) FSI
FSI
SINON
SI Fd(L) = NIL
SI Prec = NIL :
Racine := Fg(L)
SINON
SI Fg(Prec) = L : Aff_Fg(Prec, Fg(L))
SINON Aff_Fd(Prec, Fg(L)) FSI
FSI
SINON { Chercher le
plus petit descendant du sous arbre droit du noeud L }
P:= L
Q := Fd(L)
TANTQUE Fg(Q) <> NIL :
P :=Q
Q := Fg(Q)
FINTANTQUE
Aff_Info(L, Info(Q))
Aff_Fd(P, Fd(Q) )
FSI
FSI
FSI
Libérer (Q)
Estimation du temps moyen pour les algorithmes R, R' et R"
R : n / M
R': < n / M
R": log2(n/M)