Quelques indications pour le programmeur A
Lecture des fichiers
On rapelle quelques fonctions pour lire des fichiers :
fopen(fichier,"r")
permet d'ouvrir un fichier en lecture. Cette
fonction renvoie une structure de type FILE *
fcloe(file)
ferme le fichier décrit par la structure
file
fgets(buffer, size, file)
lit le fichier décrit par
file
(donné par fopen
) ligne par ligne. La ligne
courante est stockée dans la chaîne buffer
de taille
size
.
On pourra aussi revoir le TP 4.
On pourra commencer par écrire une fonction qui calcule le nombre de lignes
d'un fichier.
Le hashage
La difficulté principale du programmeur A devrait être le hashage et son
utilisation.
Le type de hashage
Le but du hashage dans notre exemple n'est pas seulement d'implémenter
des fonctions d'ensemble, mais aussi et surtout d'associer un unique entier
à chaque ligne (et le même pour deux lignes égales).
Le problème vient de la gestion des collisions (voir
TD 4).
On a deux solutions classiques :
Solution par chaînage
L'entier unique peut alors être l'adresse mémoire.
Solution par adressage ouvert
L'entier unique est alors le numéro de la case dans laquelle est
rangée la ligne. Il faut alors penser aux améliorations par
double hashage ou hashage quadratique.
Problème de taille de la table
On peut penser à trouver le nombre de lignes de chaque fichiers avant
d'allouer l'espace mémoire de la table de hashage.
Les fonctions de hashage
Il faut choisir des fonctions de hashage qui produiront le moins de collisions
possible. Ces fonctions de hashage ne devront pas pour autant ètre
trop coûteuses. On peut utiliser les charactères dans les lignes
comme des entiers. On peut les additionner, les décaler
(<<
ou >>
), en prendre le ou exclusif
avant ou après décalage (^
). À vous
de choisir votre heuristique. Essayez tout de même de ne pas vous
contenter de la tête de la ligne...
Si vous ne savez pas par où commencer...
Vous pouvez programmer les fonctions proposées ici.