Introduction aux fichiers

Introduction

Un système de traitement informatique des données ne peut pas toujours disposer, dans des variables définies, de toutes les entités sur lesquelles il intervient. Un ordinateur, par exemple, ne peut pas toujours placer toutes les données en mémoire centrale. C’est le cas lorsque le volume de données est important ou encore lorsqu’il est nécessaire d’assurer la persistance des informations qu’elles représentent. Des unités périphériques externes d’enregistrement sont alors utilisées pour enregistrer et récupérer les données. Ce chapitre étudie une forme particulière d’organisation et de structuration permettant la persistance des données impliquées dans un traitement algorithmique : les fichiers. Le prétexte est que la forme que revêt cette organisation impose des méthodes et des opérations applicables spécifiques.

La deuxième section donne quelques notions rapidement introduites sur l’organisation des supports externes d’information d’un système informatique et sur les modes d’accès à ces informations. La troisième section décrit un fichier à organisation séquentielle et les traitements de lecture et d’écriture dans un tel fichier. La section suivante...

Notions élémentaires

Cette section introduit rapidement quelques notions élémentaires sur l’organisation et l’accès aux informations enregistrées dans un fichier informatique. Elle est divisée en trois parties. La première est une introduction qui précise quelques éléments du vocabulaire du domaine. La deuxième partie présente les organisations usuelles. La troisième partie montre comment on définit une association, entre un fichier enregistré sur un support externe et une structure algorithmique de données, qui permettra de décrire les opérations d’accès aux informations enregistrées.

Organisation séquentielle

Cette section présente les algorithmes élémentaires permettant de définir les opérations de base sur un fichier logique dont le modèle est un fichier physique à organisation séquentielle. La première partie est une introduction qui précise le contexte. La deuxième partie montre comment parcourir un fichier pour lire les informations qu’il contient. La partie suivante en fait autant pour l’écriture dans le fichier. La dernière partie montre comment le mettre à jour.

1. Introduction

Un fichier physique à organisation séquentielle est constitué d’une suite d’enregistrements placés consécutivement sur un support externe. Ils sont tels que, pour accéder à un enregistrement donné e, il est nécessaire d’accéder d’abord et successivement à tous les enregistrements qui précèdent e sur le support. La figure suivante illustre ce type d’organisation.

Les enregistrements d’un fichier sont habituellement composés. Sur la figure ci-dessus, nous avons représenté quatre enregistrements et, sur la partie inférieure du schéma, un zoom montre la structure de l’un d’eux. Chaque enregistrement est fait de cinq champs : NUMÉRO, NOM-PRÉNOM, ADRESSE, CODE-POSTAL, VILLE. On peut donc définir un article composant le fichier logique associé après ouverture. 

Ainsi, par exemple pour le fichier clients de la figure précédente, le type correspondant pourrait être :

type  
    CLIENT  
structure  
    numéro     : ENTIER # Identifiant du client  
    identité   : IDENTITÉ  
    adresse    : CHAÎNE 
    codePostal : CODE_POSTAL  
    ville      : CHAÎNE  
fin CLIENT 

Les types IDENTITÉ et CODE_POSTAL ont déjà été définis au chapitre « Structures élémentaires ». Dans ce qui précède, c’est l’article qui est l’unité élémentaire d’accès à...

L’organisation directe et l’accès sélectif

Dans certaines applications, chaque article contient un attribut particulier qui l’identifie d’une manière unique dans l’ensemble des articles qui composent un fichier. On appelle clé ou identifiant un tel attribut.

Définition : clé d’un article

On appelle clé d’un article d’un fichier un attribut qui identifie d’une manière unique cet article dans le fichier.

Ainsi, deux articles distincts ont des clés différentes et, inversement, deux clés distinctes identifient deux articles distincts. Cette situation est essentiellement différente de celle qui fait d’un attribut K d’un fichier à organisation séquentielle une clé permettant d’ordonner les articles. En effet, dans ce cas, il pourrait exister plusieurs articles ayant la même valeur pour l’attribut K qui n’est donc pas une clé identifiante au sens de la définition précédente.

Lorsque le fichier est implanté sur un support adressable et que, de plus, une fonction permet d’établir une correspondance entre la clé d’un article et l’adresse de l’enregistrement associé à cet article, on peut accéder aux enregistrements d’un fichier directement, sans avoir à parcourir tous ceux qui le précèdent sur le support. Sur un support adressable, chaque emplacement est localisé par une adresse. Cependant, en algorithmique, on considère que chaque article est repéré par une adresse relative au début du fichier et non pas par rapport à un support physique programmable. La correspondance entre une adresse relative au début du fichier et l’adresse réelle sur le support est établie par les primitives d’accès au support. Ces primitives sont fournies par le système d’exploitation et son SGF et nous n’avons pas à nous en préoccuper....

Problèmes

Cette section présente des problèmes faisant intervenir des fichiers. On propose d’abord un exercice de calcul sur des statistiques d’import/export. La section suivante montre comment exploiter les réponses à un questionnaire d’attitude et la troisième section en fait autant pour les réponses à une enquête d’utilité publique. Enfin, la dernière section pose un problème difficile qui consiste à déterminer des anagrammes des mots d’un dictionnaire. Tous ces problèmes ne sont en fait que des prétextes pour écrire des algorithmes. Mais alors que précédemment, les algorithmes étaient indépendants, ici, ils doivent être composés pour obtenir une analyse complète du problème. De plus, les problèmes ne sont pas posés d’une façon académique. Ils nécessitent souvent d’être précisés ou complétés. Ainsi, aucun des exercices ne donne d’indication sur les structures à mettre en place et tous restent vagues sur la forme des données à traiter. En particulier, on ne précise jamais le type de fichier utilisé. Il faut donc faire un effort d’analyse et de réflexion pour obtenir une solution utilisable ensuite en programmation.

1. Statistiques d’import/export

On dispose d’informations relatives aux importations et exportations d’un ensemble de pays et on désire dépouiller ces informations pour en extraire un certain nombre d’indicateurs. Les informations qui concernent chaque pays sont les montants de ses importations et de ses exportations, selon 5 secteurs économiques au plus, exprimés en millions d’Euro. Les pays et les secteurs économiques sont identifiés par des nombres entiers. Le schéma conceptuel de la figure ci-dessous montre les associations entre les pays concernés et les secteurs économiques étudiés.

Ce schéma se lit de la façon suivante. Un pays importe dans 0 à 5 secteurs économiques étudiés. Pour chaque paire (pays ; secteur), l’association IMPORTER donne le montant des importations. Chaque secteur économique donne lieu à...