Discussion :

[bibi06110]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[FunK92]

Salut,

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

[koala01]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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 :

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...

[koala01]

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 ...

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

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

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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} };

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 ), 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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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