VPF::Дерево цифрового поиска (trie) - Форум программистов

avlzll

Дата 24.11.2008, 18:36 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 43
Регистрация: 30.11.2007

Репутация: нет
Всего: нет

День добрый. При реализации дерева цифрового поиска столкнулся с небольшой проблемкой.

А именно. Имеется структура вида:

Код


#define ALPH_SIZE 26 // Число букв алфавита

struct trieNode {
    
    int count; 
    
    // Массив указателей предка
    trieNode *childList[ALPH_SIZE];

    // Конструктор
    trieNode();
};

trieNode::trieNode() {
    
    count = 0;

    // Заполняем все указатели NULL-ми
    for (int index = 0; index < ALPH_SIZE; index++)
    {
        childList[index] = NULL;        
    }

}

И соответственно функция добавления в дерево.

Код


void Trie::AddToTrie(char* str) {
    
    trieNode *temp = root;  // root - корень дерева
    
    //temp->count++;
    
    // Разбиваем слово на буквы и строим дерево
    for (int i = 0; i < strlen(str) ; i++) {

        int index = str[i] - 'a'; // Получаем "хеш-адрес" буквы, a = 0, b = 1, c = 3 и т.д. 
        
        // Есть ли предок для этой буквы?
        if (temp->childList[index] == NULL) {
            
            // Если нет, то создаем            
            temp->childList[index] = new trieNode;            
            nodeCount++;
        } 
        
        //temp->childList[index]->count++;

        temp = temp->childList[index];
        
    }
    std::cout << "Слово [" << str << "] успешно добавлено в дерево !" << std::endl;
}

Все это дело успешно работает. Без ошибок. Дерево строится, но ... как видно, структура не хранит букв. Хотелось бы добавить в функцию AddToTrie() возможность писать еще и саму букву s[i] в структуру. Реализовать это по-человечески не получается.

Буду благодарен любым советам. Спасибо. smile

Это сообщение отредактировал(а) avlzll - 24.11.2008, 19:14

xvr

Дата 25.11.2008, 11:29 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 35
Всего: 223

Зачем тебе буква? Она и так уже есть неявно - в виде индекса в childList
Единственное, что у тебя не сохраняется - это признак конца слова. Для него можно завести переменную типа bool в самом trieNode

Кстати, trie делают для скорости, а такие циклы

Код


for (int i = 0; i < strlen(str) ; i++)

делают для тормознутости, не надо вычислять strlen для каждого символа в строке, он (strlen) меняться не будет, а вычисляться будет

Это сообщение отредактировал(а) xvr - 25.11.2008, 11:32

avlzll

Дата 25.11.2008, 16:53 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 43
Регистрация: 30.11.2007

Репутация: нет
Всего: нет

Цитата(xvr @ 25.11.2008, 11:29)

Код


for (int i = 0; i < strlen(str) ; i++)

делают для тормознутости, не надо вычислять strlen для каждого символа в строке, он (strlen) меняться не будет, а вычисляться будет

Да мне надо вывести все дерево на экран и никак не додумаюсь как. Понятно, что нужно использовать обратное преобразование из цифр в букву, аля (char)(i + 'a'), но что-то до конца так и не получается это сделать. А так, конечно, буквы не нужны.

За замечания спасибо - поправил.

avlzll

Дата 25.11.2008, 21:37 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 43
Регистрация: 30.11.2007

Репутация: нет
Всего: нет

Да, от букв надо отказаться - но корректно вывести так и не удается.

Код


void Trie::Print(trieNode *temp)
{
    int k;
        char tmp;

    for (k = 0; k < ALPH_SIZE; k++)
        {
            if (temp->childList[k] != NULL)
            {
                tmp = (char)(k + 'a');
                std::cout << tmp;
                Print(temp->childList[k]);
            }
        }
}

Этот кусок печатает цепочки целиком, без разбиения на слова.

При добавлении ставится флаг об окончании слова, но как его правильно применить для вывода... smile

Help

xvr

Дата 25.11.2008, 21:50 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 35
Всего: 223

Цитата(avlzll @ 25.11.2008, 21:37)

Да, от букв надо отказаться - но корректно вывести так и не удается.

Код


void Trie::Print(trieNode *temp)
{
    int k;
        char tmp;

    for (k = 0; k < ALPH_SIZE; k++)
        {
            if (temp->childList[k] != NULL)
            {
                tmp = (char)(k + 'a');
                std::cout << tmp;
                Print(temp->childList[k]);
            }
        }
}

Help

Этот кусочек работает неправильно, буквы, через которые проходит несколько путей должны выводится несколько раз, а здесь они выводятся лишь однократно. Нужно накапливать путь от корня до листа и там уже и печатать

Код


void Trie::Print(std::string& cur_path)
{
    if (this_is_last_node) std::cout << cur_path << endl;

    for (int k = 0; k < ALPH_SIZE; k++)
        {
            if (childList[k] != NULL)
            {
              char v=k+'a';
              cur_path.append(&v,1);
              childList[k]->Print(cur_path);
              cur_path.resize(cur_path.size()-1);
            }
        }
}

Вызывать так

Код


std::string dummy;
trie->Print(dummy);

avlzll

Дата 25.11.2008, 22:19 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 43
Регистрация: 30.11.2007

Репутация: нет
Всего: нет

Большое спасибо, xvr, за помощь! Немного поправил и оно заработало так, как надо.

Код


void Trie::Print(trieNode *temp, std::string& cur_path) 
{
    if (temp->isWord) std::cout << cur_path << endl;
    for (int k = 0; k < ALPH_SIZE; k++)
        {
            if (temp->childList[k] != NULL)
            {
              char v = k + 'a';
              cur_path.append(&v, 1);
              Print(temp->childList[k], cur_path);
              cur_path.resize(cur_path.size() - 1);
            }
        }
}

Для вызова сделал функцию внутри класса.

Код


void Trie::___Print()
{
    std::string dummy;
    Print(root, dummy); // root - указатель на начало дерева
}

Пойду про string почитаю по-больше. smile

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »