arbre binaire en c (dictionnaire)

arbre binaire en c (dictionnaire) - C++ - Programmation

Marsh Posté le 09-11-2002 à 19:02:49    

salut à tous,
 
je debute et je dois faire un "trie" en c, mais j'arrive pas à comprendre comment faire.
le programme doit trouver si un mot fait partie du trie, doit pouvoir ajouter un mot au trie, lister le trie et dire si un mot est prefixe dans le trie.
typiquement, on a affaire à 1 structure avec comme 1ere composante des caracteres et comme 2eme composante...?????
des pointeurs sur pointeurs sur la structure??? des pointeurs sur quoi s'il vous plait :cry:  
disons qu'à la racine on ait : a | . et b | .
 
a | .
. pointe sur : l | . et  r | . et m | . par exemple
le pointeur du r | . doit pointer à son tour vers  b | . et r | . par exemple......
 
b | .
. pointe sur : o | . et e | . par exemple
le . de o | . doit pouvoir pointer sur l | . et n | . et r | . par exemple....
 
de façon à avoir des mots (bol, bon, bonjour, allo, arbre, arreter....)
je suis pas clair du tout, mais c parce que c pas tres clair ds ma tete! et c pas facile de representer ca sur ordi...
 
PLIZ HELP ME JE SUIS DS LA ***** :(  :(  
 
merci bcp de m'aider.
ce message pourrait aussi avoir sa place ds la sous-catégorie algo mais bon, le prog doit etre en C...

Reply

Marsh Posté le 09-11-2002 à 19:02:49   

Reply

Marsh Posté le 09-11-2002 à 19:21:47    

Fais un dessin.

Reply

Marsh Posté le 09-11-2002 à 20:11:24    

ok... ca sera plus clair, j'espere qu'on pourra m'aider...
 
http://vanik187.free.fr/Divers/Arbre.jpg

Reply

Marsh Posté le 09-11-2002 à 20:18:31    

bah, en tout concon :
 

Code :
  1. typedef struct arbre
  2. {
  3. char c;
  4. arbre *fils[26];
  5. }arbre;


 
Le tableau est pas terrible, a remplacer plus tard par liste chainée & cie.

Reply

Marsh Posté le 09-11-2002 à 20:35:17    

ok merci, g encore du mal à manipuler les pointeurs.
une fois qu'on a fait ca, est ce qu'il faut trier les lettres? le a c'est le 1er, le b le 2eme... le z le 26eme?
ouais en fait j'avais une idée de la structure mais le prog... hum hum
dc si on a un truc genre

Code :
  1. typedef struct arb
  2. {
  3.   char c;
  4.   arbre *fils[26];
  5. }arb;
  6. typedef struct arb *arbre;
  7. struct arb b;
  8. arbre A=&b;


 
pr arriver au r de bor, il faut A->fils[2]->fils[15]->fils[18] ?? desolé je m'y perds un peu... :whistle:


Message édité par vanik le 09-11-2002 à 20:36:54
Reply

Marsh Posté le 09-11-2002 à 20:41:41    

heuh, tu sais, la structure interne, t'en fais ce que tu veux. tu peux effectivement considerer que le 0 c'est 'a', le 1 'b' etc etc, mais c toi qui choisi. Mais effectivement, c'est le plus simple.
 
Perso, je rajouterais aussi ca comme ca:

Code :
  1. typedef struct arbre
  2. {
  3. char c;
  4. arbre *fils[26];
  5. int terminal;
  6. }arbre;


 
terminal mis a 0 si non terminal, 1 si terminal
 
(pour pas que "bo" soit reconnu comme un mot alors que "bord" est dans l'arbre)
 
l'insertion, tu peux la voir comme ca:
 
 

Code :
  1. void insert(arbre *arbre,char *mot)
  2. {
  4. if (mot[0] == '\0') //on est a la fin du mot
  5. {
  6.   arbre->terminal = 1;
  7.   return; //fin du boulot
  8. }
  10. char c = tolower(mot[0]); //passe en minuscule  
  11. int i;
  12. if (arbre->fils[c] == NULL) //il n'existe pas encore de fils pour cette lettre
  13. {
  14. arbre->fils[c] = malloc(sizeof(arbre)); //alloue...
  15. for (i=0;i<26;i++)   //initialise...
  16. arbre->fils[i] = NULL;
  18. arbre->terminal = 0;
  19. arbre->c = c;
  20. }
  23. insert(arbre[c],mot+1); //continue sur le noeud suivant en passant a la prochaine lettre
  24. }


Message édité par chrisbk le 09-11-2002 à 20:42:41
Reply

Marsh Posté le 09-11-2002 à 22:11:53    

merci bcp à toi chris!!
maintenant il me reste plus qu'à comprendre :D
le fait que t'aies mis 2 fois arbre et 2 fois c  pour des choses differentes me perturbe un peu mais merci bcp pr les explications!!
g pa trop compris ce qu'etait fils[c] etant donné que c est une lettre, pas un chiffre, à moins que la fonction tolower renvoie l'equivalent ascii de la lettre minuscule ???
enfin merci!

Reply

Marsh Posté le 09-11-2002 à 22:14:54    

vanik a écrit a écrit :

merci bcp à toi chris!!
maintenant il me reste plus qu'à comprendre :D
le fait que t'aies mis 2 fois arbre et 2 fois c  pour des choses differentes me perturbe un peu mais merci bcp pr les explications!!




 
plait il ? :D
je vois pas trop ton pb
edit : ah, si :D et ca te perturbe a raison :
 

Code :
  1. arbre *arbre


n'est pas valide (eg arbre etant un type il ne peut plus etre utilisé comme nom de variable). Bref, remplace l'un ou l'autre par autre chose
 
 
 
 

vanik a écrit a écrit :

 
g pa trop compris ce qu'etait fils[c] etant donné que c est une lettre, pas un chiffre, à moins que la fonction tolower renvoie l'equivalent ascii de la lettre minuscule ???
enfin merci!




 
mdr, j'ai fait n'imp :D
ouaip, tolower renvoie l'equivalant minuscule, mais ca reste une lettre, pas un chiffre.
 
bref 'a' ne sera pas egal a 0 comme le code que g posté suppose :D
 
Donc :
 

Code :
  1. char c = tolower(mot[0]); //passe en minuscule   
  2. c = c -'a'; //corrige ce bug stupide :D


 
 
(que de faute dans un truc aussi petit, j'ai honte :sweat:)


Message édité par chrisbk le 09-11-2002 à 22:18:39
Reply

Marsh Posté le 09-11-2002 à 22:17:16    

au fait, un arbre binaire c un arbre qui a que deux fils, ce qui n'est pas le cas la :D

Reply

Marsh Posté le 09-11-2002 à 22:26:51    

chrisbk a écrit a écrit :

au fait, un arbre binaire c un arbre qui a que deux fils, ce qui n'est pas le cas la :D




 
 
 :whistle: oui biensur, c t pr voir si qqn suivait! :D
 bravo! :D  
 
dc du coup, qd on fait c = c-'a', c est un chiffre maintenant c'est ca? c'est égal à val ascii de c - val ascii de a ? à cause du - 'a', c'est ca? arrrg g du mal


Message édité par vanik le 09-11-2002 à 22:28:38
Reply

Marsh Posté le 09-11-2002 à 22:26:51   

Reply

Marsh Posté le 09-11-2002 à 22:30:40    

vanik a écrit a écrit :

 
 
 
 :whistle: oui biensur, c t pr voir si qqn suivait! :D
 bravo! :D  
 
dc du coup, qd on fait c = c-'a', c est un chiffre maintenant c'est ca? c'est égal à val ascii de c - val ascii de a ? à cause du - 'a', c'est ca?




 
oué, bon un char, c'est tout d'abord un entier codé sur seulement 8octet. Ensuite on utilise le codage ASCII pour faire correspondre une lettre a un chiffre. ok ? Ceci dit, il faut aussi savoir que 'a' n'a pas pour valeur 0, et que les types qui ont fait l'ascii ont eu la bone idée de ranger tout ca par ordre alphabétique (genre, 'a' = 15 (au hasard, je connais plus la vraie valeur) alors 'b'=16)
 
c'est pour ca que quand je fais :
c = c -'a'
je me retrouve avec l'indice correct pour aller chercher le fils suivant dans mon tableau (0 pour a, 1 pour b, 2 pour c etc etc etc)
ok?
 
 
 
 

Reply

Marsh Posté le 09-11-2002 à 22:42:58    

ok c donc bien c'que j'avais compris. merci à toi.
 
par contre je crois que le char est codé sur 1 octet, soit 8 bits, soit 2^8=256 valeurs possibles (d'où 256 valeurs ascii). ;)
 
merci bcp pr ton aide !!!!!!!!! :)

Reply

Marsh Posté le 09-11-2002 à 22:48:57    

"le type char est codé sur 8octets"
 
bon, je vais me coucher, dire des conneries pareilles spa possible

Reply

Marsh Posté le 09-11-2002 à 23:01:57    

vanik a écrit a écrit :

ok... ca sera plus clair, j'espere qu'on pourra m'aider...
 
http://vanik187.free.fr/Divers/Arbre.jpg




Bon maintenant que t'as fait le dessin, c'est évident, non ?

Reply

Marsh Posté le 09-11-2002 à 23:34:56    

verdoux a écrit a écrit :

 
Bon maintenant que t'as fait le dessin, c'est évident, non ?




 
LOL
booaah y'a evident et evident :sweat:  
disons qu'entre faire le dessin (que j'avais deja fait) et faire le programme y'a qq pas... g t pas sur s'il fallait à chaq fois creer 26 fils ou si y'avait pas un moyen pr creer des fils de façon "dynamique" (en creer un à chaq fois qu'on ajoute une lettre). d'ailleurs c toujours pas tres clair, mais bon ca viendra. :)

Reply

Marsh Posté le 10-11-2002 à 01:28:02    

En anglais...
"tree" veut dire arbre.
"bit" veut dire... bit.
"byte" veut dire octet (codet en fait, mais ne chipotons pas).


---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed