API tools faq
paste
Advertisement
Guest User

KONECNE SPRAVNE !!!!!!!!!!!!!!!!!!!!!!!!!!!!

a guest
Apr 26th, 2015
270
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 27.22 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4. #include <limits.h>
  5.  
  6. /**
  7. * Struktura Node slouzi k reprezentaci uzlu v B-strome
  8. * atribut keys je ukazatel na pole obsahujici klice daneho uzlu
  9. * atribut children je ukazatel na pole ukazatelu na 'n' potomku
  10. * atribut leaf urcuje, zdali je uzel list
  11. * atribut n je pocet klicu
  12. * */
  13. typedef struct Node {
  14. int *keys;
  15. struct Node **children;
  16. bool leaf;
  17. int n;
  18. } Node;
  19.  
  20. /**
  21. * Struktura BTree slouzi k reprezentaci B-stromu
  22. * atribut arity je pocet maximalnich potomku uzlu
  23. * (stupen stromu je arity/2)
  24. * atribut root je ukazatel na koren stromu
  25. * atribut height je vyska stromu, je potrebna pro vykreslovani
  26. * */
  27. typedef struct BTree {
  28. Node* root;
  29. int arity;
  30. int height;
  31. } BTree;
  32.  
  33. /**
  34. * Nalokuje novy uzel s aritou, a flagom 'leaf',
  35. * ktery znaci jestli je uzel list
  36. * Inicialne vsechny deti jsou NULL
  37. * Inicialne vsechny klice jsou INT_MAX
  38. * Inicialne je pocet klicu 'n' = 0
  39. * */
  40. Node *mallocNode(int arity, bool leaf)
  41. {
  42. Node *node = malloc(sizeof(Node));
  43. node->children = malloc(sizeof(Node*) * arity);
  44. for(int i = 0; i < arity;i++)
  45. node->children[i] = NULL;
  46. node->keys = malloc(sizeof(int) * (arity - 1));
  47. for(int i = 0; i < arity - 1; i++)
  48. node->keys[i]= INT_MAX;
  49. node->leaf = leaf;
  50. node->n = 0;
  51. return node;
  52. }
  53.  
  54. /**
  55. * Vrati pocet klicu v B-strome s korenem 'node'
  56. **/
  57. int keyCount(Node* node)
  58. {
  59. if(node == NULL) return 0;
  60. int sum = 0;
  61. sum += node->n;
  62. for (int j = 0; j < node->n + 1; ++j) {
  63. sum += keyCount(node->children[j]);
  64. }
  65. return sum;
  66. }
  67.  
  68. /**
  69. * Vypise B-strom 'tree' pomoci inorder pruchodu
  70. * Hodnoty vypisujte do pole intu, ktere vratite
  71. * */
  72. int inOrderIntoArray(Node *node,int *array,int pos){
  73. if(node==NULL){return 0;}
  74. int n=node->n,pozice=pos;
  75. for(int i=0;i<n+1;++i){
  76. if(node->leaf==false){
  77. pozice+=inOrderIntoArray(node->children[i],array,pozice);
  78. }
  79. if(i<n){
  80. array[pozice]=node->keys[i];
  81. ++pozice;
  82. }
  83. }
  84. return keyCount(node);
  85. }
  86.  
  87. int *inOrderPrintBTree(BTree *tree)
  88. {
  89. int count = keyCount(tree->root);
  90. int *array = calloc(count,sizeof(int));
  91. //TODO
  92. //printf("pred rekurzi\n");
  93. inOrderIntoArray(tree->root,array,0);
  94. //printf("\npo rekurzi\n");
  95. return array;
  96. }
  97. /**
  98. * Vypise B-strom 'tree' pomoci preorder pruchodu
  99. * Hodnoty vypisujte do pole intu, ktere vratite
  100. * */
  101. int preOrderIntoArray(Node *node,int *array,int pos){
  102. if(node==NULL){return 0;}
  103.  
  104. int n=node->n;
  105. int pozice=pos;
  106. for(int i=0;i<n;i++){
  107. array[pos+i]=node->keys[i];
  108. ++pozice;
  109. //printf("%d %d %d |",pos,pozice,array[pos+i]);
  110. }
  111. for(int i=0;i<n+1;i++){
  112. pozice+=preOrderIntoArray(node->children[i],array,pozice);
  113. }
  114. return pozice-pos;
  115. }
  116.  
  117. int *preOrderPrintBTree(BTree *tree)
  118. {
  119. if(tree->root==NULL){return NULL;}
  120. int count = keyCount(tree->root);
  121. int *array = calloc(count,sizeof(int));
  122.  
  123. //TODO\n
  124. //printf("pred rekurzi\n");
  125. preOrderIntoArray(tree->root,array,0);
  126. //printf("\npo rekurzi\n");
  127. return array;
  128. }
  129.  
  130. /**
  131. * Vypise B-strom 'tree' pomoci postorder pruchodu
  132. * Hodnoty vypisujte do pole intu, ktere vratite
  133. * */
  134. int postOrderIntoArray(Node *node,int *array,int pos,int max){
  135. if(node==NULL){return 0;}
  136. int n=node->n;
  137. int maximum=max,pozice=pos;
  138. for(int i=0;i<n;++i){
  139. array[max-n+i]=node->keys[i];
  140. --maximum;
  141. }
  142. if(node->leaf==false){
  143. for(int i=0;i<n+1;++i){
  144. pozice+=postOrderIntoArray(node->children[i],array,pozice,pozice+keyCount(node->children[i]));
  145. }
  146. }
  147. return keyCount(node);
  148. }
  149.  
  150. int *postOrderPrintBTree(BTree *tree)
  151. {
  152. if(tree->root==NULL){return NULL;}
  153. int count = keyCount(tree->root);
  154. int *array = calloc(count,sizeof(int));
  155.  
  156. //TODO
  157. //printf("pred rekurzi\n");
  158. postOrderIntoArray(tree->root,array,0,count);
  159. //printf("\npo rekurzi\n");
  160. return array;
  161. }
  162.  
  163. /**
  164. * Vyhleda uzel s klicem 'key' v B-strome 'tree'
  165. * Vrati uzel, ve kterem se nachazi klic
  166. * Pokud se klic 'key' v B-strome nenachazi, vraci NULL
  167. * */
  168. Node *searchBTree(BTree *tree, int key)
  169. {
  170. //TODO
  171. int i=0;
  172. Node *aktualni=tree->root;
  173. while(aktualni!=NULL){
  174. //printf("\nVstup do whilu\n");
  175. for(i=0;i < tree->arity-1 && key >= aktualni->keys[i];++i){
  176. //printf("Ve foru check key %d\n",i);
  177. if(aktualni->keys[i]==key){return aktualni;}
  178. }
  179. aktualni=aktualni->children[i];
  180. }
  181. return aktualni;
  182. }
  183.  
  184. /**
  185. * Overi, jestli jsou 2 stromy ekvivalentni
  186. * Pokud ano, vraci true, jinak false
  187. * */
  188.  
  189. bool isEquivBTree(BTree *tree1, BTree *tree2)
  190. {
  191. //TODO
  192. if(keyCount(tree1->root)!=keyCount(tree2->root)){return false;}
  193. if(tree1->arity!=tree2->arity){return false;}
  194. if(tree1->height!=tree2->height){return false;}
  195. int *pole1,*pole2;
  196. int pocet=keyCount(tree1->root);
  197. pole1=preOrderPrintBTree(tree1);
  198. pole2=preOrderPrintBTree(tree2);
  199. for(int i=0;i<pocet;++i){
  200. if(pole1[i]!=pole2[i]){return false;}
  201. }
  202. return true;
  203. }
  204.  
  205. /**
  206. * Vlozi klic 'key' do B-stromu 'tree'
  207. * Operace implementuje preemptivne stepeni
  208. * Muzete predpokladat, ze strom ma sudou aritu
  209. *
  210. * Pro alokaci noveho uzlu pouzijte pripravenou funkci mallocNode
  211. * */
  212. void splitChild(Node *node,int mark,int arity){
  213. //printf("LISTOVNI %d ",node->children[mark]->leaf);
  214. Node *novy=mallocNode(arity,node->children[mark]->leaf);
  215. Node *targ=node->children[mark];
  216. int stredNodu=arity/2 - 1;
  217. novy->n=(arity-2)/2;
  218. //klice do noveho
  219. //printf("MARK1");
  220. for(int i=stredNodu+1;i<arity-1;++i){
  221. novy->keys[i-stredNodu-1]=targ->keys[i];
  222. }
  223. //deti do noveho
  224. //printf("MARK2");
  225. if(targ->leaf!=true){
  226. for(int i=stredNodu+1;i<arity;++i){
  227. novy->children[i-stredNodu-1]=targ->children[i];
  228. }
  229. }
  230. //printf("MARK3 %d ",mark);
  231. //misto pro split v hornim - key
  232. for(int i=node->n-1;i>=mark;--i){
  233. printf(" %d ",i);
  234. node->keys[i+1]=node->keys[i];
  235. }
  236. //printf("MARK4");
  237. //misto pro split v hornim - child
  238. for(int i=node->n;i>=mark;--i){
  239. node->children[i+1]=node->children[i];
  240. }
  241. ++node->n;
  242. node->children[mark+1]=novy;
  243. node->keys[mark]=targ->keys[stredNodu];
  244. targ->n=stredNodu;
  245. novy->n=stredNodu;
  246. }
  247.  
  248. void insertBNode(Node *node,int key,int arity){
  249. //printf("BNODE %d ",node->keys[0]);
  250. int pozice=node->n-1;
  251. if(node->leaf==true){
  252. //printf("LIST ");
  253. for(int i=node->n-1;i>=0&&key<node->keys[i];--i){
  254. node->keys[i+1]=node->keys[i];
  255. --pozice;
  256. }
  257. ++pozice;
  258. node->keys[pozice]=key;
  259. ++node->n;
  260. }else{
  261. //printf("VETEV ");
  262. for(int i=node->n-1;i>=0&&key<node->keys[i];--i){
  263. --pozice;
  264. }
  265. ++pozice;
  266. if(node->children[pozice]->n==arity-1){
  267. //printf("VETEV2 ");
  268. splitChild(node,pozice,arity);
  269. //printf("VETEV3 ");
  270. if(key>node->keys[pozice]){
  271. ++pozice;
  272. }
  273. }
  274.  
  275. insertBNode(node->children[pozice],key,arity);
  276. }
  277. }
  278.  
  279. void insertBTree(BTree *tree, int key)
  280. {
  281. //printf("\nINSERT%d ",key);
  282. Node *koren=tree->root;
  283. if(tree->root==NULL){
  284. Node *novy=mallocNode(tree->arity,true);
  285. novy->n=1;
  286. novy->keys[0]=key;
  287. tree->root=novy;
  288. tree->root->leaf=true;
  289. }else{
  290. //printf("CHECK ");
  291.  
  292. if(tree->root->n==tree->arity-1){
  293. //printf("PLNO ");
  294. Node *novy=mallocNode(tree->arity,false);
  295. novy->children[0]=koren;
  296. tree->root=novy;
  297. splitChild(novy,0,tree->arity);
  298. ++tree->height;
  299. //if(tree->root->children[0]->leaf){printf("DLOUHAVETEV ");}
  300. }
  301. insertBNode(tree->root,key,tree->arity);
  302.  
  303. //TODO
  304. }
  305. //printf("\nNA KONCI\n");
  306. }
  307. /**
  308. * Dodatek k graphvizu:
  309. * Graphviz je nastroj, ktery vam umozni vizualizaci datovych struktur,
  310. * coz se hodi predevsim pro ladeni.
  311. * Tento program generuje nekolik souboru neco.dot v mainu
  312. * Vygenerovane soubory nahrajte do online nastroje pro zobrazeni graphvizu:
  313. * http://sandbox.kidstrythisathome.com/erdos/
  314. * nebo http://graphviz-dev.appspot.com/ - zvlada i vetsi grafy
  315. *
  316. * Alternativne si muzete nainstalovat prekladac z jazyka dot do obrazku na svuj pocitac.
  317. **/
  318. void makeGraphviz(Node* node, int arity, FILE* outputFile, int i) {
  319. if(node == NULL) return;
  320. fprintf(outputFile, "node%i[label = \"", i);
  321. int j = 0;
  322. for (j = 0; j < node->n; ++j) {
  323. fprintf(outputFile, "<f%i> |%i| ", j, node->keys[j]);
  324. }
  325. fprintf(outputFile, "<f%i>\"];\n", j);
  326. for (int j = 0; j < node->n + 1; ++j) {
  327. makeGraphviz(node->children[j], arity, outputFile, (i+1)*arity+j);
  328. }
  329. if(node->leaf) return;
  330. for (int j = 0; j < node->n + 1; ++j) {
  331. fprintf(outputFile, "\"node%i\":f%i -> \"node%i\"\n", i, j, (i+1)*arity+j);
  332. }
  333. }
  334.  
  335. void makeGraph(BTree* tree, const char* filename) {
  336. FILE* outputFile;
  337. outputFile = fopen(filename , "w");
  338. fprintf(outputFile, "digraph BTree {\n");
  339. fprintf(outputFile, "node [shape = record,height=.%i];\n", tree->height-1);
  340. makeGraphviz(tree->root, tree->arity, outputFile, 0);
  341. fprintf(outputFile, "}\n");
  342. fclose(outputFile);
  343. }
  344.  
  345. Node *createNode(int *keys, int nkeys, Node **children, int nchildren, int arity, bool leaf)
  346. {
  347. Node *node = malloc(sizeof(Node));
  348. node->children = malloc(sizeof(Node*) * arity);
  349. for (int i = 0; i < arity; i++)
  350. node->children[i] = (i < nchildren) ? children[i] : NULL;
  351. node->keys = malloc(sizeof(int) * (arity - 1));
  352. for (int i = 0; i < arity - 1; i++)
  353. node->keys[i] = (i < nkeys) ? keys[i] : INT_MAX;
  354. node->leaf = leaf;
  355. node->n = nkeys;
  356. return node;
  357. }
  358.  
  359. void freeNode(Node* node)
  360. {
  361. if (node != NULL) {
  362. for (int j = 0; j < node->n + 1; ++j) {
  363. freeNode(node->children[j]);
  364. }
  365. free(node->children);
  366. free(node->keys);
  367. free(node);
  368. }
  369. }
  370.  
  371. void freeTree(BTree *tree)
  372. {
  373. freeNode(tree->root);
  374. free(tree);
  375. }
  376.  
  377. BTree *testTree1()
  378. {
  379. BTree *tree = malloc(sizeof(BTree));
  380. tree->arity = 6;
  381.  
  382. int n1k[5] = {1, 8, 12, 16, 25};
  383. Node* n1 = createNode(n1k, 5, NULL, 0, tree->arity, true);
  384.  
  385. tree->root = n1;
  386. tree->height = 1;
  387.  
  388. return tree;
  389. }
  390.  
  391. BTree *testTree2()
  392. {
  393. BTree *tree = malloc(sizeof(BTree));
  394. tree->arity = 4;
  395.  
  396. int n12k[2] = {55, 75};
  397. Node* n12 = createNode(n12k, 2, NULL, 0, tree->arity, true);
  398. int n11k[1] = {25};
  399. Node* n11 = createNode(n11k, 1, NULL, 0, tree->arity, true);
  400. int n10k[1] = {17};
  401. Node* n10 = createNode(n10k, 1, NULL, 0, tree->arity, true);
  402. int n9k[2] = {14, 15};
  403. Node* n9 = createNode(n9k, 2, NULL, 0, tree->arity, true);
  404. int n8k[3] = {9, 10, 12};
  405. Node* n8 = createNode(n8k, 3, NULL, 0, tree->arity, true);
  406. int n7k[2] = {6, 7};
  407. Node* n7 = createNode(n7k, 2, NULL, 0, tree->arity, true);
  408. int n6k[1] = {3};
  409. Node* n6 = createNode(n6k, 1, NULL, 0,tree->arity, true);
  410. int n5k[2] = {0,1};
  411. Node* n5 = createNode(n5k, 2, NULL, 0,tree->arity, true);
  412. int n4k[3] = {16, 18, 50}; Node* n4ch[4] = {n9, n10, n11, n12};
  413. Node* n4 = createNode(n4k, 3, n4ch, 4, tree->arity, false);
  414. int n3k[1] = {8}; Node* n3ch[2] = {n7, n8};
  415. Node* n3 = createNode(n3k, 1, n3ch, 2, tree->arity, false);
  416. int n2k[1] = {2}; Node* n2ch[2] = {n5, n6};
  417. Node* n2 = createNode(n2k, 1, n2ch, 2,tree->arity, false);
  418. int n1k[2] = {5, 13}; Node* n1ch[3] = {n2, n3, n4};
  419. Node* n1 = createNode(n1k, 2, n1ch, 3, tree->arity, false);
  420.  
  421. tree->root = n1;
  422. tree->height = 2;
  423.  
  424. return tree;
  425. }
  426.  
  427. BTree *testTree3()
  428. {
  429. BTree *tree = malloc(sizeof(BTree));
  430. tree->arity = 8;
  431.  
  432. int n9k[7] = {66, 67, 68, 69, 70, 73, 79};
  433. Node* n9 = createNode(n9k, 7, NULL, 0, tree->arity, true);
  434. int n8k[7] = {40, 42, 47, 48, 50, 52, 56};
  435. Node* n8 = createNode(n8k, 7, NULL, 0, tree->arity, true);
  436. int n7k[3] = {36, 37, 38};
  437. Node* n7 = createNode(n7k, 3, NULL, 0, tree->arity, true);
  438. int n6k[5] = {29, 31, 32, 33, 34};
  439. Node* n6 = createNode(n6k, 5, NULL, 0,tree->arity, true);
  440. int n5k[3] = {23, 24, 27};
  441. Node* n5 = createNode(n5k, 3, NULL, 0,tree->arity, true);
  442. int n4k[4] = {18, 19, 20, 21};
  443. Node* n4 = createNode(n4k, 4, NULL, 0, tree->arity, true);
  444. int n3k[3] = {13, 15, 16};
  445. Node* n3 = createNode(n3k, 3, NULL, 0, tree->arity, true);
  446. int n2k[3] = {1, 3, 8};
  447. Node* n2 = createNode(n2k, 3, NULL, 0,tree->arity, true);
  448. int n1k[8] = {12, 17, 22, 28, 35, 39, 65}; Node* n1ch[8] = {n2, n3, n4, n5, n6,
  449. n7, n8, n9};
  450. Node* n1 = createNode(n1k, 7, n1ch, 8, tree->arity, false);
  451.  
  452. tree->root = n1;
  453. tree->height = 1;
  454.  
  455. return tree;
  456. }
  457.  
  458. BTree *testTree4()
  459. {
  460. BTree *tree = malloc(sizeof(BTree));
  461. tree->arity = 4;
  462.  
  463. int n12k[2] = {55, 75};
  464. Node* n12 = createNode(n12k, 2, NULL, 0, tree->arity, true);
  465. int n11k[1] = {25};
  466. Node* n11 = createNode(n11k, 1, NULL, 0, tree->arity, true);
  467. int n10k[1] = {17};
  468. Node* n10 = createNode(n10k, 1, NULL, 0, tree->arity, true);
  469. int n9k[2] = {14, 15};
  470. Node* n9 = createNode(n9k, 2, NULL, 0, tree->arity, true);
  471. int n8k[3] = {9, 10, 12};
  472. Node* n8 = createNode(n8k, 3, NULL, 0, tree->arity, true);
  473. int n7k[2] = {5, 7};
  474. Node* n7 = createNode(n7k, 2, NULL, 0, tree->arity, true);
  475. int n6k[1] = {3};
  476. Node* n6 = createNode(n6k, 1, NULL, 0,tree->arity, true);
  477. int n5k[2] = {0,1};
  478. Node* n5 = createNode(n5k, 2, NULL, 0,tree->arity, true);
  479. int n4k[3] = {16, 19, 50}; Node* n4ch[4] = {n9, n10, n11, n12};
  480. Node* n4 = createNode(n4k, 3, n4ch, 4, tree->arity, false);
  481. int n3k[1] = {8}; Node* n3ch[2] = {n7, n8};
  482. Node* n3 = createNode(n3k, 1, n3ch, 2, tree->arity, false);
  483. int n2k[1] = {2}; Node* n2ch[2] = {n5, n6};
  484. Node* n2 = createNode(n2k, 1, n2ch, 2,tree->arity, false);
  485. int n1k[2] = {5, 13}; Node* n1ch[3] = {n2, n3, n4};
  486. Node* n1 = createNode(n1k, 2, n1ch, 3, tree->arity, false);
  487.  
  488. tree->root = n1;
  489. tree->height = 2;
  490.  
  491. return tree;
  492. }
  493.  
  494. bool compareKeys(int* a1, int* a2, int n)
  495. {
  496. if (a2 == NULL || a1 == NULL)
  497. return a1 == a2;
  498. for(int i = 0; i < n; i++)
  499. if (a1[i] != a2[i]) return false;
  500. return true;
  501. }
  502.  
  503. void testInOrderPrint()
  504. {
  505. printf("###########################\n");
  506. printf("Test 1. in_order_print: ");
  507.  
  508. int res1[5] = {1, 8, 12, 16, 25};
  509. int res2[21] = {0,1,2,3,5,6,7,8,9,10,12,13,14,15,16,17,18,25,50,55,75};
  510. int res3[42] = {1, 3, 8, 12, 13, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 27,
  511. 28, 29, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 42, 47, 48,
  512. 50, 52, 56, 65, 66, 67, 68, 69, 70, 73, 79};
  513.  
  514. BTree *tree = testTree1();
  515.  
  516. int* res = inOrderPrintBTree(tree);
  517.  
  518. if (!compareKeys(res1, res, 5)) {
  519. printf("NOK\n");
  520. printf("vysledek:\t ");
  521. if (res != NULL) {
  522. for(int i = 0; i < 5; i++) printf("%d ",res[i]); putchar('\n');
  523. }else{
  524. printf("[]\n");
  525. }
  526. printf("ocekavany vysledek:");
  527. for(int i = 0; i < 5; i++) printf("%d ",res1[i]); putchar('\n');
  528. } else {
  529. free(res);
  530. freeTree(tree);
  531. tree = testTree2();
  532. res = inOrderPrintBTree(tree);
  533. if (!compareKeys(res2, res, 21)){
  534. printf("NOK\n");
  535. printf("vysledek:\t ");
  536. if (res != NULL) {
  537. for(int i = 0; i < 21; i++) printf("%d ",res[i]); putchar('\n');
  538. }else{
  539. printf("[]\n");
  540. }
  541. printf("ocekavany vysledek:");
  542. for(int i = 0; i < 21; i++) printf("%d ",res2[i]); putchar('\n');
  543. }else{
  544. free(res);
  545. freeTree(tree);
  546. tree = testTree3();
  547. res = inOrderPrintBTree(tree);
  548. if (!compareKeys(res3, res, 42)){
  549. printf("NOK\n");
  550. printf("vysledek:\t ");
  551. if (res != NULL) {
  552. for(int i = 0; i < 42; i++) printf("%d ",res[i]); putchar('\n');
  553. }else{
  554. printf("[]\n");
  555. }
  556. printf("ocekavany vysledek:");
  557. for(int i = 0; i < 42; i++) printf("%d ",res3[i]); putchar('\n');
  558. }else{
  559. printf("OK\n");
  560. }
  561. }
  562. }
  563.  
  564. makeGraph(tree, "in_order_print.dot");
  565. printf("Vykresleny B-strom najdete v souboru in_order_print.dot\n");
  566. free(res);
  567. freeTree(tree);
  568. }
  569.  
  570. void testPreOrderPrint()
  571. {
  572. printf("###########################\n");
  573. printf("Test 2. pre_order_print: ");
  574.  
  575. int res1[5] = {1, 8, 12, 16, 25};
  576. int res2[21] = {5, 13, 2, 0, 1, 3, 8, 6, 7, 9, 10, 12, 16, 18, 50, 14, 15,
  577. 17, 25, 55, 75};
  578. int res3[42] = {12, 17, 22, 28, 35, 39, 65, 1, 3, 8, 13, 15, 16, 18, 19, 20,
  579. 21, 23, 24, 27, 29, 31, 32, 33, 34, 36, 37, 38, 40, 42, 47,
  580. 48, 50, 52, 56, 66, 67, 68, 69, 70, 73, 79};
  581.  
  582. BTree *tree = testTree1();
  583.  
  584. int* res = preOrderPrintBTree(tree);
  585.  
  586. if (!compareKeys(res1, res, 5)) {
  587. printf("NOK\n");
  588. printf("vysledek:\t ");
  589. if (res != NULL) {
  590. for(int i = 0; i < 5; i++) printf("%d ",res[i]); putchar('\n');
  591. }else{
  592. printf("[]\n");
  593. }
  594. printf("ocekavany vysledek:");
  595. for(int i = 0; i < 5; i++) printf("%d ",res1[i]); putchar('\n');
  596. } else {
  597. free(res);
  598. freeTree(tree);
  599. tree = testTree2();
  600. res = preOrderPrintBTree(tree);
  601. if (!compareKeys(res2, res, 21)){
  602. printf("NOK\n");
  603. printf("vysledek:\t ");
  604. if (res != NULL) {
  605. for(int i = 0; i < 21; i++) printf("%d ",res[i]); putchar('\n');
  606. }else{
  607. printf("[]\n");
  608. }
  609. printf("ocekavany vysledek:");
  610. for(int i = 0; i < 21; i++) printf("%d ",res2[i]); putchar('\n');
  611. }else{
  612. free(res);
  613. freeTree(tree);
  614. tree = testTree3();
  615. res = preOrderPrintBTree(tree);
  616. if (!compareKeys(res3, res, 42)){
  617. printf("NOK\n");
  618. printf("vysledek:\t ");
  619. if (res != NULL) {
  620. for(int i = 0; i < 42; i++) printf("%d ",res[i]); putchar('\n');
  621. }else{
  622. printf("[]\n");
  623. }
  624. printf("ocekavany vysledek:");
  625. for(int i = 0; i < 42; i++) printf("%d ",res3[i]); putchar('\n');
  626. }else{
  627. printf("OK\n");
  628. }
  629. }
  630. }
  631.  
  632. makeGraph(tree, "pre_order_print.dot");
  633. printf("Vykresleny B-strom najdete v souboru pre_order_print.dot\n");
  634. free(res);
  635. freeTree(tree);
  636. }
  637.  
  638. void testPostOrderPrint()
  639. {
  640. printf("###########################\n");
  641. printf("Test 3. post_order_print: ");
  642.  
  643. int res1[5] = {1, 8, 12, 16, 25};
  644. int res2[21] = {0, 1, 3, 2, 6, 7, 9, 10, 12, 8, 14, 15, 17, 25, 55, 75, 16,
  645. 18, 50, 5, 13};
  646. int res3[42] = {1, 3, 8, 13, 15, 16, 18, 19, 20, 21, 23, 24, 27, 29, 31, 32,
  647. 33, 34, 36, 37, 38, 40, 42, 47, 48, 50, 52, 56, 66, 67, 68,
  648. 69, 70, 73, 79, 12, 17, 22, 28, 35, 39, 65};
  649.  
  650. BTree *tree = testTree1();
  651.  
  652. int* res = postOrderPrintBTree(tree);
  653.  
  654. if (!compareKeys(res1, res, 5)) {
  655. printf("NOK\n");
  656. printf("vysledek:\t ");
  657. if (res != NULL) {
  658. for(int i = 0; i < 5; i++) printf("%d ",res[i]); putchar('\n');
  659. }else{
  660. printf("[]\n");
  661. }
  662. printf("ocekavany vysledek:");
  663. for(int i = 0; i < 5; i++) printf("%d ",res1[i]); putchar('\n');
  664. } else {
  665. free(res);
  666. freeTree(tree);
  667. tree = testTree2();
  668. res = postOrderPrintBTree(tree);
  669. if (!compareKeys(res2, res, 21)){
  670. printf("NOK\n");
  671. printf("vysledek:\t ");
  672. if (res != NULL) {
  673. for(int i = 0; i < 21; i++) printf("%d ",res[i]); putchar('\n');
  674. }else{
  675. printf("[]\n");
  676. }
  677. printf("ocekavany vysledek:");
  678. for(int i = 0; i < 21; i++) printf("%d ",res2[i]); putchar('\n');
  679. }else{
  680. free(res);
  681. freeTree(tree);
  682. tree = testTree3();
  683. res = postOrderPrintBTree(tree);
  684. if (!compareKeys(res3, res, 42)){
  685. printf("NOK\n");
  686. printf("vysledek:\t ");
  687. if (res != NULL) {
  688. for(int i = 0; i < 42; i++) printf("%d ",res[i]); putchar('\n');
  689. }else{
  690. printf("[]\n");
  691. }
  692. printf("ocekavany vysledek:");
  693. for(int i = 0; i < 42; i++) printf("%d ",res3[i]); putchar('\n');
  694. }else{
  695. printf("OK\n");
  696. }
  697. }
  698. }
  699.  
  700. makeGraph(tree, "post_order_print.dot");
  701. printf("Vykresleny B-strom najdete v souboru post_order_print.dot\n");
  702. free(res);
  703. freeTree(tree);
  704. }
  705.  
  706. bool inKeys(int k, Node *node)
  707. {
  708. int i = 0;
  709. while (i < node->n) {
  710. if (k == node->keys[i]) return true;
  711. i++;
  712. }
  713. return false;
  714. }
  715.  
  716. void testSearch()
  717. {
  718. printf("###########################\n");
  719. printf("Test 4. search: ");
  720. BTree *tree = testTree1();
  721. Node *node = searchBTree(tree, 16);
  722. if ((node == NULL) || (!inKeys(16, node))) {
  723. printf("NOK - chybne hledani klice 16, ktery je v koreni B-stromu\n");
  724. }else{
  725. node = searchBTree(tree, 24);
  726. if (node != NULL){
  727. printf("NOK - chybne hledani klice, ktery se v B-strome nenachazi\n");
  728. }else{
  729. freeTree(tree);
  730. tree = testTree2();
  731. node = searchBTree(tree, 15);
  732. if ((node == NULL) || (!inKeys(15, node))){
  733. printf("NOK - chybne hledani klice 15, ktery je v listu\n");
  734. }else{
  735. node = searchBTree(tree, 50);
  736. if ((node == NULL) || (!inKeys(50, node))){
  737. printf("NOK - chybne hledani klice 50, ktery je ve vnitrnim uzlu\n");
  738. }else{
  739. node = searchBTree(tree, 19);
  740. if (node != NULL){
  741. printf("NOK - chybne hledani klice, ktery se v B-strome nenachazi\n");
  742. }else{
  743. printf("OK\n") ;
  744. }
  745. }
  746. }
  747. }
  748. }
  749. makeGraph(tree, "search.dot");
  750. printf("Vykresleny B-strom najdete v souboru search.dot\n");
  751. freeTree(tree);
  752. }
  753.  
  754. void testIsEquiv()
  755. {
  756. printf("###########################\n");
  757. printf("Test 5. is_equiv: ");
  758. BTree *t1 = testTree1();
  759. BTree *t2 = testTree2();
  760. if (isEquivBTree(t1, t2)){
  761. printf("NOK - B-stromy nejsou ekvivalentni, nemaji shodnou aritu\n");
  762. }else{
  763. freeTree(t1); freeTree(t2);
  764. t1 = testTree2();
  765. t2 = testTree4();
  766. if (isEquivBTree(t1, t2)){
  767. printf("NOK - B-stromy nejsou ekvivalentni, nemaji shodne hodnoty\n");
  768. }else{
  769. freeTree(t1);
  770. t1 = testTree2();
  771. if (isEquivBTree(t1, t1)){
  772. printf("OK\n");
  773. }else{
  774. printf("NOK - B-stromy jsou ekvivalentni\n");
  775. }
  776. }
  777. }
  778. freeTree(t1); freeTree(t2);
  779. }
  780.  
  781. void testInsert()
  782. {
  783. printf("###########################\n");
  784. printf("Test 6. insert: ");
  785. BTree *tree = malloc(sizeof(BTree));
  786. tree->root = NULL;
  787. tree->arity = 4;
  788. tree->height = 0;
  789.  
  790. insertBTree(tree, 1);
  791. int a1[1] = {1};
  792. if ((tree->root == NULL) || (!compareKeys(tree->root->keys,a1, 1))){
  793. printf("NOK - vkladani do prazdneho B-stromu stupne 2\n");
  794. }else{
  795. insertBTree(tree, 7);
  796. insertBTree(tree, 2);
  797. int a2[3] = {1,2,7};
  798. if((tree->root == NULL) || (!compareKeys(tree->root->keys,a2, 3))){
  799. printf("NOK - vkladani do B-stromu bez stepeni\n");
  800. }else{
  801. int a3_1[1] = {2}; int a3_2[1] = {1}; int a3_3[2] = {5, 7};
  802. insertBTree(tree,5);
  803. if(tree->root == NULL ||
  804. (!compareKeys(tree->root->keys,a3_1, 1)) ||
  805. (!compareKeys(tree->root->children[0]->keys,a3_2, 1)) ||
  806. (!compareKeys(tree->root->children[1]->keys,a3_3, 2))){
  807. printf("NOK - vkladani se stepenim korene\n");
  808. }else{
  809. insertBTree(tree, 12);
  810. insertBTree(tree, 8);
  811. int a4_1[2] = {2,7}; int a4_2[1] = {1}; int a4_3[1] = {5}; int a4_4[2] = {8, 12};
  812. if(tree->root == NULL ||
  813. (!compareKeys(tree->root->keys,a4_1, 2)) ||
  814. (!compareKeys(tree->root->children[0]->keys,a4_2, 1)) ||
  815. (!compareKeys(tree->root->children[1]->keys,a4_3, 1)) ||
  816. (!compareKeys(tree->root->children[2]->keys,a4_4, 2))){
  817. printf("NOK - vkladani se stepenim listu\n");
  818. }else{
  819. insertBTree(tree, 4);
  820. insertBTree(tree, 3);
  821. insertBTree(tree, 6);
  822. int a5_1[3] = {2,4,7}; int a5_2[1] = {3}; int a5_3[2] = {5, 6}; int a5_4[2] = {8, 12};
  823. if(tree->root == NULL ||
  824. (!compareKeys(tree->root->keys,a5_1, 3)) ||
  825. (!compareKeys(tree->root->children[1]->keys,a5_2, 1)) ||
  826. (!compareKeys(tree->root->children[2]->keys,a5_3, 2)) ||
  827. (!compareKeys(tree->root->children[3]->keys,a5_4, 2))){
  828. printf("NOK - vkladani se stepenim listu\n");
  829. }else{
  830. insertBTree(tree, 11);
  831. int a6_1[1] = {4}; int a6_2[1] = {2}; int a6_3[1] = {7}; int a6_4[2] = {5, 6}; int a6_5[3] = {8, 11, 12};
  832. if(tree->root == NULL ||
  833. (!compareKeys(tree->root->keys,a6_1, 1)) ||
  834. (!compareKeys(tree->root->children[0]->keys,a6_2, 1)) ||
  835. (!compareKeys(tree->root->children[1]->keys,a6_3, 1)) ||
  836. (!compareKeys(tree->root->children[1]->children[0]->keys,a6_4, 2)) ||
  837. (!compareKeys(tree->root->children[1]->children[1]->keys,a6_5, 3))){
  838. printf("NOK - vkladani se stepenim korene\n");
  839. }else{
  840. printf("OK\n");
  841. }
  842. }
  843. }
  844. }
  845. }
  846. }
  847. makeGraph(tree, "insert.dot");
  848. printf("Vykresleny B-strom najdete v souboru insert.dot\n");
  849. freeTree(tree);
  850. }
  851.  
  852. int main()
  853. {
  854. testInOrderPrint();//OK
  855. testPreOrderPrint();//OK
  856. testPostOrderPrint();//OK
  857. testSearch();//OK
  858. testIsEquiv();//OK
  859. testInsert();
  860. printf("###########################\n");
  861. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!