Как отсортировать несколько динамических c очередей без STL в C ++

Question

Я только начал изучать стеки, очереди и колоды. Из того, что я видел так далеко от моих учебников и от inte rnet, я понял, как работает очередь. Я пытаюсь решить проблему, которую я получил как домашнее задание, поэтому я не прошу полного решения, я просто хочу дать совет о том, как go об этой проблеме.

Что я ' я пытаюсь сделать это - взять 2 динамические c очереди и отсортировать их по размеру элементов, а затем поместить указанные элементы в третью очередь, которая также будет отсортирована. Самым простым способом для меня было бы сложить все элементы в массив, чтобы отсортировать их, а затем поместить их в очередь, однако часть задачи заключалась в том, чтобы не использовать дополнительное пространство.

Я подумал о том, как это сделать, и вот что я придумал: каждая очередь сортируется отдельно, высовывая 2 ее элемента, затем сравнивая их и выталкивая меньшую обратно, оставляя большую для сравнения. это к следующему элементу очереди. По n-му повороту они должны были быть отсортированы.

Что меня смущает, так это то, как выполнить функцию, которая будет их сравнивать. Я пытался написать код, но ничего не могу поделать, так как нам не разрешено использовать stl библиотеки. Я знаю, что вопрос довольно тупой, но я провел всю неделю в поисках этого, и я понятия не имею, что делать дальше. Даже если это ссылка на сайт, объясняющий, как это должно работать, я все равно буду признателен за это.

#include <iostream>
using namespace std;

struct elem {
    int key;
    elem* next;
}* first = NULL, * last = NULL;

struct elem2 {
    int key2;
    elem2* next3;
}* first2 = NULL, * last2 = NULL;

struct elem3 {
    int key3;
    elem3* next3;
}* first3 = NULL, * last3 = NULL;

//elem *push(int n, elem *&first, elem *&last);
//elem *pop(int &n, elem *&first, elem *&last);

elem* push(int n, elem*& first, elem*& last)
{
    elem* p = last;
    last = new elem;
    last->key = n;
    last->next = NULL;
    if (p != NULL)
        p->next = last;
    else
        first = last;
    return p;
}

elem* pop(int& n, elem*& first, elem*& last)
{
    elem* p = NULL;
    if (first) {
        n = first->key;
        p = first;
        first = first->next;
        ;

        if (first == NULL)
            last = first;

        return p;
        delete p;
    }
    else
        return nullptr;
}

void main()
{
    int ch, num, ammount, i = 1;
    do {
        cout << "\n\t Menu";
        cout << "\n 1.Add elements";
        cout << "\n 2.Add elements to second queue";
        cout << "\n 3. Merge queues and sort them";
        cout << "\n 4.Exit";
        do {
            cout << "\n Your choice is:";
            cin >> ch;
        } while (ch < 1 || ch > 4);
        switch (ch)

        {
        case 1:
            cout << "How many elements would you like to add? \n";
            cin >> ammount;
            cout << "Input queue elements:\n";

            for (i = 0; i < ammount; i++) {
                cin >> num;
                elem* push(int num, elem*& first, elem*& last);
            }
            break;

        case 2:
            cout << "How many elements would you like to add? \n";
            cin >> ammount;
            cout << "Input queue elements:\n";

            for (i = 0; i < ammount; i++) {
                cin >> num;
                elem2* push(int num, elem2*& first2, elem2*& last2);
            }
            break;

        case 3:
            break;
        }
    } while (ch != 4);
}

Я до сих пор исправлял большинство из них. Единственное, что я все еще пытаюсь сделать, это отсортировать их в третью очередь. Есть идеи, как поступить?

Answer 1

Из вашего вопроса я понял, что вы хотите реализовать функцию слияния сортировки слиянием для очередей без использования дополнительного пространства. Я написал некоторый код; Подумайте об этом. Не стесняйтесь комментировать, если вы хотите больше разъяснений ...

#include <bits/stdc++.h>
using namespace std;

// Ref.: https://www.geeksforgeeks.org/queue-linked-list-implementation/

struct QNode {
    int data;
    QNode *next;
    QNode(int d) {
        data = d;
        next = NULL;
    }
};

struct Queue {
    QNode *front, *rear;

    int size;

    Queue() {
        front = rear = NULL;
        size = 0;
    }

    void enQueue(int x) {
        QNode *temp = new QNode(x);
        if (rear == NULL) {
            front = rear = temp;
            size++;
            return;
        }
        rear->next = temp;
        rear = temp;
        size++;
    }

    void deQueue() {
        if (front == NULL)
            return;
        QNode *temp = front;
        front = front->next;
        if (front == NULL)
            rear = NULL;
        delete (temp);
        size--;
    }

    void display() {
        if (front == NULL) {
            cout << "The queue is empty!" << endl;
            return;
        }
        QNode *temp = front;
        while (temp) {
            cout << temp->data << " --> ";
            temp = temp->next;
        }
        cout << endl;
    }

    int at(int i) { // gets q[i]
        if (i < 0 or i >= size)
            throw out_of_range("The index is not valid!");
        QNode *temp = front;
        for (int j = 0; j < i; j++)
            temp = temp->next;
        return temp->data;
    };

    void replace_at(int x, int i) { // sets q[i] = x
        if (i < 0 or i >= size)
            throw out_of_range("The index is not valid!");
        QNode *temp = front;
        for (int j = 0; j < i; j++)
            temp = temp->next;
        temp->data = x;
    }
};

// Ref.: https://www.geeksforgeeks.org/merge-two-sorted-arrays-o1-extra-space/

void merge(Queue q1, Queue q2) {
    int m = q1.size;
    int n = q2.size;
    for (int i = n - 1; i >= 0; i--) {
        int j, last = q1.at(m - 1);
        for (j = m - 2; j >= 0 and q1.at(j) > q2.at(i); j--)
            q1.replace_at(q1.at(j), j + 1);
        if (j != m - 2 || last > q2.at(i)) {
            q1.replace_at(q2.at(i), j + 1);
            q2.replace_at(last, i);
        }
    }
}

int main() {

    Queue q1, q2;
    char ch;
    int data;
    do {
        cout << endl
             << "MENU" << endl
             << "1.\t Add elements to queue 1" << endl
             << "2.\t Add elements to queue 2" << endl
             << "3.\t Merge and sort the two queues" << endl
             << "4.\t Exit" << endl
             << endl
             << "Enter your choice : ";
    lb:
        cin >> ch;
        switch (ch) {
            case '1':
                cout << "Enter the data you want to insert : ";
                cin >> data;
                q1.enQueue(data);
                cout << "Queue after this operation : ";
                q1.display();
                break;
            case '2':
                cout << "Enter the data you want to insert : ";
                cin >> data;
                q2.enQueue(data);
                cout << "Queue after this operation : ";
                q2.display();
                break;
            case '3':
                merge(q1, q2);
                cout << "Queue 1 after this operation : ";
                q1.display();
                cout << "Queue 2 after this operation : ";
                q2.display();
                break;
            case '4':
                break;
            default:
                cout << "Please check your choice!" << endl
                     << "Re-enter your choice : ";
                goto lb;
        }
    } while (ch != '4');

    return 0;
}

Вот примерный прогон:

> solution.exe

MENU
1.       Add elements to queue 1
2.       Add elements to queue 2
3.       Merge and sort the two queues
4.       Exit

Enter your choice : 1
Enter the data you want to insert : 1
Queue after this operation : 1 --> 

MENU
1.       Add elements to queue 1
2.       Add elements to queue 2
3.       Merge and sort the two queues
4.       Exit

Enter your choice : 1
Enter the data you want to insert : 5
Queue after this operation : 1 --> 5 --> 

MENU
1.       Add elements to queue 1
2.       Add elements to queue 2
3.       Merge and sort the two queues
4.       Exit

Enter your choice : 1
Enter the data you want to insert : 9
Queue after this operation : 1 --> 5 --> 9 --> 

MENU
1.       Add elements to queue 1
2.       Add elements to queue 2
3.       Merge and sort the two queues
4.       Exit

Enter your choice : 1
Enter the data you want to insert : 10
Queue after this operation : 1 --> 5 --> 9 --> 10 --> 

MENU
1.       Add elements to queue 1
2.       Add elements to queue 2
3.       Merge and sort the two queues
4.       Exit

Enter your choice : 1
Enter the data you want to insert : 15
Queue after this operation : 1 --> 5 --> 9 --> 10 --> 15 --> 

MENU
1.       Add elements to queue 1
2.       Add elements to queue 2
3.       Merge and sort the two queues
4.       Exit

Enter your choice : 1
Enter the data you want to insert : 20
Queue after this operation : 1 --> 5 --> 9 --> 10 --> 15 --> 20 --> 

MENU
1.       Add elements to queue 1
2.       Add elements to queue 2
3.       Merge and sort the two queues
4.       Exit

Enter your choice : 2
Enter the data you want to insert : 2
Queue after this operation : 2 --> 

MENU
1.       Add elements to queue 1
2.       Add elements to queue 2
3.       Merge and sort the two queues
4.       Exit

Enter your choice : 2
Enter the data you want to insert : 3
Queue after this operation : 2 --> 3 --> 

MENU
1.       Add elements to queue 1
2.       Add elements to queue 2
3.       Merge and sort the two queues
4.       Exit

Enter your choice : 2
Enter the data you want to insert : 8
Queue after this operation : 2 --> 3 --> 8 --> 

MENU
1.       Add elements to queue 1
2.       Add elements to queue 2
3.       Merge and sort the two queues
4.       Exit

Enter your choice : 2
Enter the data you want to insert : 13
Queue after this operation : 2 --> 3 --> 8 --> 13 --> 

MENU
1.       Add elements to queue 1
2.       Add elements to queue 2
3.       Merge and sort the two queues
4.       Exit

Enter your choice : 3
Queue 1 after this operation : 1 --> 2 --> 3 --> 5 --> 8 --> 9 -->
Queue 2 after this operation : 10 --> 13 --> 15 --> 20 -->

MENU
1.       Add elements to queue 1
2.       Add elements to queue 2
3.       Merge and sort the two queues
4.       Exit

Enter your choice : 4