TP Noté - Arbre lexicographique et
indexation d'un texte
Informatique - Licence 2.2
L'objet de cette feuille d'exercices est l'utilisation de l'arbre
lexicographique
pour l'indexation d'un text. L'objectif est d'associer à chaque
mot du texte la position dans le texte ou ce mot apparait.
On considère la déclaration suivante de la structure
classique
d'un arbre lexicographique enrichi d'une liste de positions.
typedef struct positions{
int* positions;
/* Contient le tableau des
positions */
int tailleAlloue;
/* Contient la taille alloué */
int tailleUtilise;
/* Contient le nombre de case utilisé
du tableau */
}Positions;
struct noeud
{
char Lettre;
struct noeud * FilsGauche;
struct noeud * FrereDroit;
Positions *pos;
};
typedef struct noeud Noeud; /* nouveau
type
:
Noeud */
typedef Noeud *
Arbre;
/* pointeur sur un
Noeud */
Les prototype proposé pour les fonctions sont indicatif, vous
pouvez les modifier si cela vous semble nécessaire. Vous enverez
un mail à la fin du tp contenant vos fichiers source.
Le titre du mail devra être votre nom + votre prenom suivi de
L2.2.
Voici un exemple de main a utiliser et un fichier
test pour votre
programme.
Exercice 1- Fonctions de base de
manipulation de la structure Positions.
- Positions* CreerPositions(int tailleAlloue) qui retournera
un pointeur
sur
une structure Positions
convenablement allouée et initialisée.
- Position* RealouePosition(int
tailleAlloue, Position* pos) qui retourne une structure
contenant un tableau convenablement réalloué.
- int
LibérePositions(Positions* pos) qui libère la
structure passée en paramètre. Renvoie 1 si la
libération
s'est effectuée sans problème, 0 sinon.
- int ajouterPosition(Positions* pos, int position) qui ajoute une
position position dans la
structure pos. Renvoie 1
si l'ajout
s'est effectuée sans problème, 0 sinon.
- void AffichePositions(Positions pos). Affiche le contenu de
position.
Exercice 2- Fonctions de base de
l'arbre lexicographique
Quand c'est possible réutiliser les fonctions du tp
précédent.
- Noeud * CreerNoeud(char c)
qui retournera un pointeur
sur
un noeud
contenant le caractère passé en argument. Dans un premier
temps on n'allouera pas de place pour stocker les positions.
- Noeud* CreerFeuille(char *, int position). Qui retournera une
feuille de l'arbre contenant une position initialisée avec une
table de taille MAXPOSITION contenant la valeur position.
- int EstFeuille (Arbre a) qui testera si l'arbre
pointé par a est une
feuille,
- int EstVide (Arbre a) qui testera si l'arbre
pointé
par a
est vide,
- int DetruireNoeud (Noeud * n) qui libère l'espace
mémoire
associé au noeud n. Renvoie 1 si la
libération
s'est effectuée sans problème, 0 sinon.
Exercice 3- Insertion d'un mot
à une position.
Ecrire une fonction void
InsertionLex(Arbre *a, char* mot, int position) Qui réalise
l'insertion dans l'arbre a du
mot mot en y associant une position. Si le mot y est
déja, modifié le tableau de positions. Attention à
la taille du tableau.
Exercice 4- Positions d'un mot
Ecrire une fonction Positions*
PositionsMots(char* mot, Arbre a) qui prend un mot en
paramétre et renvoie la liste de ses positions.
Exercice 5- Création de
l'indexe d'un texte.
Écrire une fonction void Lecture(FILE * fic, Arbre*a) qui
réalise l'insertion des mots contenus dans le fichier fic dans l'arbre a. Les positions associées aux mots
sont celles de la dernière lettre de ce mot.
Exercice 6- Affichage de l'index
Écrire une fonction void Affiche(Arbre*a, char *mot, int
prof) qui affiche l'ensemble des mots contenus dans l'arbre ainsi que
leurs positions associées.