Facebook
From krul, 6 Years ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 213
  1. // 1 zadanko to podzielić na 50 list według wartości: 1-10 do nr 1 11-20 do nr 2 itp, potem posortować, i scalić
  2. // 2 podzielić na 50 list, wyjąć element najbliższy średniej z danej listy, i dać go do nowej listy, potem z tej listy nowej zrobić drzewo i usunąć z niego liście
  3. #include <iostream>
  4. #include <string>
  5. #include <cstdlib>
  6. #include <ctime>
  7. #include <fstream>
  8. #include <cmath>
  9. using namespace std;
  10. struct node
  11. {
  12.         int val;
  13.         node *next;
  14. };
  15.  
  16. struct BSTNode
  17. {
  18.         BSTNode *up, *left, *right;
  19.         int key;
  20. };
  21.  
  22. string cr, cl, cp;    
  23.  
  24. void printBT(string sp, string sn, BSTNode * v)
  25. {
  26.         string s;
  27.  
  28.         if (v)
  29.         {
  30.                 s = sp;
  31.                 if (sn == cr) s[s.length() - 2] = ' ';
  32.                 printBT(s + cp, cr, v->right);
  33.  
  34.                 s = s.substr(0, sp.length() - 2);
  35.                 cout << s << sn << v->key << endl;
  36.  
  37.                 s = sp;
  38.                 if (sn == cl) s[s.length() - 2] = ' ';
  39.                 printBT(s + cp, cl, v->left);
  40.         }
  41. }
  42.  
  43. void insert(node *&H, int x);
  44. void remove(node *&H);
  45. void show(node *H);
  46. int* ReadDataFromFile(int &size);
  47.  
  48. void swap(node *&H, node *x)
  49. {
  50.         if (x == NULL)
  51.         {
  52.                 node *p = H;
  53.                 node *tmp = H->next;
  54.                 p->next = tmp->next;
  55.                 H = tmp;
  56.                 tmp->next = p;
  57.         }
  58.  
  59.         else
  60.         {
  61.                 node *p = x->next;
  62.                 node *tmp = p->next;
  63.  
  64.                 p->next = tmp->next;
  65.                 tmp->next = p;
  66.                 x->next = tmp;
  67.         }
  68. }
  69.  
  70. void bubble(node *&H)
  71. {
  72.         bool flag = true;
  73.  
  74.         while (flag)
  75.         {
  76.                 node *p = H;
  77.                 node *tmp = NULL;
  78.                 flag = false;
  79.  
  80.                 if (p->val > p->next->val)
  81.                 {
  82.                         node *pusty = NULL;
  83.                         swap(H, pusty);
  84.                         flag = true;
  85.                 }
  86.  
  87.                 while (p->next->next != tmp)
  88.                 {
  89.                         if (p->next->val > p->next->next->val)
  90.                         {
  91.                                 swap(H, p);
  92.                                 flag = true;
  93.                         }
  94.                         p = p->next;
  95.                 }
  96.  
  97.                 tmp = p;
  98.         }
  99. }
  100.  
  101. int average(node *p)
  102. {
  103.         int suma = 0;
  104.         int licznik = 0;
  105.         if (p)
  106.         {
  107.                
  108.  
  109.                 while (p)
  110.                 {
  111.                         suma = suma + p->val;
  112.                         licznik++;
  113.                         p = p->next;
  114.                 }
  115.         }
  116.         return (suma / licznik);
  117. }
  118.  
  119. int najblizszySredniej(node *p, int srednia)
  120. {
  121.         node *tmp = p;
  122.         int najblizej =tmp->val;
  123.         int roznica, roznicaN;
  124.         while (tmp->next)
  125.         {
  126.        
  127.                 if (abs(srednia - tmp->val) < abs(srednia - tmp->next->val))
  128.                 {
  129.                         najblizej = tmp->val;
  130.                         tmp = tmp->next;
  131.                 }
  132.                 else tmp = tmp->next;
  133.         }
  134.  
  135.         return najblizej;
  136. }
  137.  
  138. void insertBST(BSTNode *&root, int x)
  139. {
  140.         BSTNode *nowy = new BSTNode;
  141.         nowy->left = nowy->right = NULL;
  142.         nowy->key = x;
  143.  
  144.         BSTNode *p = root;
  145.         if (!p)
  146.                 root = nowy;
  147.        
  148.         else while (true)
  149.         {
  150.                 if (x < p->key)
  151.                 {
  152.                         if (!p->left)
  153.                         {
  154.                                 p->left = nowy;
  155.                                 break;
  156.                         }
  157.                         else p = p->left;
  158.                 }
  159.                 else
  160.                 {
  161.                         if (!p->right)
  162.                         {
  163.                                 p->right = nowy;
  164.                                 break;
  165.                         }
  166.                         else p = p->right;
  167.                 }
  168.         }
  169.         nowy->up = p;
  170. }
  171.  
  172. bool isLeaf(BSTNode *p)
  173. {
  174.         if (p)
  175.         {
  176.                 if (!p->left && !p->right)
  177.                         return true;
  178.                 else return false;
  179.         }
  180. }
  181.  
  182. void deleteLeaf(BSTNode *&root)
  183. {
  184.         if (root)
  185.         {
  186.                 if (isLeaf(root))
  187.                 {
  188.                         if (root->up)
  189.                         {
  190.                                 if (root->up->left == root)
  191.                                         root->up->left = NULL;
  192.                                 else root->up->right = NULL;
  193.  
  194.                                 delete root;
  195.                                 root = NULL;
  196.                         }
  197.                 }
  198.                 else
  199.                 {
  200.                         deleteLeaf(root->left);
  201.                         deleteLeaf(root->right);
  202.                 }
  203.         }
  204. }
  205.  
  206. int main()
  207. {
  208.         cr = cl = cp = "  ";
  209.         cr[0] = 218; cr[1] = 196;
  210.         cl[0] = 192; cl[1] = 196;
  211.         cp[0] = 179;
  212.  
  213.         node *H = NULL;
  214.         BSTNode *root = NULL;
  215.         int size = 0;
  216.         int *t = ReadDataFromFile(size);
  217.  
  218.         node *listy[50];
  219.  
  220.         for (int i = 0; i < 50; i++)
  221.                 listy[i] = NULL;
  222.  
  223.         int i = 0;
  224.         for (int j = 0; j < 50; j++)
  225.                 for (int k = 0; k < 10; k++)
  226.                 {
  227.                         insert(listy[j], t[i]);
  228.                         i++;
  229.                 }
  230.         int srednie[50];
  231.         for (int i = 0; i < 50; i++)
  232.         {
  233.                 show(listy[i]);
  234.                 srednie[i] = average(listy[i]);
  235.                 cout << "Srednia elementow listy nr " << i + 1 << " wynosi " << srednie[i] << endl;
  236.                 int y = najblizszySredniej(listy[i], srednie[i]);
  237.                 cout << "Najblizszy sredniej: " << y << endl;
  238.                 insertBST(root, y);
  239.                 cout << endl;
  240.                
  241.         }
  242.  
  243.         cout << "Drzewo z nowej listy: " << endl;
  244.         printBT("", "", root);
  245.         cout << "Po obcieciu lisci: " << endl;
  246.         deleteLeaf(root);
  247.         printBT("", "", root);
  248.         system("PAUSE");
  249.         return 0;
  250. }
  251.  
  252. int* ReadDataFromFile(int &size)
  253. {
  254.         fstream czytaj;
  255.  
  256.         czytaj.open("liczby.txt");
  257.         czytaj >> size;
  258.         int*Data = new int[size];
  259.         for (int i = 0; i<size; i++)
  260.                 czytaj >> Data[i];
  261.         czytaj.close();
  262.  
  263.  
  264.  
  265.  
  266.         return Data;
  267. }
  268.  
  269.  
  270. void insert(node *&H, int x)
  271. {
  272.         node *pom;
  273.         pom = new node;
  274.         pom->val = x;
  275.         pom->next = H;
  276.         H = pom;
  277. }
  278.  
  279. void remove(node *&H)
  280. {
  281.         if (H != NULL)
  282.         {
  283.                 node *pom = H;
  284.                 H = pom->next;
  285.                 delete pom;
  286.         }
  287. }
  288.  
  289. void show(node *H)
  290. {
  291.         node *pom = H;
  292.         cout << "HEAD ->";
  293.         while (pom != NULL)
  294.         {
  295.                 cout << pom->val << "->";
  296.                 pom = pom->next;
  297.         }
  298.         cout << "NULL" << endl;
  299. }