Corrigé 24. Enoncé
1. Fichiers sous forme de tableaux
Le fichier peut être schématisé comme suit :
Description de F
TYPE Typebloc = STRUCTURE
T : TABLEAU[1..B] DE Type1
Nb : ENTIER { Nombre d'articles}
Lien : Typeadresse
FIN
TYPE Type1 = STRUCTURE
Article : Typearticle
Effacé : Booléen
FIN
TYPE Typearticle = STRUCTURE
Clé : Typeclé
Info : Typeqq
FIN
TYPE Typeadresse = STRUCTURE
Numbloc : ENTIER
Têtelist : ENTIER
FIN
Description de F'
TYPE Typebloc' = STRUCTURE
T' : TABLEAU[1..M] DE Type2
Lien' : ENTIER
FIN
TYPE Type2= STRUCTURE
Article : Typearticle
Effacé : Booléen
Suiv : Typeadresse
FIN
Typeadresse et Typearticle sont déjà définis.
Module de chargement initial
POUR I = 1, M
J := 1
TANTQUE J/B <= & :
Lire(Article)
Buffer.T(J).Article :=
Article
Buffer.T(J).Effacé :=
FAUX
J := J + 1
FINTANTQUE
Buffer.Nb := J-1
Buffer.Lien := (NIL, -1)
Ecrirebloc(F, I, Buffer )
FINPOUR
Module de recherche
Nous utilisons les modules suivants :
Rechdicho : recherche dichotomique d'une clé sur le fichier F. Si la clé est trouvée, I
pointe le bloc contenant cette clé.
Rech : recherche dichotomique d'une clé sur le buffer (en RAM). Si la clé est trouvée,
J pointe la position dans le bloc de cette clé.
Rechlist : recherche d'une clé dans une liste linéaire chaînée contenue dans F'. Si la
clé est trouvée, K pointe l'entrée dans le bloc contenant cette clé.
Rechdicho(F, Clé, Trouv, I)
SI NON Trouv :
"Clé inexistante"
SINON { Le Bloc I est dans Buffer1 }
Rech(Buffer1, Clé, Trouv', J)
SI Trouv' :
SI NON
Buffer1.T(J).Effacé :
Article := Buffer1.T(J).Article
SINON " Clé
inexistante" FSI
SINON
SI Buffer1.Lien.Numbloc
= NIL :
"Clé inexistante"
SINON
Rechlist(Buffer1.Lien, Clé, Trouv",K)
SI Trouv" :
SI NON Buffer2.T'(K).Effacé :
Article := Buffer2.T'(K).Article
SINON "Clé inexistante" FSI
SINON "Clé inexistante "
FSI
FSI
FSI
FSI
Développons les modules Rechdicho et Rechlist.
Recherche dichotomique sur le fichier F
Trouv := FAUX
Bi := 1
Bs := M
TANTQUE Bi <= Bs ET NON Trouv :
Milieu := (Bi+Bs) DIV 2
Lirebloc(F, M, Buffer)
SI Buffer.T(1).Article.Clé <= Clé ET
Buffer.T(Buffer.Nb).Article.Clé >= Clé :
Trouv := VRAI
SINON
SI Clé <
Buffer.T(1).Article.Clé :
Bs := M - 1
SINON
Bi := M + 1
FSI
FSI
FINTANTQUE
Recherche dans la liste linéaire chaînée contenue dans F'
On a, en entrée :
Num :le numéro du bloc o� commence la liste et
L : la tête de liste dans ce bloc.
Trouv := FAUX
Lirebloc(F', Num, Buffer)
TANTQUE L # -1 ET NON Trouv :
SI Buffer.T'(L).Article.Clé = Clé :
Trouv := VRAI
SINON
L :=
Buffer.T(L).Suiv.Têtelist
SI
Buffer.T(L).Suiv.Numbloc # Num :
Num := Buffer.T(L).Suiv.Numbloc
Lirebloc(F, Num, Buffer)
FSI
FSI
FINTANTQUE
Module de suppression
C'est exactement comme le module de recherche sauf qu'au lieu de récupérer l'article on
fait un effacement logique. De plus, on rajoute comme paramètre dans le module Rechlist
le numéro du bloc o� se trouve la clé recherchée. Comme il s'agit d'une suppression
logique, le champ Nb du bloc n'est pas décrémenté.
Rechdicho(F, Clé, Trouv, I)
SI NON Trouv :
"Clé inexistante"
SINON { Le bloc I est dans Buffer1 }
Rech(Buffer1, Clé, Trouv', J)
SI Trouv' :
SI NON
Buffer1.T(J).Effacé :
Buffer1.T(J).Effacé := VRAI
Ecrirebloc(F, I, Buffer1)
SINON " Clé
inexistante" FSI
SINON
SI Buffer1.Lien.Numbloc
= NIL :
"Clé inexistante"
SINON
Rechlist(Buffer1.Lien, Clé, Trouv",K, Num)
SI Trouv" :
SI NON Buffer2.T'(K).Effacé :
Buffer2.T'(K).Effacé := VRAI
Ecrirebloc(F, Num, Buffer1)
FSI
SINON " Clé inexistante" FSI
FSI
FSI
FSI
Informations à sauvegarder à la fermeture du fichier
1 - Nombre de blocs du fichier F
2 - Numéro du dernier bloc du fichier F'
3 - Position libre dans le dernier bloc du fichier F'.
4 - Nombre d'articles présents
5 - Numéro du premier bloc de F'.
1 pour les différentes recherches, 2 et 3 pour pouvoir effectuer une insertion d'article,
4 et 5 pour pouvoir faire une réorganisation.
Critère de réorganisation
On maintient une variable N contenant à tout moment le nombre d'articles effectif du
fichier. A chaque insertion, on fait N := N + 1 et à chaque suppression, on fait N := N -
1.
Le critère est : N = 2MB&
Algorithme de réorganisation
L'algorithme qui suit utilise trois buffers en mémoire centrale:
- Buffer 1 pour le fichier F
- Buffer2 pour le fichier F'
- Buffer pour le fichier résulat Fres.
La variable Aig sert d'aiguillage entre les fichiers F et F'.
{ Phase d'initialisation }
Lirebloc(F, 1, Buffer)
K := 0
Aig := VRAI { K et Aig sont utilisées par le module Prochain }
POUR I =1, 2M
J := 1
TANTQUE J/B <= & :
Buffer.T(J).Article :=
Prochainarticle
Buffer.T(J).Efface :=
FAUX
J := J + 1
FINTANTQUE
Buffer.Nb := J - 1
Buffer.Lien := (NIL, -1)
Ecrirebloc(Fres, I, Buffer)
FINPOUR
Prochainarticle est défini comme suit :
Trouv := FAUX
TANTQUE NON Trouv :
Prochain( TYPE, Indice)
SI TYPE = 1
SI NON
Buffer1.T(Indice).Efface :
Trouv := VRAI
Prochainarticle := Buffer1.T(Indice).Article
FSI
SINON
SI NON
Buffer2.T'(Indice).Effacé :
Trouv := VRAI
Prochainarticle := Buffer2.T'(Indice).Article
FSI
FSI
FINTANTQUE
Le module Prochain rend deux paramètres et est défini comme suit :
Prochain(type, indice): si type = 1 on récupère l'indice d'un élément du bloc du
fichier F.
Si type = 2 on récupère l'indice d'un élément du bloc du fichier F'.
SI Aig :
K := K + 1
SI K <= Buffer1.Nb
TYPE:= 1; Indice := K
SINON
SI Buffer1.Lien.Numbloc
# NIL :
Num := Buffer1.Lien.Numbloc
L := Buffer1.Lien.Têtelist
Lirebloc(F', Num, Buffer2)
TYPE := 2 ; Indice := L
Aig := NON Aig
SINON
I := I + 1
Lirebloc(F, I, Buffer1)
TYPE := 1; Indice := 1
K := 1
FSI
FSI
SINON { NON Aig }
L := Buffer2.T'(L).Suiv.Têtelist
SI L # - 1 :
SI
Buffer2.T'(L).Suiv.Numbloc # Num :
Num :=Buffer2.T'(L).Suiv.Numbloc
Lirebloc(F', Num, Buffer2)
FSI
TYPE := 2 ; Indice := L
SINON
I := I + 1
Lirebloc(F, I, Buffer1)
TYPE := 1; Indice := 1
K := 1
Aig := NON Aig
FSI
FSI
2. Implémentation d'une file d'attente
Créerfile(F) : Allouer
(Q, S)
Aff_Adr(Q, NIL)
F.Tête := Q; F.Queue
:= Q
Filevide(F) : Filevide
:= (F.Tête = F.Queue)
Enfile(F, Val) : Allouer(Q, S)
Aff_Val(Q, Val) ;
Aff_Adr(Q, NIL)
Aff_Adr(F.Queue, Q)
F.Queue := Q
Défiler(F, Val) : SI NON Filevide(F) :
Val
:= Valeur(Suivant(F.Tête))
Aff_Adr(F.Tête, Suivant(Suivant(F.Tête))
Libérer(Suivant(F.Tête))
SINON " File Vide"
FSI
3. Accès multi-critères
Schéma
Description algorithmique
Index secondaires :
TYPE T1 = STRUCTURE
Clésec : Typeclé
Têtelist: ENTIER
FIN
TYPE T2 = STRUCTURE
Cléprim : Typeclé
Suiv: ENTIER
FIN
VAR Tsc1, Tsc2 : TABLEAU[1..M] DE T1
VAR Tpc1, Tpc2 : TABLEAU[1..M] DE T2
Index primaire :
TYPE T = STRUCTURE
Cléprim : Typeclé
Adr : Typeadresse
FIN
VAR Tprim : TABLEAU[1..P] DE T
Recherche de tous les articles de clés C1 et C2
données
Recherche dichotomique de C1 sur TSC1 --> Trouv, I
SI NON Trouv :
" aucun article "
SINON
Recherche dichotomique de C2 sur TSC2 -->
Trouv', I'
SI NON Trouv' :
" aucun"
SINON
a) Former l'ensemble I,
intersection des listes I et I' contenues dans TPC1 et TPC2.
b) Pour chaque
élément de I, faire une recherche dichotomique dans TPRIM pour récupérer l'article
dans le
fichier de données.
Dans la pratique a) et b) se déroulent en parallèle.
Suppression d'article
Une suppression d'article se fait uniquement au niveau de la table
d'index primaire.
Nouvelle structure de TPRIM
TYPE T = STRUCTURE
Cléprim : Typeclé
Effacé : Booléen
Adr : Typeadresse
FIN
VAR Tprim : TABLEAU[1..P] DE T
Algorithme de suppression
Trouv := FAUX
Bi := 1
Bs := N { Nombre d'éléments dans Tprim }
TANTQUE Bi <= Bs ET NON Trouv :
Milieu := Ent(Bi+Bs) / 2 )
SI Tprim(Milieu) = Clé
Trouv := VRAI
SINON
SI Clé <
Tprim(Milieu)
Bs := Milieu - 1
SINON
Bi := Milieu + 1
FSI
FSI
FINTANTQUE
SI Trouv :
SI Tprim(Milieu).Effacé :
" Article
inexistant "
SINON
"
Tprim(Milieu).Effacé := VRAI FSI
SINON " Article inexistant " FSI