Kselax.ru

Hacker Kselax — the best hacker in the world

Menu
  • Блог
  • Контакты
  • wp plugin генератор
  • Русский
    • Русский
    • English
Menu

Двоичное дерево с данным string

Posted on 1 марта, 20133 марта, 2013 by admin

Перепишите Tnode в виде класса с конструкторами деструктором и.т.д. Определите дерево с узлами Tnode в виде классов с конструкторами деструктором и.т.д.

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

Структуры данных

Бывают линейные и не линейные структуры данных. К линейным относят связанные списки, двусвязные списки, стеки, очереди, и вся фигня которая строиться на линейном списке. К не линейным относят деревья, в частности двоичное дерево.

Вот как раз мы и рассмотрим двоичное дерево.

Двоичное дерево

Что же это такое? мы рассмотрим бинарное двоичное дерево с двумя ветками, то есть каждый узел имеет две ветки не более.

Первый элемент в двоичном дереве добавляется в корень дерева — это узел на вершине дерева, самый первый, остальные элементы, добавляются относительно этого первого узла: если элемент больше корневого узла он добавляется в правую ветку, если меньше, то в левую, и так для каждого узла, естественно с помощью рекурсивных функций.

Узлы дерева строятся на автореферентных классах (классы которые содержать в себе указатели на самих себя, то, есть создают цепочку) в кажом классе содержится элемент данных в котором храниться значение узла и два указателя на потомки узла или ветки, правую и левую ветки.

Теперь попробуем решить задачку, мы, то раньше ее сделали, ток на классах без конструктора, поэтому щас мне как, то лень втуливать туда конструктор, нет я конечно добавлю пустой конструктор и деструктор, но это мне ничо не даст, вообщем от код с добавлеными пустыми конструкторами и деструкторами:

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
//perepiwite Tnode v vide klacca c konctryktorami, dectryktorami
//dvoichnoe derevo
#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#include <string>
using std::string;
#include <cstring>
using std::strcmp;
using std::strcpy;
 
struct Tnode
{
//konctryktor
Tnode()
{
 
}
 
//dectryktor
~Tnode()
{
 
}
string word;
char* wordC;
int count;
Tnode *left;
Tnode *right;
};
 
//vuvod dereva v C-storkax
void printC(Tnode* ptr);
//vuvod clov iz dereva v alfavitnom por9dke
void printAl(Tnode* ptr,char* mas[], int &count);
//vcpomogatel6na9 function
void printAlHelp(Tnode* ptr,char* mas[],int &count);
//vuvod dereva
void print(Tnode* ptr);
//dobavlenie clov v derevo
void addWord(string &value, Tnode* ptr);
 
int main()
{
Tnode der;
Tnode* ptr=&der;
ptr->word="";
ptr->right=0;
ptr->left=0;
ptr->count=0;
 
string c[4]={"aHellow1","bworld","dgaspada","cHellow"};
 
//dobavlenie novux clov v derevo
cout <<"Vuzov 1"<<endl;
addWord(c[0],ptr);
cout <<"Vuzov 2"<<endl;
addWord(c[1],ptr);
cout <<"Vuzov 3"<<endl;
addWord(c[2],ptr);
cout <<"Vuzov 4"<<endl;
addWord(c[3],ptr);
 
cout <<"Vuvod dereva"<<endl;
print(ptr);
cout <<endl;
cout <<"Vuvod dereva C"<<endl;
printC(ptr);
char* mas[100]={0};
cout <<endl<<"Vuvod dereva v alfavite"<<endl;
int count=0;
//vuvod v otcortirovanom por9dke
printAl(ptr,mas,count);
 
return 0;
}
 
//vuvod dereva v C-strok
void printC(Tnode* ptr)
{
if(ptr->count==1)//cywectvyet element
{
cout <<ptr->wordC<<endl;
}
if(ptr->left!=0)
{
print(ptr->left);
}
if(ptr->right!=0)
{
print(ptr->right);
}
}
 
//vuvod clov iz dereva v alfavitnom por9dke
void printAl(Tnode* ptr,char* mas[], int &count)
{
printAlHelp(ptr,mas,count);
//cortiryem v alfpor9dke
for(int i=0;mas[i]!=0;i++)
{
for(int j=i+1;mas[j]!=0;j++)
{
if(mas[i][0]>mas[j][0])
{
char temp[15]="";
strcpy(temp,*(mas+i));
strcpy(mas[i],mas[j]);
strcpy(mas[j],temp);
}
}
}
//vuvod
for(int i=0;mas[i]!=0;i++)
cout <<"mas["<<i<<"]= "<<mas[i]<<endl;
 
}
//vcpomogatel6na9 function
void printAlHelp(Tnode* ptr,char* mas[],int &count)
{
if(ptr->count==1)//cywectvyet element
{
mas[count]=new char[15];
strcpy(mas[count],ptr->word.data());
cout <<"mas["<<count<<"]= "<<mas[count]<<endl;
count++;
cout <<ptr->word<<endl;
}
if(ptr->right!=0)
{
//count++;
printAlHelp(ptr->right,mas,count);
}
 
if(ptr->left!=0)
{
//count++;
printAlHelp(ptr->left,mas,count);
}
}
 
//vuvod dereva
void print(Tnode* ptr)
{
if(ptr->count==1)//cywectvyet element
{
cout <<ptr->word<<endl;
}
if(ptr->left!=0)
{
print(ptr->left);
}
if(ptr->right!=0)
{
print(ptr->right);
}
}
 
//dobavlenie clov v derevo
void addWord(string &value, Tnode* ptr)
{
if(ptr->count==0)//derevo pycto dobavl9em clovo
{
//cout <<"pycto"<<endl;
ptr->word=value;
ptr->count=1;
//dl9 ctroki v C-ctile (dobavlenie)
ptr->wordC=new char[ptr->word.size()];
strcpy(ptr->wordC,ptr->word.data());
}
else//ne pycto
{
//cout <<"Ne pycto"<<endl;
if(value>ptr->word)
{
//cout <<"bol6we dobavl9em vpravo"<<endl;
if(ptr->right==0)
ptr->right=new Tnode;//cozdaem novui ychactok pam9ti
addWord(value, ptr->right);
}
else
{
//cout <<"men6we dobavl9em vlevo"<<endl;
if(ptr->left==0)
ptr->left=new Tnode;//cozdaem novui ychactok pam9ti
addWord(value, ptr->left);
}
}
}

Ну за конструктор поговорим, как мы его можем применить в данной программе?

Конструктор

-эту функция которая всегда вызывается первой при создании объекта, и что же это нам дает? Да мы можем инициализировать новые классы. Тупо передав им значение через вызов конструктора. Можно но мне впадло делать, поэтому я вам просто примерно подскажу, где, что нужно поменять, чтобы вызов сделать через конструктор, вообщем в addWord() наверно там можно мб как то вызывать конструктор.Но здесь я создал какую, то непонятную стоменять, чтобы вызов сделать через конструктор, вообщем в addWord() наверно там можно мб как то вызывать конструктор.

Но здесь я создал какую, то непонятную структуру, конечно работает она правильно, но запутана. Я создавал через конструкторы но там было два класса, один автореферентный Tnode, а второй управляющий просто допустим Stack, от было так, а сдесь я даже и подумать не могу как же мы всетаки можем использовать конструктор?

1
2
3
4
5
6
                //cout <<"pycto"<<endl;
ptr->word=value;
ptr->count=1;
//dl9 ctroki v C-ctile (dobavlenie)
ptr->wordC=new char[ptr->word.size()];
strcpy(ptr->wordC,ptr->word.data());

тут нужно заменить эти строки создания нового вызовом конструктора объекта, при вызове конструктора долно динамически выделяться память, под новый объект, происходить инициализация объекта, и установка указателей на этот объект из предыдущего узла.

При добавлении в конструкторе выделять динамически память и инициализировать объекта.

Теперь рассмотрим деструктор

Деструктор это функция которая вызывается при уничтожении объекта. То есть относительно дерева, то в нем можно освобождать память. использовать оператор delete и указатель на сам объект.

От как мне кажется должна пойти цепная реакция, от если мы delete например правое поддерево в деструкторе, то и все правое поддерево должно вызвать свои деструкторы и высвободить память. И так цепочка будет, тянуться пока мы не уничтожим все объекты.

Я от например добавил отакой деструктор и норм работает

1
2
3
4
5
6
7
8
//dectryktor
~Tnode()
{
if(left!=0)
delete left;
if(right!=0)
delete right;
}

Ну и все, читайте больше литературу, практика без теории ничто!

 

Конечно мб я там и бред написал ну фиг сним некода проверять, но похоже на правду теория рулез, правда не все практикой подкреплено, поэтому у меня и сомнения есть небольшие 🙂 .

Добавить комментарий Отменить ответ

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Рубрики

  • C++ (293)
  • JavaScript (1)
  • linux (1)
  • MFC (39)
  • node.js (2)
  • React (3)
  • uncategorized (3)
  • vBulletin (5)
  • Visual Studio (9)
  • wordpress (18)
  • Разное (77)

Метки

Ajax bootstrap CentOS CLI expressjs FormData GDlib google Invisible reCAPTCHA JWT media MFC php react-router-dom redux repository wordpress RTTI STL vBulletin vector Visual Studio WINAPI wordpress wp-plugins XMLHttpRequest Двоичное дерево Задачи С++ Игры С++ Исключения С++ О-большое Операторы_С++ Перегрузка операторов С++ Поиск С++ Потоки Проектирование_С++ С++ Типы_С++ Типы С++ Шаблоны С++ библиотеки локализация макросы С++ сортировка С++

Свежие комментарии

  • RA3PKJ к записи visual C++, создание диалоговых окон.
  • JasonReant к записи Создание и использование статических библиотек .lib в visual studio.
  • MyWin2020 к записи Программка для заполнения форума на vBulletin 3.8.7
  • ScottJip к записи Создание и использование статических библиотек .lib в visual studio.
  • ArnoldKig к записи Создание и использование статических библиотек .lib в visual studio.
©2021 Kselax.ru Theme by ThemeGiant