C++气泡排序动态堆栈

Question

如何更改名为bubblesort的排序函数，使其使用动态堆栈。现在我已经完成了，函数可以正确排序，但使用列表，因为我为下一个项进行调解，并且在堆栈中我只能访问顶部。堆栈的数据取自外部文本文件。是否可以这样做来获得堆栈中的两个元素来比较它们，然后将它们保存在另一个堆栈或结构中（不使用数组和STL），以此类推，直到整个排序？

#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <time.h>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <deque>
#include <string>
using namespace std; 
int temp;
int br = 0;
struct stack 
{ 
    int key; 
    stack *next; 
} *start, *p, *s1 = NULL, *s2 = NULL, *help = NULL; 
void push(stack *&st, int n)
{
    stack *p = st; 
    st = new stack; 
    st -> key = n; 
    st -> next = p;
}
int pop(stack *&start, int &n) 
{
    if(start) 
    {
        stack *p = start; 
        n = start -> key; 
        start = start -> next;
        delete p;
        return 1;
    }
    else
        return 0;
}
void print_stack(int z)
{
    if (z == 1)
    {
            if(s1)
            {
                int a;
                while(pop(s1, a))
                {
                    cout << a << " ";
                    push(help, a);
                }
                 while(pop(help, a))
                    push(s1, a);
            }
            else
                cout << "Stack 1 is empty !";
    }
    if(z == 2)
    {
            if(s2)
            {
                int b;
                 while( pop(s2, b) )
                 {
                      cout << b << " ";
                      push(help, b);
                 }
                 while( pop(help, b) )
                    push(s2, b);
            }
            else
                cout << "Stack 2 is empty!";
    }
    cout << endl;
}
int bubblesort(stack *&S)
{
    stack *T;  
    int n, flag;
    int current = pop(S, n);
    if (S == NULL)
        return 0;
    do
    {
        flag = 0;
        T = S;
        while (T->next)
        {
            if (T->next->key < T->key) 
            {
                n = T->key;
                T->key = T->next->key;
                T->next->key = n;
                flag = 1;
            }
            else
                T = T->next;
        }
    } while (flag);
    return 0;
}
void input_first(stack *st)
{
    int a;
    cout << "Stack1n";
    ifstream i_file;
    i_file.open("stack1.txt", ios::in);
    if(i_file)
    {
        while (!i_file.eof())
        {
            i_file >> a;
            push(s1, a);
        }
        i_file.close();

    }
    else
        cout << "Error while opening input file!" << endl;
}
void input_second(stack *st)
{
    int a;
    cout << "Stack2n";
    ifstream i_file;
    i_file.open("stack2.txt", ios::in);
    if (i_file)
    {
        while (!i_file.eof())
        {
            i_file >> a;
            push(s2, a);
        }
        i_file.close();
    }
    else
        cout << "Error while opening input file!" << endl;
}
int main()
{
    stack *test1 = NULL;
    stack *test2 = NULL;
    input_first(test1);
    print_stack(1);
    cout << endl;
    input_second(test2);
    print_stack(2);
    cout << endl;
    cout<<"Sorted first stack: ";
    bubblesort(s1);
    print_stack(1);
    cout << endl;
    cout<<"Sorted second stack: ";
    bubblesort(s2);
    print_stack(2);
    cout << endl;
    system("pause");
    return 0;
}

Answer 1

使用源堆栈、目标堆栈和临时变量的示例算法。设s=源堆栈，t=目标堆栈。该算法通过在s和t之间来回移动数据来找到s中的最小值（请参阅下面的代码了解如何做到这一点），然后将最小值推到t上，并重复该过程，直到s被清空。然后，t中的所有值都会弹出/推回到s上。

    // s = stack to sort
    // t = temp stack
    // d = data
    // pop/push values from s to t, smallest to largest
    while(s){                     // while s not empty
        Pop(s, d);                // pop s into d
        while(t && Top(t) > d)    // push all t's > d back onto s
            Push(s, Pop(t));      //   to make a "space" for d in t
        Push(t, d);               // push d onto t 
    }
    // t now sorted in reverse order (pops return largest to smallest)
    while(t)                      // pop / push t to s
        Push(s, Pop(t));

该方法的时间复杂度为O（n^2）。如果排序是使用堆栈和一个队列或两个队列完成的，那么自下而上的合并排序可以用时间复杂性O（n-log（n））来实现。对于链表，可以使用指向节点的指针的小数组（26到32）来跟踪大小随数组的每一级别而翻倍的列表，array[i]要么为null，要么指向大小为2的幂i元素的列表，再次使用自下而上的合并排序。