:: Enseignements :: Licence :: L2 :: 2011-2012 :: Système ::

Listes chaînées génériques

Le but de ce TD est d'écrire une bibliothèque C générique 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.

Placer ces éléments dans un fichier d'en-tête listes.h.

Exercice 2 - Préliminaires: fonctions utilitaires

Écrire maintenant les quelques fonctions de gestion de listes chaînées dont les prototypes à placer dans listes.h sont les 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).

Écrire 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 forcer un transtypage (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. Ajoutez au fichier listes.h 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 la définition des 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 prototype de ces fonctions et le placer dans le fichier listes.h.

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.

Écrire les fonctions génériques suivantes:

rechercher qui 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 qui insère un élément donné dans la liste passée en argument et assure que la liste reste triée suivant un ordre défini par la fonction de type compare_any passée en argument.

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.

Modifiez la fonction liberer_liste pour vous assurer que toutes les chaînes de caractères de la listes sont libérées.

À partir de votre programme écrire un Makefile permettant de créer une bibliothèque partagée liblistes.so. Ne pas oublier de créer le fichier d'en-tête listes.h. Testez votre bibliothèque après avoir extrait votre main de test (ne pas oublier d'utiliser l'option -L pour la compilation et la variable d'environnement LD_LIBRARY_PATH lors du lancement de la commande).

Exercice 6 - Dictionnaire

Écrire une fonction lire_ligne qui lit sur un FILE* et qui stocke dans une chaîne allouée dynamiquement en la redimensionnant si cela est 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.

É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 ?