Dichotomie dans un dictionnaire

Version imprimable

Bonjour à tous, voilà je débute en C++ et j'aimerais réaliser une fonction qui permet de faire une dichotomie dans un dictionnaire, ce qui me permettrais donc d'y placer un nouveau mots ou de voir si le mot existe.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
//voilà le dico
 
struct mots
{
    char nom[10];
    int numero;
 
};
struct mots dico[20]={{"absent",3},{"content",5},{"disparu",1},{"grand", 6},{"heureux", 2},{"immense", 4},{"minus", 7},{"petit",8} };
 
 
 
//voila la fonction qui marche qu'a moitié...
 
void cherche (void)
{
    int taille;
    int i,j, bas, haut ;
    char mot[20] ={};
    cout<<"Entrer la taille de votre mots : ";
    cin>>taille;
    cout<<"Entrer le mot a chercher : ";
    for (i = 0 ; i < taille ; i++)
    {
        cin>>mot[i];
    }
 
    j = 0;
    bas=1;
    haut=8;
    while (bas <= haut)
        {
            j=(bas+haut)/2;
            if (mot[0]<=dico[j].nom[0])
            haut = (j-1);
            else
            bas=(j+1);
        }
        cout<<j;
}

Merci d'avance pour votre aide :lol:

10/01/2009, 14h15
FunK92

Salut,

Pourrait-tu cibler le problème pour que l'on puisse t'aider ?

Salut, et bienvenue sur le forum

Comme, ainsi que te l'a fait remarquer FunK92, tu n'indiques pas le problème auquel tu es confronté, je vais me permettre quelques conseils d'ordre génériques, en rapport avec ta question...

D'abord, il faut savoir qu'en C++, la définition d'un type personnalisé (structure, classe, énumération ou union) provoque automatiquement la définition du type en question...

Il n'est donc pas nécessaire de repréciser le mot clé (struct, class, enum ou union) lorsque tu veux déclarer une variable du type correspondant...

De plus, il faut savoir qu'il est possible de définir des types personnalisés non seulement dans une structure ou une classe (on parle alors de type "imbriqué"), mais que le C++ autorise aussi de définir un type personnalisé qui n'existe que dans une fonction particulière, ce qui fait que le code suivant est tout à fait valide
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <iostream> int main() { struct MyStruct { int a; int b; }; MyStruct s; s.a=2; s.b=3; std::cout<<s.a<<" "<<s.b<<std::endl; } void foo() { //impossible d'utiliser MyStruct }
Pour ces deux raisons, dans un code proche de

Code:

struct mots dico[20]={{"absent",3},{"content",5},/*...*/ };

l'utilisation du mot clé struct est non seulement inutile, mais peut s'avérer dangereuse ;)

De la même manière, il ne sert à rien de rajouter le void dans la liste d'arguments lorsqu'une fonction ne demande aucun argument...

Ta fonction se contenterait donc parfaitement d'être définie sous la forme de
Code:

1 2 3 4 void cherche () { /* ce qu'elle doit faire */ }
Ensuite, il faut savoir que les variables globales "c'est mal"...

En outre, nous ne le répéterons jamais assez, il est toujours mieux de préférer les possibilités offertes par le C++ à toute possibilité équivalente issue du C...

Ainsi, il est préférable de s'habituer directement à l'utilisation de la classe string, disponible dans l'espace de noms std par simple inclusion du fichier d'en-tête <string> dés qu'il s'agit de travailler avec des chaines de caractères, plutôt que de prendre le risque de manipuler des chaines de caractères "C style" (tableau de caractères terminés par '\0')

Enfin, le standard offre une quantité impressionnante de classes susceptibles de te faciliter énormément la vie, dont une série vraiment sympa de conteneurs permettant une mise en oeuvre simple de concepts tels que la pile, la file, la liste, les tableaux (associatifs ou non, triés ou non) où l'arbre binaire...

Pour rester dans ce qui t'intéresse, nous pourrions citer la classe set et la classe map, toutes deux également disponibles dans l'espace de noms std, par inclusion respective des fichiers <set> et <map>

Pour te permettre de faire ton choix parmi les différentes possibilités, tu peux aller faire un tour du côté de cette entrée de la FAQ

Je me suis volontairement restreint dans ma réponse (qui est déjà longue assez), parce que ce que je viens d'écrire est régulièrement expliqué en détail sur le forum...

Je te conseillerais donc d'effectuer une recherche sur le forum si tu veux des explications plus précises sur un point particulier ;)

Mais si tu veux des précisions, n'hésite pas à demander :D

10/01/2009, 17h08
bibi06110

Merci pour vos deux réponse, donc en faite j'ai réussi a corriger un petit truc c'est a dire que bas = 0 et haut = 7 !

Du coup il arrive bien a me trouver la bonne place, le problème est le suivant.

J'ai comparé a chaque fois une seul lettre (la première lettre de mon mot avec la première lettre d'un des mots de mon "dico")

Le problème est que pour le moment je n'ai que un seul et unique mot commençant par A, et un seul commençant par C etc... Si je cherche un mot commençant par A, vu que j'en ai déjà un dans mon dico il trouve pas la bonne place, pour ça je devrais utiliser la deuxième lettre ?
Mais du coup comment faire pour le faire proprement ?

Sinon merci des infos koala01. A vrai dire l'erreur que j'ai mise :

Citation:

struct mots dico[20]={{"absent",3},{"content",5},/*...*/ };

C'est ma prof qui me l'a donné en cours...
Et c'est aussi elle qui a dit de déclarer la structure en global...

Et a mon niveau, je suis pas censé me servir de <string> mais du coup c'est pas facile de manipuler des chaines de caractère dans des tableaux.

Mon problème se résoudrais très facilement si je pouvais faire tout simplement :

if (mot1 <= mots_de_mon_dico)

Mais pour ça je suis obligé d'utiliser <string> non ? Si oui, comment faire svp ?

Merci d'avance pour votre aide ;)

PS : Je n'ai pas encore vu les pointeurs, donc je ne peux pas les utiliser aussi...

Citation:

Envoyé par bibi06110

Merci pour vos deux réponse, donc en faite j'ai réussi a corriger un petit truc c'est a dire que bas = 0 et haut = 7 !

Du coup il arrive bien a me trouver la bonne place, le problème est le suivant.

J'ai comparé a chaque fois une seul lettre (la première lettre de mon mot avec la première lettre d'un des mots de mon "dico")

Le problème est que pour le moment je n'ai que un seul et unique mot commençant par A, et un seul commençant par C etc... Si je cherche un mot commençant par A, vu que j'en ai déjà un dans mon dico il trouve pas la bonne place, pour ça je devrais utiliser la deuxième lettre ?

Si tu veux commencer par gérer la première lettre du mot, il faudrait recourir aux "tables de hash", mais ce ne semble pas être dans tes cordes pour l'instant ;)...

Citation:

Envoyé par bibi06110

Sinon merci des infos koala01. A vrai dire l'erreur que j'ai mise :

Citation:

struct mots dico[20]={{"absent",3},{"content",5},/*...*/ };

C'est ma prof qui me l'a donné en cours...
Et c'est aussi elle qui a dit de déclarer la structure en global...

Ben, si elle t'apprend le C++, tu pourra lui dire que le mot clé struct ici n'est pas nécessaire
Si elle t'apprend le C, tu t'es trompé de forum (mais il faudra alors dire à ta prof de ne pas utiliser cin et cout qui sont des éléments propres au C++ ;))

Quoi qu'il en soit, il faudrait lui dire que tout le monde considère les variables globales comme "mal" et l'inciter à parler rapidement des paramètres de fonctions ;)

Enfin, il faudrait lui rappeler qu'il est très dangereux de ne pas initialiser correctement tous les éléments d'un tableau :aie:

C'est pourquoi, quitte à utiliser un tableau global de 20 éléments, il serait opportun d'initialiser les éléments non donnés sous la forme d'une une chaine vide pour le champs nom et d'une valeur qui ne sera jamais utilisée dans un élément réel pour le champs numéro.

En se basant sur le fait que numéro correspond à l'ordre d'insertion, une initialisation "cohérente" de ta variable dico prendrait une forme proche de
Code:

1 2 3 4 5 6 7 mots dico[20]={{"absent",3}, {"content",5}, {"disparu",1}, {"grand", 6}, {"heureux", 2}, {"immense", 4}, {"minus", 7}, {"petit",8}, /* ce qui suit correspond aux douze éléments non utilisés */ {"\0",21},{"\0",21},{"\0",21},{"\0",21}, {"\0",21},{"\0",21},{"\0",21},{"\0",21}, {"\0",21},{"\0",21},{"\0",21}, {"\0",21} };
Citation:

Envoyé par bibi06110

Mon problème se résoudrais très facilement si je pouvais faire tout simplement :

if (mot1 <= mots_de_mon_dico)
Mais pour ça je suis obligé d'utiliser <string> non ? Si oui, comment faire svp ?

Tel quel, oui, effectivement, seule la classe string dispose de l'opérateur < (mais pas de l'opérateur <=)
Par contre, comme ta prof te demande de travailler à la manière "C style" (quelle horreur :aie:), il faut avoir recours à la fonction issue du C ad-hoc: la fonction strcmp ;)

Cette fonction prend, comme paramètre, les deux chaines à comparer (je simplifie, car, en réalité il s'agit de deux pointeurs sur le premier caractère des chaines à comparer ;))et renvoie
0 si les deux chaines sont égales
une valeur positive si le premier caractère qui ne correspond pas a une valeur plus élevée dans la première chaine que dans la deuxième
une valeur négative dans le cas inverse

Pour pouvoir travailler de manière dichotomique, tu devrais donc travailler sous une forme proche de
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 /* str1 et str2 sont les deux chaines de caractères "C style" à comparer */ int result=strcmp(str1, str2); if(result>0) { /* que faire si str1 > str2 */ } else if(result <0) { /* que faire si str2 > str1 */ } else { /* que faire si str1 est équivalent str2 * je parle d'équivalence parce que si str1 n'est pas * plus grand que str2 et que str2 n'est pas plus grand que * str1, alors str1 et str2 devraient prendre la même position * mais, dans certains cas (pas pour les chaines de caractères), * il est possible que les deux éléments ne soient malgré tout * pas égaux :P */ }
Ensuite, il faut réfléchir à la logique correcte pour effectuer une recherche dichotomique...

Retiens déjà qu'il faut que la recherche s'effectue sur un tableau trié (ce qui signifie qu'il faut veiller à trier le tableau à chaque insertion, ou, au pire, avant chaque recherche si une insertion a été faite depuis la dernière)

Tu t'en sera douté, le but est de tester l'élément qui se trouve au milieu de ceux qui peuvent encore potentiellement correspondre, et de recommencer jusqu'à ce que tu aie trouvé l'élément ad-hoc ou que tu sois sur qu'il n'existe pas.

Pour y arriver, il faut donc travailler sous la forme d'une boucle, et disposer d'un certain nombre de valeur:
Le nombre total des éléments existants
l'index de l'élément qu'il faut tester
le nombre d'éléments à "sauter" pour atteindre le prochain élément à tester
d'un booléen permettant de savoir si l'élément recherché a été trouvé (j'ai horreur des break; qui se baladent n'importe où)
d'un booléen permettant s'il faut effectuer la boucle une fois de plus

La logique à appliquer sera alors de l'ordre de:

demander à l'utilisateur ce qu'il veut trouver (nommons le temp)
initialiser "jump" à la moitié du nombre total d'éléments à tester
initialiser "index" à la moitié du nombre total d'éléments à tester
initialiser encore à vrai
initialiser trouve à faux
tant que encore est vrai et que trouve est faux

diviser jump par 2
si l'élément qui se trouve à index-1 est plus petit que temp

index reçoit index + jump
sinon, si l'élément qui se trouve à index-1 est plus grand que temp

index reçoit index - jump
sinon

trouve vaut vrai (on a trouvé l'élément)
fin si
encore vaut vrai si jump est différent de 0
fin tant
si trouve est vrai

dire qu'on a trouvé l'élément et afficher les infos attendues
sinon

pas de bol... dire que l'on n'a pas trouvé l'élément
fin si