Posted By

stjepanmusa on 01/24/12


Tagged

Strukture podataka


Versions (?)

Zadatak_4_strukture


 / Published in: C++
 

Zadatak 4

  1. //implementacija_b_pokazivaci
  2.  
  3. struct element{
  4. int label;
  5. struct element *left,*right;
  6. };
  7. typedef struct element *node;
  8. typedef struct element *tr;
  9.  
  10. void InitB(int x,tr *T){
  11. T = new tr;
  12. T.label = x;
  13. T->left = NULL;
  14. T->right = NULL;
  15.  
  16. }
  17. node RootB(tr *T){
  18. return T;
  19. }
  20.  
  21. node LeftChildB(node n,tr *T){
  22. return n->left;
  23. }
  24. node RightChildB(node n,tr *T){
  25. return n->right;
  26. }
  27. int LabelB(node n,tr *T){
  28. return n->label;
  29. }
  30. int CreateLeftB(int x,node n,tr *T){
  31. if(!n->left){
  32. element *novi = new element;
  33. n->left = novi;
  34. novi->left = NULL;
  35. novi->right = NULL;
  36. novi->label = x;
  37. return 1;
  38. }
  39. else return 0;
  40. }
  41. int CreateRightB(int x,node n,tr *T){
  42. if(!n->right){
  43. element *novi = new element;
  44. n->right = novi;
  45. novi->left = NULL;
  46. novi->right = NULL;
  47. novi->label = x;
  48. return 1;
  49. }
  50. else return 0;
  51. }
  52. node ParentB(node n,tr *T){
  53. node cvor = NULL;
  54. if(n == T) return 0;
  55. if(T->left){
  56. if(T->left == n){
  57. cvor = T;
  58. return cvor;
  59. }
  60. cvor = ParentB(n,T->left);
  61. }
  62. if(!cvor)
  63. if(T->right){
  64. if(T->right == n){
  65. cvor = T;
  66. return cvor;
  67. }
  68. cvor = ParentB(n,T->right);
  69. }
  70. return cvor;
  71. }
  72. void DeleteB(node n,tr *T){
  73. if(n->left) DeleteB(n->left,T);
  74. if(n->right) DeleteB(n->right,T);
  75. node cvor = ParentB(n,T);
  76. if(cvor!=0){
  77. if(cvor->left == n) cvor->left = NULL;
  78. else cvor->right=NULL;
  79. delete n;
  80. }
  81. }
  82. void ChangeLabelB(int x,node n,tr *T){
  83. n->label = x;
  84. }
  85. //implementacija_b_polje
  86.  
  87. struct elem{
  88. int label;
  89. bool used;
  90. };
  91. struct tr{
  92. struct elem element[10000];
  93. };
  94. typedef struct tr *T;
  95. typedef int node;
  96.  
  97. int ParentB(int n, tr *T){
  98. if (n=1) return -1;
  99. if (n%2==0)return n/2;
  100. else return n/2-1;
  101. }
  102.  
  103. int LeftChildB(int n, tr *T){
  104. if(!T->element[n].used) return -1;
  105. else return n*2;
  106. }
  107. int RightChildB(int n, tr *T){
  108. if(!T->element[n].used) return -1;
  109. else return n*2+1;
  110. }
  111.  
  112. int LabelB(int n, tr *T){
  113. if(T->element[n].used)return T->element[n].label;
  114. else return -1;
  115. }
  116.  
  117. void ChangeLabelB(int x,int n, tr *T){
  118. if(T->element[n].used)T->element[n].label=x;
  119. }
  120.  
  121. int RootB(tr *T){
  122. if(T->element[1].used) return 1;
  123. else return -1;
  124. }
  125.  
  126. int CreateLeftB(int x,int n, tr *T){
  127. if(T->element[n*2].used) return -1;
  128. T->element[n*2].used=true;
  129. T->element[n*2].label=x;
  130. }
  131. int CreateRightB(int x,int n, tr *T){
  132. if(T->element[n*2+1].used) return -1;
  133. T->element[n*2+1].used=true;
  134. T->element[n*2+1].label=x;
  135. }
  136.  
  137. void DeleteB(int n, tr *T){
  138. if(LeftChildB(n,T)!=-1)DeleteB(LeftChildB(n,T),T);
  139. if(RightChildB(n,T)!=-1)DeleteB(RightChildB(n,T),T);
  140. T->element[n].used = 0;
  141. }
  142.  
  143. void InitB(int x,tr *T){
  144. for(int i=0;i<10000;i++) T->element[i].used=false;
  145. T->element[1].label=x;
  146. T->element[1].used=true;
  147. }
  148. //implementacija obilezenje
  149.  
  150. using namespace std;
  151.  
  152. void Preorder(int i, tr *T) {
  153. int c;
  154. cout<<T->element[i].label<<", ";
  155. c = T->element[i].firstchild;
  156. while (c!=-1) {
  157. Preorder(c,T);
  158. c = T->element[c].nextsibling;
  159. }
  160. }
  161.  
  162. void Postorder(int i, tr *T) {
  163. int c;
  164.  
  165. c = T->element[i].firstchild;
  166. while (c!=-1) {
  167. Postorder(c,T);
  168. c = T->element[c].nextsibling;
  169. }
  170. cout<<T->element[i].label<<", ";
  171. }
  172.  
  173. void Inorder(int i, tr *T) {
  174. int c;
  175. c = T->element[i].firstchild;
  176. while (c!=-1) {
  177. Inorder(c,T);
  178. cout<<T->element[i].label<<", ";
  179. c = T->element[c].nextsibling;
  180. }
  181.  
  182. }
  183. //implementacija opcenito stabla
  184.  
  185. using namespace std;
  186. struct el{
  187. int label,firstchild,nextsibling;
  188. };
  189.  
  190. struct tr{
  191. el element[1000];
  192. int first;
  193. };
  194.  
  195. tr *InitT(int x,tr *T){
  196. T=new tr;
  197. T->first=0;
  198. T->element[0].label=x;
  199. T->element[0].firstchild=-1;
  200. T->element[0].nextsibling=-1;
  201. T->first++;
  202. return T;
  203. }
  204.  
  205. int FirstChildT(int x, tr *T){
  206. return T->element[x].firstchild;
  207. }
  208.  
  209. int NextSiblingT(int x, tr *T){
  210. return T->element[x].nextsibling;
  211. }
  212.  
  213. int ParentT(int x, tr *T){
  214. if(x==T->first) return -1;
  215. for(int i=0;i<T->first;i++){
  216. if(T->element[i].firstchild==x) return i;
  217. if(T->element[T->element[i].firstchild].nextsibling==x) return i;
  218. }
  219. }
  220.  
  221. int LabelT(int x, tr *T){
  222. return T->element[x].label;
  223.  
  224. }
  225.  
  226. int ChangeLabelT(int x, int y, tr *T){
  227. if(x<0) return -1;
  228. else T->element[y].label=x;
  229. }
  230.  
  231. int RootT(tr *T){
  232. return 0;
  233. }
  234.  
  235.  
  236. void CreateT(int x,int n,tr *T){
  237. if(T->element[n].firstchild==-1){
  238. T->element[T->first].label=x;
  239. T->element[n].firstchild=T->first;
  240. T->element[T->first].nextsibling=-1;
  241. T->element[T->first++].firstchild=-1;
  242. }
  243. else{
  244. T->element[T->first].label=x;
  245. T->element[T->first].firstchild=-1;
  246. T->element[T->first].nextsibling=T->element[T->element[n].firstchild].nextsibling;
  247. T->element[T->element[n].firstchild].nextsibling=T->first++;
  248. }
  249. }
  250. int DeleteT(int x, tr *T){
  251. if(x<0) return -1;
  252. else{
  253. if(T->element[x].firstchild>0) DeleteT(T->element[x].firstchild,T);
  254. else{
  255. T->element[x].label=-1;
  256. T->first--;
  257. }
  258. }
  259. }
  260. //main
  261.  
  262. #include<iostream>
  263. using namespace std;
  264.  
  265. #include "implementacija_b_pokazivaci.h"
  266. #include "implementacija_opcenito_stablo.h"
  267. #include "implementacija_obilazenje.h"
  268. #include "implementacija_b_polje.h"
  269. void prvi(){
  270. tr *T;
  271. int vrijednost;
  272. cout<<"Korijen je 1"<<endl;
  273. T=InitT(1,T);
  274.  
  275. cout<<"Unesi (cvor 1, dijete 0): ";cin>>vrijednost;
  276. CreateT(vrijednost,0,T);
  277. cout<<"Unesi (cvor 2, dijete 0): ";cin>>vrijednost;
  278. CreateT(vrijednost,0,T);
  279. cout<<"Unesi (cvor 3, dijete 1): ";cin>>vrijednost;
  280. CreateT(vrijednost,1,T);
  281. cout<<"Unesi (cvor 3,dijete 1): ";cin>>vrijednost;
  282. CreateT(vrijednost,1,T);
  283.  
  284. for(int i=0;i<T->first;i++){
  285. cout<<i<<" : "<<LabelT(i,T)<<" "<<FirstChildT(i,T)<<" "<<NextSiblingT(i,T)<<endl;
  286. }
  287.  
  288. cout<<"Preorder: ";
  289. Preorder(0,T);
  290. cout<<"\nPostorder: ";Postorder(0,T);
  291. cout<<"\nInorder: ";Inorder(0,T);
  292. cout<<endl;
  293.  
  294. cout<<"Unesite novu vrijednost treceg cvora: ";cin>>vrijednost;
  295. ChangeLabelT(vrijednost,3,T);
  296.  
  297. cout<<"Brisanje cvora 2"<<endl;
  298. DeleteT(2,T);
  299.  
  300. for(int i=0;i<T->first;i++){
  301. cout<<i<<" : "<<LabelT(i,T)<<" "<<FirstChildT(i,T)<<" "<<NextSiblingT(i,T)<<endl;
  302. }
  303. cout<<"Dealokacija stabla..."<<endl<<endl;
  304. DeleteT(0,T);
  305. }
  306.  
  307. void drugi(){
  308. int x;
  309. cout << "Inicijalizacija stabla" << endl;
  310. tr *T=InitB(1,T);
  311. cout << "Korijen: " << LabelB(RootB(T), T)<< endl << endl;
  312.  
  313. cout << "Lijevo dijete: ";cin>>x;
  314. CreateLeftB(x, RootB(T), T);
  315. cout << "Desno dijete";cin>>x;
  316. CreateRightB(x, RootB(T), T);
  317. cout << "Lijevo dijete od 1: ";cin>>x;
  318. CreateLeftB(x, RootB(T), T);
  319. cout << "Desno dijete od 1";cin>>x;
  320. CreateRightB(x, RootB(T), T);
  321.  
  322. cout << "Mijenjanje cvora 2: "; cin>>x;
  323. ChangeLabelB(x, LeftChildB(RightChildB(RootB(T), T), T), T);
  324.  
  325.  
  326. cout << "Brisanje cvora 0" << endl;
  327. DeleteB(RootB(T), T);
  328.  
  329. }
  330.  
  331. int main() {
  332. int izbor;
  333. do{
  334.  
  335. cout<<"1. Opcenito stablo i algoritmi prohodjenja\n"
  336. <<"2. binarno stablo\n\n"
  337. <<"9. Izlaz iz programa\n";
  338.  
  339. cin >> izbor;
  340.  
  341. if(izbor == 1) prvi();
  342. else drugi();
  343. }while(izbor != 0);
  344.  
  345. return 0;
  346. }

Report this snippet  

You need to login to post a comment.