API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Aug 27th, 2015
62
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 14.38 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <conio.h>
  4. #include <windows.h>
  5. #include <time.h>
  6.  
  7. int tab[1000];
  8. int wysokosc = 5;
  9. int szerokosc = 20;
  10.  
  11. typedef struct LEAF
  12. {
  13. float value;
  14. struct LEAF *parent;
  15. struct LEAF *left;
  16. struct LEAF *right;
  17. }leaf;
  18.  
  19. void gotoxy(int x, int y);
  20. void add(leaf **root, float wartosc);
  21. void nextadd(leaf **root, leaf *parent, float wartosc);
  22. int treedelete (leaf **root);
  23. void console1(leaf **root);
  24. void console2(leaf **root);
  25. void test();
  26. void autoadd(leaf **root, int ilosc);
  27. leaf* maxvalue (leaf *root);
  28. leaf* minvalue (leaf *root);
  29. leaf* searchvalue (leaf *root, float wartosc);
  30. void deletenode(leaf *node, int value);
  31.  
  32. /***********************************************************************************************/
  33.  
  34. int main() {
  35. int usun;
  36. leaf *root = NULL;
  37. srand( time( NULL ) );
  38.  
  39. console1(&root);
  40.  
  41. if (root != NULL)
  42. {usun = treedelete(&root);
  43.  
  44. if (usun == 0) printf("Drzewo bylo puste");
  45. else if (usun == 1) printf ("Drzewo zostalo usuniete");
  46. getch();
  47.  
  48.  
  49. };
  50. return 0;
  51. }
  52. /***********************************************************************************************/
  53.  
  54.  
  55. void gotoxy(int x, int y)
  56. {
  57. COORD coord;
  58. coord.X = x;
  59. coord.Y = y;
  60. SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord);
  61. };
  62.  
  63. void add(leaf **root, float wartosc)
  64. {
  65.  
  66. if( *root == NULL )
  67. {
  68. *root = (leaf*) malloc( sizeof(leaf) );
  69. (*root)->value = wartosc;
  70. /* inicjalizacja rodzica */
  71. (*root)->parent = NULL;
  72. /* inicjalizacja dzieci */
  73. (*root)->left = NULL;
  74. (*root)->right = NULL;
  75. }
  76. else if(wartosc < (*root)->value)
  77. {
  78. nextadd(&(*root)->left, NULL, wartosc);
  79. }
  80. else if(wartosc > (*root)->value)
  81. {
  82. nextadd(&(*root)->right, NULL, wartosc);
  83. }
  84. }
  85.  
  86.  
  87. void nextadd (leaf **root, leaf *parent, float wartosc)
  88. {
  89.  
  90. if (*root == NULL )
  91. {
  92. *root = (leaf*) malloc( sizeof(leaf) );
  93. (*root)->value = wartosc;
  94. /* inicjalizacja rodzica */
  95. (*root)->parent = parent;
  96. /* inicjalizacja dzieci */
  97. (*root)->left = NULL;
  98. (*root)->right = NULL;
  99. }
  100. else if(wartosc < (*root)->value)
  101. {
  102. nextadd(&(*root)->left, *root, wartosc);
  103. }
  104. else if(wartosc > (*root)->value)
  105. {
  106. nextadd(&(*root)->right, *root, wartosc);
  107. }
  108. }
  109.  
  110.  
  111. int treedelete (leaf **root){
  112. int usun;
  113.  
  114. if (*root == NULL) usun = 0;
  115. else if( *root != NULL )
  116. {
  117. treedelete(&(*root)->left);
  118. treedelete(&(*root)->right);
  119. free(*root);
  120. *root = NULL;
  121. usun = 1;
  122. };
  123.  
  124. return usun;
  125. }
  126.  
  127.  
  128. void autoadd(leaf **root, int ilosc)
  129. {
  130. int i, value;
  131.  
  132. for (i=0;i<ilosc;i++)
  133. {
  134. value = rand() % 100000;
  135. value = value << 16;
  136. value = value | (rand() % 100000);
  137. add(root,value);
  138. }
  139. }
  140.  
  141.  
  142. leaf * maxvalue (leaf *root)
  143. { leaf *pom = root;
  144.  
  145. if (pom != NULL)
  146. {
  147. while (pom->right != NULL) pom = pom->right;
  148.  
  149. // printf("Maksymalna wartoscia jest: \t%f\n",pom->value);
  150. return pom;
  151. }
  152. else printf("Drzewo jest puste");
  153. return NULL;
  154. }
  155.  
  156.  
  157. leaf* minvalue (leaf *root)
  158. { leaf *pom = root;
  159. if (pom != NULL)
  160. {
  161.  
  162. while (pom->left != NULL) pom = pom->left;
  163. return pom;
  164. // printf("Minimalna wartoscia jest: \t%f\n",pom->value);
  165. }
  166. else printf("Drzewo jest puste");
  167. return NULL;
  168. }
  169.  
  170. leaf* searchvalue (leaf *root, float wartosc)
  171. {
  172. while (root != NULL)
  173. {
  174. if (root->value == wartosc) return root;
  175. else if (root->value > wartosc) root = root -> left;
  176. else if (root->value < wartosc) root = root -> right;
  177. }
  178. return NULL;
  179. }
  180.  
  181. int draw (leaf *root)
  182. {
  183. if (root == NULL) return 0;
  184. else
  185. {
  186. printf("(");
  187. draw(root->left);
  188. printf("%f",root->value);
  189. //
  190. draw(root->right);
  191. printf(")");
  192. return 1;
  193. }
  194. }
  195.  
  196. void delete_node(leaf *node, int value)
  197. {
  198. leaf *current = NULL, *del_node = NULL, *child = NULL;
  199. leaf *parent = NULL, *x = NULL;
  200. current = node;
  201.  
  202. while (current != NULL) {
  203. if (value == current->value) {
  204. del_node = current;
  205. //case 1: node is a leaf (no descendants)
  206. if ((del_node->left == NULL) && (del_node->right == NULL)) {
  207. //if the node to delete is to the left of root
  208. if (parent->left == del_node) {
  209. parent->left = NULL;
  210. free(del_node);
  211. printf("Element usunieto");
  212. break;
  213.  
  214. }
  215. //if the node to delete is to the right of root
  216. else if (parent->right == del_node) {
  217. parent->right = NULL;
  218. free(del_node);
  219. printf("Element usunieto");
  220. break;
  221. }
  222. }
  223. //case 2: node has one child
  224. else if ((del_node->left == NULL) || (del_node->right == NULL)) {
  225.  
  226. //if the node to delete is to the left of root
  227. if (parent->left == del_node) {
  228. if (del_node->left != NULL) {
  229. child = del_node->left;
  230. parent->left = child;
  231. free(del_node);
  232. break;
  233. }
  234. else if (del_node->right != NULL) {
  235. child = del_node->right;
  236. parent->left = child;
  237. free(del_node);
  238. break;
  239. }
  240. }
  241. //if the node to delete is to the right of root
  242. else if (parent->right == del_node) {
  243. if (del_node->left != NULL) {
  244. child = del_node->left;
  245. parent->right = child;
  246. free(del_node);
  247. break;
  248. }
  249. else if (del_node->right != NULL) {
  250. child = del_node->right;
  251. parent->right = child;
  252. free(del_node);
  253. break;
  254. }
  255. }
  256. }
  257. //case 3: node has two children
  258. else if ((del_node->left != NULL) && (del_node->right != NULL)) {
  259. x = del_node;
  260. //if the node to delete is root
  261. if (parent == NULL) {
  262. child = del_node->right;
  263. if (child->left == NULL) {
  264. child->left = del_node->left;
  265. free(del_node);
  266. break;
  267. }
  268. else {
  269. while (child->left != NULL) {
  270. parent = child;
  271. child = parent->left;
  272. }
  273. x->value = child->value;
  274. parent->left = child->right;
  275. del_node = child;
  276. free(del_node);
  277. break;
  278. }
  279. }
  280. //if the node to delete is to the left of root
  281. else if (parent->left == del_node) {
  282. child = del_node->right;
  283. if (child->left == NULL) {
  284. parent->left = child;
  285. child->left = del_node->left;
  286. free(del_node);
  287. break;
  288. }
  289. else {
  290. while (child->left != NULL) {
  291. parent = child;
  292. child = parent->left;
  293. }
  294. x->value = child->value;
  295. parent->left = child->right;
  296. del_node = child;
  297. free(del_node);
  298. break;
  299. }
  300. }
  301. //if the node to delete is to the right of root
  302. else if (parent->right == del_node) {
  303. child = del_node->right;
  304. if (child->left == NULL) {
  305. parent->right = child;
  306. child->left = del_node->left;
  307. free(del_node);
  308. break;
  309. }
  310. else {
  311. while (child->left != NULL) {
  312. parent = child;
  313. child = parent->left;
  314. }
  315. x->value = child->value;
  316. parent->left = child->right;
  317. del_node = child;
  318. free(del_node);
  319. break;
  320. }
  321. }
  322. }
  323. }
  324. //if value is less than the node's value - go left
  325. else if (value < current->value) {
  326. parent = current;
  327. current = current->left;
  328. }
  329. //if value is greater than the node's value - go right
  330. else {
  331. parent = current;
  332. current = current->right;
  333. }
  334. }
  335. }
  336. //void deletenode(leaf **root)
  337. //{
  338. //float wartosc;
  339. //
  340. // leaf *szukaj = *root;
  341. // leaf *pom, *min;
  342. //
  343. // getch();
  344. // system("cls");
  345. // printf("%s\t","Podaj wartosc elementu do usuniecia:");scanf("%f",&wartosc);
  346. // szukaj = searchvalue(*root, wartosc);
  347. // if (szukaj == NULL)
  348. // ("Wartosc nie wystepuje w drzewie \n");
  349. // else if (szukaj != NULL)
  350. // {
  351. // if ((szukaj->left == NULL) && (szukaj->right == NULL))
  352. // {
  353. // /*Brak dzieci*/
  354. // szukaj->parent = NULL;
  355. // free(szukaj);
  356. // szukaj = NULL;
  357. // }
  358. // else if ((&(szukaj)->left == NULL) || (&(szukaj)->right == NULL))
  359. // {
  360. //
  361. // /*Jedno dziecko*/
  362. // if (&(szukaj)->left == NULL)
  363. // {
  364. // pom = szukaj;
  365. // szukaj = szukaj-> right;
  366. // pom->right = NULL;
  367. // pom->parent = NULL;
  368. // free(pom);
  369. // pom = NULL;
  370. // }
  371. // else if (&(szukaj)->right == NULL)
  372. // {
  373. // pom = szukaj;
  374. // szukaj = szukaj-> left;
  375. // pom->left = NULL;
  376. // pom->parent = NULL;
  377. // free(pom);
  378. // pom = NULL;
  379. // };
  380. // }
  381. // else if ((&(szukaj)->left != NULL) && (&(szukaj)->right != NULL))
  382. // { /*Dwoje dzieci*/
  383. //
  384. // min = minvalue(szukaj->right);
  385. // szukaj->value = min->value;
  386. // deletenode(min);
  387. //
  388. // }
  389. // };
  390. //}
  391.  
  392. void console1(leaf **root){
  393. int a, wyjscie;
  394.  
  395. wyjscie = 0;
  396. while (wyjscie == 0)
  397. {
  398. system("cls");
  399. gotoxy(szerokosc,wysokosc);printf("Lukasz Kozien\n");
  400. gotoxy(szerokosc,wysokosc+1);printf("Drzewo binarne\n\n");
  401. gotoxy(szerokosc-4,wysokosc+2);printf("1 -- Samodzielne wypelnienie drzewa\n");
  402. gotoxy(szerokosc-4,wysokosc+3);printf("2 -- Testowanie\n");
  403. gotoxy(szerokosc-4,wysokosc+4);printf("0 -- Wyjscie\n");
  404.  
  405. gotoxy(1,wysokosc+6);printf("%s\n","Wcisnij odpowiedni klawisz");a = getch();
  406. //gotoxy(1,wysokosc+8);printf("%i\n",a);
  407. switch(a){
  408. case '1':
  409. system("cls");
  410. console2(root);
  411. break;
  412. case '2':
  413. system("cls");
  414. test();
  415. break;
  416. case '0':
  417. //exit(EXIT_SUCCESS);
  418. wyjscie+=1;
  419. break;
  420. // default:
  421. // console1(root);
  422. // break;
  423. };
  424. };
  425. };
  426.  
  427. void console2(leaf **root){
  428. int a, powrot, usun;
  429. float wartosc;
  430. leaf *pom, *szukaj;
  431.  
  432. powrot = 0;
  433. while (powrot == 0)
  434. {
  435. system("cls");
  436. gotoxy(szerokosc-4,wysokosc-1);printf("1 -- Dodanie elementu do drzewa\n");
  437. gotoxy(szerokosc-4,wysokosc);printf("2 -- Wyszukanie elementu w drzewie\n");
  438. gotoxy(szerokosc-4,wysokosc+1);printf("3 -- Wyszukiwanie maksimum\n");
  439. gotoxy(szerokosc-4,wysokosc+2);printf("4 -- Wyszukiwanie minimum\n");
  440. gotoxy(szerokosc-4,wysokosc+3);printf("5 -- Rysowanie drzewa\n");
  441. gotoxy(szerokosc-4,wysokosc+4);printf("6 -- Usuniecie elementu drzewa\n");
  442. gotoxy(szerokosc-4,wysokosc+5);printf("7 -- Usuniecie calego drzewa\n");
  443. gotoxy(szerokosc-4,wysokosc+6);printf("0 -- Powrot");
  444.  
  445. gotoxy(1,wysokosc+8);printf("%s\n","Wcisnij odpowiedni klawisz"); a = getch();
  446. //gotoxy(1,wysokosc+8);printf("%i\n",a);
  447.  
  448. switch(a){
  449. case '1':
  450. {printf("Dodawanie elementu\n");
  451. getch();//system("PAUSE");
  452. system("cls");
  453. printf("Podaj wartosc:\t");scanf("%f",&wartosc);
  454. add(root, wartosc);
  455. // if ((*root)->parent != NULL);
  456. // {
  457. // printf("%f\n Wartosc rodzica to", (*root)->(*parent)->value);
  458. // }
  459.  
  460. //console2(root);
  461. }
  462. break;
  463. case '2':
  464. {printf("Wyszukuje\n");
  465. getch();
  466. system("cls");
  467. printf("%s\t","Podaj wartosc:");scanf("%f",&wartosc);
  468. szukaj = searchvalue(*root, wartosc);
  469. if (szukaj != NULL) printf("Wartosc %f wystepuje w drzewie \n",wartosc);
  470. else if (szukaj == NULL) printf("Wartosc %f nie wystepuje w drzewie \n",wartosc);
  471. getch();
  472. //system("PAUSE");
  473. //console2(root);
  474. }
  475. break;
  476. case '3':
  477. {printf("Maksimum\n");
  478. pom = maxvalue(*root);
  479. printf("Maksymalna wartoscia jest: \t%f\n",pom->value);
  480. getch();//system("PAUSE");
  481. //console2(root);
  482. }
  483. break;
  484. case '4':
  485. {printf("Minimum\n");
  486. pom = minvalue(*root);
  487. printf("Minimalna wartoscia jest: \t%f\n",pom->value);
  488. getch();//system("PAUSE");
  489. //console2(root);
  490. }
  491. case '5':
  492. {printf("Rysuje drzewo \n");
  493. draw(*root);
  494. getch();//system("PAUSE");
  495. //console2(root);
  496. }
  497. break;
  498. case '6':
  499. {printf("Usuwam \n");
  500. getch();
  501. system("cls");
  502. printf("%s\t","Podaj wartosc elementu do usuniecia:");scanf("%f",&wartosc);
  503. delete_node(*root, wartosc);
  504. //system("PAUSE");
  505. //console2(root);
  506. }
  507. break;
  508. case '7':
  509. {printf("Usuniecie calego drzewa\n");
  510. getch();//system("PAUSE");
  511. usun = treedelete(root);
  512. if (usun == 0) printf("Drzewo bylo puste\nn");
  513. else if (usun == 1) printf ("Drzewo zostalo usuniete\n");
  514. getch();// console2(root);
  515. }
  516. break;
  517. case '0':
  518. powrot+=1;
  519. break;
  520. // default:
  521. // console2(root);
  522. // break;
  523. };
  524. };
  525. };
  526.  
  527. void test()
  528. { int i, j, value;
  529. int n[] = {1000, 2000, 5000, 10000, 20000, 50000, 100000, 200000, 500000, 1000000, 2000000, 5000000, 10000000, 0};
  530. int *np;
  531. FILE *f;
  532. LARGE_INTEGER frequency, t1, t2;
  533. double elapsedTimeSec;
  534.  
  535. leaf *root = NULL;
  536.  
  537. srand (time(NULL));
  538.  
  539. f = fopen("Raport.txt","w");
  540. fprintf(f,"Raport wyszukiwan drzewa binarnego\n");
  541.  
  542. for (np = n; *np; np++) {
  543. treedelete(&root);
  544. for (i=*np;i>0;i--)
  545. {
  546. value = ((int)(rand() % 256) << 24) + ((int)(rand() % 256) << 16) + ((int)(rand() % 256) << 8) + (int)(rand() % 256);
  547. add(&root,value);
  548. if (i < 1000) {
  549. tab[i] = value;
  550. }
  551. }
  552.  
  553. QueryPerformanceFrequency(&frequency);
  554. QueryPerformanceCounter(&t1);
  555. {
  556. for (j=0;j<1000;j++)
  557. searchvalue(root,tab[j]);
  558. }
  559. QueryPerformanceCounter(&t2);
  560.  
  561. elapsedTimeSec = (double)(t2.QuadPart - t1.QuadPart) / frequency.QuadPart ;
  562.  
  563. printf("%i\t %f\t %f\t %f\t %f\n",*np,elapsedTimeSec, t2.QuadPart, t1.QuadPart, frequency.QuadPart);
  564. fprintf(f,"Wyszukiwanie 1000 elementow w %i elementowym drzewie wynioslo %f \n", *np,elapsedTimeSec );
  565. }
  566. fclose(f);
  567. getch();
  568. }
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!