Posted By

ivan_uzarevic on 01/19/15


Tagged

data array tree structures next programming child first Algorithms Parent sibling Strukture podataka c++ Prvo dijete brat roditelj informatics sljedei algoritmi


Versions (?)

opcenito_stablo


 / Published in: C++
 

Program za izvođenje općenitog stabla (prvo dijete - sljedeći brat) za 4. zadatak iz kolegija Strukture podataka

  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <ctime>
  4. #include <conio.h>
  5. using namespace std;
  6.  
  7. struct elem {
  8. int labela;
  9. int firstchild, nextsibling;
  10. };
  11.  
  12. struct tstablo {
  13. elem elements[1000];
  14. int first;
  15. };
  16. tstablo *stablo = new tstablo;
  17. int broj_cvorova = 0;
  18.  
  19. int parentT (int n, tstablo *stablo) {
  20. if (stablo->first == n)
  21. return -1;
  22. for (int i = 0; i < 1000; i++) {
  23. if (stablo->elements[i].firstchild == n)
  24. return i;
  25. if(stablo->elements[i].nextsibling == n)
  26. return parentT(i,stablo);
  27. }
  28. return -2;
  29. }
  30.  
  31. int firstchildT(int n, tstablo *stablo) {
  32. if (stablo->elements[n].firstchild == -1)
  33. return -1;
  34. return stablo->elements[n].firstchild;
  35. }
  36.  
  37. int nextsiblingT(int n, tstablo *stablo) {
  38. if (stablo->elements[n].nextsibling == -1)
  39. return -1;
  40. return stablo->elements[n].nextsibling;
  41. }
  42.  
  43. int labelT (int n, tstablo *stablo) {
  44. if (parentT(n, stablo) != -2)
  45. return stablo->elements[n].labela;
  46. }
  47.  
  48. int rootT (tstablo *stablo) {
  49. return stablo->first;
  50. }
  51.  
  52. int createT (int x, int n, tstablo *stablo) {
  53. if (parentT(n, stablo) == -2) {
  54. cout << "Ne postoji cvor u stablu na toj poziciji" << endl;
  55. return -1;
  56. }
  57. if (stablo->elements[n].firstchild == -1) {
  58. stablo->elements[n].firstchild = x;
  59. stablo->elements[x].firstchild = -1;
  60. stablo->elements[x].nextsibling = -1;
  61. stablo->elements[x].labela = rand() % 100 + 1;
  62. return 1;
  63. }
  64.  
  65. int tekuci;
  66. int brat;
  67. brat = stablo->elements[n].firstchild;
  68. while (brat != -1) {
  69. tekuci = brat;
  70. brat = stablo->elements[tekuci].nextsibling;
  71. }
  72. stablo->elements[tekuci].nextsibling = x;
  73. stablo->elements[x].firstchild = -1;
  74. stablo->elements[x].nextsibling = -1;
  75. stablo->elements[x].labela = rand() % 100 + 1;
  76. return 1;
  77. }
  78.  
  79. void changelabelT (int x, int n, tstablo *stablo) {
  80. if (parentT(n, stablo) != -2)
  81. stablo->elements[n].labela = x;
  82. }
  83.  
  84. int deleteT (int n, tstablo *stablo) {
  85. int roditelj, brat, dijete;
  86. roditelj = parentT(n, stablo);
  87. brat = stablo->elements[roditelj].firstchild;
  88. if (parentT(n, stablo) == -2) {
  89. return -1;
  90. }
  91. while (stablo->elements[n].firstchild != -1) {
  92. dijete = stablo->elements[n].firstchild;
  93. deleteT (dijete, stablo);
  94. }
  95. if (n == brat)
  96. stablo->elements[parentT(n,stablo)].firstchild =stablo->elements[n].nextsibling;
  97. else if (stablo->elements[n].nextsibling != -1)
  98. stablo->elements[brat].nextsibling = stablo->elements[n].nextsibling;
  99. stablo->elements[n].labela = 0;
  100. broj_cvorova--;
  101. return 1;
  102. }
  103.  
  104.  
  105. void initT (int x, tstablo *stablo) {
  106. int oznaka;
  107. for (int i = 0; i < 1000; i++) {
  108. stablo->elements[i].firstchild = -1;
  109. stablo->elements[i].nextsibling = -1;
  110. stablo->elements[i].labela = 0;
  111. }
  112. stablo->first = x;
  113. cout << "Unesite labelu(oznaku) korijena: ";
  114. cin >> oznaka;
  115. stablo->elements[x].labela = oznaka;
  116. }
  117.  
  118. void ispis(tstablo *stablo) {
  119. for(int i = 0; i < 1000; i++) {
  120. if (stablo->elements[i].labela != 0)
  121. cout << i << " ::::: " << stablo->elements[i].labela << " ::::: "
  122. << stablo->elements[i].firstchild << " ::::: "
  123. << stablo->elements[i].nextsibling << endl;
  124. }
  125. cout << endl << endl;
  126. }
  127.  
  128. int main() {
  129. srand(time(0));
  130. int pozicija;
  131. initT(0, stablo);
  132. broj_cvorova++;
  133. ispis(stablo);
  134. cout << "KREIRANJE STABLA OD 10 ELEMANTA" << endl;
  135. getch();
  136. for (int i = 1; i <= 9;) {
  137. broj_cvorova++;
  138. system("cls");
  139. cout << i << ". pozicija u polju: " << endl;
  140. cout << "Unesite poziciju cvora gdje ce se kreirati dijete cvora: ";
  141. cin >> pozicija;
  142. if(createT(i,pozicija,stablo) == -1) {
  143. --i;
  144. broj_cvorova--;
  145. }
  146. ispis(stablo);
  147. i++;
  148. getch();
  149. }
  150. system("cls");
  151. ispis(stablo);
  152.  
  153. int izbor;
  154. int cvor;
  155. int vrijednost;
  156. do {
  157. cout << "ENTER ZA NASTAVAK" << endl;
  158. getch();
  159. system("cls");
  160. cout << "IZBORNIK" << endl;
  161. cout << "1. Roditelj cvora" << endl;
  162. cout << "2. Prvo dijete cvora" << endl;
  163. cout << "3. Sljedeci brat cvora" << endl;
  164. cout << "4. Labela (oznaka) cvora" << endl;
  165. cout << "5. Korijen stabla" << endl;
  166. cout << "6. Kreiranje cvora" << endl;
  167. cout << "7. Promjena labele cvora" << endl;
  168. cout << "8. Brisanje cvora sa svim potomcima" << endl;
  169. cout << "9. Izlaz iz programa" << endl;
  170. cout << "Unesite mogucnost: ";
  171. cin >> izbor;
  172. cout << endl << endl;
  173. switch(izbor) {
  174. case 1:
  175. ispis(stablo);
  176. cout << "Unesite poziciju cvora: ";
  177. cin >> cvor;
  178. cout << "Roditelj cvora: " << parentT(cvor,stablo) << endl;;
  179. break;
  180. case 2:
  181. ispis(stablo);
  182. cout << "Unesite poziciju cvora: ";
  183. cin >> cvor;
  184. cout << "Prvo dijete cvora: " << firstchildT(cvor,stablo) << endl;
  185. break;
  186. case 3:
  187. ispis(stablo);
  188. cout << "Unesite poziciju cvora: ";
  189. cin >> cvor;
  190. cout << "Sljedeci brat cvora: " << nextsiblingT(cvor,stablo) << endl;
  191. break;
  192. case 4:
  193. ispis(stablo);
  194. cout << "Unesite poziciju cvora: ";
  195. cin >> cvor;
  196. cout << "Labela cvora: " << labelT(cvor,stablo) << endl;
  197. break;
  198. case 5:
  199. ispis(stablo);
  200. cout << "Korijen stabla: " << rootT(stablo) << endl;
  201. break;
  202. case 6:
  203. cout << "Unesite poziciju cvora gdje ce se kreirati dijete cvora: ";
  204. cin >> cvor;
  205. if(createT(broj_cvorova++,cvor,stablo) == -1)
  206. broj_cvorova--;
  207. ispis(stablo);
  208. break;
  209. case 7:
  210. ispis(stablo);
  211. cout << "Unesite poziciju cvora gdje zelite promijeniti labelu: ";
  212. cin >> cvor;
  213. cout << "Unesite oznaku(labelu) zamjene: ";
  214. cin >> vrijednost;
  215. changelabelT(vrijednost,cvor,stablo);
  216. system("cls");
  217. ispis(stablo);
  218. break;
  219. case 8:
  220. ispis(stablo);
  221. cout << "Unesite poziciju cvora kojeg zelite obrisati ";
  222. cin >> cvor;
  223. if(deleteT(cvor,stablo) == -1)
  224. cout << "Ne postoji cvor sa tom pozicijom za brisanje" << endl;
  225. cout << "Broj cvorova(sa korijenom): " << broj_cvorova << endl;
  226. getch();
  227. system("cls");
  228. ispis(stablo);
  229. break;
  230.  
  231. }
  232. } while(izbor != 9);
  233.  
  234.  
  235. return 0;
  236. }

Report this snippet  

You need to login to post a comment.