Corrigé 26. Enoncé
1. Système de gestion de fichiers avec réorganisation
dynamique
Table d'index
TYPE T = STRUCTURE
Clé : CAR
Adr, Depl : ENTIER
Longueur
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 ( - 1 )
Fb : : nombre maximal
d'entrées dans un 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.
AdrList: adresse du bloc o� commence la liste des trous.
DepList: déplacement dans ce bloc o� commence cette liste.
Structure 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 : Nbart
Position 18 - 20 : AdrList
Position 21 - 24 : DepList
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
Initialisation
M = 200
N = 10
Der = N
D = 0
Nbrart = 0
AdrList = Nil
Deplist = 0
Organisation d'un trou commençant à la position x dans un bloc
Position x - Position x + 3 : longueur du
trou.
Position x + 4 - Position x + 6 : adresse du bloc o� se trouve le
trou suivant.
Position x + 7 - Position x + 10 : déplacement dans ce bloc o�
commence le trou.
Position x + 11 - .... : reste du trou.
Les positions finales sont Modulo B. Dans le cas o� ça déborde, la suite est continuée
sur le bloc suivant.
Nous utiliserons par la suite les 2 modules suivants :
1. Module Recopie( Buf, L, Adr, Depl, Sauvdepl )
Recopie une zone Buf de L caractères dans le bloc Adr du fichier à partir de Depl. Ce
module rend dans Sauvdepl la position o� se termine Buf dans le buffer d'écriture.
K := Min ( B-Depl, L)
I := - 1
POUR J=Depl,Depl+K-1 :
I := I + 1
Buffer[J] := Buf[I]
FINPOUR
Sauvdepl := J
Ecrirebloc(Fp, Adr, Buffer)
SI (L > B-Depl)
Adr := Adr + 1
Lirebloc(Fp, Adr, Bloc)
I := - 1;
POUR J=B-Depl, L-1 :
I := I + 1
Buffer[I] := Buf[J]
FINPOUR
Sauvdepl := I + 1
Ecrirebloc(Fp, Adr, Buffer)
FSI
2. Module Rec ( Chaîne, Buffer, L, K)
Recopie la chaîne de caractères Chaîne dans buffer à partir de la position L. Ensuite,
met à blanc les caractères de la zone restante. K étant le nombre total de caractères
de cette zone.
J := L - 1
POUR I := 0 , Long(Chaîne)-1 :
J := J + 1 ; Buffer[J]
:= Chaîne[I]
FINPOUR
POUR I := Long(Chaîne), K
J := J + 1
Buffer[J] := ' '
FINPOUR
Nous utiliserons également les deux modules Ch et Nombre définis au niveau de l'énoncé
permettant de faire les conversions Nombre --> Chaîne de caractères et inversement.
Fermeture du fichier
Il s'agit de la sauvegarde des caractéristiques.
{M : Nombre total de blocs alloués au fichier}
Buffer[0] := '2'
Buffer[1] := '0'
Buffer[2] := '0'
{ N :Nombre de blocs alloués pour les caractéristiques et l'index }
Buffer[3] := '1 '
Buffer[4] := '0'
Buffer[5] := ' '
{ Der : Adresse du dernier bloc de données }
Chaîne := Ch(Der)
Rec(Chaîne, Buffer, 6, 2)
{ D : Déplacement disponible dans ce bloc }
Chaîne := Ch( D)
Rec(Chaîne, Buffer, 9, 3)
{ Nbrart : Nombre d'articles }
Chaîne := Ch(Nbrart)
Rec(Chaîne, Buffer, 13, 4)
{ Adrlist : Adresse du bloc o� se trouve la liste}
Chaîne := Ch(Adrlist)
Rec(Chaîne, Buffer, 18, 2)
{ Deplist : Déplacement dans ce bloc o� commence le trou }
Chaîne := Ch(Deplist)
Rec(Chaîne, Buffer, 21, 3)
Ecrirebloc(Fp, 0, Buffer)
{ Sauvegarde de l'index }
K := -1
N := Nbrart
Nindex := 0
Continu := VRAI
TANTQUE Continu :
M := Min ( Fb, N)
POUR I:=1, M
K:=K+1
{ Clé }
L := -1
POUR J=0, 4 :
L := L + 1
Buffer[l] := Tchaîne[I].Clé[J]
FINPOUR
{ Adresse }
Chaîne :=
Ch(Tchaîne[K].Adr)
Rec(Chaîne, Buffer,
(I-1)*16 +5, 2)
{ Déplacement }
Chaîne :=
Ch(Tchaîne[K].Depl);
Rec(Chaîne, Buffer,
(I-1)*16 + 8, 3)
{ Longueur }
Chaîne :=
Ch(Tchaîne[K].Longueur)
Rec(Chaîne, Buffer,
(I-1)*16 + 12, 3)
FINPOUR
Nindex := Nindex + 1
SI ( Nindex > N )
" Débordement
Index")
Arret
SINON
Ecrirebloc(Fp, Nindex,
Buffer)
FSI
N := N - Fb;
SI ( N <:= 0 ) Continu := FAUX FSI
FINTANTQUE
Recherche d'un trou
Recherche un trou de longueur supérieure ou égale à L.
Trouver := vrai : trou trouvé.
Contenu du trou
Longtrou : longueur du trou.
Adr : adresse du
bloc o� se trouve le trou suivant.
Depl : déplacement dans
ce bloc o� commence le trou.
Adresse du trou
List : adresse du
bloc o� se trouve le bloc.
Deplist : déplacement dans ce bloc o�
commence ce trou.
Adresse du trou précédent
Preclist : adresse du bloc o� se trouve
le trou précédent.
Precdeplist : déplacement dans ce bloc
o� commence ce trou.
Reclist := NIL
Precdeplist := NIL
List := Adrlist
Deplist := Deplist
Trouver := FAUX
TANTQUE NON Trouver ET List # NIL :
Lirebloc(Fp, List, Buffer)
K:=Min(11, B-Deplist) { 11 est la longueur
minimale d'un trou }
POUR J=0, K-1 :
Buf[J] :=
Buffer[Deplist+J]
FINPOUR
SI (11 > B-Deplist) :
Lirebloc( Fp, List + 1,
Buffer )
J := - 1
POUR I=K, 10 :
J := J + 1
Buf[I] := Buffer[J]
FINPOUR
FSI
J := -1
POUR I=0, 3 :
J := J + 1
Chaîne[J] := Buf[I]
FINPOUR
Longtrou := Nombre(Chaîne)
J := -1
POUR I=4, 6 :
J := J + 1
Chaîne[J] := Buf[I]
FINPOUR
Adr := Nombre(Chaîne)
J := -1
POUR I=7, 10 :
J := J + 1
Chaîne[J] := Buf[I]
FINPOUR
Depl := Nombre(Chaîne)
SI Longtrou >:= L
Trouver := VRAI
SINON
Preclist := List
Precdeplist := Deplist
List := Adr
Deplist := Depl
FSI
FINTANTQUE
Insertion d'un trou
Insère un "trou" dans la liste des trous.
{ Formation de l'élément de la liste par le triplet ( long, AdrList,
DepList ) }
Chaîne := Ch (Longueur )
Rec(Chaîne, Buf, 0, 3)
Chaîne := Ch (Adrlist )
Rec(Chaîne, Buf, 4, 3)
Chaîne := Ch (Deplist )
Rec(Chaîne, Buf, 7, 4)
Adrlist := Adr;
Deplist := Depl;
{ Ramener le bloc contenant l'article supprimé }
Lirebloc(Fp, Adr, Buffer)
Recopie(Buf, 11, Adr, Depl , Sauvdepl)
Insérer un article de clé Clef donnée, d'information Info donnée
et de longueur L donnée
Recherche ( Clef, Trouv, I)
SI NON Trouv :
Article := Clef + Info
{ Existe-t-il un trou de longueur >:= L ? }
Recherchetrou( L, Trouver, Longtrou, Adr, Depl,
List, Deplist,Preclist, Precdeplist)
SI Trouver : { Buffer contient le trou }
{ Insérer l'article
dans ce trou, puis mettre à Jour Tchaîne et la liste des trous }
Recopie(Article, L,
List, Deplist,Sauvdepl)
{ Rajouter une entrée
dans Tchaîne }
Nbrart := Nbrart + 1
SI Nbrart > Max_clé
" Débordement Index "
Arret
FSI
POUR J = Nbrart-1, I+1,
-1 :
Tchaîne[J] := Tchaîne[J-1]
FINPOUR
Tchaîne[I].Clé :=
Clef
Tchaîne[I].Adr := List
Tchaîne[I].Depl:=
Deplist
Tchaîne[I].Longueur :=
L
{ Mise à jour du
chaînage }
SI Longtrou - L < 11
:
{ Trou irrécupérable }
SI Preclist # NIL :
{ Convertir Adr, Depl }
Rec(Chaîne, Buf, 0, 2)
Chaîne := Ch (Depl )
Rec(Chaîne, Buf, 3, 3)
{ Les recopier sur le fichier }
Precdeplist := Precdeplist + 4
{ Cas o� Precdeplist >= B }
SI Precdeplist >:= B :
Preclist := Preclist + 1
Precdeplist := Precdeplist - B
FSI
{Ramener le bloc Preclist}
Lirebloc(Fp, Preclist,
Buffer)
Recopie(Buf, 7, Preclist,Precdeplist, Sauvdepl)
SINON
Adrlist := Adr
Deplist := Depl
FSI
SINON
{ Trou restant récupérable }
Chaîne := Ch (Longtrou - L )
Rec(Chaîne, Buf, 0, 3)
Chaîne := Ch (Adr )
Rec(Chaîne, Buf, 4, 2)
Chaîne := Ch (Depl )
Rec(Chaîne, Buf, 7, 3)
Recopie( Buf, 11, List, Sauvdepl,Sauvd)
SI Preclist # NIL :
{Convertir Sauvdepl }
Chaîne := Ch (Sauvdepl )
Rec(Chaîne, Buf, 0, 3)
{Changer uniquement le déplacement}
Precdeplist := Precdeplist + 7
{ Cas o� Precdeplist >= B }
SI Precdeplist >:= B :
Preclist := Preclist + 1
Precdeplist := Precdeplist - B
FSI
{Ramener le bloc Preclist }
Lirebloc(Fp, Preclist, Buffer)
Recopie(Buf, 4,Preclist,Precdeplist ,Sauvdepl)
SINON
Adrlist := List
Deplist := Sauvdepl
FSI
FSI
SINON { Trouver = FAUX }
Sauvder := Der
{ Ramener le dernier
bloc }
Lirebloc(Fp, Der,
Buffer)
K := Min ( B-D, L)
Ind := - 1
POUR J=D, D+K-1 :
Ind := Ind + 1
Buffer[J] := Article[Ind]
FINPOUR
Sauvd := J
Ecrirebloc(Fp, Der,
Buffer)
SI L > B-D :
Sauvder := Der
Der := Der + 1
SI Der > M :
" Débordement fichier "
Arret
SINON
Ind := - 1
POUR J=B-D, L - 1 :
Ind := Ind + 1
Buffer[Ind] := Article[J]
FINPOUR
Sauvd := Ind+1
Ecrirebloc(Fp, Der, Buffer)
FSI
FSI
{ Rajouter une entrée
dans Tchaîne }
Nbrart := Nbrart + 1
SI Nbrart > Max_clé
:
" Débordement Index "
Arret
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].Depl:= D
Tchaîne[I].Adr :=
Sauvder
Tchaîne[I].Longueur :=
L
D := Sauvd
FSI
SINON "Clef existe " FSI
Supprimer un article de clé Clef donnée
Recherche ( Clef, Trouv, I) :
SI Trouv :
SI Tchaîne[i].Longueur > 10 :
Insérertrou (
Tchaîne[i].Longueur, Tchaîne[i].Adr,
Tchaîne[i].Depl )
POUR J:=I ,Nbrart-1 :
Tchaîne[j] := Tchaîne[j+1]
FINPOUR
Nbrart := Nbrart - 1
SINON " Trou irrécupérable " FSI
SINON
"Clé inexistante "
FSI