:: Enseignements :: Licence :: L2 :: 2008-2009 :: Structures de données ::

---

InTern (Index ternaire)

---

But du projet

Vous devrez implémenter en C un programme capable d'indexer les mots d'un texte en notant toutes leurs positions.

Calcul des mots

Les mots seront lus depuis un fichier texte passé en argument de votre programme. On considérera que les mots sont ce que scanf("%64s",resultat); calcule, c'est-à-dire une séquence d'au plus 64 caractères qui ne sont pas des séparateurs.

Stockage de l'index

Les mots seront stockés dans un arbre ternaire de recherche. Pour chaque fin de mot, représentée par un noeud étiqueté par '\0', on stockera la liste des positions auxquelles il apparaît grâce à une liste chaînée d'entiers. Les types à utiliser seront donc les suivants:

struct liste {
		int valeur;
		struct liste* suivant;
};
		
struct ATR {
		struct ATR* gauche;
		struct ATR* droit;
		char c;
		struct ATR* milieu;
		struct liste* positions;
};	
	

Sortie du programme

Une fois le texte indexé, votre programme devra explorer l'arbre ternaire et afficher sur sa sortie standard la liste des mots dans l'ordre alphabétique, en indiquant sur une ligne pour chaque mot ses occurrences de la façon suivante:

mot1 pos1 pos2 pos3 ...		
	

Par exemple, pour ce fichier texte, le rendu devrait être celui-ci:

Le 0
chat 3 45
du 8 42
est 17 50
gros. 54
le 33
mais 28
petit 11 36
petit, 21
	

Conditions de rendu

• Il est interdit d'utiliser du code externe: vous devrez tout coder vous-mêmes.
• Tout code commun à plusieurs projets vaudra ZERO pour tous les projets concernés.

---