:: Enseignements :: Licence :: L2 :: 2009-2010 :: Système ::
| Listes chaînées génériques |
Le but de ce TD est d'écrire des fonctions C génériques pour la gestion de listes
chaînées. L'intérêt de fonctions génériques est d'avoir des fonctions qui sont adaptées
à tous les types de données sans qu'il soit nécessaire de les réécrire ou même de les
modifier.
Exercice 1 - Définitions des types
Tout d'abord, nous allons écrire un mécanisme de gestion de listes chaînées. Le
type des éléments contenus dans la liste chaînée sera défini par l'union suivante:
typedef union {
int n;
float f;
} any;
L'utilisation de ce type
any nous permet de faire des listes de « n'importe quoi ».
Si un nouveau type d'élément est nécessaire, il suffira de l'ajouter à cette union.
Nous allons utiliser la structure de liste définie comme suit :
typedef struct liste_ {
any data;
struct liste_* suivant;
} Liste;
Le any data correspond à la donnée contenue dans la cellule courante et
suivant correspond à la cellule suivante.
Exercice 2 - Préliminaires: fonctions utilitaires
On va écrire maintenant les quelques fonctions de gestion de listes chaînées suivantes :
- Liste* creer_liste(any data,Liste* suivant); qui crée une nouvelle
à partir de la valeur et de la liste passés en paramètres.
- void liberer_liste(Liste* l); qui libère la
mémoire occupée par la liste.
- void ajout_en_tete(Liste* *tete,any data);
qui ajoute un élément en tête de la liste.
Il est important de noter que, quel que soit le type des éléments de la liste,
l'ensemble du code ne change pas. On peut donc dire que ce code est parfaitement
générique. En revanche une recompilation peut être nécessaire si le type any évolue
(particulièrement si sizeof(any) change).
Ecrivez une fonction main permettant de tester
l'ensemble des fonctions que vous avez écrites avec une listes d'entiers. Pour cela,
vous écrirez une fonction afficher_int qui affiche le contenu d'une liste
en supposant qu'elle contient des entiers.
Astuce: la norme du C indique que, dans une union, tous les champs commencent
au début de la zone mémoire associée à l'union. Vous pouvez donc toujours faire un cast
vers le type
any, quel que soit le champ que vous souhaitez utiliser. Ainsi,
pour créer une cellule avec la valeur entière 14, il vous suffit d'écrire:
creer_liste((any)14,NULL);
Exercice 3 - Affichage
Dans l'exercice précédent, vous avez écrit une fonction d'affichage propre aux listes contenant
des entiers. Or, cette fonction sera quasiment identique quel que soit le type des éléments, seul
l'affichage d'un élément changera. On peut donc écrire une fonction d'affichage qui prend en
paramètre la liste à afficher et un comportement, celui qui indique comment afficher un élément.
Justement, c'est à ça que servent les pointeurs de fonctions. Quand vous aurez fini de frissonner
de terreur après avoir lu la phrase précédente, ajoutez à votre code la définition de type suivante:
/* on définit le type d'une fonction permettant d'afficher un
* élément de type any */
typedef void (*afficher_any)(any);
Vous pouvez maintenant écrire les fonctions de ce type chargées d'afficher un entier ou un flottant.
Vous pourrez ensuite écrire la fonction générique d'affichage de liste:
void afficher_liste(Liste*,afficher_any f);
Exercice 4 - Toujours plus de généricité
On souhaite maintenant faire des opérations de recherche et de tri sur nos
listes génériques. Pour cela, il faut disposer de fonctions de comparaison
générique de deux éléments. Définissez le type de ces fonctions.
Pour les fonctions de comparaison entre deux éléments a et b,
l'usage est de renvoyer 0 en cas d'égalité, une valeur négative si a est
plus petit que b, et une valeur positive sinon. Donnez des fonctions de
comparaison pour les entiers et les flottants.
On vous demande maintenant d'écrire les fonctions génériques suivantes:
-
rechercher: renvoie un pointeur vers le maillon de la première occurrence de l'élément recherché ou NULL si l'élément cherché n'est pas dans la liste;
-
insertion_triee: insère l'élément donné à sa bonne place dans la liste.
Testez vos fonctions sur des listes d'entiers, puis sur des listes de flottants.
Exercice 5 - Extension du type any
Nous souhaitons maintenant gérer également les chaînes de caractères.
Modifier le type any en conséquence, et écrire les fonctions d'affichage
et de comparaison nécessaires. Une fois que vous aurez testé tout cela, vous écrirez
un programme qui lit les lignes de l'entrée standard et qui les
affiche triées. Pour cela, vous utiliserez une liste de chaîne de caractères dans laquelle
vous ferez des insertions triées. Pour la lecture des lignes, vous écrirez une fonction
lire_ligne qui lit sur l'entrée standard et qui stocke dans une chaîne allouée
dynamiquement et redimensionnée si nécessaire avec realloc. La fonction doit retourner
la chaîne allouée et remplie, sans le \n final, ou NULL si le flux d'entrée est
tari.
Vérifiez que vous obtenez bien le même résultat que votre
programme sort du TP précédent, en utilisant la commande diff.
Ajoutez l'appel à liberer_liste que vous aviez oublié, recompilez avec
l'option -g et demandez à valgrind de vous confirmez que vous avez
bien libéré toute la mémoire. Pleurez et cherchez à comprendre le problème. Comment le
corriger ?
Exercice 6 - Dictionnaire
On demande d'écrire un programme dico qui prend
au moins deux arguments au moyen du mécanisme argc, argv en paramètre de la
fonction main. Ces paramètres sont un fichier contenant une liste de mots (par
exemple /usr/share/dict/french), et un ou plusieurs mots. Le programme doit charger
complètement le dictionnaire en mémoire, puis indiquer pour chaque mot s'il existe ou
pas dans le dictionnaire.
Par exemple la ligne d'exécution suivante :
dico /usr/share/dict/french abandon kaouete zouave zapoyoko
aura la sortie suivante :
abandon appartient au dictionnaire
kaouete n'appartient pas au dictionnaire
zouave appartient au dictionnaire
zapoyoko n'appartient pas au dictionnaire
Exercice 7 - Temps de recherche...
Comparer avec la commande time le temps nécessaire pour rechercher un mot, selon
qu'il est au début, à la fin, au milieu, etc. du dictionnaire.
time ./dico /usr/share/dict/french mot
Ne pourrait-on pas améliorer les temps de recherche en
utilisant une autre structure de données qu'une liste ?
© Université de Marne-la-Vallée