Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Algorithmique et structures de données Chapitre 7 Les fichiers séquentiels 7.1

Algorithmique et structures de données Chapitre 7 Les fichiers séquentiels 7.1 Notion de fichier et définitions La structure de données dont nous envisageons maintenant l’étude est la structure de fichier séquentiel. L’accès séquentiel à des fichiers garde encore à l’heure actuelle une grande importance pratique dans les problèmes de gestion par exemple. Nous allons définir de façon abstraite les objets formant un fichier séquentiel comme une collection d’informations et les propriétés fonctionnelles de ces objets comme les caractéristiques formelles de cette collection. Cette démarche abstraite facilite la conception des algorithmes et des modèles de programmes manipulant ces objets. On distingue deux types de fichiers : les fichiers séquentiels et les fichiers à accès aléatoire. Dans un fichier à accès séquentiel, les valeurs ne peuvent être accédées que dans le même ordre dans lequel ils ont été stockés. Pour traiter un tel fichier, on doit se déplacer à travers les éléments successifs dans le même ordre que leurs emplacements respectifs dans la mémoire. Par contre, les valeurs dans un fichier aléatoire, aussi appelé fichier à accès direct, peuvent être accédées dans n’importe quel ordre voulu par le programmeur. Définition d’un fichier séquentiel Un fichier séquentiel sur un ensemble de valeurs E est une suite finie d’éléments de E, munie de certaines propriétés. Considérons par exemple :  un tiroir de fiches signalitiques de livres dans une bibliothèque,  la suite des enregistrements sur un cédérom,  la file des clients d’une banque attendant devant un guichet. Dans tous ces exemples, on peut définir : a) Un ensemble de places ou positions P totalement ordonné puisque l’on peut distinguer le premier enregistrement que l’on peut écouter sur un cédérom, le deuxième client qui passe devant le guichet, la dernière fiche du tiroir. b) Un ensemble de valeurs E : l’ensemble des fiches du tiroir, des clients de la banque, des morceaux de musique enregistrés. c) Dans tous les exemples précédents, l’opérateur humain est capable de détecter la fin de la bande, le dernier client, le dernière fiche. d) Fonctionnellement, on peut définir :  une correspondance entre une place de P et un élément de E,  un moyen de détecter la dernière place : une marque particulière peut être associée à cette place dans le cas du traitement du fichier par un automate,  un moyen d’accès à la première place de l’ensemble P. Dr Ndi Nyoungui André 1 Algorithmique et structures de données On remarque enfin, dans tous ces exemples, qu’un fichier séquentiel peut être considéré comme un support mobile défilant devant un repère fixe (par exemple, guichet de banque, tête de lecture du lecteur de cédérom). Le sens de défilement devant ce repère fixe (que nous appelons dans le schéma abstrait de représentation d’un fichier la tête de lecture/écriture) est toujours le même. En effet, lorsqu’un client est déjà passé devant le guichet, il ne lui est pas possible de repasser devant le même guichet sans avoir à reprendre place à la queue de la file. Nous avons donné un certain nombre de situations de la vie courante qui correspondent au modèle de fichier séquentiel. En informatique, d’autre part, on utilise un certain nombre de moyens de stockage d’informations, magnétiques ou optiques, dont le traitement par un dispositif électromagnétique de lecture/écriture correspond au modèle de fichier séquentiel. Ces dispositifs physiques (supports de fichiers dits séquentiels) sont les plus simples à réaliser techniquement. Ils ont non seulement un intérêt historique, mais encore une grande importance pratique dans les systèmes informatiques existants. 7.1.2 Définitions formelles Nous allons formaliser la notion de fichier séquentiel pour faciliter son utilisation dans l’écriture des algorithmes. Fichier séquentiel Définition Soient :  Un ensemble quelconque E de valeurs appelé ensemble des valeurs du fichier séquentiel,  Un ensemble fini P, totalement ordonné, appelé l’ensemble des places du fichier séquentiel. Un fichier séquentiel à valeurs dans E est une application f de P dans E. L’ensemble P des places du fichier peut être représenté par une suite d’emplacements mémoire consécutifs destinés au stockage des composantes du fichier. 7.1.3 Les attributs d’un fichier séquentiel Un fichier séquentiel est défini par les attributs suivants :  Le type du fichier ou type des éléments du fichier,  Un nom qui permet de le désigner et de le distinguer des autres fichiers,  Un état, qui est défini à tout instant et qui peut évoluer au cours du temps. 7.1.4 Définition de types de fichiers Le type d’un fichier définit le type des éléments du fichier. Le type d’un fichier est défini en utilisant les mêmes règles que pour la définition des autres types de données. La définition d’un type de fichier s’effectue de la manière suivante : type tfichier = fichier de télément ; Dr Ndi Nyoungui André 2 Algorithmique et structures de données où tfichier est un identificateur de type de fichier, et télément est le type des éléments du fichier ; télément peut être un type de données scalaires (entier, réel, caractère, booléen) ou un type structuré (article, vecteur, chaîne de caractères). Quelques exemples de définition de types de fichiers. type fentiers = fichier de entier ; fréels = fichier de réel ; temployé = article matricule : entier ; nom : chaîne ; prénom : chaîne ; salaire : réel ; fin ; femployé = fichier de temployé ; 7.1.5 Déclaration de fichiers Une fois qu’un type de fichier est défini, on peut ensuite déclarer des fichiers de ce type. Pour déclarer un fichier séquentiel f, on utilise une instruction de déclaration de la forme suivante : var f : tfichier ; où tfichier est un identificateur de type de fichier préalablement défini. Quelques exemples de déclaration de variables fichiers. variable f : fentiers ; employés : femployé ; 7.1.6 Accès à un fichier séquentiel La référence à un fichier implique deux informations :  l’identificateur de fichier déclaré dans l’algorithme ;  le nom système (au niveau du système d’exploitation) du fichier dans le support de stockage (disquette, disque dur, cédérom,…). Ainsi pour accéder à un fichier disque, il faut établir une relation entre l’identificateur du fichier (variable manipulée dans l’algorithme) et le nom système du fichier (au niveau du système d’exploitation). Cette relation est établie au moyen d’une instruction d’assignation dont la forme générale est la suivante : assigner(f, nomfichier) ; où f est l’identificateur de fichier déclaré dans le programme et nomfichier est le nom système du fichier sur le disque. Une fois l’opération d’assignation effectuée, l’accès aux éléments du fichier dans l’algorithme se fait à travers l’identificateur de fichier f. On remarquera que contrairement aux tableaux, un fichier est un récipient permanent de données ayant une image dans un support de mémoire secondaire (disque dur ou disquette). Dr Ndi Nyoungui André 3 Algorithmique et structures de données Cette caractéristique permet donc aux fichiers de pouvoir conserver leur contenu à long terme : un fichier est réutilisable après l’exécution du programme. 7.1.7 Opérations de base sur les fichiers Un ensemble d'opérations ou fonctions (primitives) de base permettent d’accéder aux éléments d’un fichier, notamment :  de créer ou de détruire des fichiers,  de consulter ou de modifier l'état d'un fichier,  de combiner des fichiers entre eux.  Interpréteur associé à un fichier séquentiel La lecture et l'écriture dans un fichier étant séquentielles, on spécifie pour chaque fichier f une tête de lecture/écriture tête(f) qui indique à tout moment l’élément de f auquel on peut accéder directement. On a accès à un élément du fichier f que lorsque la place correspondant à cet élément se trouve en face de la tête de lecture/écriture. L’élément qui se trouve en face de tête(f) est appelé l’élément courant ou élément accessible. Un fichier étant une suite finie, on introduit une marque spéciale qui permet au mécanisme d’interprétation de détecter la fin du fichier. Figure 7.1. Illustration de la tête de lecture/écriture Les primitives d'accès aux fichiers séquentiels sont définies comme suit:  Indicateur de fin de fichier Cet indicateur est une fonction booléenne notée fin(f) qui prend la valeur vrai lorsque tête(f) se trouve en face de la marque de fin de fichier ; il prend la valeur faux dans le cas contraire. Un fichier est vide si sa première place correspond à la marque de fin de fichier.  Création ou ouverture d’un fichier en écriture Cette opération permet de créer un fichier initialement vide. fin(f) est mis à vrai. Elle s’exprime de la manière suivante : assigner(f, nomfichier) ; réécrire(f) ; ou tout simplement réécrire(f, nomfichier) ; Dr Ndi Nyoungui André 4 Marque de fin de fichier tête de lecture/écriture Algorithmique et structures de données Si le fichier existe déjà sur le disque, son contenu est effacé.  Ouverture d’un fichier en lecture L'ouverture d'un fichier permet de le rendre utilisable en lecture et d'initialiser les indicateurs. Elle s’exprime par : assigner(f, nomfichier) ; relire(f) ; ou tout simplement relire(f, nomfichier) ; Son effet est le suivant : relire(f) : si vide(f) alors fin(f) = vrai sinon début tête(f)  <pointeur sur la uploads/Litterature/ algorithmique-2.pdf