Discussion :

[gnto]

Bonjour les amis,

Voila je souhaite faire de la colorisation syntaxique donc il me faut un analyseur lexical e + un dico.
Je voudrais quelle que chose de rapide, j'ai pensé à un dico avec arbre AVL cousus car j'ai le code sous la main .

La question que pensez vous de cette structure ? que me conseillez-vous comme structure pour réaliser un dico dont la recherche est rapide ? Y'a t-il des bibliothèques réalisant tout ca pour moi ? (à tout hasard )

PS: Oui si j'avais des sous j'aurais pu acheter un bouquin sur le C et structure avancé, voire aussi le K&R

[Médinoc]

Pour un dico à recherche rapide, ça dépend si tu as besoin qu'il soit trié ou non.
Généralement, on fait comme le proposent les collections Java ou les Dictionary de .Net:
Non-trié ---> Table de hachage
Trié ---> Arbre équilibré.

[skip78]

Bah pour un dico j'imagine qu'il faut trier tout de même
un ABR fera l'affaire

[ToTo13]

Bonjour,

la majorité des dictionnaires se font à l'aide de tables de hashage. Ils utilisent deux clefs de hachages :
- Une pour le mots.
- Une pour parcourir la table si la case est déjà occupé.

Bon courage...

[gnto]

Merci pour vos réponses,
J'avais mis le cerveau a off, donc trié ca sera optimisé pour la recherche, donc j'ai reprendre mon arbre (binaire de recherche) AVL.

[Médinoc]

Euh... Trié n'est PAS optimisé pour la recherche: La recherche se fait en O(Log n), alors qu'en haché c'est presque du O(1).

PS: Pourquoi une seconde table de hachage quand il y a collision dans la première ? Il existe toujours une chance non-nulle de collision dans les deux...
Généralement, mes tables de hachages perso sont des tableaux de listes non-triées si je n'ai pas à vérifier la présence de doublons, et des tableaux de listes triées si je dois m'assurer de ne pas créer de doublons.