Listes chaînées triées

Les définitions de type suivantes permettent de représenter une liste chaînée triée de mots, qu'on peut appeler lexique ou lexicon:

Vous trouvez dans la librairie <string.h>, des fonctions permettant de faire des opérations sur des chaînes de caractères : les comparer, les copier, etc.

• La documentation de la librairie <string.h>.

Écrire les fonctions

1. cell *allocate_cell(char word[]) qui alloue l'espace mémoire nécessaire pour une nouvelle cellule et retourne l'adresse de cette nouvelle cellule. La fonction doit allouer la place nécessaire pour le mot word (le caractère '\0' de terminaison inclus) et initialiser le champ word, le champ occurrence signifiant qu'il n'y a qu'une occurrence et le champ next à NULL. S'il n'y a plus de place disponible, la fonction renvoie la valeur NULL ;
2. int insert_in_lexicon(lexicon *lex, char word[]) qui insère la valeur word dans le lexique *lex. Si le mot apparaît déjà dans la liste, vous devrez incrémenter le champ occurrence. La fonction renvoie l'adresse de la cellule correspondant au mot ajouté, ou NULL en cas de problème ;
3. void print_lexicon(lexicon lex) qui affiche le lexique dans l'ordre alphabétique en donnant pour chaque mot son nombre d'occurrence ;
4. cell *find_in_lexicon(lexicon lex, char word[]) qui renvoie l'adresse de la cellule contenant le mot word. La fonction renvoie NULL si le mot n'est pas présent dans le lexique lex ;
5. int word_occurrence_in_lexicon(lexicon lex, char word[]) qui renvoie le nombre d'occurrences du mot word dans le lexique lex ;
6. void free_lexicon(lexicon *lex) qui libère tout l'espace mémoire occupé par le lexique *lex.

Pour ouvrir et fermer des fichiers en C, on utilise les deux fonctions fopen et fclose de la librairie <stdio.h> :

Le paramètre mode de la fonction fopen détermine si on ouvre le fichier pour la lecture ("r") ou pour l'écriture ("w"). La fonction renvoie un pointeur FILE * qui représente le fichier, ou NULL en cas d'erreur. Ensuite, on se sert de ce pointeur pour lire ou écrire en utilisant fscanf et fprintf qui fonctionnent comme scanf et printf mais qui prennent en premier argument le pointeur du fichier.

• La documentation de la librairie <stdio.h>.

Écrire les deux fonctions suivantes :

1. int read_text(FILE *input, lexique *lex) qui lit les mots d'un fichier de texte input et qui construit le lexique. Cette fonction retournera -1 en cas de problème et 0 si tout s'est bien passé.
2. void save_lexicon(FILE *output, lexique lex) qui sauvegarde le lexique dans le fichier output. Chaque ligne du fichier output devra contenir le mot suivi de son nombre d'occurrence séparés par un espace.

Écrire une fonction main qui permet de tester toutes ces fonctions. Les noms des fichiers pour la lecture du texte et la sauvegarde du lexique devront être transmis sur la ligne de commande. Les tests nécessaires à l'ouverture des fichiers devront être faits dans la fonction principale.

Modifier la structure et les fonctions précédentes afin d'enregistrer, via une liste chaînée d'entiers pour chaque mot, les positions de ce mot dans le texte.