Corrigé 16. Enoncé
1. Un système de gestion de fichiers avec réorganisation
différée
Définition des caractéristiques et initialisation
La structure de la table d'index est la suivante :
TYPE T = STRUCTURE
Clé : CAR
Adr, Depl : ENTIER
Longueur : ENTIER
FIN
VAR Tchaîne TABLEAU [0 : Max_clé] DE T
On utilise les constantes :
B : capacité du bloc.
Max_clé : nombre maximal de clés.
Fb : nombre maximal
d'entrées dans le bloc d'index.
Paramètres
M : nombre total de blocs alloués.
N : nombre de blocs alloués pour l'index.
Der : numéro du dernier bloc alloué.
D : déplacement libre dans ce bloc.
Nbrart : nombre d'articles dans le fichier.
Cumul : nombre de caractères inaccessibles.
Seuil : seuil de réorganisation.
Initialisation
M = 200
N = 10
Der = N
D = 0
Nbrart = 0
Cumul = 0
Seuil = 0.30
Organisation du bloc 0 contenant les
caractéristiques
Position 0 - 2 : M
Position 3 - 5 : N
Position 6 - 8 : Der
Position 9 - 12 : D
Position 13 - 17 : Cumul
Position 18 - 22 : Nbart
Position 23 - 27 : Seuil
Structure du bloc d'index
Position 0 - 4 : clé
Position 5 - 7 : adresse du bloc
Position 8 - 11 : déplacement dans le bloc
Position 12 - 15 : longueur
Structure du Buffer
Buffer : TABLEAU [0:B] DE CAR
Ouverture du fichier
{ Lecture du bloc 0 contenant les caratéristiques du fichier }
Lirebloc(Fp, 0, Buffer)
Chaîne := ''
POUR I=0, 2 :
Chaîne := Chaîne + Buffer[I]
FINPOUR
M := Nombre (Chaîne)
Chaîne := ''
POUR I=3, 5 :
Chaîne := Chaîne + Buffer[I]
FINPOUR
N := Nombre (Chaîne)
Chaîne := ''
POUR I=6, 8 :
Chaîne := Chaîne + Buffer[I]
FINPOUR
Der := Nombre (Chaîne)
Chaîne := ''
POUR I=9, 12 :
Chaîne := Chaîne + Buffer[I]
FINPOUR
D := Nombre (Chaîne)
Chaîne := ''
POUR I=13, 17 :
Chaîne := Chaîne + Buffer[I]
FINPOUR
Cumul := Nombre (Chaîne)
Chaîne := ''
POUR I=18, 22 :
Chaîne := Chaîne + Buffer[I]
FINPOUR
Nbrart := Nombre (Chaîne)
Chaîne := ''
POUR I=23, 28 :
Chaîne := Chaîne + Buffer[I]
FINPOUR
Seuil:= Nombre (Chaîne)
{ Construction de la table Tchaîne }
N := Nbrart
Nindex := 0
K := - 1
TANTQUE N > 0 :
Nindex := Nindex + 1;
Lirebloc(Fp, Nindex, Buffer)
M := Min (Fb, N) { Minimum }
Le := 0;
POUR I=1, M :
{ Clé }
Clef := ''
POUR J=Le, Le+4 :
Clef := Clef + Buffer(J)
FINPOUR
{ Adresse }
Chaîne := ''
POUR J=Le+5, Le+7 :
Chaîne := Chaîne + Buffer(J)
FINPOUR
Adresse := Nombre(Chaîne);
{ Déplacement }
Chaîne := ''
POUR J=Le+8, Le+11 :
Chaîne := Chaîne + Buffer(J)
FINPOUR
Depl := Nombre(Chaîne)
{ Longueur }
Chaîne := ''
POUR J=Le+12, Le+15 :
Chaîne := Chaîne + Buffer(J)
FINPOUR
Long := Nombre(Chaîne)
K := K + 1;
Tchaîne(K).Clé := Clef
Tchaîne(K).Adr := Adresse
Tchaîne(K).Depl:= Depl
Tchaîne(K).Longueur := Long
Le := Le + 16
FINPOUR
N := N - Fb
FINTANTQUE
Consultation
Le module qui suit récupère dans la variable Article l'article de clé Clef. Long
désigne sa longueur.
Récupérer (Clef, Article, Long) :
Recherche ( Clef, Trouv, I)
SI Trouv :
Adr := Tchaîne[I].Adr
D := Tchaîne[I].Depl
Long := Tchaîne[I].Longueur
Lirebloc(Fp, Adr, Buffer)
K:=Min(Long, B-D)
Article := ''
POUR J=0,K-1 :
Article := Article +
Buffer[D+J]
FINPOUR
SI Long > B-D :
Adr := Adr + 1
Lirebloc(Fp, Adr,
Buffer)
L := - 1;
POUR J=K,Long - 1 :
L := L + 1
Article := Article + Buffer[L]
FINPOUR
FSI
SINON " Clé inexistante " FSI
Le module Recherche ( Clef, Trouv, I ) qui recherche une clé dans
la table TCHAINE est défini comme suit :
I := 0; Trouv := FAUX; Arrêt := FAUX
TANTQUE NON Trouv ET I < Nbrart ET NON Arrêt
SI Clef := Tchaîne[I].Clé :
Trouv := VRAI
SINON
SI Clef <
Tchaîne[I].Clé :
Arrêt := VRAI
SINON I := I + 1 FSI
FSI
FINTANTQUE
Insertion
Insérer (Clef, Info, L ) :
Article := Clef
Article := Article + Info { Concaténation }
Recherche ( Clef, Trouv, I)
SI NON Trouv :
Sauvder := Der
{ Ramener le drnier bloc }
Lirebloc(Fp, Der, Buffer)
K := Min ( B-D, L)
L := - 1
POUR J=D, D+K-1 :
L := L + 1
Buffer[J] := Article[L]
FINPOUR
Sauvd := J
Ecrirebloc(Fp, Der, Buffer)
SI L > B-D :
Sauvder := Der
Der := Der + 1
SI Der > M :
" Débordement du fichier "
Arrêt
SINON
L := - 1;
POUR J=B-D, L - 1 :
L := L + 1
Buffer[L] := Article[J]
FINPOUR
Sauvd :=L+1
Ecrirebloc(Fp, Der, Buffer)
FSI
FSI
{ Rajouter une entrée dans Tchaîne }
Nbrart := Nbrart + 1
SI Nbrart > Max_clé :
" Débordement
Index "
Arrêt
SINON
POUR J = Nbrart-1,I +1,
- 1 :
Tchaîne[J] := Tchaîne[J-1]
FINPOUR
FSI
Tchaîne[I].Clé := Clef
Tchaîne[I].Adr := Sauvder
Tchaîne[I].Depl:= D
Tchaîne[I].Longueur := L
D := Sauvd
SINON
"Clef existe "
FSI
Réorganisation
Fr étant le nouveau fichier créé.
Der := N; D := 0
POUR I=0, Nbrart- 1 :
Récupérer( Tchaîne[I].Clé, Article, L)
Sauvder := Der
K := Min ( B-D, L)
L := - 1
POUR J=D, D + K - 1 :
L := L + 1
Buffer[J] := Article[L]
FINPOUR
Sauvd := J;
SI K := B - D :
Ecrirebloc( Fr, Der,
Buffer)
FSI
SI L > B-D:
Sauvder := Der
Der := Der +1
L := - 1
POUR J=B-D, L - 1 :
L := L + 1
Buffer[L] :=Article[J]
FINPOUR
Sauvd :=L+1
FSI
Tchaîne[I].Adr := Sauvder
Tchaîne[I].Depl:= D
D := Sauvd
Der := Sauvder
FINPOUR