:: Enseignements :: Licence :: L2 :: 2009-2010 :: Système ::
[LOGO]

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 :

  1. 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.
  2. void liberer_liste(Liste* l); qui libère la mémoire occupée par la liste.
  3. 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:

  1. 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;
  2. 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 ?