Posted By

MonikaBistrovic on 01/05/11


Tagged


Versions (?)

Strukture podataka zadatak 4


 / Published in: C++
 

  1. // polje.h
  2.  
  3. typedef int cijeli;
  4. typedef int funkcija;
  5. struct pom {
  6. cijeli element;
  7. cijeli iskoristen;
  8. };
  9.  
  10. struct stablo_polje {
  11. pom elementi[10000];
  12. };
  13.  
  14. typedef stablo_polje bs;
  15. typedef int cvor;
  16.  
  17. funkcija ParentB(cvor n,bs *stablo)
  18. {
  19. if (n==1)
  20. {
  21. return -1;
  22. }
  23. else if ((n%2)==0)
  24. {
  25. return n/2;
  26. }
  27. else
  28. {
  29. return (n-1)/2;
  30. }
  31. }
  32.  
  33. funkcija LeftChildB(cvor n,bs *stablo)
  34. {
  35. n=2*n;
  36. if (stablo->elementi[n].iskoristen==0)
  37. {
  38. return -1;
  39. }
  40. else
  41. return n;
  42. }
  43.  
  44. funkcija RightChildB(cvor n,bs *stablo)
  45. {
  46. n=2*n+1;
  47. if (stablo->elementi[n].iskoristen==0)
  48. {
  49. return -1;
  50. }
  51. else
  52. return n;
  53. }
  54.  
  55. cijeli LabelB(cvor n,bs *stablo)
  56. {
  57. return stablo->elementi[n].element;
  58. }
  59.  
  60. void ChangeLabelB(cijeli x,cvor n,bs *stablo)
  61. {
  62. stablo->elementi[n].element=x;
  63. }
  64.  
  65. funkcija RootB(bs stablo)
  66. {
  67. return 1;
  68. }
  69.  
  70. void CreateLeftB(cijeli x,cvor n,bs *stablo)
  71. {
  72. n=n*2;
  73. if (stablo->elementi[n].iskoristen)
  74. {
  75. cout<<"postoji ljevo dijete!!!!";
  76. }
  77. else
  78. {
  79. stablo->elementi[n].element=x;
  80. stablo->elementi[n].iskoristen=1;
  81. }
  82. }
  83.  
  84.  
  85. void CreateRightB(cijeli x,cvor n,bs *stablo)
  86. {
  87. n=n*2+1;
  88. if (stablo->elementi[n].iskoristen)
  89. {
  90. cout<<"postoji desno dijete!!!!";
  91. }
  92. else
  93. {
  94. stablo->elementi[n].element=x;
  95. stablo->elementi[n].iskoristen=1;
  96. }
  97. }
  98.  
  99. void DeleteB(cvor n,bs *stablo)
  100. {
  101. cijeli i=n*2,j=n*2+1;
  102. if (stablo->elementi[i].iskoristen)
  103. DeleteB (i,stablo);
  104. if (stablo->elementi[j].iskoristen)
  105. DeleteB (j,stablo);
  106. stablo->elementi[n].iskoristen=0;
  107. }
  108.  
  109. void InitB(cijeli x,bs *stablo)
  110. {
  111. for (cijeli i=0;i<9999;i++)
  112. stablo->elementi[i].iskoristen=0;
  113. stablo->elementi[1].iskoristen=1;
  114. stablo->elementi[1].element=x;
  115. }
  116.  
  117.  
  118. //main polje
  119.  
  120. #include <iostream>
  121. using namespace std;
  122. #include "polja.h"
  123.  
  124.  
  125. int main()
  126. {
  127. cijeli x,j;
  128. bs stablo;
  129.  
  130. InitB(2,&stablo);
  131.  
  132. //dodavanje startnog lijevog djeteta
  133. cout << "Kreiram lijevo pocetno stablo sa vrijednoscu 22" <<endl;
  134. CreateLeftB(22,1,&stablo);
  135. cout << "Brisem korijen na lokaciji 1" <<endl;
  136. DeleteB(1,&stablo );
  137. //generiranje ostatka stabla brojeva, koristenje ostalih imoplementiranih funkcija
  138. for (int i=1;i<10;i++)
  139. {
  140. x=rand()%100;
  141. j=1;
  142. do
  143. {
  144. if (LabelB(j,&stablo)>=x)
  145. {
  146. if (LeftChildB(j,&stablo)==-1)
  147. {
  148. CreateLeftB(x,j,&stablo);
  149. cout<<"ljevo "<<x;
  150. break;
  151. }
  152. else
  153. {
  154. j=j*2;
  155. cout<<"ljevo ";
  156. }
  157. }
  158. else if(LabelB(j,&stablo)<x)
  159. {
  160. if (RightChildB(j,&stablo)==-1)
  161. {
  162. CreateRightB(x,j,&stablo);
  163. cout<<"desno "<<x;
  164. break;
  165. }
  166. else
  167. {
  168. j=j*2+1;
  169. cout<<"desno ";
  170. }
  171. }
  172. }while(1);
  173. }
  174. int a;
  175. cin >> a;
  176.  
  177. return 0;
  178. }
  179.  
  180.  
  181. // pokazivaci.h
  182.  
  183.  
  184. typedef int cijeli;
  185. struct stablo_pok {
  186. cijeli element;
  187. struct stablo_pok *ljevo,*desno;
  188. };
  189. typedef stablo_pok *funkcija;
  190. typedef stablo_pok *cvor;
  191. typedef stablo_pok bs;
  192.  
  193. funkcija ParentB(cvor n,bs *stablo)
  194. {
  195. static bs *trazeni=n;
  196. bs *i;
  197. if (stablo->ljevo!=NULL)
  198. {
  199. if (stablo->ljevo==n)
  200. return stablo;
  201. else
  202. i=ParentB(trazeni,stablo->ljevo);
  203. }
  204. else
  205. {
  206. if (stablo->desno!=NULL)
  207. {
  208. if (stablo->desno==n)
  209. return stablo;
  210. else
  211. i=ParentB(trazeni,stablo->desno);
  212. }
  213. }
  214. return i;
  215. }
  216.  
  217. funkcija LeftChildB(bs *stablo)
  218. {
  219. return stablo->ljevo;
  220. }
  221.  
  222. funkcija RightChildB(bs *stablo)
  223. {
  224. return stablo->desno;
  225. }
  226.  
  227. cijeli LabelB(bs *stablo)
  228. {
  229. return stablo->element;
  230. }
  231.  
  232. void ChangeLabelB(cijeli x,bs *stablo)
  233. {
  234. stablo->element=x;
  235. }
  236.  
  237. funkcija RootB(bs *stablo)
  238. {
  239. return stablo;
  240. }
  241.  
  242. void CreateLeftB(cijeli x,bs *stablo)
  243. {
  244. if (stablo->ljevo!=NULL)
  245. cout<<"postoji ljevo djete!!";
  246. else
  247. {
  248. bs *novi=new bs;
  249. novi->element=x;
  250. stablo->ljevo=novi;
  251. novi->desno=NULL;
  252. novi->ljevo=NULL;
  253. }
  254. }
  255.  
  256.  
  257. void CreateRightB(cijeli x,bs *stablo)
  258. {
  259. if (stablo->desno!=NULL)
  260. cout<<"postoji desno djete!!";
  261. else
  262. {
  263. bs *novi=new bs;
  264. novi->element=x;
  265. stablo->desno=novi;
  266. novi->desno=NULL;
  267. novi->ljevo=NULL;
  268. }
  269. }
  270.  
  271. void DeleteB(bs *stablo)
  272. {
  273. if (stablo->ljevo!=NULL)
  274. DeleteB(stablo->ljevo);
  275. if (stablo->desno!=NULL)
  276. DeleteB(stablo->desno);
  277. delete stablo;
  278. }
  279.  
  280. void InitB(cijeli x,bs *stablo)
  281. {
  282.  
  283. stablo->element=x;
  284. stablo->ljevo=NULL;
  285. stablo->desno=NULL;
  286. }
  287.  
  288.  
  289. // pokazivaci main
  290.  
  291. #include <iostream>
  292. using namespace std;
  293. #include "pokazivaci.h"
  294.  
  295. int main()
  296. {
  297.  
  298. bs stablo;
  299. cout << "Inicijaliziram korijen" <<endl;
  300. InitB(2,&stablo);
  301.  
  302. CreateLeftB(22,&stablo);
  303. CreateRightB(23,&stablo);
  304. cout << "Lijevi korijen: " << LeftChildB(&stablo)->element <<endl;
  305. cout << "Desni korijen: " << RightChildB(&stablo)->element <<endl;
  306. cout << "Labela korijena: " << LabelB(&stablo) <<endl;
  307. cout << "Brisem korijen" <<endl;
  308. DeleteB(&stablo );
  309. int a;
  310. cin>>a;
  311. return 0;
  312. }

Report this snippet  

You need to login to post a comment.