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

Вставка элемента в дерево - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.87
MECTb
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 13
05.12.2010, 02:49     Вставка элемента в дерево #1
Доброго времени суток.Такая проблема,есть задача:
Написать программу,реализующую вставку в Trie дерево.С помощью этой программы создайте Trie дерево и удалите из него слова заканчивающиеся на согласную букву.

Алгоритм решения я впринципе понимаю.А вот с реализацией возникают трудности..

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
#include <vcl.h>
#include <iostream.h>
#pragma hdrstop
 
//---------------------------------------------------------------------------
#define ALPHA_SIZE 26
struct TrieNode
     {
       int count;
       TrieNode *childList[ALPHA_SIZE];
     };
TrieNode *childList[ALPHA_SIZE];(приходется почему то объявлять вне структуры иначе не видит)
void InitTrieTree()
{
   for(int index=0;index<ALPHA_SIZE;index++)
     {childList[index]=NULL;};
      count=0;(тут компилятор выдает ошибку)
}
#pragma argsused
void main()
{
SetConsoleOutputCP(1251);
 
дальше будут вызовы всех функций
 
}
Кому не сложно помогите..
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
05.12.2010, 06:57     Вставка элемента в дерево #2
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
struct node {
    std::string str;
    std::list<node*> children;
    node(const std::string& s):str(s),cildren() {}
};
bool push(node *&t, const std::string& key, const std::string& newvalue)
{
    if (t!=NULL) {
        if (key == t->str) {
            t->children.push_back(new node(newvalue));
            return true;
        } else {  // key != t->str
            if (not t->children().empty()) {
                 for (std::list<node*>::iterator i=t->children.begin(); t != t->children.end(); ++i) {
                      if (push(*i, key, newvalue)) braek;
                 }
                 return true;
            } else {  // t->children().empty() == true
                 return false;
            }
        }
    } else { // t == NULL
         t = new node(newvalue);
         return true;
    }
}
void print(tree *t, int n)
{
     if (t!=NULL) {
          std::cout << t->str;
          if (not t->children.empty()) {
                std::cout << ":\n";
                for (std::list<node*>::iterator i=t->children.begin(); t != t->children.end(); ++i) {
                      for (int k=0; k!=n;++k) std::cout << "  ";
                      print(*i, n + 1);
                }
          } else {
                std::cout << ".\n";
          }
     }
}
int main() {
   node *tree = NULL;
   push(tree,"","first");
   push(tree,"first","second");
   push(tree,"first","third");
   push(tree,"first","forth");
   push(tree,"third","fifth");
   push(tree,"second","sixth");
   push(tree,"second","seventh");
   print(tree, 0);
   return 0;
}
чета типа того, я не компилировал. Еще бы дописать функцию для удаления всего этого...
Насчет удаления тех, что заканчиваются на согласную:
для каждого потомка - сморим на последнюю букву поля str,
если на согласная - всех детей этого потомка добавляем к детям его предка,
а его самого из списка детей предка удаляем.
лень писать, сам сделаешь правда?
И болранд си++ это ересь , лучше другой возьми, например среда code::blocks замечательная.

P. S. push - это как бы добавление по ключу, добавляет узлу со указанной строкой потомка с указанной строкой.
MECTb
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 13
05.12.2010, 14:48  [ТС]     Вставка элемента в дерево #3
Щас если разберусь досконально во всем что ты мне написал,то думаю смогу)

Спасибо большое)

Еще если не сложно можешь подробно рассписать буквально что делается в каждой строке?Буду очень признателен..
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
05.12.2010, 19:24     Вставка элемента в дерево #4
эх... а ты прогу откомпилировал? ладно я сам ща все есделаю )
боже мой, сколько у меня опечаток... ужас
C++
1
2
3
4
5
struct node {
    std::string str;                               // строка текста - данные содержащиеся в узле.
    std::list<node*> children;               // список детей узла.
    node(const std::string& s):str(s),children() {} // конструктор, для создания узла
};
вот тебе работающая прога:
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
#include <iostream>
#include <string>
#include <list>
 
struct node {
    std::string str;
    std::list<node*> children;
    node(const std::string& s):str(s),children() {}
};
// добавление в дерево элемента по ключу
// возвращает true если узел был успешно вставлен в под дерево
// и false в другом случае (не нашлось указанного предка)
// key - ключ по которому ищем предка,
// newvalue - данные для нового узла.
bool push(node *&t, const std::string& key, const std::string& newvalue)
{
    // сначала надо проверить - если указатель нулевой к нему нельзя обращаться.
    if (t!=NULL) {
        if (key == t->str) {  // если этот узел тот кому у список детей надо вставить новый узел то...
            t->children.push_back(new node(newvalue)); // ... собственно вставляем новый узел.
            return true; // вставка успешная значит вернем true.
        } else {  // key != t->str, это не тот узел который должен стать родительским для нового узла...
            // ... значит надо попробовать поискать среди его детей,
            if (not t->children.empty()) { // если дети есть,
                 for (std::list<node*>::iterator i=t->children.begin(); i != t->children.end(); ++i) {
                      // проходим по списку детей и пытаемся впарить новый узел каждому из них
                      // и если получается (см. ниже) то прерываем попытки впарить ивернем true.
                      if (push(*i, key, newvalue)) break;
                 }
                 return true;
            } else {  // t->children.empty() == true - если нет детей
                 // ключ не совпадает, детей нет, искать негде - в это поддерево вставить
                 // новый узел не удалось, вернем false
                 return false;
            }
        }
    } else { // t == NULL - узла нет, такое может быть только если толкаем в корень,
         // нету узла - сделаем. И вернем true т.к. получилось добавить новый узел.
         t = new node(newvalue);
         return true;
    }
}
// вывод дерева на экран
// эту мне лень коментировать, просто логика в следующем:
// выводим текущий узел и всех его детей в списке под ним с отступом,
// чтобы была видна иерархия.
void print(node *t, int n)
{
     if (t!=NULL) {
          std::cout << t->str;
          if (not t->children.empty()) {
                std::cout << ":\n";
                for (std::list<node*>::iterator i=t->children.begin(); i != t->children.end(); ++i) {
                      for (int k=0; k!=n;++k) std::cout << "  ";
                      print(*i, n + 1);
                }
          } else {
                std::cout << ".\n";
          }
     }
}
// корректное освобождение памяти, выделенной под дерево.
// проходим по дереву и удаляем все узлы и освобождаем списки.
void del(node *&t)
{
    if (t != NULL) {
        if (not t->children.empty()) {
            for (std::list<node*>::iterator i=t->children.begin(); i != t->children.end(); ++i) {
                del(*i);
            }
            t->children.clear();
        }
        delete t;
    }
}
int main() {
   node *tree = NULL; // корень дерева
   // далее заталкиваем в дерево элементы
   push(tree,"","first");
   push(tree,"first","second");
   push(tree,"first","third");
   push(tree,"first","forth");
   push(tree,"third","fifth");
   push(tree,"second","sixth");
   push(tree,"second","seventh");
   // выводим на экран ...
   print(tree, 1);
   // ... и удаляем
   del(tree);
   return 0;
}
свою функцию сам пиши, помогу если что.
вывод программы:
Код
first:
  second:
    sixth.
    seventh.
  third:
    fifth.
  forth.
MECTb
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 13
06.12.2010, 00:39  [ТС]     Вставка элемента в дерево #5
В Builder 6 выдает такие ошибки:

C++ Error] Unit1.cpp(26): E2451 Undefined symbol 'not'
[C++ Error] Unit1.cpp(26): E2377 If statement missing )
[C++ Warning] Unit1.cpp(44): W8070 Function should return a value
[C++ Error] Unit1.cpp(53): E2451 Undefined symbol 'not'
[C++ Error] Unit1.cpp(53): E2377 If statement missing )
[C++ Error] Unit1.cpp(69): E2451 Undefined symbol 'not'
[C++ Error] Unit1.cpp(69): E2377 If statement missing )

После замены not на &&,проблемы остались:

[C++ Error] Unit1.cpp(26): E2188 Expression syntax
[C++ Error] Unit1.cpp(38): E2377 If statement missing )
[C++ Warning] Unit1.cpp(44): W8070 Function should return a value
[C++ Error] Unit1.cpp(53): E2188 Expression syntax
[C++ Error] Unit1.cpp(62): E2377 If statement missing )
[C++ Error] Unit1.cpp(69): E2188 Expression syntax
[C++ Error] Unit1.cpp(75): E2377 If statement missing )

Кто специализируется по билдерам,подскажите..
Заранее благодарен.
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
06.12.2010, 00:46     Вставка элемента в дерево #6
строки обозначенные здесь не согласуются с приведенным выше кодом. лучше выложи что у тебя получилось.
MECTb
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 13
06.12.2010, 00:52  [ТС]     Вставка элемента в дерево #7
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
#include <iostream>
#include <string>
#include <list>
 
struct node {
    std::string str;
    std::list<node*> children;
    node(const std::string& s):str(s),children() {}
};
// добавление в дерево элемента по ключу
// возвращает true если узел был успешно вставлен в под дерево
// и false в другом случае (не нашлось указанного предка)
// key - ключ по которому ищем предка,
// newvalue - данные для нового узла.
bool push(node *&t, const std::string& key, const std::string& newvalue)
{
    // сначала надо проверить - если указатель нулевой к нему нельзя обращаться.
    if (t!=NULL) {
        if (key == t->str) {  // если этот узел тот кому у список детей надо вставить новый узел то...
            t->children.push_back(new node(newvalue)); // ... собственно вставляем новый узел.
            return true; // вставка успешная значит вернем true.
        } else {  // key != t->str, это не тот узел который должен стать родительским для нового узла...
            // ... значит надо попробовать поискать среди его детей,
            if (&& t->children.empty()) { // если дети есть,
                 for (std::list<node*>::iterator i=t->children.begin(); i != t->children.end(); ++i) {
                      // проходим по списку детей и пытаемся впарить новый узел каждому из них
                      // и если получается (см. ниже) то прерываем попытки впарить ивернем true.
                      if (push(*i, key, newvalue)) break;
                 }
                 return true;
            } else {  // t->children.empty() == true - если нет детей
                 // ключ не совпадает, детей нет, искать негде - в это поддерево вставить
                 // новый узел не удалось, вернем false
                 return false;
            }
        }
    } else { // t == NULL - узла нет, такое может быть только если толкаем в корень,
         // нету узла - сделаем. И вернем true т.к. получилось добавить новый узел.
         t = new node(newvalue);
         return true;
    }
}
// вывод дерева на экран
// эту мне лень коментировать, просто логика в следующем:
// выводим текущий узел и всех его детей в списке под ним с отступом,
// чтобы была видна иерархия.
void print(node *t, int n)
{
     if (t!=NULL) {
          std::cout << t->str;
          if (&& t->children.empty()) {
                std::cout << ":\n";
                for (std::list<node*>::iterator i=t->children.begin(); i != t->children.end(); ++i) {
                      for (int k=0; k!=n;++k) std::cout << "  ";
                      print(*i, n + 1);
                }
          } else {
                std::cout << ".\n";
          }
     }
}
// корректное освобождение памяти, выделенной под дерево.
// проходим по дереву и удаляем все узлы и освобождаем списки.
void del(node *&t)
{
    if (t != NULL) {
        if (&& t->children.empty()) {
            for (std::list<node*>::iterator i=t->children.begin(); i != t->children.end(); ++i) {
                del(*i);
            }
            t->children.clear();
        }
        delete t;
    }
}
int main() {
   node *tree = NULL; // корень дерева
   // далее заталкиваем в дерево элементы
   push(tree,"","first");
   push(tree,"first","second");
   push(tree,"first","third");
   push(tree,"first","forth");
   push(tree,"third","fifth");
   push(tree,"second","sixth");
   push(tree,"second","seventh");
   // выводим на экран ...
   print(tree, 1);
   // ... и удаляем
   del(tree);
   return 0;
}
Я полностью скопировал написанный тобой код и вставил в билдер,чтобы посмотреть правильность вывода и работоспособность,в итоге он выдал то что написанно выше..

&& - Это логическое AND если я не ошибаюсь,а там должно быть логическое отрицание?
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
06.12.2010, 00:59     Вставка элемента в дерево #8
блин, да я балда не то насоветовал! конечно отрицание! каюсь, каюсь! восклицательный знак надо ставить.
MECTb
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 13
06.12.2010, 01:39  [ТС]     Вставка элемента в дерево #9
После замены на восклицательный знак,в самом коде ошибок он не обнаружил.
Но выдал следующее:

[Linker Error] Unresolved external '__InitVCL' referenced from C:\PROGRAM FILES\BORLAND\CBUILDER6\LIB\CP32MTI.LIB|crtlvcl
[Linker Error] Unresolved external '__ExitVCL' referenced from C:\PROGRAM FILES\BORLAND\CBUILDER6\LIB\CP32MTI.LIB|crtlvcl

Добавлено через 22 минуты
Как я понимаю он не может найти нужные ему библиотеки,котрые следует подключить к проекту и указать к ним путь...Но разве так должно быть,если мне требуется написать проект в Console Wizard?..

Добавлено через 6 минут
Все разобрался,при создании проекта нужно было отключить Use VCL.
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
06.12.2010, 01:45     Вставка элемента в дерево #10
дай ка угадаю навскидку, но может связать функции инициализации визуальных объектов, типа окна и все такое, м... наверно тип проекта не тот выбран. Там должно быть что-нибудь вроде "консольное приложение".

П. С. упс, опоздал.
MECTb
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 13
06.12.2010, 02:35  [ТС]     Вставка элемента в дерево #11
Я правильно понимаю что мы сами выбираем в какой корень мы заталкиваем?
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
06.12.2010, 03:03     Вставка элемента в дерево #12
в данном случае - да. Только ты наверное имел ввиду не в "корень", а в" узел". Корень-то всегда один, это локальная переменная tree через которую осуществляется доступ ко всему дереву, потому и "корень".

Выбираем какой узел станет родительским для нового узла по средствам ключа.
Можно и по другому сделать, чтобы новый узел вставлялся случайным образом, или в лексикографичском порядке.
MECTb
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 13
06.12.2010, 03:12  [ТС]     Вставка элемента в дерево #13
Да я имел в виду узел,а по какому принципу можно сделать чтобы само определялось куда нужно создать лист?Например Вводятся 2 слова Пол и Полковник,чтобы получалось в 1 узле Пол,а в его лист дописывалось ковник?Или чтобы осуществлялось таким образом:

Название: ris76_1.jpg
Просмотров: 183

Размер: 3.2 Кб
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
06.12.2010, 03:38     Вставка элемента в дерево #14
std::string можно сравнивать операторами >, <, ==, !=.
дерево должно быть бинарным.
вовремя вставки необходимо сравнивать данные (str) узла и вставляемую строку (newvalue) оператором <, и если вставляемое больше то вставлять в левое поддерево, меньше - в правое.
для этого надо будет переопределить node
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct node{
    std::string str;
    node *left, *right; // левое, правое поддеревья.
    node(const std::string& s):str(s),left(NULL),rigth(NULL) {}
};
void push(node *&t,std::string newvalue) {
    if (t != NULL) {
       if (newvalue < t->str) push(t->left, newvalue);
       else if (newvalue > t->str) push(t->right, newvalue);
       else std::cout << "Такое значение уже содержится в дереве.\n";
    } else {
       t = new node(newvalue);
    }
}
// использование
node *tree = NULL;
push(tree,"g");
push(tree,"r");
push(tree,"c");
push(tree,"b");
push(tree,"h");
push(tree,"a");
push(tree,"i");
типа того
MECTb
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 13
06.12.2010, 04:34  [ТС]     Вставка элемента в дерево #15
Вот тут node(const std::string& s):str(s),left(NULL),rigth(NULL) {}

Выдал:

[C++ Error] Unit1.cpp(15): E2312 'rigth' is not an unambiguous base class of 'node'

Добавлено через 26 минут
И если я правильно понимаю,то функция вывода этого дерева будет как вывод обычного бинарного?

C++
1
2
3
4
5
6
7
8
9
10
void print(node *t, int n)
{
   if (t!=NULL) 
       {
         print(t->left, n+1);//Вывод левого поддерева
         for(int i=0;i<n;i++)cout<<" ";//Сдвиг позиции соответственно уровню
         cout<<t->str<<endl;//Вывод корня поддерева
         print(t->right, n+1);//Вывод правого поддерева
       }     
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.12.2010, 03:35     Вставка элемента в дерево
Еще ссылки по теме:

Вставка листа в дерево C++
Добавления элемента в бинарное дерево C++
C++ Вставка элемента

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

Или воспользуйтесь поиском по форуму:
MECTb
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 13
17.12.2010, 03:35  [ТС]     Вставка элемента в дерево #16
Вот полностью рабочий код,удовлетворяющий решению задачи,может кому пригодится...

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
#include <string.h>
#include <iostream.h>
#include <vcl.h>
 
struct Tree {
Tree *child[26];
bool term;
int count;
};
 
Tree *initTree() {
Tree *T = new Tree;
for(int i = 0; i < 26; i++) {
T->child[i] = NULL;
}
T->count = 0;
T->term = false;
return T;
}
 
void addWordTree(Tree *root, char *str) {
Tree *T = root;
int length = strlen(str);
for(int i = 0; i < length; i++) {
int index = str[i] - 'a';
if(T->child[index] == NULL) {
T->child[index] = initTree();
T->count++;
}
T = T->child[index];
if(i == (length - 1)) {
T->term = true;
}
}
}
 
void printTree(Tree *T, const char *str) {
 if(T->count>0) {
  for(int i = 0; i < 26; i++) {
   if(T->child[i]) {
    string s("");
    s.assign(str);
    s.append(1, (char) (i + (int) 'a'));
    printTree(T->child[i], s.data());
   }
  }
 }
 if(T->term) cout << str << endl;
}
 
void main() {
SetConsoleOutputCP(1251);
char consonants[] = {'b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x', 'z'};
Tree *T = initTree();
 
for(int i = 0; i < 3; i++) {
int k;
char str[10];
std::cout<<"Введите ветвь дерева"<<endl;
std::cin >> str;
int l = strlen(str);
for(int j=0; j < 20; j++)
{if (str[l-1] == consonants[j]) {*str = NULL; k = 1;} }
if(k == 1){ cout<<"Строка была удалена"<<endl;} else { cout<<"Строка была успешно добавлена"<<endl;}
addWordTree(T, str);
k = 0;
}
printTree(T, "");
system("PAUSE");
}
Yandex
Объявления
17.12.2010, 03:35     Вставка элемента в дерево
Ответ Создать тему
Опции темы

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