C++

arbre binaire en c (dictionnaire)

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : arbre binaire en c (dictionnaire)

vanik

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

Publicité

verdoux

And I'm still waiting

Fais un dessin.

vanik

ok... ca sera plus clair, j'espere qu'on pourra m'aider...

chrisbk

bah, en tout concon :

Code :

typedef struct arbre
{
char c;
arbre *fils[26];
}arbre;

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

vanik

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 :

typedef struct arb
{
char c;
arbre *fils[26];
}arb;
typedef struct arb *arbre;
struct arb b;
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

chrisbk

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 :

typedef struct arbre
{
char c;
arbre *fils[26];
int terminal;
}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 :

void insert(arbre *arbre,char *mot)
{
if (mot[0] == '\0') //on est a la fin du mot
{
arbre->terminal = 1;
return; //fin du boulot
}
char c = tolower(mot[0]); //passe en minuscule
int i;
if (arbre->fils[c] == NULL) //il n'existe pas encore de fils pour cette lettre
{
arbre->fils[c] = malloc(sizeof(arbre)); //alloue...
for (i=0;i<26;i++) //initialise...
arbre->fils[i] = NULL;
arbre->terminal = 0;
arbre->c = c;
}
insert(arbre[c],mot+1); //continue sur le noeud suivant en passant a la prochaine lettre
}

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

vanik

merci bcp à toi chris!!
maintenant il me reste plus qu'à comprendre
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!

chrisbk

vanik a écrit a écrit :

merci bcp à toi chris!!
maintenant il me reste plus qu'à comprendre

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 ?
je vois pas trop ton pb
edit : ah, si et ca te perturbe a raison :

Code :

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

Donc :

Code :

char c = tolower(mot[0]); //passe en minuscule
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

chrisbk

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

vanik

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

:whistle: oui biensur, c t pr voir si qqn suivait!
bravo!

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

Publicité

chrisbk

vanik a écrit a écrit :

:whistle:

oui biensur, c t pr voir si qqn suivait!

bravo!

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?

vanik

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

chrisbk

"le type char est codé sur 8octets"

bon, je vais me coucher, dire des conneries pareilles spa possible

verdoux

And I'm still waiting

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 ?

vanik

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.

Musaran

Cerveaulté

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

FORUM HardWare.fr

Programmation

C++

arbre binaire en c (dictionnaire)

Sujets relatifs
[JAVA] convertir un entier en binaire et vice et versa	connaissez vous une documentation sur 'ARBRE GENEALOGOQUE'c++
Arbre genealogique humain en c++ ??????	[JAVA]Arbre
regwrite et valeur binaire	[C++] ou trouver un dictionnaire des fonctions ???
comment mettre le caractere ' dans une fonction print('arbre '1' ');	ASM -> langage binaire (win32)
[VB] Extraire les données d'un fichier en BINAIRE ??	[PHP] manipulation binaire
Plus de sujets relatifs à : arbre binaire en c (dictionnaire)

Page générée en 0.088 secondes