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

из раздела Рекурсия - C++

Восстановить пароль Регистрация
 
utwo
 Аватар для utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
07.01.2010, 14:26     из раздела Рекурсия #1
Всем привет! С праздниками!

Возникли проблемы с следующей задачкой. С чего начать?
Может какой-нибудь сырой код для наглядности и понимания?

Прoгрaммa oтoбрaжaeт нa экрaнe cтруктуру дaнных - дeрeвo.
Для рaвнoмeрнoгo рaзмeщeния вeршин прoгрaммa дoлжнa «знaть»
для кaждoй вeршины интeрвaл пoзиций экрaнa, кoтoрый выдeлeн
для дaннoгo пoддeрeвa, и кoличecтвo вeршин в пoддeрeвe. caмo
дeрeвo мoжнo зaдaть cтaтичecки (инициaлизaция).

Спасибо за любой ответ!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.01.2010, 14:26     из раздела Рекурсия
Посмотрите здесь:

C++ Рекурсия
Рекурсия C++
Копирование одного раздела в другой C++
C++ Проверить доступность дискового раздела _getdrives
Рекурсия C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
07.01.2010, 15:51     из раздела Рекурсия #2
старо как мир:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct node // узел дерева
{
         int info; //значние хранимое узлом
         node *left, right;//леове, правое поддерево соответственно
};
void print(int n) //само собой void print(int) принадлежит классу или структуре - дереву.
{
      if (right) right->print(n+1); //спускаемся по правой ветке доконца, какапливаем количство отступов (n+1)
      for (int i=0;i<n;i++) cout << "    "; //вот, спустились, дальше нукуда, распечатываем елемент.
      cout << info << endl;                 //когда рекусрсия разворачивается печатаются и все остальные элементы. через которые мы спускались
      if (left) left->print(n+1); //незабывем спуститься и по правой ветке, что бы сделат тоже самое
}
int main()
{
    //...
    tree T;//дерево T
    //заполнение дерева
    T.print(1);//вывод дерева на экран
}
utwo
 Аватар для utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
07.01.2010, 16:05  [ТС]     из раздела Рекурсия #3
Aye Aye
Спасибо Огромное за быстрый ответ! +100

Честно говоря по комментам не совсем понял. Можно по подробнее описать?
Старо как мир? Это потому что уже обсуждалось неоднократно и очень давно. Если не сложно ткните пальцем плз..где и когда.
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
07.01.2010, 16:27     из раздела Рекурсия #4
тыкаю пальцем: ТЫК

без использования классов получится. но будь внимателен, у структур нет деструкторов. надо будет как следует продумать удаление дерва из памяти. (точно так же как у меня в примере, только надо вызвать удаление всех элементов в конце работы с деревом)
utwo
 Аватар для utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
07.01.2010, 16:34  [ТС]     из раздела Рекурсия #5
Цитата Сообщение от Aye Aye Посмотреть сообщение
тыкаю пальцем: ТЫК

без использования классов получится. но будь внимателен, у структур нет деструкторов. надо будет как следует продумать удаление дерва из памяти. (точно так же как у меня в примере, только надо вызвать удаление всех элементов в конце работы с деревом)
Значит template и class можно заменить на структуры, но только теперь остается корректно удалить дерево.
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
07.01.2010, 17:01     из раздела Рекурсия #6
нет, еще надо будет везде вместо шаблонных типов T и I поставить конкретные типы, int, например.
ну и вообще просмотреть весь код, может еще что то надо поменять... в main() надо удалить конкретизацию шаблонов
utwo
 Аватар для utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
10.01.2010, 19:19  [ТС]     из раздела Рекурсия #7
Aye Aye,
будет возможность помочь переделать код без классов и шаблонов?

Немного переделал код, оставил только функционал добавления и просмотра
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
102
103
104
105
106
107
#include<iostream>
using namespace std;
 
template <class T,class I> class node
{
      private:
              T x; //ключ
              I info;//информация
              node* LL; //left link
              node* RL; //right link
      public:
             node(){x=0;LL=0;RL=0;};
             ~node()
             {
                  if (LL) LL->~node();
                  if (RL) RL->~node();
                  if (LL) {delete LL; LL=0;}
                  if (RL) {delete RL; RL=0;}
             }
             void putx(T new_x,I new_info){this -> x=new_x;this -> info=new_info;}
             void null_leftlink(){this -> LL=0;}
             void null_rightlink(){this -> RL=0;}
             void add(T new_x, I new_info)
             {
                  if (LL&&(new_x < x)) LL->add(new_x,new_info);
                  if (RL&&(new_x > x)) RL->add(new_x,new_info);
                  
                  if (!LL&&(new_x < x))
                  {
                          node* N=new node;
                          N->x=new_x;
                          N->info=new_info;
                          N->LL=0;
                          N->RL=0;
                          LL=N;
                  }
                  if (!RL&&(new_x > x))
                  {
                          node* N=new node;
                          N->x=new_x;
                          N->info=new_info;
                          N->LL=0;
                          N->RL=0;
                          RL=N;
                  }
             }
             void print(int tab)
             {
                  if (RL) RL-> print(tab + 1);
                     for(int i=1;i!=tab;i++)cout << "  "; cout <<this->x << "-"<< this->info << endl;
                  if(LL) LL->print(tab + 1);      
             }
 
 
};
 
template <class T,class I> class tree
{
      private:
              node <T,I>* link;
      public:
             tree(){link=0;};
             void add(T new_x,I new_info)
             {
                  if (link) link->add(new_x,new_info);
                  else
                  {
                      node<T,I>* N=new node<T,I>;
                      N->putx(new_x,new_info);
                      N->null_leftlink();
                      N->null_rightlink();
                      link=N;
                  }
             };
             void print(){if(link)link->print(1);else cout << "No tree existing\n";}
             
           
          
};
 
int main()
{
 
    tree <int,char> *T=new tree <int,char>; // создание дерева
    //menu
    int choos=0;
    const int exit=3;
    while (choos!=exit)
    {
          cout << "  1-add;\n"
                  "  2-print;\n"
                  "  3-exit;\n"
                  "enter-> "; cin >> choos; system("cls");
          switch (choos){
                 case 1: {
                         int key; //ключ.
                         char val; //значение
                         cout << "enter key: "; cin >> key;
                         cout << "enter int value: "; cin >> val; 
                         T->add(key,val); 
                         break;
                 }
                 case 2: T->print(); break;
          }
    }
    delete T; //удаление дерева, используется деструктор.
}
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
10.01.2010, 21:32     из раздела Рекурсия #8
вот, вместо шаблонных классов структуры:
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
#include<iostream>
using namespace std;
 
struct node
{
             int x; //êëþ÷
             char info;//ГЁГ*ôîðìГ*öèÿ
             node* LL; //left link
             node* RL; //right link
             node(){x=0;LL=0;RL=0;};
             ~node()
             {
                  if (LL) LL->~node();
                  if (RL) RL->~node();
                  if (LL) {delete LL; LL=0;}
                  if (RL) {delete RL; RL=0;}
             }
             void putx(int new_x,char new_info){this -> x=new_x;this -> info=new_info;}
             void null_leftlink(){this -> LL=0;}
             void null_rightlink(){this -> RL=0;}
             void add(int new_x, char new_info)
             {
                  if (LL&&(new_x < x)) LL->add(new_x,new_info);
                  if (RL&&(new_x > x)) RL->add(new_x,new_info);
                  
                  if (!LL&&(new_x < x))
                  {
                          node* N=new node;
                          N->x=new_x;
                          N->info=new_info;
                          N->LL=0;
                          N->RL=0;
                          LL=N;
                  }
                  if (!RL&&(new_x > x))
                  {
                          node* N=new node;
                          N->x=new_x;
                          N->info=new_info;
                          N->LL=0;
                          N->RL=0;
                          RL=N;
                  }
             }
             void print(int tab)
             {
                  if (RL) RL-> print(tab + 1);
                     for(int i=1;i!=tab;i++)cout << "  "; cout <<this->x << "-"<< this->info << endl;
                  if(LL) LL->print(tab + 1);      
             }
 
 
};
 
struct tree
{
             node* link;
             tree(){link=0;};
             void add(int new_x,char new_info)
             {
                  if (link) link->add(new_x,new_info);
                  else
                  {
                      node* N=new node();
                      N->putx(new_x,new_info);
                      N->null_leftlink();
                      N->null_rightlink();
                      link=N;
                  }
             };
             void print(){if(link)link->print(1);else cout << "No tree existing\n";}
};
 
int main()
{
 
    tree *T=new tree; // ñîçäГ*Г*ГЁГҐ äåðåâГ*
    //menu
    int choos=0;
    const int exit=3;
    while (choos!=exit)
    {
          cout << "  1-add;\n"
                  "  2-print;\n"
                  "  3-exit;\n"
                  "enter-> "; cin >> choos; system("cls");
          switch (choos){
                 case 1: {
                         int key; //êëþ÷.
                         char val; //Г§Г*Г*Г·ГҐГ*ГЁГҐ
                         cout << "enter key: "; cin >> key;
                         cout << "enter int value: "; cin >> val; 
                         T->add(key,val); 
                         break;
                 }
                 case 2: T->print(); break;
                  }
    }
    delete T; //ГіГ¤Г*ëåГ*ГЁГҐ äåðåâГ*, èñïîëüçóåòñÿ äåñòðóêòîð.
}
utwo
 Аватар для utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
10.01.2010, 21:38  [ТС]     из раздела Рекурсия #9
глюк
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.01.2010, 11:08     из раздела Рекурсия
Еще ссылки по теме:

C++ Рекурсия
C++ рекурсия в с++ ( ?: = if() else)
рекурсия C++

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

Или воспользуйтесь поиском по форуму:
utwo
 Аватар для utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
12.01.2010, 11:08  [ТС]     из раздела Рекурсия #10
Aye Aye, спасибо большое! Все прекрасно работает!

Но вот теперь нужно внести небольшие изменения:

Элeмeнт дeрeвa coдeржит либo дaнныe (cтрoкa oгрaничeннoй
длины), либo укaзaтeли нa прaвoe и лeвoe пoддeрeвья. Стрoки в
дeрeвe получаются упoрядoчeны. Нaпиcaть функцию включeния нoвoй cтрoки.
Обрaтить внимaниe нa тo, чтo элeмeнт c укaзaтeлями нe coдeржит
дaнных, и при включeнии нoвoй вeршины вeршину c дaнными
cлeдуeт зaмeнить нa вeршину c укaзaтeлями.


Если я правильно понял, дерево мое теперь должны выглядеть таким образом?
[IMG]http://s005.***********/i210/1001/70/359df1ab5f24t.jpg[/IMG]
Yandex
Объявления
12.01.2010, 11:08     из раздела Рекурсия
Ответ Создать тему
Опции темы

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