allia

слияние хз

Dec 2nd, 2020 (edited)
466
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<string>
  3.  
  4. using namespace std;
  5.  
  6. struct ListElem
  7. {
  8.    int value;
  9.    ListElem *next;
  10. };
  11.  
  12. class SortedList
  13. {  
  14.   ListElem *pbeg, *pend;
  15.    void push_back(ListElem *ptr);
  16.    ListElem *pop_front();
  17.    int Size;
  18. public:
  19.    SortedList() { pend = pbeg = NULL; }
  20.    void merge(SortedList &lst);
  21.    void sort(SortedList );
  22.    int pop_front_type();
  23.    void push_front(int val);
  24.    int get_Size() {return Size;};
  25. };
  26.  
  27. ListElem *SortedList::pop_front()
  28. {
  29.    if (pbeg == 0)
  30.     return NULL;
  31.    ListElem *ptr = pbeg;
  32.    pbeg = pbeg->next;
  33.    if (pbeg == 0)
  34.     pend = NULL;
  35.    return ptr;
  36. }
  37.  
  38. void SortedList::push_back(ListElem *ptr)
  39. {
  40.    ptr->next = NULL;
  41.    if (pbeg == 0)
  42.     pbeg = pend = ptr;
  43.    else
  44.    {
  45.     pend->next = ptr;
  46.     pend = ptr;
  47.     }
  48. }
  49.  
  50. void SortedList::push_front(int val)
  51. {
  52.    ListElem *pnew = new ListElem;
  53.    pnew->value = val;
  54.    pnew->next = pbeg;
  55.    pbeg = pnew;
  56.    if (!pend)
  57.      pend = pnew;
  58.   Size++;
  59. }
  60.  
  61. int SortedList::pop_front_type()
  62. {
  63.    if (!pbeg)
  64.    return -1;
  65.    ListElem *ptr = pbeg;
  66.    int val = pbeg->value;
  67.    pbeg = pbeg->next;
  68.    if (!pbeg)
  69.     pend = NULL;
  70.    delete ptr;
  71.    return val;
  72. }
  73.  
  74. void SortedList::merge(SortedList& B)
  75. {
  76.   if (!B.pbeg)
  77.    return;
  78.   if (!pbeg)
  79.   {
  80.     pbeg = B.pbeg;
  81.     pend = B.pend;
  82.     B.pbeg = B.pend = NULL;
  83.   }
  84.   else
  85.   {
  86.     SortedList C;
  87.     ListElem *ptr;
  88.     while (pbeg != 0 || B.pbeg != 0)
  89.     {
  90.       if (B.pbeg == 0)
  91.        ptr = pop_front();
  92.       else if (pbeg == 0)
  93.        ptr = B.pop_front();
  94.       else if (pbeg->value <= B.pbeg->value)
  95.         ptr = pop_front();
  96.       else ptr = B.pop_front();
  97.        C.push_back(ptr);
  98.     }
  99.     pbeg = C.pbeg;
  100.     pend = C.pend;
  101.     C.pbeg = C.pend = NULL;
  102.   }
  103. }
  104.  
  105. int main()
  106. {
  107.  SortedList lst;
  108.   int number, n;
  109.  
  110.  for (int i = 0; i<n; i++)
  111.     {
  112.       cin >> number;
  113.       lst.push_front(number);
  114.     }
  115.  
  116.    lst.merge(lst);
  117.  
  118.   int dlina = lst.get_Size();
  119.  
  120.   int *arr = new int[dlina];
  121.  
  122.   for (int i = 0; i < dlina; i++)
  123.    arr[i] = lst.pop_front_type();
  124.  
  125.    for (int i = dlina - 1; i >= 0; i--)
  126.     cout << arr[i] << " ";
  127. }
  128.  
  129.  
RAW Paste Data