Cours d'algorithmique

Partie 6.

Fichiers

COURS 17 : Introduction aux fichiers et aux structures de fichiers

COURS 18 : Concepts fondamentaux de structures de fichiers

COURS 19 : Maintenance de fichiers

COURS 20 : Tri de fichiers

TRAVAUX DIRIGES

Partie 8.

Fichiers

COURS 17 : Introduction aux fichiers et aux structures de fichiers

Objectifs : fournir les raisons d’utilisation des mémoires secondaires et introduire les notions de fichiers et de structures de fichiers; décrire le lien entre un fichier logique à l’intérieur d’un programme avec un fichier physique réel sur le support externe ; décrire les opérations fondamentales sur les fichiers : OUVRIR, CREER, FERMER, LIRE, ECRIRE, POSITIONNER

17.1 Raisons de l'utilisation des mémoires secondaires :

Bien que la mémoire centrale (RAM) fournit une forme d'accès simple et rapide, il existe plusieurs raisons qui nous poussent à ranger les informations sur mémoire externe plutôt qu'en RAM :

- l'espace RAM est assez limité comparé à l'espace mémoire externe,

- la RAM est beaucoup plus chère que la mémoire externe,

- la RAM est volatile( léger), la mémoire externe ne l'est pas.

17.2 Fichier

L'information en mémoire externe est organisée sous forme de fichiers. Un fichier peut être vu comme une collection d'octets représentant des informations. Ces octets sont organisés hiérarchiquement en structures afin de faciliter les opérations sur le fichier.

17.3 Structure de fichier

Le problème avec le stockage externe est la lenteur des accès aux données. Aussi, faut-il trouver une stratégie intelligente de rangement et de recherche de données. C'est ce que nous appelons structure de fichier (organisation imposée à un fichier afin de faciliter le traitement du fichier). L'idéal c'est d'avoir en un seul essai, l'information désirée. Ceci revient à dire que si nous désirons avoir plusieurs éléments d'informations, il faut les avoir tous à la fois plutôt que de faire des accès séparés pour chaque élément.

17.4 Fichiers physiques et fichiers logiques

Au niveau du programme on travaille sur un fichier logique ( vue abstraite). Un lien doit toujours être établi entre ce fichier logique et un fichier physique réel se trouvant sur un support externe. Dans certains langages, ceci est fait généralement dans le programme (en PASCAL ceci se fait avec l'instruction ASSIGN) ou à l'extérieur au niveau du langage de commande. Dans d'autres langages, le lien est établi à partir de l'opération CREER ou OUVRIR. L'opération FERMER détruit le lien entre le fichier logique et le fichier physique.

17.5 Ouverture, Création et fermeture

Ouverture : rend le fichier prêt pour son utilisation. Il y a positionnement au début du fichier

Création : ouvre le fichier dans le sens qu'il devient prêt pour son utilisation

Fermeture : rend l'accès impossible au fichier. Généralement la fermeture est automatique, pris en charge par le système de gestion de fichiers.

17. 6 Lecture et écriture

Les opérations LIRE et ECRIRE exigent 3 informations :

- le nom logique du fichier

- zone mémoire interne

- un indication sur la quantité d'information à lire ou à écrire.

Les opérations LIRE et ECRIRE sont suffisantes pour traiter le fichier séquentiellement, mais cette forme d'accès est inefficace dans la plupart des cas.

17.7 Détection de la fin de fichier

Une autre opération utile sur les fichiers est celle de la détection de fin de fichier. Elle prend des formes variées d'un langage à un autre.

17.8 L’opération de positionnement

Cette opération, quand elle existe, permet de positionner la tête de lecture/écriture à une position spécifique du fichier. Les langages qui fournissent cette opération autorise l'accès direct. Le fichier est alors vu comme un grand tableau.

17.9 Description algorithmique d’un fichier

On définit un fichier comme suit :

VAR Nom : FICHIER DE Type

Nom est le nom du fichier et Type est le type d’un article du fichier.

Le fichier peut être vu comme

un ensemble d’articles

un ensemble de blocs

Dans le cas où le fichier est vu comme un ensemble de blocs, on peut considérer les cas où les articles sont de longueur fixe ou variable. Dans le premier cas le bloc est contient au moins un tableau d’articles. Dans le second cas, un tableau de caractères.

Opérations

    Ouvrir (Nom) : ouverture du fichier
    Fermer(Nom) : fermeture du fichier

    Positionner (Nom, I) : positionnement au I-ème article (ou bloc) du fichier

    Lirefichier (Nom, Zone) : Lecture dans le buffer Zone de l'article courant
    Ecrirefichier (Nom, Zone) : Ecriture du buffer Zone à la position courante du fichier.

Les opérations Lirefichier et Ecrirefichier permettent d’avancer dans le fichier d’une unité. A l’ouverture du fichier, la position courante est 1.

Article ou bloc d’en-tête

Au sein d’un même fichier on peut avoir des articles ( ou blocs) de types différents : un type pour les articles (ou blocs) et un type pour l’article (bloc) d’en-tête contenant les caractéristiques du fichier, c’est à dire toutes les informations utiles pour l’exploitation du fichier.

On adopte la définition suivante :

    Type Nomdutype = Structure
        Cas Select de
            1 : ( définitions des champs de l'article (ou bloc) )
            2 : ( définitions des champs de l'article (ou bloc) d'en-tête)
    Fin

Afin de modifier le type courant, on positionne le sélecteur à 1 ou 2 selon que l’on fait une lecture (écriture) d’un article (bloc)du fichier ou d’un article(bloc) d’en-tête.

Si Zone est un variable du type Nomdutype, la sélection se fait par l’opération SELECT(Valeur) avec valeur dans {1, 2}. La sélection courante reste valide, jusqu’à la nouvelle opération de sélection.

17.10 Utilisation en PASCAL

Les principales opérations permettant de traiter un fichier en PASCAL sont les suivantes :

    - RESET()         :    Ouvre un fichier
    - REWRITE()        :      Crée un fichier
    - CLOSE()        :     Ferme un fichier
    - SEEK()        :     Se positionne à un endroit précis du fichier
    - READ()        :     Lit un enregistrement.
    - ECRIRE()        :     Ecrit un enregistrement

Exemple

Le programme qui suit

crée un fichier d’enregistrements

le parcours

lui rajoute un élément

et accède directement à certains enregistrement

PROGRAM Fichiers;
TYPE
    Type_article = RECORD
    Nom : STRING[12];
    Age : INTEGER;
    Poids : REAL
    END;
VAR
    Nom : STRING[12];
    Age : INTEGER;
    Poids : REAL;
    I : INTEGER;
    Article : Type_article;
    Fichier : File OF Type_article;

BEGIN
    ASSIGN(Fichier, 'Fich.Pas');
    REWRITE(Fichier);
    FOR I:= 1 TO 5 DO
        BEGIN
            WRITELN('Introduire Article Nø ', I );
           WRITE('Nom ?'); READLN (Nom);
           WRITE('Age ?'); READLN (Age);
           WRITE('Poids ?'); READLN (Poids);
          Article.Nom := Nom;
          Article.Age := Age;
          Article.Poids := Poids;
          WRITE(Fichier, Article)
     END;

    RESET(Fichier);
    WHILE NOT EOF(Fichier) DO
        BEGIN
        READ(Fichier, Article);
        WRITELN( Article.Nom, ' ',Article.Age, ' ', Article.Poids:4:2);
        READLN;
        END;

    SEEK(Fichier, Filesize(Fichier));
    FOR I:= 1 TO 2 DO
        BEGIN
        WRITELN('Introduire Un Autre Article' );
        WRITE('Nom ?'); READLN (Nom);
        WRITE('Age ?'); READLN (Age);
        WRITE('Poids ?'); READLN (Poids);
        Article.Nom := Nom;
        Article.Age := Age;
        Article.Poids := Poids;
        WRITE(Fichier, Article)
        END;

    SEEK(Fichier, 2);
    READ(Fichier, Article);
    WRITELN( Article.Nom, ' ',Article.Age, ' ', Article.Poids:4:2);
    READLN;

    SEEK(Fichier, 6);
    READ(Fichier, Article);
    WRITELN( Article.Nom, ' ',Article.Age, ' ', Article.Poids:4:2);
    READLN;
END.

COURS 18 :Concepts fondamentaux de structures de fichiers

Objectifs : Introduire les concepts de structures de fichiers suivants : - fichier continu ( stream en anglais ) - limites des champs et des articles - articles et champs de longueur fixe et variable; - recherche séquentielle - accès direct - accès au fichier et organisation du fichier

18.1 Fichier continu

Le niveau le plus bas d'organisation de fichier est de considérer le fichier comme une suite continue de caractères.

Exemple : lecture d’un fichier TEXT en PASCAL.

Le fichier est une suite continue de caractères (octets). Aucune information supplémentaire est ajoutée pour distinguer les agrégats. ces derniers sont appelés champ. Un champs est la plus petite unité logique d'information dans un fichier. Un champ est une notion logique, c'est un outil conceptuel.

18.2 Structures des champs

On peut délimiter les champs de plusieurs façons :

- fixer la longueur du champ

- commencer chaque champ par un indicateur de longueur

- placer un délimiteur à la fin de chaque champ pour le séparer du prochain.

18.3 Structures des articles

Un article est un ensemble de champs formant une même entité quand le fichier est vu en terme d'un haut niveau d'organisation.

Un article est un outil logique conceptuel.

Les structures possibles d’un article peuvent être comme suit :

- fixer la longueur de l'article en nombre d'octets ou en nombre de champs,

- commencer chaque article avec un indicateur de longueur ( nombre d'octets ),

- utiliser un second fichier (index) pour garder la trace des adresses octets de chaque article,

- placer un délimiteur à la fin de chaque article pour le séparer du prochain article.

18.4 L'accès séquentiel

Il s'agit de rechercher un élément en commençant par le début du fichier. Une boucle avec comme critère d'arrêt : fin de fichier rencontrée ou élément trouvé.

Le critère principal d’évaluation est le nombre de lectures ( nombre d'accès au disque )

Si le fichier possède n articles, il faut au plus n accès pour retrouver un élément et en moyenne n/2 accès. Une recherche séquentielle est aussi dite de l'ordre de O(n), c’est à dire proportionnel à n.

Un façon d’améliorer la recherche séquentielle est regrouper plusieurs articles par bloc.

Un Bloc peut être vu comme un collection d'articles rangés comme une unité physiquement contiguë.

Sur le disque, l'opération de positionnement du bras est beaucoup plus lente que le transfert lui même : Le coût de positionnement d'un article et de son transfert, puis le positionnement d'un autre article et de son transfert est plus grand que celui de positionnement juste une fois suivi du transfert des 2 articles à la fois.

On peut donc améliorer le coût de la recherche en lisant dans un bloc plusieurs articles à la fois, puis traiter le bloc d'articles en RAM.

Comme exemple, si on a fichier de 1000 articles, une recherche séquentielle sans bloc ( non bufferisée) exige en moyenne 5OO lectures. En utilisant des blocs de 32 articles, le nombre moyen de lectures devient égal à 15. Chaque lecture exige alors un peu plus de temps, puisque plus de données sont transférées, ce qui est meilleur que des lectures individuelles pour chaque article.

On pourra parler de lecture physique et de lecture logique.

18.5 L'accès direct

Le plus simple format d'article permettant l'accès direct par numéro relatif implique l'utilisation des articles de longueur fixe. Quand la donnée elle-même est composée de quantité de taille fixe ( par exemple des codes), les articles de longueur fixe fournissent de bonne performance et une bonne utilisation de l'espace.

A chaque article est associé un numéro relatif de l'article dans le fichier. Ce dernier est considéré comme un tableau d'articles. le premier article a un numéro relatif égal à 0, le second 1, etc.

On ne peut faire çà que dans le cas des articles de longueur fixe.

Si r est la taille d'un article (en octets), le déplacement octet de l'article de numéro n est égal à nr.

Si la taille des données dans un article est variable, beaucoup d'espace sera perdu. Dans cette situation, le concepteur doit analyser le problème avec prudence sur la possibilité d'utiliser des articles de longueur variable.

18.6 Article d'en-tête

Quelquefois, il est utile de garder la trace de certaines informations du fichier telles que le nombre d'articles, date de création, dernière version, etc. Un article d'en-tête est alors utilisé.

C'est un article placé au début du fichier donnant des informations sur le fichier.

18.7 Méthode d’accès aux fichiers et organisation du fichier.

Il est important de savoir la différence entre l'accès au fichier et l'organisation du fichier.

Méthode d'accès du fichier : approche utilisée pour localiser un article dans le fichier. En général, 2 alternatives : l'accès séquentiel t l'accès direct.

Méthode d'organisation de fichier : Combinaisons de structures conceptuelles et physiques utilisées pour distinguer un champ d'un autre et un article d'un autre. Un exemple de sorte d'organisation d'un fichier est : article de longueur fixe contenant un nombre variable de champs délimités de longueurs variables

18.8 Exemple (en PASCAL)

Le programme PASCAL qui suit réalise les opérations suivantes :

- Création

- Ouverture

- Fermeture

- Insertion de clés générées aléatoirement

- Parcours séquentiel et listage

- Recherche séquentielle d'articles

PROGRAM Fichier1;
CONST
    B = 10;
TYPE
    Typecle = INTEGER ;
    Typeqq = STRING[20] ;
    Nature = (Inf, Table);
    Typearticle = RECORD
        Cle : Typecle;
        Info : Typeqq
    END;
    Typebloc = RECORD
    CASE Diff : Nature OF
    1 : ( Nombre : INTEGER;
           Tab : ARRAY[1..B] OF Typearticle );
    2 : ( Nombre_elements, Efface, Dernierblocseq, Dernierseq: INTEGER )
    END;

VAR
    Fs : TEXT;
    I : INTEGER;
    Efface, Nombre_elements : INTEGER;
    F : File OF Typebloc;
    Dernierseq,Dernierblocseq : INTEGER;
    Bloc : Typebloc;

    { Création du fichier }
    PROCEDURE Creation;
    BEGIN
        Bloc.Diff := Inf;
        Bloc.Nombre_elements := 0;
        Bloc.Efface := 0;
        Bloc.Dernierblocseq := 1;
        Bloc.Dernierseq := 0;
        REWRITE(F);
        SEEK(F, 0);
        WRITE(F, Bloc);
        CLOSE(F)
    END;

    { Ouverture du fichier }
    PROCEDURE Ouvrir;
    BEGIN
        Bloc.Diff := Inf;
        RESET(F);
        SEEK(F, 0);
        READ(F, Bloc);
        Efface := Bloc.Efface;
        Nombre_elements := Bloc.Nombre_elements;
        Dernierblocseq := Bloc.Dernierblocseq;
        Dernierseq := Bloc.Dernierseq;
    END;

    { Fermeture du fichier }
    PROCEDURE Fermer;
    BEGIN
        Bloc.Diff := Inf;
        Bloc.Nombre_elements := Nombre_elements;
        Bloc.Efface := Efface;
        Bloc.Dernierblocseq := Dernierblocseq;
        Bloc.Dernierseq := Dernierseq;
        RESET(F);
        SEEK(F, 0);
        WRITE(F, Bloc);
    END;

    { Parcours séquentiel du fichier et listage de ses éléments sur un fichier TEXT }
    PROCEDURE Impseq;
    VAR
        I, J : INTEGER;
    BEGIN
        RESET(F);
        { Les caractéristiques }
        WRITELN(Fs, 'Caractéristiques du fichier : ');
        WRITELN(Fs);
        WRITELN(Fs, '- Nombre d''articles : ', Nombre_elements );
        WRITELN(Fs, '- Nombre d''articles effac‚s :', Efface);
        WRITELN(Fs, '- Dernier bloc :', Dernierblocseq);
        WRITELN(Fs, '- Dernier indice dans le dernier bloc :', Dernierseq);
        WRITELN(Fs);
        WRITELN(Fs);
        WRITELN(Fs, 'Contenu du fichier : ');
        FOR I:=2 TO Dernierblocseq DO
        BEGIN
                SEEK(F, I-1);
            READ(F, Bloc);
            WRITELN(Fs);
            WRITELN(Fs, 'Bloc ',I, ' :');
            FOR J:=1 TO Bloc.Nombre DO
                    WRITE(Fs, Bloc.Tab[J].Cle, ' ' );
            WRITELN(Fs);
        END;
    END;

    { Insertion en fin de fichier }
    PROCEDURE Add (Cle : INTEGER);
    BEGIN
    Nombre_elements := Nombre_elements + 1 ;
    Inc(Dernierseq);
    IF Dernierseq <= B
    THEN
        BEGIN
                Bloc.Tab[Dernierseq].Cle:= Cle;
            Inc(Bloc.Nombre)
        END
    ELSE
        BEGIN
            Inc(Dernierblocseq);
            SEEK(F, Dernierblocseq - 1);
            WRITE(F, Bloc);
            Bloc.Tab[1].Cle := Cle;
            Bloc.Nombre := 1;
            Dernierseq := 1;
        END;
    END;

    { Recherche séquentielle d'un article de clé donnée }
    FUNCTION Recherche (Clef : INTEGER) : BOOLEAN;
    VAR
        I, J : INTEGER;
        Trouv : BOOLEAN;
    BEGIN
        WRITELN(Fs, ' Recherche de ', Clef, ' ...');
        RESET(F);
        I:= 2;
        Trouv := FALSE;
        WHILE (I <= Dernierblocseq ) AND NOT Trouv DO
            BEGIN
                SEEK(F, I-1);
            READ(F, Bloc);
            J:= 1;
            WHILE (J <=Bloc.Nombre) AND NOT Trouv DO
                    IF Bloc.Tab[J].Cle = Clef
                THEN Trouv := TRUE
                ELSE J := J + 1;
            I := I + 1
        END;
    Recherche := Trouv;
    END;

BEGIN
    ASSIGN(Fs, 'R_F1.Pas');
    REWRITE(Fs);
    ASSIGN(F, 'Fichier');
    WRITELN(Fs, 'Cr‚ation du fichier...');
    WRITELN(Fs);
    Creation;
    WRITELN(Fs, 'Ouverture du fichier...');
    WRITELN(Fs);
    Ouvrir;
    WRITELN(Fs, 'Insertion de 55 articles de clés générées aléatoirement...');
    WRITELN(Fs);
    Bloc.Diff := Table;
    Bloc.Nombre := 0;
    FOR I:=1 TO 55 DO
        Add( Random(1000) );
    { Ecriture Dernier Bloc }
    IF Dernierseq > 0
    THEN
    BEGIN
        Inc(Dernierblocseq);
        SEEK(F, Dernierblocseq - 1);
        WRITE(F, Bloc);
    END;
    CLOSE(F);

    { Parcours séquentiel du fichier et listage de ses éléments }
    Impseq;

    WRITELN(Fs);
    WRITELN(Fs, 'Recherche d''articles...');
    WRITELN(Fs);
    IF Recherche(993)
    THEN WRITELN(Fs, 'Article existe')
    ELSE WRITELN(Fs, 'Article n''existe pas');

    IF Recherche(374)
    THEN WRITELN(Fs, 'Article existe')
    ELSE WRITELN(Fs, 'Article n''existe pas');

    IF Recherche(164)
    THEN WRITELN(Fs, 'Article existe')
    ELSE WRITELN(Fs, 'Article n''existe pas');

    IF Recherche(858)
    THEN WRITELN(Fs, 'Article existe')
    ELSE WRITELN(Fs, 'Article n''existe pas');

    IF Recherche(402)
    THEN WRITELN(Fs, 'Article existe')
    ELSE WRITELN(Fs, 'Article n''existe pas');

    IF Recherche(616)
    THEN WRITELN(Fs, 'Article existe')
    ELSE WRITELN(Fs, 'Article n''existe pas');

    WRITELN(Fs);
    WRITELN(Fs, 'Fermeture du fichier...');
    Fermer;
    CLOSE(Fs);
END.

Les Résultats

Contenu du fichier R_F1.PAS
Création du fichier...

Ouverture du fichier...

Insertion de 55 articles de cl‚s générées aléatoirement...

Caractéristiques du fichier :

- Nombre d'articles : 55
- Nombre d'articles effacés :0
- Dernier bloc :7
- Dernier indice dans le dernier bloc :5

Contenu du fichier :

Bloc 2 :
0 56 429 276 886 17 885 603 395 896

Bloc 3 :
374 116 624 106 914 221 115 111 768 490

Bloc 4 :
722 323 53 96 657 593 541 164 111 286

Bloc 5 :
573 776 300 828 643 993 278 191 216 330

Bloc 6 :
244 404 820 420 858 632 756 641 494 406

Bloc 7 :
536 502 635 853 616

Recherche d'articles...

Recherche de 993 ...
Article existe
Recherche de 374 ...
Article existe
Recherche de 164 ...
Article existe
Recherche de 858 ...
Article existe
Recherche de 402 ...
Article n'existe pas
Recherche de 616 ...
Article existe

Fermeture du fichier...

COURS 19: Maintenance de fichier

Objectifs : définir les notions de réorganisations statique et dynamique comme des moyens de réutiliser l’espace dans un fichier.

19.1 Maintenance du fichier

Le concepteur doit définir :

- la méthode d'accès et

- l'organisation du fichier.

Le concepteur doit aussi définir les sortes de changement que le fichier subit pendant sa vie.

Si le fichier est très volatile ( ou dynamique, c’est à dire qui subit beaucoup d'insertions et de suppressions ) et est utilisé dans un environnement temps-réel, l'organisation du fichier devrait faciliter les changements rapides. Un fichier de réservation de places est un bon exemple de fichier volatile utilisé en temps réel ( fichier on-line).

A l'autre extrême, on a des fichiers off-line qui subissent très peu de changements et n'exigent pas d'être à jour momentanément. Dans ses fichiers, on a pas besoin d'inclure des extra-structures pour permettre les changements rapides. Un exemple de fichier off-line est un fichier de courrier que l’on pourrait consulter en différé.

La maintenance d'un fichier est importante car, en général, les performances se détériorent quand les changements sont faits sur le fichier. Par exemple, une modification d'un article dans un fichier de longueur variable est telle que le nouveau article est de taille plus grande. Que faire ?

- On pourra utiliser un chaînage vers la fin du fichier, puis ajouté l'information supplémentaire.

- On pourra réécrire tout l'article à la fin du fichier( à moins que le fichier est ordonné) laissant ainsi un "trou" dans l'emplacement original de l'article.

Les modifications sont de 3 formes :

- ajout d’un article,

- mise à jour d'un article,

- suppression d'un article.

Si le seul changement dans le fichier est un ajout d'articles, il n'y a pas de détérioration. C'est seulement quand des articles de longueur variable sont modifiés, ou quand des articles de longueurs fixes ou variables sont supprimés que la maintenance du fichier devient compliquée et intéressante. Comme une mise à jour peut toujours être traitée comme une suppression suivie d'un ajout, notre intérêt portera uniquement sur la suppression d'articles. Quand un article est supprimé, nous devons réutilisé l'espace. Aussi, dans ce qui suit nous allons analyser de plus près comment récupérer cet espace.

19.2 Réorganisation

Quand on supprime un article, on place généralement une marque spéciale.

maintenant, comment récupérer l'espace ?

Les articles ainsi effacés ( effacement logique ), restent dans cet état une période de temps. On pourra alors les récupérer.

Un programme spécial de réorganisation ou de compactage est alors utilisé pour reconstruire le fichier sans les articles effacés (effacement physique). Le critère de lancement peut être le nombre d'articles effacés ou selon un calendrier.

Pour certaines applications, on aimerait récupérer l'espace le plus tôt possible ( fichiers dynamiques , temps réel, ..). C’est ce qu’on appelle réorganisation dynamique.

Il existe des méthodes qui permettent la récupération dynamique des articles effacés pour un fichier où les articles sont de longueur fixe ou variable. Ces techniques utilisent les concept de liste linéaire chaînée.

19.3 Exemple de programme de réorganisation

Ce programme utilise le fichier créé par le programme précédent pour faire les opérations suivantes :

- Ouvre un fichier existant

- Rajoute des articles en fin de fichier

- Supprime logiquement des articles

- Ferme le fichier.

- Réorganise le fichier par la construction d’un autre.

PROGRAM Fichier2;
CONST
    B = 10;
TYPE
    Typecle = INTEGER ;
    Typeqq = STRING[20] ;
    Nature = (Inf, Table);
    Typearticle = RECORD
        Cle : Typecle;
        Info : Typeqq
    END;
    Typebloc = RECORD
    CASE Diff : Nature OF
        1 : ( Nombre : INTEGER;
                Tab : ARRAY[1..B] OF Typearticle );
        2 : ( Nombre_elements, Efface, Dernierblocseq, Dernierseq: INTEGER )
    END;

VAR
    Fs : TEXT;
    Efface, Nombre_elements : INTEGER;
    F : File OF Typebloc;
    Dernierseq,Dernierblocseq : INTEGER;
    Bloc : Typebloc;

    { Ouverture du fichier }
    PROCEDURE Ouvrir;
    BEGIN
        Bloc.Diff := Inf;
        RESET(F);
        SEEK(F, 0);
        READ(F, Bloc);
        Efface := Bloc.Efface;
        Nombre_elements := Bloc.Nombre_elements;
        Dernierblocseq := Bloc.Dernierblocseq;
        Dernierseq := Bloc.Dernierseq;
    END;

    { Fermeture du fichier }
    PROCEDURE Fermer;
    BEGIN
        Bloc.Diff := Inf;
        Bloc.Nombre_elements := Nombre_elements;
        Bloc.Efface := Efface;
        Bloc.Dernierblocseq := Dernierblocseq;
        Bloc.Dernierseq := Dernierseq;
        RESET(F);
        SEEK(F, 0);
        WRITE(F, Bloc);
    END;

    { Parcours séquentiel du fichier et listage de ses éléments sur un fichier TEXT }
    PROCEDURE Impseq;
    VAR
        I, J : INTEGER;
    BEGIN
        RESET(F);
        { Les caractéristiques }
        WRITELN(Fs, '* * * Caractéristiques du fichier : ');
        WRITELN(Fs);
        WRITELN(Fs, '- Nombre d''articles : ', Nombre_elements );
        WRITELN(Fs, '- Nombre d''articles effacés :', Efface);
        WRITELN(Fs, '- Dernier bloc :', Dernierblocseq);
        WRITELN(Fs, '- Dernier indice dans le dernier bloc :', Dernierseq);
        WRITELN(Fs);
        WRITELN(Fs, '* * * Contenu du fichier : ');
        FOR I:=2 TO Dernierblocseq DO
        BEGIN
             SEEK(F, I-1);
            READ(F, Bloc);
            WRITELN(Fs);
            WRITELN(Fs, 'Bloc ',I, ' :');
            FOR J:=1 TO Bloc.Nombre DO
                    WRITE(Fs, Bloc.Tab[J].Cle, ' ' );
            WRITELN(Fs);
        END;
    END;

    { Recherche séquentielle d'un article de clé donnée }
    FUNCTION Recherche (Clef : INTEGER) : BOOLEAN;
    VAR
        I, J : INTEGER;
        Trouv : BOOLEAN;
    BEGIN
        RESET(F);
        I:= 2;
        Trouv := FALSE;
        WHILE (I <= Dernierblocseq ) AND NOT Trouv DO
        BEGIN
            SEEK(F, I-1);
            READ(F, Bloc);
            J:= 1;
            WHILE (J <=Bloc.Nombre) AND NOT Trouv DO
                IF Bloc.Tab[J].Cle = Clef
                THEN Trouv := TRUE
                ELSE J := J + 1;
            I := I + 1
        END;
        Recherche := Trouv;
    END;

    { Ajouter un article à un fichier }
    PROCEDURE Ajouter (Cle : INTEGER);
    BEGIN
        WRITELN(Fs, 'Ajout de l''article ', Cle, '...');
        Nombre_elements := Nombre_elements + 1 ;
        Inc(Dernierseq);
        IF Dernierseq <= B
        THEN
        BEGIN
             SEEK(F, Dernierblocseq - 1);
            READ(F, Bloc);
            Bloc.Tab[Dernierseq].Cle:= Cle;
            Inc(Bloc.Nombre);
            SEEK(F, Dernierblocseq - 1);
            WRITE(F, Bloc);
        END
        ELSE
        BEGIN
            Inc(Dernierblocseq);
            Bloc.Tab[1].Cle := Cle;
            Bloc.Nombre := 1;
            Dernierseq := 1;
            SEEK(F, Dernierblocseq - 1);
            WRITE(F, Bloc);
        END;
    END;

    { Suppression d'un article de clé donnée }
    PROCEDURE Supprimer (Clef : INTEGER) ;
    VAR
        I, J : INTEGER;
        Trouv : BOOLEAN;
    BEGIN
        WRITELN(Fs, 'Supprimer l''article ', Clef, ' ...');
        RESET(F);
        I:= 2;
        Trouv := FALSE;
        WHILE (I <= Dernierblocseq ) AND NOT Trouv DO
        BEGIN
                SEEK(F, I-1);
                READ(F, Bloc);
                J:= 1;
                WHILE (J <=Bloc.Nombre) AND NOT Trouv DO
                     IF Bloc.Tab[J].Cle = Clef
                     THEN
                         BEGIN
                            Bloc.Tab[J].Cle := - 1;
                             SEEK(F, I-1);
                             WRITE(F, Bloc);
                             Efface := Efface + 1;
                             Trouv := TRUE
                         END
                     ELSE J := J + 1;
                 I := I + 1
        END;
        IF NOT Trouv THEN WRITELN(Fs, 'Article inexistant');
    END;

    { Réorganisation }
    PROCEDURE Reorganiser;
    VAR
        I, J : INTEGER;
        Dernierbloc, Dernier : INTEGER;
        Fnouv : File OF Typebloc;
        Blocnouv : Typebloc;
    PROCEDURE Add (Cle : INTEGER);
    BEGIN
        Inc(Dernier);
        IF Dernier <= B
        THEN
                BEGIN
                    Blocnouv.Tab[Dernier].Cle:= Cle;
                     Inc(Blocnouv.Nombre)
            END
        ELSE
                BEGIN
                     Inc(Dernierbloc);
                     SEEK(Fnouv, Dernierbloc - 1);
                     WRITE(Fnouv, Blocnouv);
                     Blocnouv.Tab[1].Cle := Cle;
                     Blocnouv.Nombre := 1;
                     Dernier := 1;
                END;
    END;

    BEGIN
        Blocnouv.Diff := Table;
        Blocnouv.Nombre := 0;
        Dernierbloc := 1;
        Dernier := 0;
        ASSIGN(Fnouv, 'Fnouveau');
        REWRITE(Fnouv);
        RESET(F);
        FOR I:=2 TO Dernierblocseq DO
        BEGIN
            SEEK(F, I-1);
            READ(F, Bloc);
            FOR J:=1 TO Bloc.Nombre DO
                IF Bloc.Tab[J].Cle <> - 1
                THEN Add ( Bloc.Tab[J].Cle )
        END;

        { Ecriture Dernier Bloc }
        IF Dernier > 0
       THEN
        BEGIN
            Inc(Dernierbloc);
            SEEK(Fnouv, Dernierbloc - 1);
            WRITE(Fnouv, Blocnouv);
        END;
        Blocnouv.Diff := Inf;
        Blocnouv.Dernierseq := Dernier;
        Blocnouv.Dernierblocseq := Dernierbloc;
        Blocnouv.Efface := 0;
        Blocnouv. Nombre_elements := Nombre_elements - Efface;
        WRITELN(Fs);
        WRITELN(Fs, '* * * Caractéristiques du nouveau fichier : ');
        WRITELN(Fs);
        WRITELN(Fs, '- Nombre d''articles : ', Blocnouv.Nombre_elements );
        WRITELN(Fs, '- Nombre d''articles Effac‚s :', Blocnouv.Efface);
        WRITELN(Fs, '- Dernier bloc :', Blocnouv.Dernierblocseq);
        WRITELN(Fs, '- Dernier indice dans le dernier bloc :', Blocnouv.Dernierseq);
        WRITELN(Fs);
        WRITELN(Fs, '* * * Contenu du nouveau fichier : ');
        SEEK(Fnouv, 0);
        WRITE(Fnouv, Blocnouv);
        CLOSE(Fnouv);
        RESET(Fnouv);
        FOR I:=2 TO Dernierbloc DO
        BEGIN
            SEEK(Fnouv, I-1);
            READ(Fnouv, Blocnouv);
            WRITELN(Fs, 'Bloc ',I, ' :');
            FOR J:=1 TO Blocnouv.Nombre DO
                WRITE(Fs, Blocnouv.Tab[J].Cle, ' ' );
            WRITELN(Fs);
        END;
    END;

BEGIN
    ASSIGN(Fs, 'R_F2.Pas');
    REWRITE(Fs);
    ASSIGN(F, 'Fichier');
    WRITELN(Fs, 'Ouverture du fichier...');
    WRITELN(Fs);
    Ouvrir;
    Bloc.Diff := Table;

    WRITELN(Fs, 'Rajout d''articles en fin de fichier...');
    IF NOT( Recherche(333) ) THEN Ajouter(333);
    IF NOT( Recherche(444)) THEN Ajouter(444);
    WRITELN(Fs);

    WRITELN(FS, 'Parcours séquentiel du fichier et listage de ses éléments...');
    WRITELN(Fs);
    Impseq;
    WRITELN(Fs);
    WRITELN(Fs, 'Suppression d''articles...');
    WRITELN(Fs);
    Supprimer(993);
    Supprimer(374);
    Supprimer(164);
    Supprimer(858);
    Supprimer(402);
    Supprimer(616);

    WRITELN(Fs);
    WRITELN(FS, 'Parcours séquentiel du fichier et listage de ses éléments...');
    WRITELN(Fs);
    Impseq;
    WRITELN(Fs, 'Fermeture du fichier...');
    WRITELN(Fs);
    Fermer;

    WRITELN(Fs, 'Reorganisation...');
    Reorganiser;
    WRITELN(Fs);
    CLOSE(Fs)
END.

Les résultats (Contenu du fichier R_f2.pas)

Ouverture du fichier...

Rajout d'articles en fin de fichier...
Ajout de l'article 333...
Ajout de l'article 444...

Parcours séquentiel du fichier et listage de ses éléments...

* * * Caractéristiques du fichier :

- Nombre d'articles : 57
- Nombre d'articles effacés :0
- Dernier bloc :7
- Dernier indice dans le dernier bloc :7

* * * Contenu du fichier :

Bloc 2 :
0 56 429 276 886 17 885 603 395 896

Bloc 3 :
374 116 624 106 914 221 115 111 768 490

Bloc 4 :
722 323 53 96 657 593 541 164 111 286

Bloc 5 :
573 776 300 828 643 993 278 191 216 330

Bloc 6 :
244 404 820 420 858 632 756 641 494 406

Bloc 7 :
536 502 635 853 616 333 444

Suppression d'articles...

Supprimer l'article 993 ...
Supprimer l'article 374 ...
Supprimer l'article 164 ...
Supprimer l'article 858 ...
Supprimer l'article 402 ...
Article inexistant
Supprimer l'article 616 ...

Parcours séquentiel du fichier et listage de ses éléments...

* * * Caractéristiques du fichier :

- Nombre d'articles : 57
- Nombre d'articles effacés :5
- Dernier bloc :7
- Dernier indice dans le dernier bloc :7

* * * Contenu du fichier :

Bloc 2 :
0 56 429 276 886 17 885 603 395 896

Bloc 3 :
-1 116 624 106 914 221 115 111 768 490

Bloc 4 :
722 323 53 96 657 593 541 -1 111 286

Bloc 5 :
573 776 300 828 643 -1 278 191 216 330

Bloc 6 :
244 404 820 420 -1 632 756 641 494 406

Bloc 7 :
536 502 635 853 -1 333 444
Fermeture du fichier...

Réorganisation...

* * * Caractéristiques du nouveau fichier :

- Nombre d'articles : 52
- Nombre d'articles Effacés :0
- Dernier bloc :7
- Dernier indice dans le dernier bloc :2

* * * Contenu du nouveau fichier :
Bloc 2 :
0 56 429 276 886 17 885 603 395 896
Bloc 3 :
116 624 106 914 221 115 111 768 490 722
Bloc 4 :
323 53 96 657 593 541 111 286 573 776
Bloc 5 :
300 828 643 278 191 216 330 244 404 820
Bloc 6 :
420 632 756 641 494 406 536 502 635 853
Bloc 7 :
333 444

COURS 20 : Tri de fichiers

Objectifs : décrire la manière de trier un fichier en présentant l’algorithme le plus usité qui est le tri par fusion.

20.1 Tri de tout le fichier en mémoire

Cette méthode est utilisée quand la taille du fichier n’est pas importante. Le fichier peut alors être entièrement mis en mémoire centrale.

La technique consiste donc à charger entièrement le fichier en mémoire dans un vecteur, puis réaliser le tri par l’une des méthodes vues précédemment. Le tri se fait bien entendu uniquement sur la clé.

L’algorithme pourrait être le suivant :

- Lire les articles du fichiers à trier dans un tableau ARTICLE

Extraire les clés des articles afin de construire la table CLE

Former la table INDEX des indices

Trier le fichier INDEX en se basant sur le tableau CLE

Construire le fichier trié à partir du vecteur INDEX.

20. 2 Tri entièrement en mémoire uniquement des clés du fichier

On ne charge que les clés du fichier avant de réaliser le tri entièrement en mémoire.

L’algorithme est le suivant :

Récupérer toutes les clés des articles dans la table CLE

Former la table INDEX des indices

Trier le fichier INDEX en se basant sur le tableau CLE

Récupérer l’article du du fichier de donner pour l’écrire sur le fichier résultat.

L’inconvénient de cette technique réside dans les positionnements aléatoires des têtes de lectures/écriture dus aux deuxièmes lectures obligatoires des articles. Par contre, l’avantage par rapport à la première méthode est que l’on peut trier des fichiers de tailles beaucoup plus grandes.

20.3 Tri par fusion

C’est la technique la plus générale. Elle est utilisée pour trier des grands fichiers.

Si on dispose d’un méga RAM, avec des articles de 100 octets chacun, on pourra trier en mémoire centrale des portions de

1000 000 / 100 = 10 000 articles

On peut énoncer l’algorithme comme suit :

Lire les articles en RAM dans un tableau tant qu’il y a de la place.

Trier ce tableau

Le mettre dans un fichier

Répéter ces trois opérations autant de fois qu’il faut jusqu’à épuisement de tous les articles du fichier. On construit ainsi un ensemble de n fichiers triés.

Appliquez l’algorithme de fusion à ces n fichiers.

Avantages

Chaque article est lu seulement une fois.

Quelque soit la taille du fichier, on peut appliquer cette méthode.

La lecture du fichier d’entrée est complètement séquentielle, ce qui est plus efficace que la deuxième méthode exposée.

Les lectures durant la phase de fusion et les écritures sont aussi séquentielles.

On utilise les opérations de positionnement uniquement quand on charge un buffer.

Supposons que la taille d’un fichier soit réservé pour tous les buffers utilisés.

40 fichiers * 10 Positionnements/Fichier = 1600 Positionnements.

Comme il y a 40 fichiers, on aura 40 buffers de 1/40 de la taille du fichier.

Amélioration

On peut améliorer la technique en effectuant la fusion sur plusieurs étapes en réduisant le degré de fusion et en incrémentant la taille des buffers.

Au lieu de fusionner les 4O fichiers d’un seul coup, on procède autrement. On fait par exemple une fusion 8 :8 :8 :8 :8

Une fois qu’on a construit les 4O fichiers initiaux, on applique 5 fois la fusion pour construire donc 5 fichiers intermédiaires. Enfin, on applique une seule fusion sur ces fichiers pour obtenir le fichier désiré.

L’inconvénient de cette méthode est que chaque article est lu 2 fois. Par contre l’avantage est que l’on peut utiliser les grands buffers, ce qui permet de réduire les opérations de positionnement.

Pour chacune des 5 fusions ( sur 8 fichiers) on utilise 8 buffers de 1/8 de la taille du fichier. Donc 8 positionnements / fichier * 8 fichiers = 64 positionnements. Pour toutes les fusions on aura 5 fichiers * 40 positionnements/fichier = 200 Positionnements.

Le nombre total de Positionnements est alors de 320 + 200 = 520.

En acceptant de lire deux fois le même article, on réduit le nombre de Positionnements par 2/3.

Si nous prenons un fichier de 800 000 articles, on aura 80 fichiers initiaux, ce qui nous fait 6400 Positionnements.

En utilisant une fusion 10 :10 :10 :10 : 10 :10 :10 :10, on réduira le nombre de Positionnements à 640 + 800 = 1440 !

20.4 Programmation du tri par fusion en PASCAL

Dans ce qui suit, nous présentons deux programmes. Le premier construit n fichiers triés à partir d’un fichier trié. Le second fusionne ces n fichiers. Nous fournissons également les résultats détaillés pour ces deux programmes.

Premier programme : construction de n fichiers triés à partir d’un fichier non trié

PROGRAM Fichier3;
CONST
    B = 10;
TYPE
    Typecle = INTEGER ;
    Typeqq = STRING[20] ;
    Nature = (Inf, Table);
    Typearticle = RECORD
        Cle : Typecle;
        Info : Typeqq
    END;
    Typebloc = RECORD
        CASE Diff : Nature OF
    1 : ( Nombre : INTEGER;
    Tab : ARRAY[1..B] OF Typearticle );
    2 : ( Nombre_elements, Efface, Dernierblocseq, Dernierseq: INTEGER )
    END;
    Typefichier = File OF Typebloc;
VAR
    Fs : TEXT;
    I, J : INTEGER;
    Efface, Nombre_elements : INTEGER;
    F : File OF Typebloc;
    Dernierseq,Dernierblocseq : INTEGER;
    Bloc : Typebloc;
    F1 : Typefichier;
    Dernierseq1,Dernierblocseq1 : INTEGER;
    Bloc1 : Typebloc;

    Depl, Numbloc : INTEGER;
    Temp, S : Typearticle;
    Tab : ARRAY[1..20] OF Typearticle;
    K : INTEGER;
    Num : INTEGER;

    { Ouverture du fichier }
    PROCEDURE Ouvrir;
    BEGIN
        Bloc.Diff := Inf;
        RESET(F);
        SEEK(F, 0);
        READ(F, Bloc);
        Efface := Bloc.Efface;
        Nombre_elements := Bloc.Nombre_elements;
        Dernierblocseq := Bloc.Dernierblocseq;
        Dernierseq := Bloc.Dernierseq;
    END;

    { Parcours séquentiel du fichier et listage de ses éléments sur un fichier TEXT }
    PROCEDURE Impseq;
    VAR
        I, J : INTEGER;
    BEGIN
        RESET(F1);
        { Les caract‚ristiques }
        WRITELN(Fs, ' + Caractéristiques du fichier : ');
        WRITELN(Fs);
        WRITELN(Fs, ' >> Nombre d''articles : ', Nombre_elements );
        WRITELN(Fs, ' >> Nombre d''articles effac‚s :', Efface);
        WRITELN(Fs, ' >> Dernier bloc :', Dernierblocseq1);
        WRITELN(Fs, ' >> Dernier indice dans le dernier bloc :', Dernierseq1);
        WRITELN(Fs);
        WRITELN(Fs);
        WRITELN(Fs, ' + Contenu du fichier : ');
        FOR I:=2 TO Dernierblocseq1 DO
        BEGIN
             SEEK(F1, I-1);
            READ(F1, Bloc1);
            WRITELN(Fs);
            WRITELN(Fs, 'Bloc ',I, ' :');
            FOR J:=1 TO Bloc1.Nombre DO
                WRITE(Fs, Bloc1.Tab[J].Cle, ' ' );
            WRITELN(Fs);
        END;
    END;
    { Insertions répétées en fin de fichier }
    PROCEDURE Add (Article : Typearticle);
    BEGIN
        Nombre_elements := Nombre_elements + 1 ;
        Inc(Dernierseq1);
        IF Dernierseq1 <= B
        THEN
            BEGIN
                Bloc1.Tab[Dernierseq1]:= Article;
                Inc(Bloc1.Nombre)
            END
        ELSE
            BEGIN
                Inc(Dernierblocseq1);
                SEEK(F1, Dernierblocseq1 - 1);
                WRITE(F1, Bloc1);
                Bloc1.Tab[1] := Article;
                Bloc1.Nombre := 1;
                Dernierseq1 := 1;
            END;
    END;

    PROCEDURE Suivant ( VAR S: Typearticle);
    BEGIN
        IF (Numbloc= Dernierblocseq) AND (Depl >= Dernierseq)
        THEN S.Cle := -1
        ELSE
            BEGIN
                Depl := Depl + 1;
                IF Depl <= B
                THEN
                     S := Bloc.Tab(.Depl.)
                ELSE
                     IF Numbloc = Dernierblocseq
                     THEN S.Cle := - 1
                     ELSE
                        BEGIN
                             Numbloc := Numbloc + 1;
                             SEEK(F, Numbloc-1);
                             READ(F, Bloc);
                             Depl := 1;
                             S := Bloc.Tab(.Depl.)
                        END;
            END;
    END;

BEGIN
    ASSIGN(Fs, 'R_f3.Pas');
    REWRITE(Fs);
    ASSIGN(F, 'Fichier');
    WRITELN(Fs, 'Ouverture du fichier...');
    WRITELN(Fs);
    Ouvrir;
    WRITELN(Fs, 'Construction des fichiers...');
    Depl := 0;
    Numbloc := 2;
    SEEK(F, 1);
    READ(F, Bloc);
    Num:= 0;
    Suivant(S);
    WHILE S.Cle <> -1 DO
    BEGIN
    WRITELN(Fs);
    WRITELN(Fs, '* * * Chargement d''une partie du fichier dans un tableau...');
    WRITELN(Fs);
    K:=1;
    WHILE (K <= 20) AND (S.Cle <> -1) DO
    BEGIN
        Tab(.K.) := S;
        Suivant(S);
        K:= K + 1
    END;
    K:= K-1;
    WRITELN(Fs, '* * * Tri en mémoire...');
    WRITELN(Fs);
    FOR I:= 1 TO K-1 DO
        FOR J:=K DOWNTO I+1 DO
            IF Tab(.J-1.).Cle > Tab(.J.).Cle
            THEN
                 BEGIN
                    Temp := Tab(.J-1.);
                    Tab(.J-1.) := Tab(.J.);
                    Tab(.J.) := Temp
                 END;

    WRITELN(Fs, 'Résultat du tri :');
    WRITELN(Fs);
    FOR I:=1 TO K DO
        WRITELN(Fs, Tab(.I.).Cle );
    WRITELN(Fs);
    WRITELN(Fs, '* * * Recopier le tableau sur un fichier...');
    WRITELN(Fs);
    Num := Num + 1;
    ASSIGN(F1, 'Fichier'+CHR( 48+Num) );
    REWRITE(F1);
    Bloc1.Diff := Table;
    Bloc1.Nombre := 0;
    Dernierblocseq1 := 1;
    Dernierseq1 := 0;
    Nombre_elements := 0;
    Efface := 0;
    FOR I:=1 TO K DO
        Add( Tab(.I.) );

    { Ecriture Dernier Bloc }
    IF Dernierseq1 > 0
    THEN
        BEGIN
             Inc(Dernierblocseq1);
            SEEK(F1, Dernierblocseq1 - 1);
            WRITE(F1, Bloc1);
        END;
    Bloc1.Diff := Inf;
    Bloc1.Nombre_elements := Nombre_elements;
    Bloc1.Efface := Efface;
    Bloc1.Dernierblocseq := Dernierblocseq1;
    Bloc1.Dernierseq := Dernierseq1;
    RESET(F1);
    SEEK(F1, 0);
    WRITE(F1, Bloc1);
    WRITELN(Fs, 'Parcours séquentiel du fichier et listage de ses éléments');
    WRITELN(Fs);
    Impseq;
    END;
    CLOSE(Fs);
END.

Les résultats (Contenu du fichier R_F3.pas)

Ouverture du fichier...

Construction des fichiers...

* * * Chargement d'une partie du fichier dans un tableau...

* * * Tri en mémoire...

Résultat du tri :17
56
106
111
115
116
221
276
374
395
429
490
603
624
768
885
886
896
914

* * * Recopier le tableau sur un fichier...

Parcours séquentiel du fichier et listage de ses éléments

+ Caractéristiques du fichier :

>> Nombre d'articles : 20
>> Nombre d'articles effacés :0
>> Dernier bloc :3
>> Dernier indice dans le dernier bloc :10

+ Contenu du fichier :

Bloc 2 :
0 17 56 106 111 115 116 221 276 374

Bloc 3 :
395 429 490 603 624 768 885 886 896 914

* * * Chargement d'une partie du fichier dans un tableau...

* * * Tri en m‚moire...

Résultat du tri :

53
96
111
164
191
216
278
286
300
323
330
541
573
593
643
657
722
776
828
993

* * * Recopier le tableau sur un fichier...

Parcours séquentiel du fichier et listage de ses éléments

+ Caractéristiques du fichier :

>> Nombre d'articles : 20
>> Nombre d'articles effacés :0
>> Dernier bloc :3
>> Dernier indice dans le dernier bloc :10

+ Contenu du fichier :

Bloc 2 :
53 96 111 164 191 216 278 286 300 323

Bloc 3 :
330 541 573 593 643 657 722 776 828 993

* * * Chargement d'une partie du fichier dans un tableau...

* * * Tri en m‚moire...

Résultat du tri :

244
404
406
420
494
502
536
616
632
635
641
756
820
853
858

* * * Recopier le tableau sur un fichier...

Parcours séquentiel du fichier et listage de ses éléments

+ Caractéristiques du fichier :

>> Nombre d'articles : 15
>> Nombre d'articles effacés :0
>> Dernier bloc :3
>> Dernier indice dans le dernier bloc :5

+ Contenu du fichier :

Bloc 2 :
244 404 406 420 494 502 536 616 632 635

Bloc 3 :
641 756 820 853 858

Deuxième programme : Fusion de n fichiers triés.

PROGRAM Fichier4;
CONST
    B = 10;
    Infini = 10000;
TYPE
    Typecle = INTEGER ;
    Typeqq = STRING[20] ;
    Nature = (Inf, Table);
    Typearticle = RECORD
        Cle : Typecle;
        Info : Typeqq
    END;
    Typebloc = RECORD
        CASE Diff : Nature OF
        1 : ( Nombre : INTEGER;
            Tab : ARRAY[1..B] OF Typearticle );
        2 : ( Nombre_elements, Efface, Dernierblocseq, Dernierseq: INTEGER )
        END;
    Typefichier = File OF Typebloc;
    Type_element = RECORD
        Numbloc : INTEGER;
        Depl : INTEGER;
        Dernierbloc : INTEGER;
        Dernier : INTEGER;
    Nombre_elements : INTEGER;
    Ptbloc : ^Typebloc;
    END;

VAR
    Fichier : ARRAY[1..10] OF Type_element;
    Tabmin : ARRAY[1..10] OF Typecle;
    Pluspetit : Typecle;
    Indice : INTEGER;
    Exist : BOOLEAN;
    Fs : TEXT;
    I : INTEGER;

    Efface, Nombre_elements : INTEGER;
    F, Fich, Fich1, Fich2, Fich3 : File OF Typebloc;
    Dernierseq,Dernierblocseq : INTEGER;
    Bloc : Typebloc;

    Depl, Numbloc : INTEGER;
    Temp, S : Typearticle;
    Tab : ARRAY[1..20] OF Typearticle;
    K : INTEGER;
    Num : INTEGER;

    { Création Du Fichier }
    PROCEDURE Creation;
    BEGIN
        Bloc.Diff := Inf;
        Bloc.Nombre_elements := 0;
        Bloc.Efface := 0;
        Bloc.Dernierblocseq := 1;
        Bloc.Dernierseq := 0;
        REWRITE(F);
        SEEK(F, 0);
        WRITE(F, Bloc);
        CLOSE(F)
    END;

    { Ouverture du fichier }
    PROCEDURE Ouvrir;
    BEGIN
        Bloc.Diff := Inf;
        RESET(F);
        SEEK(F, 0);
        READ(F, Bloc);
        Efface := Bloc.efface;
        Nombre_elements := Bloc.Nombre_elements;
        Dernierblocseq := Bloc.Dernierblocseq;
        Dernierseq := Bloc.Dernierseq;
    END;

    { Le minimum courant }
    PROCEDURE Min ( VAR Inf : Typecle; VAR Indice : INTEGER; VAR Exist : BOOLEAN);
    VAR
        I, NInfini : INTEGER;
    BEGIN
        Inf := Tabmin[1];
        Indice := 1;
        IF Tabmin[1] = Infini
        THEN NInfini := 1
        ELSE NInfini := 0;
        FOR I:=2 TO Num DO
            IF Tabmin[I] = Infini
            THEN NInfini := NInfini + 1
            ELSE
                     IF Inf > Tabmin[I]
            THEN
                    BEGIN
                        Inf := Tabmin[I];
                         Indice := I
                     END;
        Exist := NOT ( Num = NInfini )
    END;

    { Parcours séquentiel du fichier et listage de ses éléments sur un fichier TEXT }
    PROCEDURE Impseq;
    VAR
        I, J : INTEGER;
    BEGIN
        RESET(F);
        { Les caractéristiques }
        WRITELN(Fs, ' + Caractéristiques du fichier : ');
        WRITELN(Fs);
        WRITELN(Fs, ' >> Nombre d''articles : ', Nombre_elements );
        WRITELN(Fs, ' >> Nombre d''articles effac‚s :', Efface);
        WRITELN(Fs, ' >> Dernier bloc :', Dernierblocseq);
        WRITELN(Fs, ' >> Dernier indice dans le dernier bloc :', Dernierseq);
        WRITELN(Fs);
        WRITELN(Fs);
        WRITELN(Fs, ' + Contenu du fichier : ');
        FOR I:=2 TO Dernierblocseq DO
        BEGIN
            SEEK(F, I-1);
            READ(F, Bloc);
            WRITELN(Fs);
            WRITELN(Fs, 'Bloc ',I, ' :');
            FOR J:=1 TO Bloc.Nombre DO
                     WRITE(Fs, Bloc.Tab[J].Cle, ' ' );
            WRITELN(Fs);
        END;
    END;

    { Insertions répétées en fin de fichier }
    PROCEDURE Add (Article : Typearticle);
    BEGIN
        Nombre_elements := Nombre_elements + 1 ;
        Inc(Dernierseq);
        IF Dernierseq <= B
        THEN
            BEGIN
                Bloc.Tab[Dernierseq]:= Article;
                Inc(Bloc.Nombre)
            END
        ELSE
            BEGIN
                Inc(Dernierblocseq);
                SEEK(F, Dernierblocseq - 1);
                WRITE(F, Bloc);
                Bloc.Tab[1] := Article;
                Bloc.Nombre := 1;
                Dernierseq := 1;
           END;
    END;

    { Le suivant sur un fichier donné }
    PROCEDURE Suivant ( I : INTEGER; VAR S: Typearticle);
    BEGIN
        IF (Fichier[I].Numbloc= Fichier[I].Dernierbloc) AND (Fichier[I].Depl >= Fichier[I].Dernier)
        THEN S.Cle := Infini
        ELSE
        BEGIN
             Fichier[I].Depl := Fichier[I].Depl + 1;
            IF Fichier[I].Depl <= B
            THEN
                    S := Fichier[I].Ptbloc^.Tab(.Fichier[I].Depl.)
            ELSE
                IF Fichier[I].Numbloc = Fichier[I].Dernierbloc
                THEN S.Cle := Infini
                ELSE
                        BEGIN
                            Fichier[I].Numbloc := Fichier[I].Numbloc + 1;
                            CASE I of
                            1 : BEGIN
                                        SEEK(Fich1, Fichier[I].Numbloc-1);
                                        READ(Fich1, Fichier[I].Ptbloc^)
                                END;
                            2 : BEGIN
                                        SEEK(Fich2, Fichier[I].Numbloc-1);
                                        READ(Fich2, Fichier[I].Ptbloc^)
                                 END;
                            3 : BEGIN
                                         SEEK(Fich3, Fichier[I].Numbloc-1);
                                         READ(Fich3, Fichier[I].Ptbloc^)
                                 END;
                         END;
                 Fichier[I].Depl := 1;
                 S := Fichier[I].Ptbloc^.Tab(.Fichier[I].Depl.)
            END
        END;

BEGIN
    ASSIGN(Fs, 'R_f4.Pas');
    REWRITE(Fs);
    { Le fichier à créer }
    ASSIGN(F, 'Fichier');
    WRITELN(Fs, 'Création du fichier...');
    WRITELN(Fs);
    Creation;
    WRITELN(Fs, 'Ouverture du fichier...');
    WRITELN(Fs);
    Ouvrir;
    Bloc.Diff := Table;
    Bloc.Nombre := 0;
    Num := 3;
    { Récupération des caractéristiques et chargement des premiers blocs de chaque fichier }
    FOR I:=1 TO Num DO
    BEGIN
        NEW(Fichier[I].Ptbloc);
        Fichier[I].Ptbloc^.Diff := Inf;
        ASSIGN(Fich, 'Fichier'+ CHR(48+I) );
        RESET(Fich);
        SEEK(Fich, 0);
        READ(Fich, Fichier[I].Ptbloc^);
        Fichier[I].Nombre_elements := Fichier[I].Ptbloc^.Nombre_elements;
        Fichier[I].Dernierbloc := Fichier[I].Ptbloc^.Dernierblocseq;
        Fichier[I].Dernier := Fichier[I].Ptbloc^.Dernierseq;
        Bloc.Diff := Table;
        Fichier[I].Depl := 0;
        Fichier[I].Numbloc := 2;
        SEEK(Fich, 1);
        READ(Fich, Fichier[I].Ptbloc^)
    END;

    ASSIGN(Fich1, 'Fichier1');
    ASSIGN(Fich2, 'Fichier2');
    ASSIGN(Fich3, 'Fichier3');
    RESET(Fich1);
    RESET(Fich2);
    RESET(Fich3);

    { Fusion des fichiers }
    FOR I:= 1 TO Num DO
    BEGIN
        Suivant(I, S);
        Tabmin[I] := S.Cle
    END;
    WRITELN(Fs, 'Trace de la fusion :');
    WRITELN(Fs);
    Min(Pluspetit, Indice, Exist);
    WHILE Exist DO
    BEGIN
        WRITELN(Fs, 'Fichier ', Indice, ' ----> ', Pluspetit);
        S.Cle := Pluspetit;
        Add( S);
        Suivant(Indice, S);
        Tabmin[Indice] := S.Cle;
        Min(Pluspetit, Indice, Exist)
    END;

    { Ecriture du dernier bloc }
    IF Dernierseq > 0
    THEN
    BEGIN
        Inc(Dernierblocseq);
        SEEK(F, Dernierblocseq - 1);
        WRITE(F, Bloc);
    END;
    Bloc.Diff := Inf;
    Bloc.Nombre_elements := Nombre_elements;
    Bloc.Efface := Efface;
    Bloc.Dernierblocseq := Dernierblocseq;
    Bloc.Dernierseq := Dernierseq;
    SEEK(F, 0);
    WRITE(F, Bloc);
    WRITELN(Fs);
    WRITELN(Fs, 'Parcours séquentiel du fichier et listage de ses éléments');
    WRITELN(Fs);
    Impseq;
    CLOSE(Fs);
END.

Les résultats (Contenu du fichier R_F4.PAS)

Création du fichier...Ouverture du fichier...Trace de la fusion :Fichier 1 ----> 0Fichier 1 ----> 17Fichier 2 ----> 53Fichier 1 ----> 56Fichier 2 ----> 96Fichier 1 ----> 106Fichier 1 ----> 111Fichier 2 ----> 111
Fichier 1 ----> 115
Fichier 1 ----> 116
Fichier 2 ----> 164
Fichier 2 ----> 191
Fichier 2 ----> 216
Fichier 1 ----> 221
Fichier 3 ----> 244
Fichier 1 ----> 276
Fichier 2 ----> 278
Fichier 2 ----> 286
Fichier 2 ----> 300
Fichier 2 ----> 323
Fichier 2 ----> 330
Fichier 1 ----> 374
Fichier 1 ----> 395
Fichier 3 ----> 404
Fichier 3 ----> 406
Fichier 3 ----> 420
Fichier 1 ----> 429
Fichier 1 ----> 490
Fichier 3 ----> 494
Fichier 3 ----> 502
Fichier 3 ----> 536
Fichier 2 ----> 541
Fichier 2 ----> 573
Fichier 2 ----> 593
Fichier 1 ----> 603
Fichier 3 ----> 616
Fichier 1 ----> 624
Fichier 3 ----> 632
Fichier 3 ----> 635
Fichier 3 ----> 641
Fichier 2 ----> 643
Fichier 2 ----> 657
Fichier 2 ----> 722
Fichier 3 ----> 756
Fichier 1 ----> 768
Fichier 2 ----> 776
Fichier 3 ----> 820
Fichier 2 ----> 828
Fichier 3 ----> 853
Fichier 3 ----> 858
Fichier 1 ----> 885
Fichier 1 ----> 886
Fichier 1 ----> 896
Fichier 1 ----> 914
Fichier 2 ----> 993

Parcours séquentiel du fichier et listage de ses éléments

+ Caractéristiques du fichier :

>> Nombre d'articles : 55
>> Nombre d'articles effacés :0
>> Dernier bloc :7
>> Dernier indice dans le dernier bloc :5

+ Contenu du fichier :

Bloc 2 :
0 17 53 56 96 106 111 111 115 116

Bloc 3 :
164 191 216 221 244 276 278 286 300 323

Bloc 4 :
330 374 395 404 406 420 429 490 494 502

Bloc 5 :
536 541 573 593 603 616 624 632 635 641

Bloc 6 :
643 657 722 756 768 776 820 828 853 858

Bloc 7 :
885 886 896 914 993

TRAVAUX DIRIGES

1. Construire un fichier F1 de 1000 entiers générés de manière aléatoires.

2. Construire un fichier F2 de tableaux de 10 éléments en prenant tous les éléments de
du fichier F1.

3. Construire un fichier F3 d'enregistrements contenant le carré, le cube, la racine carrée
et la racine cubique de chaque éléments du fichier F1.

4. Réaliser les 2 méthodes de tri exposées en 20-1 et 20-2 dans le cours.