Форум программистов, компьютерный форум CyberForum.ru

Trie дерево, реализовать вставку - C++

Восстановить пароль Регистрация
 
dzrkot
zzzZZZ...
 Аватар для dzrkot
516 / 346 / 53
Регистрация: 11.09.2013
Сообщений: 1,977
10.08.2014, 19:47     Trie дерево, реализовать вставку #1
вообщем в алгоритмах я не силён...
накидал код, знаю что он уродлив и не работает (я несколько раз переписывал add() поэтому там есть непонятные лишние вещи - там каша...)
необходимо реализовать вставку в дерево, само дерево описано вот так
http://habrahabr.ru/post/111874/

вообщем мб подскажет кто, я уже просто запутался, мб завтра на свежую голову разберусь

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
 
template<class T>
class tree{
    public:
    struct node
        {
        T data;             // данные узла
        char key;           // ключ текущего узла
        node *childList;    // массив листьев текущего узла
        int size;           // кол-во узлов в узле
        };
    node head;
    tree(char c,T d)        // конструктор дерева
        {
        head.size=0;
        head.data=d;
        head.key=c;
        cout<<"new tree is created"<<endl;
        cout<<"key = "<<head.key<<endl;
        cout<<"data = "<<head.data<<endl;
        };
 
    void add(char k, char *c);// к - ключ нового узла, *с - "путь" до него
    void show();
};
template<class T>
void tree<T>::show()
    {
    }
 
template<class T>
void tree<T>::add(char k, char *c)// к - ключ нового узла, *с - "путь" до него
    {
 
    int counter=0,i=0;                  // уровень глубины ключа
    bool flag=true;                       // конец ключа
    node *temp=&head;               // начало дерева
    node *temp2;
 
        if(c[counter]==temp->key)
            {
            counter++;
 
         if (counter==strlen(c)-1)                   // если достигли конец ключа, то создаем нвоый узел, записываем в него данные и выходим
                {
                cout<<"end of tree"<<endl;
                flag=false;
                temp->size++;
                temp->childList=new node[temp->size];
                temp=&(temp->childList[temp->size-1]);
                temp->key=k;
                temp->childList=0;
                temp->size=0;
                }
            else
                {
                temp2=&temp->childList[i];
                cout<<"temp2->key = "<<temp2->key<<endl;
                cout<<"c[counter] = "<<c[counter]<<endl;
                cout<<"strlen(c)-1 = "<<strlen(c)-1<<endl;
                cout<<"counter = "<<counter<<endl;
                }
            if(c[counter]==temp2->key)
                {
                cout<<"asd"<<endl;
                temp=&(temp->childList[i]);
                counter++;
                }
            else
                {
                i++;
                }
 
        }
    }
 
int main()
{
    srand(time(0));
    char c;
    cout<<"cin key :";
    cin>>c;
    tree<int> a(c,rand()%20);
    cin>>c;
    char d[1]={'r'};
    a.add(c,d);
    cin>>c;
    char dd[3]={'r','a','\0'};
 
    a.add(c,dd);
    cin>>c;
    char ddd[4]={'r','a','z','\0'};
 
    a.add(c,ddd);
    return 0;
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.08.2014, 19:47     Trie дерево, реализовать вставку
Посмотрите здесь:

Сделать вставку асма C++
Реализовать алгоритм.перебор(дерево) C++
Напишите программу, которая бы читала дерево в формате (а) и затем печатала бы это дерево в формате (б). C++
C++ Как реализовать вставку ассемблерного кода в код с++ для очистки экрана?
пишу программу на С++, и делаю в ней ассемблеровскую вставку. Возможно ли в этой _asm вставке сделать С++ вставку? C++
C++ Нужно реализовать класс Бинарное дерево.
C++ Реализовать структуру данных «сбалансированное дерево поиска»
C++ Реализовать бинарное дерево, каждому ребру которого соответствует целое число

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,921
Записей в блоге: 1
10.08.2014, 21:42     Trie дерево, реализовать вставку #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от dzrkot Посмотреть сообщение
само дерево описано вот так
Статья "ни о чем", со странной терминологией и типичной для хабра орфографией. Нормальных статей и реализаций Trie - море, начните, хотя бы, с wiki.

Из книг, IMHO, лучше всего взять Гасфилд Д. "Строки, деревья и последовательности в алгоритмах + примеры".

Библиотека работы со строками к книге Гасфилда: Strmat 1.5

Готовые реализации с codeproject:

Using Ternary DAGs for Spelling Correction
Class for quick string lookup
Patricia Trie Template Class
Patricia and Huffman, Sitting in a Trie
+
Boolean Text Search Queries and their Processing
A Lite-Memory Dictionary
dzrkot
zzzZZZ...
 Аватар для dzrkot
516 / 346 / 53
Регистрация: 11.09.2013
Сообщений: 1,977
10.08.2014, 22:36  [ТС]     Trie дерево, реализовать вставку #3
Цитата Сообщение от gazlan Посмотреть сообщение
Статья "ни о чем", со странной терминологией и типичной для хабра орфографией. Нормальных статей и реализаций Trie - море, начните, хотя бы, с wiki.
ну из неё я получил хоть примерное представление о том, что это за структура данных
Yandex
Объявления
10.08.2014, 22:36     Trie дерево, реализовать вставку
Ответ Создать тему
Опции темы

Текущее время: 03:31. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru