daily pastebin goal
14%
SHARE
TWEET

Untitled

a guest Dec 7th, 2017 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //SDIZO I1 212A LAB03
  2. //Szymon Lisiecki
  3. //ls39343@zut.edu.pl
  4.  
  5. #include <iostream>
  6. #include <ctime>
  7. #include <fstream>
  8.  
  9. using namespace std;
  10.  
  11. // Węzeł drzewa
  12. struct Wezel{
  13.     int klucz;
  14.     char tab[11];                              // do konwersji z inta na chara: zrobić coś w stylu, że  korzeń->tab[11] = konwersja, funkcja konwersji
  15.     Wezel *leweDziecko, *praweDziecko;
  16. };
  17.  
  18. // drzewo
  19. struct Drzewo {
  20.     Wezel *korzen;
  21. };
  22.  
  23. static int licznikInOrder;
  24. static int licznikPreOrder;
  25. static int licznikPostOrder;
  26.  
  27. // inicjalizacja drzewa
  28. void Zeruj(Drzewo *choinka) {
  29.  
  30.     choinka->korzen = NULL;
  31.  
  32. }
  33.  
  34. // usuwa element o wartosci klucza
  35. Wezel* Usun(Drzewo *choinka, int klucz) {
  36.     if (choinka->korzen == NULL)    return NULL;
  37.  
  38.     Wezel *aktualny, *cel, *poprzedni;
  39.  
  40.     aktualny = choinka->korzen;
  41.     cel = NULL;
  42.     poprzedni = NULL;
  43.  
  44.     while (1) {
  45.         if (aktualny->klucz == klucz)
  46.             cel = aktualny;
  47.  
  48.         if (klucz < aktualny->klucz) {
  49.             if (aktualny->leweDziecko == NULL)
  50.                 break;
  51.             poprzedni = aktualny;
  52.             aktualny = aktualny->leweDziecko;
  53.         }
  54.         else {
  55.             if (aktualny->praweDziecko == NULL)
  56.                 break;
  57.             poprzedni = aktualny;
  58.             aktualny = aktualny->praweDziecko;
  59.         }  
  60.     }
  61.  
  62.     if (cel == NULL)
  63.         return false;
  64.     else {
  65.         if (poprzedni == NULL) {
  66.             delete aktualny;
  67.             choinka->korzen = NULL;
  68.         }
  69.         else {
  70.             // Łączenie wskaznikami
  71.             // aktualny wezel wskazuje na zmieniony
  72.             cel->klucz = aktualny->klucz;
  73.             if (poprzedni->leweDziecko == aktualny)
  74.  
  75.                 if (aktualny->praweDziecko != NULL && aktualny->praweDziecko->praweDziecko == NULL && aktualny->praweDziecko->leweDziecko)
  76.                     poprzedni->leweDziecko = aktualny->praweDziecko;
  77.                 else
  78.                     poprzedni->leweDziecko = aktualny->leweDziecko;
  79.  
  80.             else
  81.                 if (aktualny->leweDziecko != NULL && aktualny->leweDziecko->praweDziecko == NULL && aktualny->leweDziecko->leweDziecko)
  82.                     poprzedni->praweDziecko = aktualny->leweDziecko;
  83.                 else
  84.                     poprzedni->praweDziecko = aktualny->praweDziecko;
  85.  
  86.  
  87.             delete aktualny;
  88.         }
  89.     }
  90.    
  91. }
  92.  
  93.  
  94. // lewo -> korzen -> prawo
  95. void Wyswietl_InOrder(Wezel *choinka) {
  96.     if (choinka == NULL) return;
  97.  
  98.     licznikInOrder++;
  99.  
  100.     Wyswietl_InOrder(choinka->leweDziecko);
  101.     cout << choinka->klucz << endl;
  102.     Wyswietl_InOrder(choinka->praweDziecko);
  103.  
  104. }
  105.  
  106. // korzen -> lewo -> prawo
  107. void Wyswietl_PreOrder(Wezel *choinka) {
  108.     if (choinka == NULL) return;
  109.     licznikPreOrder++;
  110.  
  111.     cout << choinka->klucz << endl;
  112.     Wyswietl_PreOrder(choinka->leweDziecko);
  113.     Wyswietl_PreOrder(choinka->praweDziecko);
  114.  
  115. }
  116. // lewo -> prawo -> korzen
  117. //void Wyswietl_PostOrder(Wezel *choinka) {
  118. //  if (choinka == NULL) return;
  119. //  licznikPostOrder++;
  120. //
  121. //  Wyswietl_PostOrder(choinka->leweDziecko);
  122. //  Wyswietl_PostOrder(choinka->praweDziecko);
  123. //  cout << choinka->klucz << endl;
  124. //}
  125.  
  126.  
  127. bool Szukaj(Drzewo *choinka, int klucz) {
  128.     if (choinka->korzen == NULL) return false;
  129.  
  130.     Wezel* pomocniczy = choinka->korzen;
  131.     Wezel* rodzic = nullptr;
  132.  
  133.     while (pomocniczy != NULL && pomocniczy->klucz != klucz) {
  134.         //rodzic jest aktualnym
  135.         rodzic = pomocniczy;
  136.  
  137.         //jak klucz jest mniejszy od pomocniczego to idz do lewego dziecka, else..
  138.         if (klucz < pomocniczy->klucz)
  139.             pomocniczy = pomocniczy->leweDziecko;
  140.         else
  141.             pomocniczy = pomocniczy->praweDziecko;
  142.     }
  143.  
  144.     if (pomocniczy == NULL)
  145.     {
  146.         //cout << "Nie znaleziono wezla o podanym kluczu." << endl;
  147.         return false;
  148.     }
  149.    
  150.     //cout << "Znaleziono wezel o podanym kluczu" << endl;
  151.     return true;
  152.  
  153. }
  154. // znajduje wezel o zadanej wartosci klucza
  155.  
  156. bool Wstaw_PoKluczu(Drzewo *choinka, int klucz) {
  157.     Wezel *pomocniczy, *rodzic;
  158.  
  159.     if (Szukaj(choinka, klucz)==true) return false; // jeżeli znajdzie klucz to zwraca false
  160.    
  161.     Wezel *aktualnyWezel = new Wezel();
  162.     aktualnyWezel->klucz = klucz;
  163.  
  164.     char aktualnaTablica[11]; //deklaracja chara
  165.     sprintf_s(aktualnaTablica, "%d", klucz);  //konwersja z int na char
  166.     aktualnyWezel->tab[11] = aktualnaTablica[11]; //nadanie charowi wyrazenia z inta
  167.    
  168.    
  169.  
  170.     if (choinka->korzen == NULL) {
  171.         choinka->korzen = aktualnyWezel; // jeżeli było puste to teraz ma korzeń
  172.         aktualnyWezel->leweDziecko = NULL;
  173.         aktualnyWezel->praweDziecko = NULL;
  174.         pomocniczy = choinka->korzen;
  175.     } else {
  176.         pomocniczy = choinka->korzen;
  177.         while (pomocniczy != NULL)
  178.         {
  179.             if (pomocniczy->klucz > klucz)
  180.             {
  181.                 rodzic = pomocniczy;
  182.                 pomocniczy = pomocniczy->leweDziecko;
  183.             }
  184.             else {
  185.                 rodzic = pomocniczy;
  186.                 pomocniczy = pomocniczy->praweDziecko;
  187.             }
  188.         }
  189.         aktualnyWezel->klucz = klucz;
  190.         aktualnyWezel->leweDziecko = NULL;
  191.         aktualnyWezel->praweDziecko = NULL;
  192.  
  193.         if (rodzic->klucz > klucz)
  194.             rodzic->leweDziecko = aktualnyWezel;
  195.         else
  196.             rodzic->praweDziecko = aktualnyWezel;
  197.     }
  198.  
  199.     return true;
  200. }
  201.  
  202. // losowanie klucza i wstawianie do funkcji Wstaw_
  203. void WstawLosowo(Drzewo *choinka, int iloscWezlow) {
  204.     srand(time(NULL));
  205.  
  206.     while (iloscWezlow-- > 0) {
  207.         int klucz = (rand() % 20000) - 10000;
  208.  
  209.         Wstaw_PoKluczu(choinka, klucz);
  210.     }
  211.  
  212. }
  213.  
  214.  
  215. int main() {
  216.     clock_t czasPoczatkowy = clock();
  217.     ifstream plik("inlab03.txt");
  218.     if (plik.fail()) return -1;
  219.  
  220.     int x, k1, k2, k3, k4;
  221.  
  222.     plik >> x >> k1 >> k2 >> k3 >> k4;
  223.  
  224.     cout << "Liczba elementow do wylosowania: " << x << endl;
  225.     cout << "Wartosc klucza k1: " << k1 << endl;
  226.     cout << "Wartosc klucza k2: " << k2 << endl;
  227.     cout << "Wartosc klucza k3: " << k3 << endl;
  228.     cout << "Wartosc klucza k4: " << k4 << endl;
  229.     cout << endl;
  230.  
  231.    
  232.     Drzewo choinka;
  233.     Zeruj(&choinka);   //drzewo puste
  234.    
  235.     Usun(&choinka, k1);
  236.    
  237.     Wstaw_PoKluczu(&choinka, k1);
  238.  
  239.     WstawLosowo(&choinka, x);
  240.    
  241.     cout << "Wyswietlanie in-order: " << endl;
  242.     Wyswietl_InOrder(choinka.korzen);
  243.     cout << "Liczba odwiedzonych wezlow: ";
  244.     cout << licznikInOrder << endl;
  245.     licznikInOrder = 0;
  246.  
  247.     cout << "Wyswietlanie pre-order: " << endl;
  248.     Wyswietl_PreOrder(choinka.korzen);
  249.     cout << "Liczba odwiedzonych wezlow: ";
  250.     cout << licznikPreOrder << endl;
  251.     licznikPreOrder = 0;
  252.  
  253.     Wstaw_PoKluczu(&choinka, k2);
  254.  
  255.     cout << "Wyswietlanie in-order: " << endl;
  256.     Wyswietl_InOrder(choinka.korzen);
  257.     cout << "Liczba odwiedzonych wezlow: ";
  258.     cout << licznikInOrder << endl;
  259.     licznikInOrder = 0;
  260.  
  261.     Wstaw_PoKluczu(&choinka, k3);
  262.     Wstaw_PoKluczu(&choinka, k4);
  263.     Usun(&choinka, k1);
  264.  
  265.     cout << "Wyswietlanie pre-order: " << endl;
  266.     Wyswietl_PreOrder(choinka.korzen);
  267.     cout << "Liczba odwiedzonych wezlow: ";
  268.     cout << licznikPreOrder << endl;
  269.     licznikPreOrder = 0;
  270.  
  271.     Szukaj(&choinka, k1);
  272.  
  273.     Usun(&choinka, k2);
  274.    
  275.     cout << "Wyswietlanie in-order: " << endl;
  276.     Wyswietl_InOrder(choinka.korzen);
  277.     cout << "Liczba odwiedzonych wezlow: ";
  278.     cout << licznikInOrder << endl;
  279.     licznikInOrder = 0;
  280.  
  281.     Usun(&choinka, k3);
  282.     Usun(&choinka, k4);
  283.  
  284.     /*cout << "Wyswietlanie post-order: " << endl;
  285.     Wyswietl_PostOrder(choinka.korzen);
  286.     cout << "Liczba odwiedzonych wezlow: ";
  287.     cout << licznikPostOrder << endl;*/
  288.  
  289.     clock_t czasKoncowy = clock();
  290.     double roznicaCzasow = (double)(czasKoncowy - czasPoczatkowy) / CLOCKS_PER_SEC;
  291.     cout << "program wykonywal sie w " << roznicaCzasow << " sekund" << endl;
  292.  
  293.     getchar();
  294.     getchar();
  295.     return 0;
  296. }
RAW Paste Data
Top