CSI 2531 Gestion de fichiers Hiver 2004
Computer Science University of Ottawa
Devoir à la maison #1
(100 points,
poids 10%)
A rendre le lundi 9 février 2004 a 17:00 (par le biais de webCT)
|
1 Programme: Tri par clé (80 points) 1.1 Description du problème On vous demande d’écrire un programme qui lit
un fichier, trie les enregistrements, et écrit le résultat dans un autre
fichier en utilisant C++ comme langage de référence. Le format de
l’enregistrement du fichier en entrée est différent de celui en sortie. Description
de l’enregistrement du fichier en entrée: Les
enregistrements arrivent dans un ordre indéterminé. Chaque enregistrement a
une longueur variable et se termine par 2 caractères indiquant la fin de la
ligne. Les champs de l’enregistrement sont de longueur variable et sont
séparés par le caractère |. La description des champs est la suivante:
Le
fichier en entrée devrait être lu comme un fichier binaire. Description
de l’enregistrement du fichier en sortie: Le fichier en sortie aura les enregistrements
tries par code cours. Chaque enregistrement a une longueur variable. Les
enregistrements sont presque identiques à ceux dans le fichier en sortie,
excepté que les enregistrements en sortie ne contiennent pas les 2 caractères
fin de ligne à la fin, et que les deux premiers octets de l’enregistrement
consistent en un indicateur de longueur contenant le nombre d’octets dans
l’enregistrement (non comptabilisé la longueur de l’indicateur lui-même.) Le
fichier de sortie devrait être écrit en binaire. Méthode
de tri par clé: Il est très important que vous suiviez la
méthode de tri par clé décrite ici. Il est déconseillé d’utiliser une autre
méthode. Le tri par clé est une méthode pour trier par une clé spécifiée. Il
est utilisé dans des situations où la mémoire principale est insuffisante
pour contenir tous les enregistrements du fichier, mais elle est assez large
pour contenir toutes les clés du fichier. Nous travaillerons sous cette
supposition. Le tri
par clé consiste en les étapes suivantes: 1. Lire
le fichier en entrée, un enregistrement a la fois, stocker seulement les clés
dans un tableau (code cours) et l’octet offset de l’enregistrement. (Notons:
Votre tableau ne devrait pas contenir le contenu total de l’enregistrement,
mais simplement la clé) 2. Trier
le tableau en ordre croissant de la clé. 3.
Utiliser les informations dans le tableau pour écrire séquentiellement les
enregistrements du fichier en sortie dans l’ordre trié par clé. Notez
qu’après le tableau est triée, vous aurez à balayer les positions du tableau
dans l’ordre. Pour chaque position du tableau, vous avez besoin d’utiliser
l’octet offset afin de positionner et lire l’enregistrement a partir du
fichier d’entrée, et immédiatement écrire séquentiellement l’enregistrement
dans le fichier de sortie avec le nouveau format. Notez que dans la première étape,
une fois vous avez l’octet offset pour un enregistrement et pour un
enregistrement précédent, vous pouvez calculer la longueur de
l’enregistrement, laquelle sera nécessaire quand on écrira l’enregistrement
de sortie dans l’étape 3. En C++, vous pouvez facilement obtenir la position
du pointeur courent dans un fichier en utilisant la méthode tellg. 1.2 Les détails d’implémentation et les
standards pour vos arguments de la ligne de commande de votre programme: Le nom du fichier en entrée pour votre programme
sera donné sur la ligne de commande. Ceci veut dire que votre programme est
compilé et un fichier exécutable est crée, vous allez l’exécuter sur l’invite
de DOS et spécifier quelques arguments lesquels représenteront les noms de
fichiers à être utilisés dans votre programme. Les détails du comment accéder
aux arguments de la ligne de commande dans votre programme seront expliqués
dans un page séparée dans le web. Plus précisément, le mécanisme principal
qui fait cela implique l’utilisation
des arguments suivants dans le programme principal: int main (int
argc, char* argv[]) ... Vous pouvez chercher dans l’Internet les
informations sur l’utilisation des ces paramètres ou dans le livre C++. Création
et exécution de votre programme: Les standards ci-dessous (noms de fichiers et
chemin de l’exécution de votre programme) devraient être suivis
scrupuleusement. Vous pouvez utiliser votre créativité dans le sens ou vous
concevez votre classe et votre programme, mais le numéro, le nom de fichier
et le chemin qui sont utilisés par l’assistant devrait suivre le standard. Créer un projet et l’appeler tricle avec les classes et les fichiers suivants: Tricle
(fichiers: tricle.cpp, tricle.h) Programme
principal (fichier: main.cpp) Le
programme exécutable sera appelé tricle.exe par défaut. Ce
programme (tricle.exe) sera exécuté à l’invite de DOS ou l’utilisateur peut
spécifier les arguments de la ligne de commande utilisant le format suivant: tricle.exe
<fichier en entrée> <fichier en sortie> ou tricle <fichier en
entrée> <fichier en sortie> ou
<fichier en entrée> est le nom physique du fichier en entrée et
<fichier en sortie> est nom physique du fichier en sortie. Tester et vérifier vos fichiers en sortie: Vous devez fournir deux fichiers en entrée
pour tester votre programme: small.txt et courses.txt. Vous utiliserez un
programme fourni par nous qui vérifie vos fichiers en sortie. Vous vérifierez
parmi autres choses que le fichier de sortie est trié et qu’il bougera
d’enregistrement en enregistrement via la longueur initiale de l’indicateur.
Toutefois, vous devriez créer le fichier en sortie dans un format exact qui
est spécifié dans le devoir. Quand le programme de vérification est
disponible, il vous sera fourni dans le site webCT. Documentation et style: Votre programme doit être bien documenté et
écrit en bon style. Une partie de la note sera réservée à la documentation et
au style. Pour documenter votre programme, écrire les commentaires pour
expliquer les actions des lignes suivantes. Pour chaque fonction ou méthode
ajoutez une explication complète avant elle, l’expliquant et ce que ses
paramètres représentent. Pour chaque classe crée, ajoutez une explication
avant elle. Quand et
comment envoyer votre devoir: Créer un
répertoire nommé a1 contenant seulement ce qui suit: main.cpp, tricle.cpp,
tricle.h et written.txt. Le fichier written.txt contient vos réponses aux
questions écrites données dans la Section 2. Chaque fichier doit contenir une
entête d’étudient: Nom, numéro étudient, Cours et Section. Compressez le répertoire
et envoyez le fichier compressé au webCT (un seul fichier est envoyé.) 2 Partie écrite: Dispositif de stockage secondaire (20 marks) 2.1 Disques (10 marks) Étant donnée un disque système Western
Digital Caviar AC22100 avec les caractéristiques suivantes: Capacité:
2,100 MB Temps de
recherché moyen: 12 msec Délai de
rotation moyen: 6msec Vitesse
de transfert: 12 msec/piste Octets
par secteur: 512 Secteurs
par piste: 63 Pistes
par cylindre: 16 Cylindres:
4092 Supposez
que vous voulez stocker un fichier avec 350,000 enregistrements de 80 octets. 1.
Combien de cylindres sont nécessaires pour contenir le fichier étant donné
qu’un enregistrement peut occuper plusieurs secteurs, pistes ou cylindres? 2.
Combien de cylindres sont nécessaires pour contenir le fichier si un
enregistrement ne peut pas occuper plus d’un secteur? 3.
Supposez la situation en question 2, et supposez qu’il n’y a pas
d’interférence provenant d’autres processus et que le fichier remplit
complètement un cylindre avant de continuer sur un autre cylindre et que les
cylindres demandés sont dispersés aléatoirement sur le disque. Combien de
temps prendrait-on pour accéder au fichier entier en séquence? 4. Sous
les mêmes suppositions que la question 3, combine de temps prendrait-on pour
accéder au fichier entier aléatoirement (accession a chaque enregistrement,
mais en ordre aléatoire)? 2.2 Bandes magnétiques (10
marks) Supposez que vous voulez stocker un fichier
avec 350,000 enregistrements de 80 octets de long sur une bande magnétique de
densité 1600 octets par inch, un gap d’interblocage de 0.5 inch, et une
longueur de bande de 2400 pieds. 1. Quel
sont le minimum et le maximum du facteur de blocage qui est nécessaire pour
utiliser exactement trois bandes magnétiques? 2. Quel
est la densité d’enregistrement quand le facteur de blocage de 50 est
utilisé? 3. La
vitesse de la bande magnétique es 150 inch par seconde. Quel est la vitesse
de transmission de cette configuration? |