Facebook
From krul, 6 Years ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 251
  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.        
  122.  
  123.         if (!p)
  124.                 return false;
  125.        
  126.         int najblizej = p->val;
  127.                 int ABS = abs(p->val - srednia);
  128.                 while (p->next)
  129.                 {
  130.                        
  131.                         if ( ABS < (abs(p->next->val - srednia)))
  132.                                 p = p->next;
  133.                        
  134.                         else
  135.                         {
  136.                                 najblizej = p->next->val;
  137.                                 ABS = abs(p->next->val - srednia);
  138.                                 p = p->next;
  139.                         }
  140.                 }
  141.        
  142.  
  143.         return najblizej;
  144. }
  145.  
  146. void insertBST(BSTNode *&root, int x)
  147. {
  148.         BSTNode *nowy = new BSTNode;
  149.         nowy->left = nowy->right = NULL;
  150.         nowy->key = x;
  151.  
  152.         BSTNode *p = root;
  153.         if (!p)
  154.                 root = nowy;
  155.        
  156.         else while (true)
  157.         {
  158.                 if (x < p->key)
  159.                 {
  160.                         if (!p->left)
  161.                         {
  162.                                 p->left = nowy;
  163.                                 break;
  164.                         }
  165.                         else p = p->left;
  166.                 }
  167.                 else
  168.                 {
  169.                         if (!p->right)
  170.                         {
  171.                                 p->right = nowy;
  172.                                 break;
  173.                         }
  174.                         else p = p->right;
  175.                 }
  176.         }
  177.         nowy->up = p;
  178. }
  179.  
  180. bool isLeaf(BSTNode *p)
  181. {
  182.         if (p)
  183.         {
  184.                 if (!p->left && !p->right)
  185.                         return true;
  186.                 else return false;
  187.         }
  188. }
  189.  
  190. void deleteLeaf(BSTNode *&root)
  191. {
  192.         if (root)
  193.         {
  194.                 if (isLeaf(root))
  195.                 {
  196.                         if (root->up)
  197.                         {
  198.                                 if (root->up->left == root)
  199.                                         root->up->left = NULL;
  200.                                 else root->up->right = NULL;
  201.  
  202.                                 delete root;
  203.                                 root = NULL;
  204.                         }
  205.                 }
  206.                 else
  207.                 {
  208.                         deleteLeaf(root->left);
  209.                         deleteLeaf(root->right);
  210.                 }
  211.         }
  212. }
  213.  
  214. int main()
  215. {
  216.         cr = cl = cp = "  ";
  217.         cr[0] = 218; cr[1] = 196;
  218.         cl[0] = 192; cl[1] = 196;
  219.         cp[0] = 179;
  220.  
  221.         node *H = NULL;
  222.         BSTNode *root = NULL;
  223.         int size = 0;
  224.         int *t = ReadDataFromFile(size);
  225.  
  226.         node *listy[50];
  227.  
  228.         for (int i = 0; i < 50; i++)
  229.                 listy[i] = NULL;
  230.  
  231.         int i = 0;
  232.         for (int j = 0; j < 50; j++)
  233.                 for (int k = 0; k < 10; k++)
  234.                 {
  235.                         insert(listy[j], t[i]);
  236.                         i++;
  237.                 }
  238.         int srednie[50];
  239.         for (int i = 0; i < 50; i++)
  240.         {
  241.                 show(listy[i]);
  242.                 srednie[i] = average(listy[i]);
  243.                 cout << "Srednia elementow listy nr " << i + 1 << " wynosi " << srednie[i] << endl;
  244.                 int y = najblizszySredniej(listy[i], srednie[i]);
  245.                 cout << "Najblizszy sredniej: " << y << endl;
  246.                 insert(H, y);
  247.                 insertBST(root, y);
  248.                 cout << endl;
  249.                
  250.         }
  251.         cout << "Nowa lista: " << endl;
  252.         show(H);
  253.         cout << endl;
  254.         cout << "Drzewo z nowej listy: " << endl;
  255.         printBT("", "", root);
  256.         cout << "Po obcieciu lisci: " << endl;
  257.         deleteLeaf(root);
  258.         printBT("", "", root);
  259.         system("PAUSE");
  260.         return 0;
  261. }
  262.  
  263. int* ReadDataFromFile(int &size)
  264. {
  265.         fstream czytaj;
  266.  
  267.         czytaj.open("liczby.txt");
  268.         czytaj >> size;
  269.         int*Data = new int[size];
  270.         for (int i = 0; i<size; i++)
  271.                 czytaj >> Data[i];
  272.         czytaj.close();
  273.  
  274.  
  275.  
  276.  
  277.         return Data;
  278. }
  279.  
  280.  
  281. void insert(node *&H, int x)
  282. {
  283.         node *pom;
  284.         pom = new node;
  285.         pom->val = x;
  286.         pom->next = H;
  287.         H = pom;
  288. }
  289.  
  290. void remove(node *&H)
  291. {
  292.         if (H != NULL)
  293.         {
  294.                 node *pom = H;
  295.                 H = pom->next;
  296.                 delete pom;
  297.         }
  298. }
  299.  
  300. void show(node *H)
  301. {
  302.         node *pom = H;
  303.         cout << "H->";
  304.         while (pom != NULL)
  305.         {
  306.                 cout << pom->val << "->";
  307.                 pom = pom->next;
  308.         }
  309.         cout << "NULL" << endl;
  310. }