Devoir S F S D

Les algorithmes de :
* Recherche
* Insertion
* Suppression
* Requête a intervalle

Les membres :
* Touati Kamel
* Hamrani Ferroudja
* Hadjebar Mounia
* Habi yasmine
Type : TOF

type tbloc : structure

tab : tableau [1..b] de tenreg
NB : entier
fin structure
type tenreg : structure
cle : entier
efface : booleen
champ1 :typeQLq …
fin structure
f = fichier de tbloc buffer buf ENTETE (entier , entier)
// 1 car = nombre des blocs et 2 car = nombre des éléments dans le fichier

1
2
3
suppression_physique( c : typeqlq ; nomfichier : chaine )
Var
Trouv : booleen ; i,j,k : entier
Debut
Rech(c,nomfichier,trouv,i,j)
Si (trouv) alors
Ouvrir(f,nomfichier,’r+’)
Liredir(f,i,buf)
k := j
Si ( j != [Link]) alors
Tq (k < [Link]) faire
[Link][k] := [Link][k+1]
k := k +1
fin tq
(1) : i := i + 1
si ( i < entete(f,1)) alors

4
 buf1 := lire(f,i)
[Link][[Link]] := [Link][1]
fin si
ecriredir(f,i-1,buf)
buf := buf1
Tq ( i < entete(f,1)) faire
k := 1
Tq (k < [Link]) faire
[Link][k] := [Link][k+1]
k := k +1
fin tq
i := i + 1
si ( i < entete(f,1)) alors
liredir(f,i,buf1)
[Link][[Link]] := [Link][1]
fin si
ecriredir(f,i-1,buf)
buf := buf1
fin tq
sinon
aller a (1)
fin si
i := entete(f,1)
lirebloc(f,i,buf)
si ([Link] == 1 ) // si le dernier bloc contient une seule élément donc
lorsque en faire le décalage le dernier bloc vas supprimer
nb := entete(f,1)
affecte_entete(f,1,nb-1)
finSI
n := entete(f,2)

5
 affecte_entete(f,2,n-1)
sinon
Ecrire (‘’ L’ élément n’existe pas ! ‘’)
Fermer(f)

Fin

articles : structure
tab : tableau[1..100]de typeEnreg
nb : entier
fin structure

Procédure Requete( a:entier, b:entier , nomfichier : chaine ; var articles :

articles)
Var
Trouv : booleen ; i,j : entier
Debut
Rech(a,nomfichier,trouv,i,j)
k := 1
nb := 0
si (trouv) alors
Ouvrir(f,nomfichier,’r+’)
tantque(i<=entete(f,1))faire
Liredir(f,i,buf)
tantque(j<=[Link])faire
si( [Link][j].cle <= b )
[Link][k] := [Link][j]
k := k + 1
j := j + 1
[Link] := [Link] + 1

6
 sinon
aller a (2)
fin tq
j := 1
i := i + 1
fin tq

sinon
Ecrire("L' élément n'existe pas!")
finsi
(2) fermer(f)
Fin

Type TNOF
type tbloc : structure
tab : tableau [1..b] de tenreg
NB : entier
fin structure
type tenreg : structure
cle : entier
efface : booleen
champ1 :typeQLq …
fin structure
f = fichier de tbloc buffer buf ENTETE (entier , entier)
// 1 car = nombre des blocs et 2 car = nombre des éléments dans le fichier

Procédure Recherche( c:entier ; nomfichier : chaine ; var trouv :booleen ;

i,j:entier )

7
Var
i := 1 ; trouv := faux ;
Debut
ouvrir(f,nomfichier,'r')
TQ ( i<=entete(f,1) et trouv == faux) faire
liredir(f,I ,buf)
j := 1
TQ ( j<=[Link] et trouv == faux) faire
si ( [Link][j].cle == c et [Link][j].efface == faux) alors
trouv := vrai
sinon
j := j + 1
fin TQ
i := i + 1
fin TQ
si ( trouv := faux ) alors
i := entete(f,1)
j := [Link]
fermer(f)
Fin

insertion( c:entier ; nomfichier : chaine ; element : typeEnreg )

Var
Trouv : booleen ; i,j : entier
Debut
ouvrir(f,nomfichier,'w')
Recherche( c , nomfichier , trouv , i , j )
si (non trouv) alors // i = dernier bloc et j = dernier element dans le bloc

8
 liredir(f,i,buf)
si(j<b) alors
[Link][j+1] = element
sinon
i=i+1
affecte_entete(f,1,i)
[Link][1] = element
[Link] = 1
ecriredir(f,i,buf)
fin si
n := entete(f,2)
affecte_entete(f,2,n+1)

sinon
ecrire ("L'élément existe déjà ! " )

fermer(f)
Fin

Suppression Logique c’est la même dans type TOF

suppression_physique( c : typeqlq ; nomfichier : chaine )

Var
Trouv : booleen ; i,j : entier
Debut
Rech(c,nomfichier,trouv,i,j)
Si (trouv) alors
Ouvrir(f,nomfichier,’r+’)
Liredir(f,i,buf)

9
 si ( i == entete(f,1) et j == [Link]) alors
[Link][j] := #
[Link] := [Link] -1
si ([Link] == 0 ) alors
affecte_entete(f,1,i-1)
sinon
ecriredir(f,i,buf)
finsi

sinon
i1 = entete(f,1)
Liredir(f,i1,buf1)
j1 := [Link]
[Link][j] := [Link][j1]
ecriredir(f,i,buf)
[Link][j1] := #
[Link] := [Link] -1
si ([Link] == 0 ) alors
affecte_entete(f,1,i1-1)
sinon
ecriredir(f,i1,buf1)
finsi
finsi
n := entete(f,2)
affecte_entete(f,2,n-1)
sinon
Ecrire (‘’ L’ élément n’existe pas ! ‘’)
Fermer(f)

10
Fin

articles : structure
tab : tableau[1..100]de typeEnreg
nb : entier
fin structure

Procédure Requete( a:entier, b:entier , nomfichier : chaine ; var articles :

articles)
Var
i :=1
Debut
ouvrir(f,nomfichier,'r')
TQ ( i<=entete(f,1)) faire
liredir(f,I,buf)
j := 1 ; k := 1
TQ ( j<=[Link]) faire
si ( [Link][j].cle >= a et [Link][j].cle <=b ) alors
[Link][k] := [Link][j]
k := k + 1
[Link] := [Link] + 1
sinon
j := j + 1
fin TQ
i := i + 1

11
 fin TQ
fermer(f)
Fin

Type LNOF
type tbloc : structure
tab : tableau [1..b] de tenreg
NB : entier
suivant : entier
fin structure
type tenreg : structure
cle : entier
efface : booleen
champ1 :typeQLq …
fin structure
f = fichier de tbloc buffer buf ENTETE (entier , entier)
// 1 car = nombre des blocs et 2 car = nombre des éléments dans le fichier

Procédure Recherche( c:entier ; nomfichier : chaine ; var trouv :booleen , i , j)

Var
i := 1 , trouv := faux ; tete : pointeur sur tbloc
Debut
ouvrir(f,nomfichier,'r')
TQ (i <= entete(f,1) et trouv == faux) faire
liredir(f,i,buf)
j := 1
TQ ( j<=[Link] et trouv == faux) faire

12
 si ( [Link][j].cle == c et [Link][j].efface == faux) alors
trouv := vrai
sinon
j := j + 1
fin TQ
i := [Link]
fin TQ
si ( trouv := faux ) alors
i := entete(f,1) //i c’est le dernier bloc
j := [Link] // j c’est le dernier élément dans le dernier bloc
fin si
fermer(f)
fin

insertion( c:entier ; nomfichier : chaine ; element : typeEnreg )

Var
Trouv : booleen ; i,j,k : entier ; x : tenreg
Debut
ouvrir(f,nomfichier,'r+')
Recherche( c , nomfichier , trouv , i , j)
si (non trouv) alors // i= dernier bloc et j = dernier element dans le bloc
liredir(f,i,buf)
si(j<b) alors
[Link][j+1] = element
ecrirebloc(f,i,buf)
sinon
i := [Link]
affecte_entete(f,1,i)
allouer(nouveau)

13
 [Link][1] := element
[Link] := 1
[Link] := -1
ecrirebloc(f,i, nouveau)
fin si
n := entete(f,2)
affecte_entete(f,2,n+1)
sinon
ecrire ("L'élément existe déjà! " )

fermer(f)
Fin
Suppression Logique c’est la même dans type TOF

suppression_physique( c : typeqlq ; nomfichier : chaine )

Var
Trouv : booleen ; i,j : entier
Debut
Rech(c,nomfichier,trouv,i,j)
Si (trouv) alors
Ouvrir(f,nomfichier,’r+’)
liredir(f,i,buf)
si ( i == entete(f,1) et j == [Link]) alors
// supprimer le dernier element dans le dernier bloc
[Link][j] := #
[Link] := [Link] -1
si ([Link] == 0 ) alors
i := entete(f,1) - 1
lirebloc(f,i,buf)

14
 [Link] := -1
ecrirebloc(f,i,buf)
affecte_entete(f,1,i)
sinon
ecriredir(f,i,buf)
finsi

sinon
i1 = entete(f,1)
liredir(f,i1,buf1)
j1 := [Link]
[Link][j] := [Link][j1]
ecriredir(f,i,buf)
[Link][j1] := #
[Link] := [Link] -1
si ([Link] == 0 ) alors
i := entete(f,1) - 1
lirebloc(f,i,buf)
[Link] := -1
ecrirebloc(f,i,buf)
affecte_entete(f,1,i)
sinon
ecriredir(f,i1,buf1)
finsi
finsi
n := entete(f,2)
affecte_entete(f,2,n-1)
sinon
Ecrire (‘’ L’ élément n’existe pas ! ‘’)

15
Fermer(f)

Fin

articles : structure
tab : tableau[1..100]de typeEnreg
nb : entier
fin structure

Procédure Requete( a:entier, b:entier , nomfichier : chaine ; var articles :

articles)
Var
i,j,k : entier
Debut
ouvrir(f,nomfichier,'r')
i :=1
TQ ( i <= entete(f,1) ) faire
liredir(f,i,buf)
j := 1 ; k := 1
TQ ( j<=[Link]) faire
si ( [Link][j].cle >= a et [Link][j].cle <=b ) alors
[Link][k] := [Link][j]
k := k + 1
[Link] := [Link] + 1
finSi
j := j + 1
fin TQ
i := [Link]

16
 fin TQ
fermer(f)
Fin

Type LOF
type tbloc : structure
tab : tableau [1..b] de tenreg
NB : entier
suivant : entier
prec : entier
fin structure
type tenreg : structure
cle : entier
efface : booleen
champ1 :typeQLq …
fin structure
f = fichier de tbloc buffer buf ENTETE (entier , entier)
// 1 car = nombre des blocs et 2 car = nombre des éléments dans le fichier

17
insertion( c:entier ; nomfichier : chaine ; element : typeEnreg )
Var
Trouv : booleen ; i,j,k : entier ; x : tenreg
Debut
Recherche( c , nomfichier , trouv , i , j)
si (non trouv) alors

18
 ouvrir(f,nomfichier,'r+')
liredir(f,i,buf)
x := [Link][[Link]]
k := [Link]
TQ (k > j) faire
[Link][k] := [Link][k-1]
k:= k – 1
FinTQ
[Link][j] := element
si([Link]<b) alors
[Link] := [Link] + 1
[Link][[Link]] = element
ecrirebloc(f,i,buf)
sinon
allouer(nouveau)
[Link][1] := element
[Link] := 1
[Link] := nouveau
i := i + 1
si (i<= entete(f,1)) alors
lirebloc(f,i,buf1)
[Link] := buf1
sinon
[Link] := -1
affecte_entete(f,1,i)
fin si
n := entete(f,2)
affecte_entete(f,2,n+1)
sinon

19
 ecrire ("L'élément existe déjà ! " )

fermer(f)
Fin

Suppression Logique c’est la même dans type TOF

suppression_physique( c : typeqlq ; nomfichier : chaine )

Var
Trouv : booleen ; i,j,k : entier ;
Debut
Rech(c,nomfichier,trouv,i,j)
Si (trouv) alors
Ouvrir(f,nomfichier,’r+’)
liredir(f,i,buf)
k := j
Si ( j != [Link]) alors
Tq (k < [Link]) faire
[Link][k] := [Link][k+1]
k := k +1
fin tq
(1) : i := [Link]
si ( i < entete(f,1)) alors
buf1 := lire(f,i)
[Link][[Link]] := [Link][1]
fin si
ecriredir(f,i-1,buf)
buf := buf1
Tq ( i < entete(f,1)) faire

20
 k := 1
Tq (k < [Link]) faire
[Link][k] := [Link][k+1]
k := k +1
fin tq
i := [Link]
si ( i < entete(f,1)) alors
liredir(f,i,buf1)
[Link][[Link]] := [Link][1]
fin si
ecriredir(f,i-1,buf)
buf := buf1
fin tq
sinon
aller a (1)
fin si
([Link] == 1 ) // si le dernier bloc contient un seul élément donc lorsque en
faire le décalage le dernier bloc vas supprimer
nb := entete(f,1) - 1
affecte_entete(f,1,nb)
lirebloc(f,nb,buf)
[Link] := -1
ecriredir(f,i-1,buf)

finSI

n := entete(f,2)
affecte_entete(f,2,n-1)
sinon
Ecrire (‘’ L’ élément n’existe pas ! ‘’)

21
Fermer(f)

Fin

articles : structure
tab : tableau[1..100]de typeEnreg
nb : entier
fin structure

Procédure Requete( a:entier, b:entier , nomfichier : chaine ; var articles :

articles)
Var
Trouv : booleen ; i,j : entier
Debut
Rech(a,nomfichier,trouv,i,j)
k := 1
[Link] := 0
si (trouv) alors
Ouvrir(f,nomfichier,’r+’)
tantque(i<=entete(f,1))faire
Liredir(f,i,buf)
tantque(j<=[Link])faire
si( [Link][j].cle <= b )
[Link][k] := [Link][j]
k := k + 1
j := j + 1
[Link] := [Link] + 1
sinon
aller a (2)

22
 fin tq
j := 1
i := [Link]
fin tq

sinon
Ecrire("L' élément n'existe pas!")
finsi
(2) fermer(f)
Fin

Type LnoVc
type tbloc : structure
tab : tableau [1..b] de caractères
NB : entier
suivant : entier
fin structure
f = fichier de tbloc buffer buf ENTETE(entier , entier ,entier ,entier)
// 1 car = num du premier bloc
2 car = num de dernier bloc
3 car =la 1ere position libre dans le dernier bloc
4 car le nombre de caractères perdus suite aux suppressions logiques

l’enregistrement peut avoir le forme suivante :

bbb | b | bbbbbbbbbbbbbbbbbbbb |bbbb…….b
3 caractère pour la taille de l’enregistrement
1 caractère pour indiquer l’effacement logique
20 caractère pour la clé de l’enreg

23
N car pour les autres informations

Procédure Recherche( c:entier ; nomfichier : chaine ; var trouv :booleen , i , j)

Var
i , j : entier ; trouv := booléen
Debut
ouvrir(f,nomfichier,'r')
i := 1
j := 1
trouv := faux
liredir(f,i,buf)
TQ (non trouv) et (i <= entete(f,2) ou i == entete(f,2) et j != entete(f,3)) faire
Recuperer_chaine(3,i,j,longeur) ; Recuperer_chaine(1,i,j,efface)
Recuperer_chaine(20,i,j,cle_rech)
Si (cle_rech == c) et (efface == ‘F’) alors
Trouv = vrai
Sinon
j := j + nombre( longeur)-24
si ( j > b ) alors
j := j – b
i := [Link]
liredir(f,i,buf)
finSI
finSi
finTQ
fermer(f)
fin

Procédure recuperer_chaine(n :entier : Var i,j :entier ; Var ch : chaine )

24
Var k :entier
Debut
Pour (k := 1 ,n ) faire
Si (j <= b ) alors
Ch[k] := [Link][j]
j := j + 1
sinon //chevauchement
i := [Link]
liredir (f,i,buf)
ch[k] := [Link][1]
j := 2
finsi
finPour

Fin
insertion( c:chaine[20] ; nomfichier : chaine; element : typeEnreg )
Var
Trouv : booleen ; i,j,k : entier
Debut
Recherche( c , nomfichier , trouv , i , j)
Si (trouv == faux ) alors
ouvrir(f,nomfichier,'A')
i := entete (f,2)
j := entete(f,3)
chaine_longueur := element[1 :3]
//convertir la longueur en chaine de 3 car
Ecrire_chaine(3,chaine_longueur,i,j)
Ecrire_chaine(1,’F’,i,j)
chaine_longueur := entier(chaine_longueur )
Ecrire_chaine(chaine_longueur- 4 ,element[4 : ],i,j)

25
 [Link] := -1
ecriredir(f,i,buf)
si ( i != entete(f,2)) alors
affecte_entete(f,2,i)
finSI
affecte_entete(f,3,j)
sinon
ecrire ("L'élément existe déjà ! " )

finSi
fermer(f)
Fin

Procédure Ecrire_chaine (n :entier , ch : chaine , Var i,j : entier )

Var
K : entier ; i1 : entier
Debut
Pour ( k := 1 , n ) faire
Si ( j<=b ) alors
[Link][j] := ch[k]
j := j + 1
sinon
i1 : allocbloc(f)
[Link] := i1
ecriredir(f,i,buf)
i := i1

26
 [Link] [1] := ch[k]
j := 2
finSI
finPour

Fin

Procédure Suppression_logique(c : chaine[20] , nomfichier :chaine)

Var
Trouv : booleen ; i,j : entier
Debut
Ouvrir(f,nomfichier,’A’)
Recherche(c,nomfichier,trouv,i,j)
Si (trouv ) alors
j := j + 3
[Link][j] := ‘ V ’
ecriredir(f,i,j)

Sinon
Ecrire ( ‘’L’élément n’existe pas ! ‘’)
finSI

Fin
articles : structure
tab : tableau[tailleMax]de caractères
nb : entier //nombre des enreg
fin structure

27
Procédure Requete( a:entier, b:entier , nomfichier : chaine ; var articles :
articles)
Var
i,j,k : entier
Debut
ouvrir(f,nomfichier,'r')
i :=1
TQ ( i < entete(f,2) ou i == entete(f,2) et j != entete(f,3)) faire
liredir(f,i,buf)
j := 1 ; k := 1
Recuperer_chaine(3,i,j,longeur) ; Recuperer_chaine(1,i,j,efface)
Recuperer_chaine(20,i,j,cle_rech)
cle_rech := entier (cle_rech) //convertir
longueur := entier (longueur) //convertir
j := j – 24
Si (cle_rech >= a et cle_rech <= b) et (efface == ‘F’) alors
Pour ( n := 1 , longueur ) faire
[Link][k] := [Link][j]
k := k + 1
j := j + 1
finPour
[Link] := [Link] + 1

Sinon
j := j + nombre( longeur)
si ( j > b ) alors
j := j – b
i := [Link]
finSI

28
 finSi
finTQ

fermer(f)
Fin

Type LnoVnc
type tbloc : structure
tab : tableau [1..b] de caractères
NB : entier
suivant : entier
fin structure
f = fichier de tbloc buffer buf ENTETE(entier , entier ,entier ,entier)
// 1 car = num du premier bloc
2 car = num de dernier bloc
3 car =la 1ere position libre dans le dernier bloc
4 car le nombre de caractères perdus suite aux suppressions logiques

l’enregistrement peut avoir le forme suivante :

bbb | b | bbbbbbbbbbbbbbbbbbbb |bbbb…….b
3 car pour la taille de l’enregistrement
1 car pour indiquer l’effacement logique
20 car pour la clé de l’enreg
N car pour les autres informations

Procédure Recherche( c:entier ; nomfichier : chaine ; var trouv :booleen , i , j)

Var
i , j : entier ; trouv := booléen

29
Debut
ouvrir(f,nomfichier,'r')
i := 1
j := 1
trouv := faux
liredir(f,i,buf)
TQ (non trouv) et (i <= entete(f,2) ou i == entete(f,2) et j != entete(f,3)) faire
Recuperer_chaine(3,i,j,longeur) ; Recuperer_chaine(1,i,j,efface)
Recuperer_chaine(20,i,j,cle_rech)
Si (cle_rech == c) et (efface == ‘F’) alors
Trouv = vrai
Sinon
j := j + nombre( longeur)-24
si ( j > b ) alors
j := 1
i := [Link]
liredir(f,i,buf)
finSI
finSi
finTQ
fermer(f)
fin

Procédure recuperer_chaine(n :entier : Var i,j :entier ; Var ch : chaine )

Var k :entier
Debut
Pour (k := 1 ,n ) faire
Si (j <= b ) alors
Ch[k] := [Link][j]
j := j + 1

30
 finsi
finPour

Fin
insertion( c:chaine[20] ; nomfichier : chaine; element : typeEnreg )
Var
Trouv : booleen ; i,j,k : entier
Debut
Recherche( c , nomfichier , trouv , i , j)
Si (trouv == faux ) alors
ouvrir(f,nomfichier,'A')
i := entete (f,2)
j := entete(f,3)
chaine_longueur := element[1 :3]
//convertir la longueur en chaine de 3 car
SI (j +entier(chaine_longueur) <= b ) alors
Ecrire_chaine(3,chaine_longueur,i,j)
Ecrire_chaine(1,’F’,i,j)
chaine_longueur := entier(chaine_longueur)
Ecrire_chaine(chaine_longueur-4 ,element[4 : ],i,j)
[Link] := -1
ecriredir(f,i,buf)
Sinon
i := [Link]
j := 1
Ecrire_chaine(3,chaine_longueur,i,j)
Ecrire_chaine(1,’F’,i,j)
chaine_longueur := entier(chaine_longueur)
Ecrire_chaine(chaine_longueur-4 ,element[4 : ],i,j)
[Link] := -1

31
 ecriredir(f,i,buf)
finSI

si ( i != entete(f,2)) alors
affecte_entete(f,2,i)
finSI
affecte_entete(f,3,j)
sinon
ecrire ("L'élément existe déjà ! " )

finSi
fermer(f)
Fin

Procédure Ecrire_chaine (n :entier , ch : chaine , Var i,j : entier )

Var
K : entier ; i1 : entier
Debut
Pour ( k := 1 , n ) faire
Si ( j<=b ) alors
[Link][j] := ch[k]
j := j + 1
finSI
finPour

Fin

32
Procédure Suppression_logique(c : chaine[20] , nomfichier :chaine)
Var
Trouv : booleen ; i,j : entier
Debut
Ouvrir(f,nomfichier,’A’)
Recherche(c,nomfichier,trouv,i,j)
Si (trouv ) alors
j := j + 3
[Link][j] := ‘ V ’
ecriredir(f,i,j)

Sinon
Ecrire ( ‘’L’élément n’existe pas ! ‘’)
finSI

Fin
articles : structure
tab : tableau[tailleMax]de caractères
nb : entier //nombre des enreg
fin structure

Procédure Requete( a:entier, b:entier , nomfichier : chaine ; var articles :

articles)
Var
i,j,k : entier
Debut
ouvrir(f,nomfichier,'r')
i :=1
TQ ( i < entete(f,2) ou i == entete(f,2) et j != entete(f,3)) faire

33
 liredir(f,i,buf)
j := 1 ; k := 1
Recuperer_chaine(3,i,j,longeur) ; Recuperer_chaine(1,i,j,efface)
Recuperer_chaine(20,i,j,cle_rech)
cle_rech := entier (cle_rech) //convertir
longueur := entier (longueur) //convertir
j := j – 24
Si (cle_rech >= a et cle_rech <= b) et (efface == ‘F’) alors
Pour ( n := 1 , longueur ) faire
[Link][k] := [Link][j]
k := k + 1
j := j + 1
finPour
[Link] := [Link] + 1

Sinon
j := j + nombre( longeur)-24
si ( j > b ) alors
j := 1
i := [Link]
finSI
finSi
finTQ

fermer(f)
Fin

Type LoVc
type tbloc : structure

34
 tab : tableau [1..b] de caractères
NB : entier
suivant : entier
prec : entier
fin structure
f = fichier de tbloc buffer buf ENTETE(entier , entier ,entier ,entier ,entier)
// 1 car = num du premier bloc
2 car = num de dernier bloc
3 car = la 1ere position libre dans le dernier bloc
4 car = le nombre de caractères perdus suite aux suppressions logiques
5 car = position de dernier element dans le bloc

l’enregistrement peut avoir le forme suivante :

bbb | b | bbbbbbbbbbbbbbbbbbbb |bbbb…….b
3 car pour la taille de l’enregistrement
1 car pour indiquer l’effacement logique
20 car pour la clé de l’enreg
N car pour les autres informations

Procédure Recherche( c:entier ; nomfichier : chaine ; var trouv :booleen , i , j)

Var
bi , bs , inf , sup : entier ;
trouv , stop:= booléen
Debut
ouvrir(f,nomfichier,'r')
bs := entete(f,2)
bi := 1
trouv := faux ; stop := faux ; j := 1
TQ ( bi <= bs et Non trouv et Non stop )

35
i := (bi + bs ) div 2
liredir(f , i , buf)
j := j + 4
Recuperer_chaine(20,i,j,cle1)
j := entete(f, 5)
j := j + 4
si ( j > b ) alors
j := j – b
i := [Link]
finSI
Recuperer_chaine(20,i,j,cle2)
cle1 := entier(cle1) ; cle2 := entier(cle2)
Si ( c >= cle1 et c <= cle2 ) alors
inf := 1 ; sup := nombre_element(i)
// nombre_element == fonction qui calcule nombre des éléments
dans le bloc
TQ (inf <= sup et non trouv )
Milieu(i,inf,sup, k)
Recuperer_chaine(3,i,k,longueur)
Recuperer_chaine(1,i,k,efface)
Recuperer_chaine(20,i,k,cle)
longueur := entier(longueur)
cle := entier(cle)
longueur := entier(longueur)
Si ( c == cle ) alors
Trouv := vrai
Sinon
Si (c < cle ) alors
Sup := k -24
sinon

36
 inf := k + longueur – 24
finSI
finSI
finTQ
Si( inf > sup) alors
j := inf
finSI
stop := vrai
Sinon
Si (c < cle1 )
bs := [Link]
sinon
bi := [Link]
finSI
finSI
finTQ
SI (bi > bs ) alors
i := bi
j := 1
finSi
fermer(f)
Fin

Procédure recuperer_chaine(n :entier : Var i,j :entier ; Var ch : chaine )

Var k :entier
Debut
Pour (k := 1 ,n ) faire
Si (j <= b ) alors
Ch[k] := [Link][j]

37
 j := j + 1
sinon //chevauchement
i := [Link]
liredir (f,i,buf)
ch[k] := [Link][1]
j := 2
finsi
finPour

Fin
Procédure milieu ( i : entier , j : entier , sup : entier ; var k : entier )
Var
Debut
nenreg := nombre_element(i,j,sup)
nenreg := (nenreg) div 2
cpt := 0
TQ (cpt < nenreg) faire
Recuperer_chaine(3,bloc,j,longueur)
longueur := entier(longueur)
j := j + longueur – 3
cpt := cpt + 1
finTQ

k := j
Fin

Procédure nombre_element ( i : entier , j : entier, sup : entier)

Var
J : entier ; cpt : entier
Debut

38
 cpt := 0
TQ (j < sup) faire
Recuperer_chaine(3,bloc,j,longueur)
longueur := entier(longueur)
j := j + longueur – 3
cpt := cpt + 1
finTQ
retourner cpt

Fin

insertion(nomfichier : chaine; element : typeEnreg )

Var
Trouv,continu : booleen ; i,j,k : entier
Debut
c := element [5 .. 24]
Recherche( c , nomfichier , trouv , i , j)
Si (trouv == faux ) alors
ouvrir(f,nomfichier,'A')
l liredir(f,i,buf)
L := element [1..3] // L : taille de l’enreg
t := taille(buf) //nombre des caractères dans le bloc
Si ( L + t < b ) alors //buffer n’est pas plein
K :=0
N := j + 1
// sauvegarder les elemnts apres la postion j
Tantque ( N < b ) faire
Articles [K ] := [Link][N]
K := K + 1
N := N + 1

39
 finTQ
cpt := 1
tantque(cpt <= L ) faire
[Link][j ] := element[cpt]
j := j+ 1
cpt := cpt + 1
finTQ
cpt := 1
tantque(cpt <= k ) faire
[Link][j ] := articles[cpt]
cpt := cpt + 1
j := j + 1
finTQ
Sinon
K :=0
N := j + 1
// sauvegarder les elemnts apres la postion j
Tantque ( N < b ) faire
Articles [K ] := [Link][N]
K := K + 1
N := N + 1
finTQ
cpt := 1
tantque(cpt <= L ) faire
[Link][j ] := element[cpt]
j := j+ 1
cpt := cpt + 1
finTQ
cpt := 1

40
 tantque(j <=b ) faire
[Link][j ] := articles[cpt]
cpt := cpt + 1
j := j+ 1
finTQ
i := buf .suiv

finSi

sinon
ecrire ("L'élément existe déjà ! " )

finSi
fermer(f)
Fin

Procédure Ecrire_chaine (n :entier , ch : chaine , Var i,j : entier )

Var
K : entier ; i1 : entier
Debut
Pour ( k := 1 , n ) faire
Si ( j<=b ) alors
[Link][j] := ch[k]
j := j + 1
sinon
i1 : allocbloc(f)

41
 [Link] := i1
ecriredir(f,i,buf)
i := i1
[Link] [1] := ch[k]
j := 2
finSI
finPour

Fin

Procédure Suppression_logique(c : chaine[20] , nomfichier :chaine)

Var
Trouv : booleen ; i,j : entier
Debut
Ouvrir(f,nomfichier,’A’)
Recherche(c,nomfichier,trouv,i,j)
Si (trouv ) alors
j := j + 3
si ( j > b ) alors
j := j – b
i := [Link]
finSI
[Link][j] := ‘ V ’
ecriredir(f,i,j)

Sinon
Ecrire ( ‘’L’élément n’existe pas ! ‘’)
finSI

42
Fin
articles : structure
tab : tableau[tailleMax]de caractères
nb : entier //nombre des enreg
fin structure

Procédure Requete( a:entier, b:entier , nomfichier : chaine ; var articles :

articles)
Var
i,j,k : entier
Debut
ouvrir(f,nomfichier,'r')
Rech(a,nomfichier,trouv,i,j)
TQ ( i < entete(f,2) ou i == entete(f,2) et j != entete(f,3)) faire
liredir(f,i,buf)
k := 1
Recuperer_chaine(3,i,j,longeur) ; Recuperer_chaine(1,i,j,efface)
Recuperer_chaine(20,i,j,cle_rech)
cle_rech := entier (cle_rech) //convertir
longueur := entier (longueur) //convertir
j := j – 24
Si (cle_rech >= a et cle_rech <= b) et (efface == ‘F’) alors
Pour ( n := 1 , longueur ) faire
[Link][k] := [Link][j]
k := k + 1
j := j + 1
finPour
[Link] := [Link] + 1

43
 Sinon
j := j + nombre( longeur)
si ( j > b ) alors
j := j – b
i := [Link]
finSI
finSi
finTQ

fermer(f)
Fin

Type LoVnc
type tbloc : structure
tab : tableau [1..b] de caractères
NB : entier
suivant : entier
prec : entier
fin structure
f = fichier de tbloc buffer buf ENTETE(entier , entier ,entier ,entier ,entier)
// 1 car = num du premier bloc
2 car = num de dernier bloc
3 car = la 1ere position libre dans le dernier bloc
4 car = le nombre de caractères perdus suite aux suppressions logiques
5 car = position de dernier element dans le bloc

l’enregistrement peut avoir le forme suivante :

bbb | b | bbbbbbbbbbbbbbbbbbbb |bbbb…….b
3 car pour la taille de l’enregistrement
1 car pour indiquer l’effacement logique

44
20 car pour la clé de l’enreg
N car pour les autres informations

Procédure Recherche( c:entier ; nomfichier : chaine ; var trouv :booleen , i , j)

Var
bi , bs , inf , sup : entier ;
trouv , stop:= booléen
Debut
ouvrir(f,nomfichier,'r')
bs := entete(f,2)
bi := 1
trouv := faux ; stop := faux ; j := 1
TQ ( bi <= bs et Non trouv et Non stop )
i := (bi + bs ) div 2
liredir(f , i , buf)
j := j + 4
Recuperer_chaine(20,i,j,cle1)
j := entete(f, 5)
Recuperer_chaine(20,i,j,cle2)
cle1 := entier(cle1) ; cle2 := entier(cle2)
Si ( c >= cle1 et c <= cle2 ) alors
inf := 1 ; sup := nombre_element(i)
// nombre_element == fonction qui calcule nombre des éléments
dans le bloc
TQ (inf <= sup et non trouv )
Milieu(i,inf,sup, k)
Recuperer_chaine(3,i,k,longueur)
Recuperer_chaine(1,i,k,efface)

45
 Recuperer_chaine(20,i,k,cle)
longueur := entier(longueur)
cle := entier(cle)
longueur := entier(longueur)
Si ( c == cle ) alors
Trouv := vrai
Sinon
Si (c < cle ) alors
Sup := k -24
sinon
inf := k + longueur – 24
finSI
finSI
finTQ
Si( inf > sup) alors
j := inf
finSI
stop := vrai
Sinon
Si (c < cle1 )
bs := [Link]
sinon
bi := [Link]
finSI
finSI
finTQ
SI (bi > bs ) alors
i := bi
j := 1

46
 finSi
fermer(f)
Fin

Procédure recuperer_chaine(n :entier : Var i,j :entier ; Var ch : chaine )

Var k :entier
Debut
Pour (k := 1 ,n ) faire
Si (j <= b ) alors
Ch[k] := [Link][j]
j := j + 1
finsi
finPour

Fin
Procédure milieu ( i : entier , j : entier , sup : entier ; var k : entier )
Var
Debut
nenreg := nombre_element(i,j,sup)
nenreg := (nenreg) div 2
cpt := 0
TQ (cpt < nenreg) faire
Recuperer_chaine(3,bloc,j,longueur)
longueur := entier(longueur)
j := j + longueur – 3
cpt := cpt + 1
finTQ

k := j
Fin

47
Procédure nombre_element ( i : entier , j : entier, sup : entier)
Var
J : entier ; cpt : entier
Debut
cpt := 0
TQ (j < sup) faire
Recuperer_chaine(3,bloc,j,longueur)
longueur := entier(longueur)
j := j + longueur – 3
cpt := cpt + 1
finTQ
retourner cpt

Fin

insertion(nomfichier : chaine; element : typeEnreg )

Var
Trouv,continu : booleen ; i,j,k : entier
Debut
c := element [5 .. 24]
Recherche( c , nomfichier , trouv , i , j)
Si (trouv == faux ) alors
ouvrir(f,nomfichier,'A')
l liredir(f,i,buf)
L := element [1..3] // L : taille de l’enreg
t := taille(buf) //nombre des caractères dans le bloc
Si ( L + t < b ) alors //buffer n’est pas plein
K :=0

48
 N := j + 1
// sauvegarder les elemnts apres la postion j
Tantque ( N < b ) faire
Articles [K ] := [Link][N]
K := K + 1
N := N + 1
finTQ
cpt := 1
tantque(cpt <= L ) faire
[Link][j ] := element[cpt]
j := j+ 1
cpt := cpt + 1
finTQ
cpt := 1
tantque(cpt <= k ) faire
[Link][j ] := articles[cpt]
cpt := cpt + 1
j := j + 1
finTQ
Sinon
K :=0
N := j + 1
// sauvegarder les elemnts apres la postion j
Tantque ( N < b ) faire
Articles [K ] := [Link][N]
K := K + 1
N := N + 1
finTQ
cpt := 1

49
 tantque(cpt <= L ) faire
[Link][j ] := element[cpt]
j := j+ 1
cpt := cpt + 1
finTQ
cpt := 1
tantque(j <=b ) faire
[Link][j ] := articles[cpt]
cpt := cpt + 1
j := j+ 1
finTQ
i := buf .suiv

finSi

sinon
ecrire ("L'élément existe déjà ! " )

finSi
fermer(f)
Fin

Procédure Ecrire_chaine (n :entier , ch : chaine , Var i,j : entier )

Var
K : entier ; i1 : entier
Debut

50
 Pour ( k := 1 , n ) faire
Si ( j<=b ) alors
[Link][j] := ch[k]
j := j + 1
finSI
finPour

Fin

Procédure Suppression_logique(c : chaine[20] , nomfichier :chaine)

Var
Trouv : booleen ; i,j : entier
Debut
Ouvrir(f,nomfichier,’A’)
Recherche(c,nomfichier,trouv,i,j)
Si (trouv ) alors
j := j + 3
si ( j < b ) alors
[Link][j] := ‘ V ’
ecriredir(f,i,j)
finSI

Sinon
Ecrire ( ‘’L’élément n’existe pas ! ‘’)
finSI

Fin
articles : structure
tab : tableau[tailleMax]de caractères

51
 nb : entier //nombre des enreg
fin structure

Procédure Requete( a:entier, b:entier , nomfichier : chaine ; var articles :

articles)
Var
i,j,k : entier
Debut
ouvrir(f,nomfichier,'r')
Rech(a,nomfichier,trouv,i,j)
TQ ( i < entete(f,2) ou i == entete(f,2) et j != entete(f,3)) faire
liredir(f,i,buf)
k := 1
Recuperer_chaine(3,i,j,longeur) ; Recuperer_chaine(1,i,j,efface)
Recuperer_chaine(20,i,j,cle_rech)
cle_rech := entier (cle_rech) //convertir
longueur := entier (longueur) //convertir
j := j – 24
Si (cle_rech >= a et cle_rech <= b) et (efface == ‘F’) alors
Pour ( n := 1 , longueur ) faire
[Link][k] := [Link][j]
k := k + 1
j := j + 1
finPour
[Link] := [Link] + 1

Sinon
j := j + nombre( longeur)
si ( j > b ) alors

52
 j := 1
i := [Link]
finSI
finSi
finTQ

fermer(f)
Fin

Type TnoVc
type tbloc : structure
tab : tableau [1..b] de caractères
NB : entier
fin structure
f = fichier de tbloc buffer buf ENTETE(entier , entier ,entier ,entier)
// 1 car = num du premier bloc
2 car = num de dernier bloc
3 car =la 1ere position libre dans le dernier bloc
4 car le nombre de caractères perdus suite aux suppressions logiques

l’enregistrement peut avoir le forme suivante :

bbb | b | bbbbbbbbbbbbbbbbbbbb |bbbb…….b
3 car pour la taille de l’enregistrement
1 car pour indiquer l’effacement logique
20 car pour la clé de l’enreg
N car pour les autres informations

Procédure Recherche( c:entier ; nomfichier : chaine ; var trouv :booleen , i , j)

Var

53
i , j : entier ; trouv := booléen
Debut
ouvrir(f,nomfichier,'r')
i := 1
j := 1
trouv := faux
liredir(f,i,buf)
TQ (non trouv) et (i <= entete(f,2) ou i == entete(f,2) et j != entete(f,3)) faire
Recuperer_chaine(3,i,j,longeur) ; Recuperer_chaine(1,i,j,efface)
Recuperer_chaine(20,i,j,cle_rech)
Si (cle_rech == c) et (efface == ‘F’) alors
Trouv = vrai
Sinon
j := j + nombre( longeur)-24
si ( j > b ) alors
j := j – b
i := i + 1
liredir(f,i,buf)
finSI
finSi
finTQ
fermer(f)
fin

Procédure recuperer_chaine(n :entier : Var i,j :entier ; Var ch : chaine )

Var k :entier
Debut
Pour (k := 1 ,n ) faire
Si (j <= b ) alors
Ch[k] := [Link][j]

54
 j := j + 1
sinon //chevauchement
i := i + 1
liredir (f,i,buf)
ch[k] := [Link][1]
j := 2
finsi
finPour

Fin
insertion( c:chaine[20] ; nomfichier : chaine; element : typeEnreg )
Var
Trouv : booleen ; i,j,k : entier
Debut
Recherche( c , nomfichier , trouv , i , j)
Si (trouv == faux ) alors
ouvrir(f,nomfichier,'A')
i := entete (f,2)
j := entete(f,3)
chaine_longueur := element[1 :3]
//convertir la longueur en chaine de 3 car
Ecrire_chaine(3,chaine_longueur,i,j)
Ecrire_chaine(1,’F’,i,j)
chaine_longueur := entier(chaine_longueur )
Ecrire_chaine(chaine_longueur- 4 ,element[4 : ],i,j)
ecriredir(f,i,buf)
si ( i != entete(f,2)) alors
affecte_entete(f,2,i)
finSI
affecte_entete(f,3,j)

55
 sinon
ecrire ("L'élément existe déjà ! " )

finSi
fermer(f)
Fin

Procédure Ecrire_chaine (n :entier , ch : chaine , Var i,j : entier )

Var
K : entier ; i1 : entier
Debut
Pour ( k := 1 , n ) faire
Si ( j<=b ) alors
[Link][j] := ch[k]
j := j + 1
sinon
ecriredir(f,i,buf)
i := i + 1
[Link] [1] := ch[k]
j := 2
finSI
finPour

Fin

Procédure Suppression_logique(c : chaine[20] , nomfichier :chaine)

56
Var
Trouv : booleen ; i,j : entier
Debut
Ouvrir(f,nomfichier,’A’)
Recherche(c,nomfichier,trouv,i,j)
Si (trouv ) alors
j := j + 3
[Link][j] := ‘ V ’
ecriredir(f,i,j)

Sinon
Ecrire ( ‘’L’élément n’existe pas ! ‘’)
finSI

Fin
articles : structure
tab : tableau[tailleMax]de caractères
nb : entier //nombre des enreg
fin structure

Procédure Requete( a:entier, b:entier , nomfichier : chaine ; var articles :

articles)
Var
i,j,k : entier
Debut
ouvrir(f,nomfichier,'r')
i :=1
TQ ( i < entete(f,2) ou i == entete(f,2) et j != entete(f,3)) faire
liredir(f,i,buf)
j := 1 ; k := 1

57
 Recuperer_chaine(3,i,j,longeur) ; Recuperer_chaine(1,i,j,efface)
Recuperer_chaine(20,i,j,cle_rech)
cle_rech := entier (cle_rech) //convertir
longueur := entier (longueur) //convertir
j := j – 24
Si (cle_rech >= a et cle_rech <= b) et (efface == ‘F’) alors
Pour ( n := 1 , longueur ) faire
[Link][k] := [Link][j]
k := k + 1
j := j + 1
finPour
[Link] := [Link] + 1

Sinon
j := j + nombre( longeur)
si ( j > b ) alors
j := j – b
i := i + 1
finSI
finSi
finTQ

fermer(f)
Fin

Type TnoVnc
type tbloc : structure
tab : tableau [1..b] de caractères
NB : entier

58
 suivant : entier
fin structure
f = fichier de tbloc buffer buf ENTETE(entier , entier ,entier ,entier)
// 1 car = num du premier bloc
2 car = num de dernier bloc
3 car =la 1ere position libre dans le dernier bloc
4 car le nombre de caractères perdus suite aux suppressions logiques

l’enregistrement peut avoir le forme suivante :

bbb | b | bbbbbbbbbbbbbbbbbbbb |bbbb…….b
3 car pour la taille de l’enregistrement
1 car pour indiquer l’effacement logique
20 car pour la clé de l’enreg
N car pour les autres informations

Procédure Recherche( c:entier ; nomfichier : chaine ; var trouv :booleen , i , j)

Var
i , j : entier ; trouv := booléen
Debut
ouvrir(f,nomfichier,'r')
i := 1
j := 1
trouv := faux
liredir(f,i,buf)
TQ (non trouv) et (i <= entete(f,2) ou i == entete(f,2) et j != entete(f,3)) faire
Recuperer_chaine(3,i,j,longeur) ; Recuperer_chaine(1,i,j,efface)
Recuperer_chaine(20,i,j,cle_rech)
Si (cle_rech == c) et (efface == ‘F’) alors
Trouv = vrai

59
 Sinon
j := j + nombre( longeur)-24
si ( j > b ) alors
j := 1
i := i + 1
liredir(f,i,buf)
finSI
finSi
finTQ
fermer(f)
fin

Procédure recuperer_chaine(n :entier : Var i,j :entier ; Var ch : chaine )

Var k :entier
Debut
Pour (k := 1 ,n ) faire
Si (j <= b ) alors
Ch[k] := [Link][j]
j := j + 1
finsi
finPour

Fin
insertion( c:chaine[20] ; nomfichier : chaine; element : typeEnreg )
Var
Trouv : booleen ; i,j,k : entier
Debut
Recherche( c , nomfichier , trouv , i , j)
Si (trouv == faux ) alors
ouvrir(f,nomfichier,'A')
i := entete (f,2)

60
 j := entete(f,3)
chaine_longueur := element[1 :3]
//convertir la longueur en chaine de 3 car
SI (j +entier(chaine_longueur) <= b ) alors
Ecrire_chaine(3,chaine_longueur,i,j)
Ecrire_chaine(1,’F’,i,j)
chaine_longueur := entier(chaine_longueur)
Ecrire_chaine(chaine_longueur-4 ,element[4 : ],i,j)
ecriredir(f,i,buf)
Sinon
i := i + 1
j := 1
Ecrire_chaine(3,chaine_longueur,i,j)
Ecrire_chaine(1,’F’,i,j)
chaine_longueur := entier(chaine_longueur)
Ecrire_chaine(chaine_longueur-4 ,element[4 : ],i,j)
ecriredir(f,i,buf)
finSI

si ( i != entete(f,2)) alors
affecte_entete(f,2,i)
finSI
affecte_entete(f,3,j)
sinon
ecrire ("L'élément existe déjà ! " )

finSi
fermer(f)
Fin

61
Procédure Ecrire_chaine (n :entier , ch : chaine , Var i,j : entier )
Var
K : entier ; i1 : entier
Debut
Pour ( k := 1 , n ) faire
Si ( j<=b ) alors
[Link][j] := ch[k]
j := j + 1
finSI
finPour

Fin

Procédure Suppression_logique(c : chaine[20] , nomfichier :chaine)

Var
Trouv : booleen ; i,j : entier
Debut
Ouvrir(f,nomfichier,’A’)
Recherche(c,nomfichier,trouv,i,j)
Si (trouv ) alors
j := j + 3
[Link][j] := ‘ V ’
ecriredir(f,i,j)

Sinon

62
 Ecrire ( ‘’L’élément n’existe pas ! ‘’)
finSI

Fin
articles : structure
tab : tableau[tailleMax]de caractères
nb : entier //nombre des enreg
fin structure

Procédure Requete( a:entier, b:entier , nomfichier : chaine ; var articles :

articles)
Var
i,j,k : entier
Debut
ouvrir(f,nomfichier,'r')
i :=1
TQ ( i < entete(f,2) ou i == entete(f,2) et j != entete(f,3)) faire
liredir(f,i,buf)
j := 1 ; k := 1
Recuperer_chaine(3,i,j,longeur) ; Recuperer_chaine(1,i,j,efface)
Recuperer_chaine(20,i,j,cle_rech)
cle_rech := entier (cle_rech) //convertir
longueur := entier (longueur) //convertir
j := j – 24
Si (cle_rech >= a et cle_rech <= b) et (efface == ‘F’) alors
Pour ( n := 1 , longueur ) faire
[Link][k] := [Link][j]
k := k + 1
j := j + 1
finPour

63
 [Link] := [Link] + 1

Sinon
j := j + nombre( longeur)-24
si ( j > b ) alors
j := 1
i := i + 1
finSI
finSi
finTQ

fermer(f)
Fin

Type ToVc
type tbloc : structure
tab : tableau [1..b] de caractères
NB : entier
suivant : entier
prec : entier
fin structure
f = fichier de tbloc buffer buf ENTETE(entier , entier ,entier ,entier ,entier)
// 1 car = num du premier bloc
2 car = num de dernier bloc
3 car = la 1ere position libre dans le dernier bloc
4 car = le nombre de caractères perdus suite aux suppressions logiques
5 car = position de dernier element dans le bloc

l’enregistrement peut avoir le forme suivante :

bbb | b | bbbbbbbbbbbbbbbbbbbb |bbbb…….b
3 car pour la taille de l’enregistrement

64
1 car pour indiquer l’effacement logique
20 car pour la clé de l’enreg
N car pour les autres informations

Procédure Recherche( c:entier ; nomfichier : chaine ; var trouv :booleen , i , j)

Var
bi , bs , inf , sup : entier ;
trouv , stop:= booléen
Debut
ouvrir(f,nomfichier,'r')
bs := entete(f,2)
bi := 1
trouv := faux ; stop := faux ; j := 1
TQ ( bi <= bs et Non trouv et Non stop )
i := (bi + bs ) div 2
liredir(f , i , buf)
j := j + 4
Recuperer_chaine(20,i,j,cle1)
j := entete(f, 5)
j := j + 4
si ( j > b ) alors
j := j – b
i := i + 1
finSI
Recuperer_chaine(20,i,j,cle2)
cle1 := entier(cle1) ; cle2 := entier(cle2)
Si ( c >= cle1 et c <= cle2 ) alors

65
 inf := 1 ; sup := nombre_element(i)
// nombre_element == fonction qui calcule nombre des éléments
dans le bloc
TQ (inf <= sup et non trouv )
Milieu(i,inf,sup, k)
Recuperer_chaine(3,i,k,longueur)
Recuperer_chaine(1,i,k,efface)
Recuperer_chaine(20,i,k,cle)
longueur := entier(longueur)
cle := entier(cle)
longueur := entier(longueur)
Si ( c == cle ) alors
Trouv := vrai
Sinon
Si (c < cle ) alors
Sup := k -24
sinon
inf := k + longueur – 24
finSI
finSI
finTQ
Si( inf > sup) alors
j := inf
finSI
stop := vrai
Sinon
Si (c < cle1 )
bs := i – 1
sinon
bi := i + 1

66
 finSI
finSI
finTQ
SI (bi > bs ) alors
i := bi
j := 1
finSi
fermer(f)
Fin

Procédure recuperer_chaine(n :entier : Var i,j :entier ; Var ch : chaine )

Var k :entier
Debut
Pour (k := 1 ,n ) faire
Si (j <= b ) alors
Ch[k] := [Link][j]
j := j + 1
sinon //chevauchement
i := i + 1
liredir (f,i,buf)
ch[k] := [Link][1]
j := 2
finsi
finPour

Fin
Procédure milieu ( i : entier , j : entier , sup : entier ; var k : entier )
Var
Debut

67
 nenreg := nombre_element(i,j,sup)
nenreg := (nenreg) div 2
cpt := 0
TQ (cpt < nenreg) faire
Recuperer_chaine(3,bloc,j,longueur)
longueur := entier(longueur)
j := j + longueur – 3
cpt := cpt + 1
finTQ

k := j
Fin

Procédure nombre_element ( i : entier , j : entier, sup : entier)

Var
J : entier ; cpt : entier
Debut
cpt := 0
TQ (j < sup) faire
Recuperer_chaine(3,bloc,j,longueur)
longueur := entier(longueur)
j := j + longueur – 3
cpt := cpt + 1
finTQ
retourner cpt

Fin

insertion(nomfichier : chaine; element : typeEnreg )

Var

68
 Trouv,continu : booleen ; i,j,k : entier
Debut
c := element [5 .. 24]
Recherche( c , nomfichier , trouv , i , j)
Si (trouv == faux ) alors
ouvrir(f,nomfichier,'A')
liredir(f,i,buf)
L := element [1..3] // L : taille de l’enreg
t := taille(buf) //nombre des caractères dans le bloc
Si ( L + t < b ) alors //buffer n’est pas plein
K :=0
N := j + 1
// sauvegarder les elemnts apres la postion j
Tantque ( N < b ) faire
Articles [K ] := [Link][N]
K := K + 1
N := N + 1
finTQ
cpt := 1
tantque(cpt <= L ) faire
[Link][j ] := element[cpt]
j := j+ 1
cpt := cpt + 1
finTQ
cpt := 1
tantque(cpt <= k ) faire
[Link][j ] := articles[cpt]
cpt := cpt + 1
j := j + 1

69
 finTQ
Sinon
K :=0
N := j + 1
// sauvegarder les elemnts apres la postion j
Tantque ( N < b ) faire
Articles [K ] := [Link][N]
K := K + 1
N := N + 1
finTQ
cpt := 1
tantque(cpt <= L ) faire
[Link][j ] := element[cpt]
j := j+ 1
cpt := cpt + 1
finTQ
cpt := 1
tantque(j <=b ) faire
[Link][j ] := articles[cpt]
cpt := cpt + 1
j := j+ 1
finTQ
i := i+1

finSi

sinon
ecrire ("L'élément existe déjà ! " )

70
 finSi
fermer(f)
Fin

Procédure Ecrire_chaine (n :entier , ch : chaine , Var i,j : entier )

Var
K : entier ; i1 : entier
Debut
Pour ( k := 1 , n ) faire
Si ( j<=b ) alors
[Link][j] := ch[k]
j := j + 1
sinon
ecriredir(f,i,buf)
i := i + 1
[Link] [1] := ch[k]
j := 2
finSI
finPour

Fin

Procédure Suppression_logique(c : chaine[20] , nomfichier :chaine)

Var
Trouv : booleen ; i,j : entier
Debut

71
 Ouvrir(f,nomfichier,’A’)
Recherche(c,nomfichier,trouv,i,j)
Si (trouv ) alors
j := j + 3
si ( j > b ) alors
j := j – b
i := i + 1
finSI
[Link][j] := ‘ V ’
ecriredir(f,i,j)

Sinon
Ecrire ( ‘’L’élément n’existe pas ! ‘’)
finSI

Fin
articles : structure
tab : tableau[tailleMax]de caractères
nb : entier //nombre des enreg
fin structure

Procédure Requete( a:entier, b:entier , nomfichier : chaine ; var articles :

articles)
Var
i,j,k : entier
Debut
ouvrir(f,nomfichier,'r')
Rech(a,nomfichier,trouv,i,j)
TQ ( i < entete(f,2) ou i == entete(f,2) et j != entete(f,3)) faire
liredir(f,i,buf)

72
 k := 1
Recuperer_chaine(3,i,j,longeur) ; Recuperer_chaine(1,i,j,efface)
Recuperer_chaine(20,i,j,cle_rech)
cle_rech := entier (cle_rech) //convertir
longueur := entier (longueur) //convertir
j := j – 24
Si (cle_rech >= a et cle_rech <= b) et (efface == ‘F’) alors
Pour ( n := 1 , longueur ) faire
[Link][k] := [Link][j]
k := k + 1
j := j + 1
finPour
[Link] := [Link] + 1

Sinon
j := j + nombre( longeur)
si ( j > b ) alors
j := j – b
i := i + 1
finSI
finSi
finTQ

fermer(f)
Fin

Type ToVnc
type tbloc : structure
tab : tableau [1..b] de caractères

73
 NB : entier
suivant : entier
prec : entier
fin structure
f = fichier de tbloc buffer buf ENTETE(entier , entier ,entier ,entier ,entier)
// 1 car = num du premier bloc
2 car = num de dernier bloc
3 car = la 1ere position libre dans le dernier bloc
4 car = le nombre de caractères perdus suite aux suppressions logiques
5 car = position de dernier element dans le bloc

l’enregistrement peut avoir le forme suivante :

bbb | b | bbbbbbbbbbbbbbbbbbbb |bbbb…….b
3 car pour la taille de l’enregistrement
1 car pour indiquer l’effacement logique
20 car pour la clé de l’enreg
N car pour les autres informations

Procédure Recherche( c:entier ; nomfichier : chaine ; var trouv :booleen , i , j)

Var
bi , bs , inf , sup : entier ;
trouv , stop:= booléen
Debut
ouvrir(f,nomfichier,'r')
bs := entete(f,2)
bi := 1
trouv := faux ; stop := faux ; j := 1
TQ ( bi <= bs et Non trouv et Non stop )
i := (bi + bs ) div 2

74
liredir(f , i , buf)
j := j + 4
Recuperer_chaine(20,i,j,cle1)
j := entete(f, 5)
j := j + 4
Recuperer_chaine(20,i,j,cle2)
cle1 := entier(cle1) ; cle2 := entier(cle2)
Si ( c >= cle1 et c <= cle2 ) alors
inf := 1 ; sup := nombre_element(i)
// nombre_element == fonction qui calcule nombre des éléments
dans le bloc
TQ (inf <= sup et non trouv )
Milieu(i,inf,sup, k)
Recuperer_chaine(3,i,k,longueur)
Recuperer_chaine(1,i,k,efface)
Recuperer_chaine(20,i,k,cle)
longueur := entier(longueur)
cle := entier(cle)
longueur := entier(longueur)
Si ( c == cle ) alors
Trouv := vrai
Sinon
Si (c < cle ) alors
Sup := k -24
sinon
inf := k + longueur – 24
finSI
finSI
finTQ
Si( inf > sup) alors

75
 j := inf
finSI
stop := vrai
Sinon
Si (c < cle1 )
bs := i - 1
sinon
bi := i + 1
finSI
finSI
finTQ
SI (bi > bs ) alors
i := bi
j := 1
finSi
fermer(f)
Fin

Procédure recuperer_chaine(n :entier : Var i,j :entier ; Var ch : chaine )

Var k :entier
Debut
Pour (k := 1 ,n ) faire
Si (j <= b ) alors
Ch[k] := [Link][j]
j := j + 1
finsi
finPour

Fin
Procédure milieu ( i : entier , j : entier , sup : entier ; var k : entier )

76
Var
Debut
nenreg := nombre_element(i,j,sup)
nenreg := (nenreg) div 2
cpt := 0
TQ (cpt < nenreg) faire
Recuperer_chaine(3,bloc,j,longueur)
longueur := entier(longueur)
j := j + longueur – 3
cpt := cpt + 1
finTQ

k := j
Fin

Procédure nombre_element ( i : entier , j : entier, sup : entier)

Var
J : entier ; cpt : entier
Debut
cpt := 0
TQ (j < sup) faire
Recuperer_chaine(3,bloc,j,longueur)
longueur := entier(longueur)
j := j + longueur – 3
cpt := cpt + 1
finTQ
retourner cpt

Fin

77
insertion(nomfichier : chaine; element : typeEnreg )
Var
Trouv,continu : booleen ; i,j,k : entier
Debut
c := element [5 .. 24]
Recherche( c , nomfichier , trouv , i , j)
Si (trouv == faux ) alors
ouvrir(f,nomfichier,'A')
l liredir(f,i,buf)
L := element [1..3] // L : taille de l’enreg
t := taille(buf) //nombre des caractères dans le bloc
Si ( L + t < b ) alors //buffer n’est pas plein
K :=0
N := j + 1
// sauvegarder les elemnts apres la postion j
Tantque ( N < b ) faire
Articles [K ] := [Link][N]
K := K + 1
N := N + 1
finTQ
cpt := 1
tantque(cpt <= L ) faire
[Link][j ] := element[cpt]
j := j+ 1
cpt := cpt + 1
finTQ
cpt := 1
tantque(cpt <= k ) faire
[Link][j ] := articles[cpt]

78
 cpt := cpt + 1
j := j + 1
finTQ
Sinon
K :=0
N := j + 1
// sauvegarder les elemnts apres la postion j
Tantque ( N < b ) faire
Articles [K ] := [Link][N]
K := K + 1
N := N + 1
finTQ
cpt := 1
tantque(cpt <= L ) faire
[Link][j ] := element[cpt]
j := j+ 1
cpt := cpt + 1
finTQ
cpt := 1
tantque(j <=b ) faire
[Link][j ] := articles[cpt]
cpt := cpt + 1
j := j+ 1
finTQ
i := buf .suiv

finSi

sinon

79
 ecrire ("L'élément existe déjà ! " )

finSi
fermer(f)
Fin

Procédure Suppression_logique(c : chaine[20] , nomfichier :chaine)

Var
Trouv : booleen ; i,j : entier
Debut
Ouvrir(f,nomfichier,’A’)
Recherche(c,nomfichier,trouv,i,j)
Si (trouv ) alors
j := j + 3
si ( j < b ) alors
[Link][j] := ‘ V ’
ecriredir(f,i,j)
finSI

Sinon
Ecrire ( ‘’L’élément n’existe pas ! ‘’)
finSI

Fin
articles : structure
tab : tableau[tailleMax]de caractères
nb : entier //nombre des enreg
fin structure

80
Procédure Requete( a:entier, b:entier , nomfichier : chaine ; var articles :
articles)
Var
i,j,k : entier
Debut
ouvrir(f,nomfichier,'r')
Rech(a,nomfichier,trouv,i,j)
TQ ( i < entete(f,2) ou i == entete(f,2) et j != entete(f,3)) faire
liredir(f,i,buf)
k := 1
Recuperer_chaine(3,i,j,longeur) ; Recuperer_chaine(1,i,j,efface)
Recuperer_chaine(20,i,j,cle_rech)
cle_rech := entier (cle_rech) //convertir
longueur := entier (longueur) //convertir
j := j – 24
Si (cle_rech >= a et cle_rech <= b) et (efface == ‘F’) alors
Pour ( n := 1 , longueur ) faire
[Link][k] := [Link][j]
k := k + 1
j := j + 1
finPour
[Link] := [Link] + 1

Sinon
j := j + nombre( longeur)
si ( j > b ) alors
j := 1
i := i + 1
finSI

81
 finSi
finTQ

fermer(f)
Fin

82