Considérons la structure de fichier suivante :

Vue macroscopique :

Le fichier est un tableau non ordonné de blocs de 1K (1024 octets).

Vue microscopique :

Les articles sont de longueur variable.

Les clés des articles sont de longueur fixe (4 caractères)

Les articles ne sont pas en chevauchement sur des blocs contigus.

La longueur de l’article constitue un séparateur et occupe 3 octets.

Les suppressions d’articles et le phénomène de non chevauchement engendrent des trous dans le fichier. Dans le but de récupérer dynamiquement ces trous, on maintient un autre fichier présent en mémoire pendant l’exploitation du fichier dans une table ( Table_trous ) à trois entrées : numéro du bloc du trou, déplacement dans le bloc o� se trouve le trou et longueur du trou ( en octets ).

Ainsi, l’insertion d’un article commence par la recherche d’un trou de longueur suffisante dans Table_trous. Si un tel trou existe, l’article est y inséré sinon il est inséré dans le dernier bloc du fichier.

Périodiquement, quand le nombre moyen de trous par bloc dépasse k (donné) une réorganisation du fichier est entreprise dans le but de ne laisser qu’un seul trou par bloc. (placé en queue)

Enoncer les caractéristiques du fichier et écrire le module de création.

Ecrire les algorithmes de recherche, d’insertion et de réorganisation.

Donner les nombres moyens d’accès des opérations considérées ainsi que l’opération de suppression. Quel est le but de la réorganisation.

On utilisera un seul buffer en mémoire. Dans l’algorithme de réorganisation, on ne tolérera pas les blocs vides.

N.B

.Tous les algorithmes doivent être écrits à base de modèles ( machines abstraites ).

Machine abstraite sur les fichiers :

OUVRIR (Flogique, Fphysique, Mode) : Ouvrir le fichier logique et l’associer au fichier physique en précisant si le fichier est nouveau ('N') ou ancien ('A').

FERMER(Flogique) : Fermer le fichier.

LIRESEQ (Flogique, V) : Lecture dans la variable V l'article se trouvant à la position courante.

ECRIRESEQ (Flogique, V) : Ecriture de l'article V à la position courante.

LIREDIR (Flogique, V, n) : Lecture du n-ième article du fichier.

ECRIREDIR (Flogique, V, n) : Ecriture de l'article V à la n-ième position.

RAJOUTER (Flogique, V) : Rajoute un article en fin du fichier

FINFICH (Flogique) : Prédicat égal à vrai si la fin du fichier est rencontrée, faux sinon.

ALLOC_BLOC(Flogique) : Position d'un bloc ( ou article ) dans laquelle on pourra écrire.

ENTETE (F, i) : Récupérer la i-ème caractéristique du fichier.

AFF_ENTETE(F, i, v) : Affecter v comme i-ème caractéristique du fichier.

On utilisera

- les modules de conversion

C(entier) -à chaîne

E(chaine) à entier

- les modules de copie et récupération de chaines

Copie ( C, L, Debut ) : copier la chaîne de caractères C de longueur L dans le buffer à partir de la position Debut.

Extraire(Debut, L, chaine) : extraire du buffer la chaîne de longueur L commençant à Debut dans la chaîne C.

- les modules de gestion des trous

Inserer_trou (a, b, L) : insère le trou d’adresse (a, b) et de longueur L.

Supprimer_trou (a,b) : supprime le trou d’adresse (a, b)

Rechercher_trou(L, trouv, a, b, long) : recherche d’un trou de longueur � L. S’il est trouvé, Trouv est à vrai et (a, b est son adresse et Long sa longueur.

Est_ce_un_trou (a, b, trouv, L ) : si l’article à l’adresse (a, b) est un trou, Trouv est vrai et L est sa longueur.

- les modules sur les chaînes de caractères

Longchaine(C) : fournit la longueur de la chaîne C.

Caract(C, i) : fournit le i-ème caractère de la chaîne C.