Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<string>
- using namespace std;
- struct ListElem
- {
- int value;
- ListElem *next;
- };
- class SortedList
- {
- ListElem *pbeg, *pend;
- void push_back(ListElem *ptr);
- ListElem *pop_front();
- int Size;
- public:
- SortedList() { pend = pbeg = NULL; }
- void merge(SortedList &lst);
- void sort(SortedList );
- int pop_front_type();
- void push_front(int val);
- int get_Size() {return Size;};
- };
- ListElem *SortedList::pop_front()
- {
- if (pbeg == 0)
- return NULL;
- ListElem *ptr = pbeg;
- pbeg = pbeg->next;
- if (pbeg == 0)
- pend = NULL;
- return ptr;
- }
- void SortedList::push_back(ListElem *ptr)
- {
- ptr->next = NULL;
- if (pbeg == 0)
- pbeg = pend = ptr;
- else
- {
- pend->next = ptr;
- pend = ptr;
- }
- }
- void SortedList::push_front(int val)
- {
- ListElem *pnew = new ListElem;
- pnew->value = val;
- pnew->next = pbeg;
- pbeg = pnew;
- if (!pend)
- pend = pnew;
- Size++;
- }
- int SortedList::pop_front_type()
- {
- if (!pbeg)
- return -1;
- ListElem *ptr = pbeg;
- int val = pbeg->value;
- pbeg = pbeg->next;
- if (!pbeg)
- pend = NULL;
- delete ptr;
- return val;
- }
- void SortedList::merge(SortedList& B)
- {
- if (!B.pbeg)
- return;
- if (!pbeg)
- {
- pbeg = B.pbeg;
- pend = B.pend;
- B.pbeg = B.pend = NULL;
- }
- else
- {
- SortedList C;
- ListElem *ptr;
- while (pbeg != 0 || B.pbeg != 0)
- {
- if (B.pbeg == 0)
- ptr = pop_front();
- else if (pbeg == 0)
- ptr = B.pop_front();
- else if (pbeg->value <= B.pbeg->value)
- ptr = pop_front();
- else ptr = B.pop_front();
- C.push_back(ptr);
- }
- pbeg = C.pbeg;
- pend = C.pend;
- C.pbeg = C.pend = NULL;
- }
- }
- int main()
- {
- SortedList lst;
- int number, n;
- for (int i = 0; i<n; i++)
- {
- cin >> number;
- lst.push_front(number);
- }
- lst.merge(lst);
- int dlina = lst.get_Size();
- int *arr = new int[dlina];
- for (int i = 0; i < dlina; i++)
- arr[i] = lst.pop_front_type();
- for (int i = dlina - 1; i >= 0; i--)
- cout << arr[i] << " ";
- }
RAW Paste Data