Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on May 17th, 2012  |  syntax: None  |  size: 4.54 KB  |  hits: 14  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. struct node
  5. {
  6.     int value;
  7.     char content [34];
  8. };
  9.  
  10. node HEAP [32] [2500];
  11. int last [32];
  12.  
  13. // funkcja pomocnicza, zwracajaca numer wybranego kopca
  14. int HeapNumber (char sign)
  15. {
  16.     int numb = (int) sign - '0' - 17;
  17.     return numb;
  18. }
  19.  
  20. void ClearTab (char tab [])
  21. {
  22.     for (int i = 0; i < 34; i++)
  23.     {
  24.                 tab [i] = 0;
  25.         }
  26. }
  27.  
  28. // funkcja zwracajaca numer przodka elementu
  29. int ParentNode (int numb)
  30. {
  31.         if (numb == 1)
  32.         {
  33.                 return 1;
  34.         }
  35.         else if (numb % 5 == 0)
  36.         {
  37.                 return numb / 5;
  38.         }
  39.         else if (numb % 5 == 1)
  40.         {
  41.                 return (numb - 1) / 5;
  42.         }
  43.         else
  44.         {
  45.                 return (numb + 5 - (numb % 5)) / 5;
  46.         }
  47. }
  48.  
  49. int SmallestChild (int heap_numb, int current_node)
  50. {
  51.         int tmp = current_node * 5 - 3;
  52.         int smallest = HEAP [heap_numb] [tmp].value;
  53.         int smallest_node_numb = tmp;
  54.  
  55.         for (int i = 1; i < 5; i++)
  56.         {
  57.                 if (HEAP [heap_numb] [tmp + i].value < smallest && HEAP [heap_numb] [tmp + i].value > 0)
  58.                 {
  59.                         smallest = HEAP [heap_numb] [tmp + i].value;
  60.                         smallest_node_numb = tmp + i;
  61.                 }
  62.         }
  63.  
  64.         return smallest_node_numb;
  65. }
  66.  
  67. void AddToHeap (int value, char content [], int heap_numb)
  68. {
  69.         int current = ++last [heap_numb];
  70.  
  71.         HEAP [heap_numb] [current].value = value;
  72.  
  73.         for (int i = 0; i < 34; i++)
  74.         {
  75.                 HEAP [heap_numb] [current].content [i] = content [i];
  76.         }
  77.  
  78.         while (HEAP [heap_numb] [current].value <  HEAP [heap_numb] [ParentNode (current)].value)
  79.         {
  80.                 swap (HEAP [heap_numb] [current],  HEAP [heap_numb] [ParentNode (current)]);
  81.                 current = ParentNode (current);
  82.         }
  83. }
  84.  
  85. void RemoveFromHeap (int heap_numb)
  86. {
  87.         if (HEAP [heap_numb] [1].value)
  88.         {
  89.                 char tmp [34];
  90.                
  91.                 for (int i = 0; i < 34; i++)
  92.                 {
  93.                         tmp [i] = HEAP [heap_numb] [1].content [i];
  94.                 }
  95.  
  96.                 int current = 1, temp;
  97.  
  98.                 HEAP [heap_numb] [1] = HEAP [heap_numb] [last [heap_numb]];
  99.  
  100.                 HEAP [heap_numb] [last [heap_numb]].value = 0;
  101.                 ClearTab (HEAP [heap_numb] [last [heap_numb]].content);
  102.  
  103.                 --last [heap_numb];
  104.  
  105.                 while (HEAP [heap_numb] [SmallestChild (heap_numb, current)].value < HEAP [heap_numb] [current].value && HEAP [heap_numb] [SmallestChild (heap_numb, current)].value > 0)
  106.                 {
  107.                         temp = SmallestChild (heap_numb, current);
  108.                         swap (HEAP [heap_numb] [current], HEAP [heap_numb] [SmallestChild (heap_numb, current)]);
  109.                         current = temp;
  110.                 }
  111.  
  112.                 cout << tmp << endl;
  113.         }
  114. }
  115.  
  116. void JoinHeaps (int heap_numb, int heap_numb2)
  117. {
  118.         for (int i = last [heap_numb2]; i >= 1; i--)
  119.         {
  120.                 AddToHeap (HEAP [heap_numb2] [last [heap_numb2]].value, HEAP [heap_numb2] [last [heap_numb2]].content, heap_numb);
  121.  
  122.                 HEAP [heap_numb2] [last [heap_numb2]].value = 0;
  123.                 ClearTab (HEAP [heap_numb2] [last [heap_numb2]].content);
  124.                 last [heap_numb2]--;
  125.         }
  126. }
  127.  
  128. void ChangePriority (int heap_numb, int old, int fresh)
  129. {
  130.         int i = 1, j = 0, temp;
  131.         while (i <= last [heap_numb])
  132.         {
  133.                 if (HEAP [heap_numb] [i].value == old)
  134.                 {
  135.                         HEAP [heap_numb] [i].value = fresh;
  136.  
  137.                         while (HEAP [heap_numb] [i].value <  HEAP [heap_numb] [ParentNode (i)].value)
  138.                         {
  139.                                 swap (HEAP [heap_numb] [i],  HEAP [heap_numb] [ParentNode (i)]);
  140.                                 i = ParentNode (i);
  141.                                 j++;
  142.                         }
  143.  
  144.                         if (j = 0)
  145.                         {
  146.                                 while (HEAP [heap_numb] [SmallestChild (heap_numb, i)].value < HEAP [heap_numb] [i].value && HEAP [heap_numb] [SmallestChild (heap_numb, i)].value > 0)
  147.                                 {
  148.                                         temp = SmallestChild (heap_numb, i);
  149.                                         swap (HEAP [heap_numb] [i], HEAP [heap_numb] [SmallestChild (heap_numb, i)]);
  150.                                         i = temp;
  151.                                 }
  152.                         }
  153.                         break;
  154.                 }
  155.                 i++;
  156.         }
  157. }
  158.  
  159. int main ()
  160. {
  161.         char polecenie, heap_sign, heap_sign2, content [34];
  162.         int numer_kopca, numer_kopca2, value, value2;
  163.  
  164.         while (cin >> polecenie)
  165.         {
  166.                 // dodaj element, np. I M 10 ZAWARTOSC
  167.                 if (polecenie == 'I')
  168.                 {
  169.                         cin >> heap_sign;
  170.                         numer_kopca = HeapNumber (heap_sign);
  171.  
  172.                         cin >> value;
  173.                         cin >> content;
  174.  
  175.                         AddToHeap (value, content, numer_kopca);
  176.                 }
  177.  
  178.                 // usun maksymalny element, np. D S
  179.                 else if (polecenie == 'D')
  180.                 {
  181.                         cin >> heap_sign;
  182.                         numer_kopca = HeapNumber (heap_sign);
  183.  
  184.                         RemoveFromHeap (numer_kopca);
  185.                 }
  186.  
  187.                 // join heaps, ex. J A B
  188.                 else if (polecenie == 'J')
  189.                 {
  190.                         cin >> heap_sign;
  191.                         numer_kopca = HeapNumber (heap_sign);
  192.  
  193.                         cin >> heap_sign2;
  194.                         numer_kopca2 = HeapNumber (heap_sign2);
  195.  
  196.                         if (numer_kopca != numer_kopca2)
  197.                         {
  198.                                 JoinHeaps (numer_kopca, numer_kopca2);
  199.                         }
  200.                 }
  201.  
  202.                 else if (polecenie == 'M')
  203.                 {
  204.                          cin >> heap_sign;
  205.                          numer_kopca = HeapNumber (heap_sign);
  206.  
  207.                          cin >> value;
  208.                          cin >> value2;
  209.  
  210.                          if (value != value2)
  211.                          {
  212.                                 ChangePriority (numer_kopca, value, value2);
  213.                          }
  214.                 }
  215.         }
  216.  
  217.         return 0;
  218. }
create a new version of this paste RAW Paste Data