Перепишите 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; } |
Ну и все, читайте больше литературу, практика без теории ничто!
Конечно мб я там и бред написал ну фиг сним некода проверять, но похоже на правду теория рулез, правда не все практикой подкреплено, поэтому у меня и сомнения есть небольшие 🙂 .