Introduction :
L’élaboration
d’un dictionnaire se basant sur l’alphabet français peut se faire de
différentes manières à savoir les tableaux simples, les tables associatives (Hash-code),
les listes chaînées et les arbres. La dernière solution qui se base sur les
arbres présente la meilleure en terme
d’optimisation de l’espace mémoire et de la rapidité de recherche et
d’intervention et ceux dus à la notion de récursivité utilisée largement dans
ce genre de manipulation.
Travail
demandé :
Dans ce présent travail, on
demande d’écrire un programme contenant un menu pour gérer un dictionnaire
contenant des mots de la langue
française qui seront présentés par ordre alphabétique fournissant pour chacun
une définition. Pour se faire, nous disposons d’un menu comportant des
fonctions pour créer un dictionnaire, pour y ajouter des mots , pour en supprimer, pour afficher tous les
éléments, pour rechercher et enfin pour fermer et quitter le fichier.
Architecture
utilisée :
On
a opté pour l’utilisation des arbres, suivant l’architecture ci-dessus :
S_noeud *droite, *gauche:
deux pointeurs pour la navigation dans l’arbre.
Char *info :
pointe sur un espace dynamique pour recevoir le mot en question.
Char *def :
pointe sur un espace dynamique pour recevoir la définition associée.
Les différentes étapes
d’élaboration du menu sont expliquées ci-dessous:
1. Étapes de réalisation:
Pour
élaborer ce mini projet, plusieurs étapes ont été suivies:
- L’ajout d’un mot au dictionnaire.
- La recherche d’un mot dans le
dictionnaire.
- La suppression d’un mot du dictionnaire.
- La fermeture du dictionnaire.
Pour ce faire, un menu
a été établi. Ce menu comporte toutes les fonctionnalités citées. Toutes ces
fonctions sont décrites en détails dans les paragraphes qui suivent.
1.1. Élaboration du menu:
Le
menu général de notre programme se
présente comme suit:
1-
Ajouter un mot au dictionnaire.
2-
Rechercher un mot dans le dictionnaire.
3-
Supprimer un mot du dictionnaire.
4-
Fermer le dictionnaire.
Donc
un ensemble de fonction a été élaboré afin d’exécuter le menu ci-dessus tout en
utilisant les arbres sous c afin d’optimiser l’espace mémoire et en s’appuyant
sur la notion de récursivité.
1.2. Les fonctions principales du programme:
Pour
ajouter un élément au dictionnaire, on a recours à une fonction qui ne retourne
rien et qui prend comme paramètre un pointeur de pointeur de type t_noeud. Le
prototype de la fonction qui permet l’ajout est arbre
* create(char nb[],arbre * prim,char d[]).
Dans la fonction create,
On fait entrer le mot à insérer et on teste s’il existe déjà ou pas. Si
l’élément existe, le mot ne sera pas accepté, sinon il sera ajouté avec succès.
La
fonction Exist
qui nous permettra de chercher un mot dans le dictionnaire,
elle retourne void et reçoit comme paramètre un pointeur nœud de type t_noeud.
Le prototype de cette fonction est void Exist(arbre *src ,char elt[]).
Dès
que l’utilisateur désire supprimer un élément du dictionnaire, on fait appel à
la fonction Supprimer
dont le prototype est : void Supprimer(arbre**src, char
*chaine). Cette fonction permet de vérifier si le
mot entré existe dans le dictionnaire. Si c’est le cas elle permet de bien
supprimer l’élément.
On
trouve aussi la fonction Suppression
dont le prototype est :
void Suppression(arbre **src) qui
permet de libérer le nœud à supprimer ainsi que sa définition.
2. Algorithmes:
typedef
struct tree{
char mot[10];
char def[1000];
struct tree *droite;
struct
tree *gauche;
}arbre;
ajouter (&R, mot[30])
i=0;
D=R;
ptr
prec, temp;
Tantque
(i<m.lenght())
D=D->bas;
prec=Null;
Tant que (D!=Null) et ((D->lettre)<mot[i])
prec=D;
D=D->suivant;
fin tantque
si ((D->lettre)=mot[i]) alors
D=D->bas;
i=i+1;
sinon
temp=(ptr) malloc(size of(noeud));
temp->lettre=mot[i];
si (prec=!=Null) alors
prec->suivant=temp;
temp->suivant=D;
sinon
si (D=Null)
D->bas=temp;
temp->haut=D;
temp->suivant=Null;
sinon
temp->suivant=D;
D->haut=Null;
finsi
finsi
finsi
fintantque
si i>=mot.lenght() alors
D->bas=definition;
---------------------------------------------------------------------------------------------------------------------
rechercher(&R,
mot[30])
D=R;
tantque (D->bas!=Null) et
(i=<mot.lenght())
tantque (D!=Null) et
(mot[i]>D->lettre)
D=D->suivant;
fintantque
si mot[i]=D->lettre alors
D=D->bas;
i=i+1;
sinon
return -1;
fintantque
si ( i=mot.lenght()) et
(D->definition!=Null) alors
return
D->definition;
sinon
return -1
finsi
---------------------------------------------------------------------------------------------------------------------
supprimer(&R,
mot[30])
D=recherche(&R, mot[30])
si (D!=Null)
alors
si
D->bas!=Null
alors D->definition=Null;
sinon tantque
((D->haut->definition)!=Null) et ((D->haut->suivant)!=Null)
free(D);
3. Ecrans de saisie:
Menu principal:
Ajout d’un mot:
Recherche d’un mot:
Suppression d’un mot:
Quitter le programme :
Conclusion :
L’élaboration
de ce programme permet d’étudier profondément les arbres comme structure
et outil puissant dans la gestion de grandes tables de données. L’introduction de
la gestion dynamique de la mémoire nous a permis de gérer d’une façon optimale
l’occupation de la mémoire et mettre en évidence la force des pointeurs.