Вот такой алгоритм на QT я использовал для проблемы поиска слова в словаре. Сложность pow(log,2).
Заполняется дерево. В элементах дерева количество первых символов для сравнения и слово. Если первые символы совпадают,
то проверяется слово целиком. для заполнения дерева словами функция add_word_to_tree("абак"). для поиска наличия слова в словаре функция find_in_tree(word_tree,"краб"). Просто скопировать код в QT программу и исправить, если что возникло.
Код:
class tree_node {
public:
tree_node():right(NULL),left(NULL){}
~tree_node() { delete right; delete left; }
int cnt;
QString word;
tree_node* right;
tree_node* left;
} *word_tree = NULL;
void recu_add_word(tree_node* node, QString word)
{
if (node->word.left(node->cnt) == word.left(node->cnt))
{
if (node->left == NULL)
{
node->left = new tree_node();
node->left->word = word;
node->left->cnt = node->cnt + 1;
} else {
recu_add_word(node->left, word);
}
} else {
if (node->right == NULL)
{
node->right = new tree_node();
node->right->word = word;
node->right->cnt = node->cnt;
} else {
recu_add_word(node->right, word);
}
}
}
void add_word_to_tree(QString word)
{
if (word_tree == NULL)
{
word_tree = new tree_node();
word_tree->word = word;
word_tree->cnt = 1;
} else {
recu_add_word(word_tree, word);
}
}
int find_in_tree(tree_node *node, QString word)
{
int ret = 1;
if (node == NULL) return 1;
if (node->word.left(node->cnt) == word.left(node->cnt)){
if (node->word == word)
ret = 0;
else
if (ret != 0)
ret = find_in_tree(node->left, word);
} else
if (ret != 0)
ret = find_in_tree(node->right, word);
return ret;
}
13.02.2009, 19:08 
