deushiro

Untitled

Oct 15th, 2021
782
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3.  
  4. struct Number {
  5.     int* num;
  6.     int* counter;
  7.  
  8.     explicit Number(int* num = new int(), int* counter = new int()) {
  9.         this->num = num;
  10.         this->counter = counter;
  11.     }
  12.  
  13. };
  14.  
  15. struct Node {
  16.     Number data;
  17.     Node* p_next;
  18.  
  19.     explicit Node(Number& data, Node* p_next = nullptr) {
  20.         this->data = data;
  21.         this->p_next = p_next;
  22.     }
  23. };
  24.  
  25. struct List {
  26.     List() : size_(0), head(nullptr), tail(nullptr) {
  27.     }
  28.  
  29.     ~List() {
  30.         clear();
  31.     }
  32.  
  33.     bool empty() const {
  34.         return (head == nullptr);
  35.     }
  36.  
  37.     void pushBack(Number& value) {
  38.         Node* new_node = new Node(value);
  39.         if (head == nullptr) {
  40.             head = new_node;
  41.         } else {
  42.             tail->p_next = new_node;
  43.         }
  44.         tail = new_node;
  45.         ++size_;
  46.     }
  47.  
  48.     void popFront() {
  49.         Node* current = head;
  50.         head = head->p_next;
  51.         (*(current->data.counter))--;
  52.         if (*(current->data.counter) == 0) {
  53.             delete current->data.counter;
  54.             delete current->data.num;
  55.         }
  56.         --size_;
  57.         delete current;
  58.     }
  59.  
  60.     void clear() {
  61.         while (!empty()) {
  62.             popFront();
  63.         }
  64.         head = nullptr;
  65.         tail = nullptr;
  66.         size_ = 0;
  67.     }
  68.  
  69.     int& front() {
  70.         return *(head->data.num);
  71.     }
  72.     const int& front() const {
  73.         return *(head->data.num);
  74.     }
  75.  
  76.     size_t size() const {
  77.         return size_;
  78.     }
  79.     size_t size_;
  80.     Node* head;
  81.     Node* tail;
  82. };
  83.  
  84. void print(List* list) {
  85.     Node* current = list->head;
  86.     while (current != nullptr) {
  87.         std::cout << *(current->data.num) << " ";
  88.         current = current->p_next;
  89.     }
  90.     std::cout << "\n";
  91. }
  92.  
  93. List* merge(const List& a, const List& b) {
  94.     List* new_list = new List();
  95.     Node* first = a.head;
  96.     Node* second = b.head;
  97.     while (first != nullptr && second != nullptr) {
  98.         if (*(first->data.num) <= *(second->data.num)) {
  99.             new_list->pushBack(first->data);
  100.             first = first->p_next;
  101.         } else {
  102.             new_list->pushBack(second->data);
  103.             second = second->p_next;
  104.         }
  105.     }
  106.     while (first != nullptr) {
  107.         new_list->pushBack(first->data);
  108.         first = first->p_next;
  109.     }
  110.     while (second != nullptr) {
  111.         new_list->pushBack(second->data);
  112.         second = second->p_next;
  113.     }
  114.     return new_list;
  115. }
  116.  
  117. int main() {
  118.     int n, m;
  119.     std::cin >> n >> m;
  120.     List a, b;
  121.     for (size_t i = 0; i < n; ++i) {
  122.         int x;
  123.         std::cin >> x;
  124.         int* new_num = new int(x);
  125.         int* counter = new int(2);
  126.         Number number = Number(new_num, counter);
  127.         a.pushBack(number);
  128.     }
  129.     for (size_t i = 0; i < m; ++i) {
  130.         int x;
  131.         std::cin >> x;
  132.         int* new_num = new int(x);
  133.         int* counter = new int(2);
  134.         Number number = Number(new_num, counter);
  135.         b.pushBack(number);
  136.     }
  137.    
  138.     List* answer = merge(a, b);
  139.     print(answer);
  140.     return 0;
  141. }
RAW Paste Data