L3 - Informatique
Année 2004-2005
TP 2 - Ensembles dynamiques
Partie 1
Programmez l'ensemble dynamique vu en TD.
Remarque : dans un premier temps, vous pouvez vous contenter d'un ensemble dynamique de caractères.
Partie 2 : Applications
L'objectif de ces exercices est de vous montrer que
lorsqu'un type de données abstrait est correctement
écrit, il facilite réellement la programmation. Faites
l'effort de réutiliser les fonctions des exercices
précédents. Au lieu de faire une modification par
exercice, c'est à dire de rendre vos fonctions de plus en plus
spécifiques à un problème particulier,
modifiez-les afin de les rendre de plus en plus
générales. De cette manière, vous pourrez utiliser
la même fonction de gestion d'ensemble pour tous les exercices du
TP. A chaque modification d'une fonction utilisée dans plusieurs
exercices, modifiez également les exercices
précédents afin qu'ils fonctionnent toujours.
Le plus simple pour utiliser la même fonction
/ structure de données dans plusieurs programmes consiste
à l'écrire dans un fichier source séparé.
Pour construire un programme dont les fonctions sont répartis
dans plusieurs fichiers C / H, reportez vous à l'exemple de la
semaine dernière et n'oubliez pas de lire : comment écrire un makefile.
Exercice 1
Ecrivez une fonction permettant de remplacer efficacement fgets
: elle adaptera automatiquement la taille de l'ensemble de
caractères renvoyés au nombre de caractères lus.
Exercice 2
Ecrivez un programme qui charge et affiche chaque
ligne d'un fichier texte passé en paramètre. La lecture
de chaque ligne du fichier utilisera votre fonction de lecture de
l'exercice 1.
Exercice 3
Modifiez le programme précédent afin
qu'il conserve en mémoire tous les mots du fichier texte. Un mot
sera a priori un ensemble dynamique de caractères. Le contenu du
fichier sera représenté comme un ensemble dynamique de
mots.
Remarque : il va falloir
généraliser un petit peu votre ensemble dynamique afin de
pouvoir l'utiliser comme ensemble de caractères et comme
ensemble de mots. Soit vous écrivez deux ensembles
différents, soit vous modifiez votre ensemble pour qu'il puisse
faire les deux.
Exercice 4
Ecrivez un programme qui charge tous les mots d'un dictionnaire, puis qui vérifie que tous les mots d'un fichier texte passé en paramètre existent dans le dictionnaire.
Quelle est la complexité de la
vérification orthographique complète ?? comment faire
mieux ? quelle fonction faut-il modifier ? faut-il orgraniser certaines
données différement afin de faire la vérification
plus vite ? quelle amélioration peut on espérer ?
Modifier la fonction de vérification afin
qu'elle renvoie les mots les plus proches d'un mot mal
orthographié. On pourra se contenter de compter le nombre de
lettres égales entre deux mots pour définir le terme
"proche".
Est-il nécessaire de conserver en
mémoire la totalité des informations ? peut-on faire plus
simple ?