顺序栈输出所以可能序列

Question

/*3)假设栈的输入序列为1、2、3、...、n，设计算法求出所有可能的出栈序列。
比如输入1、2、3、4、5，可能出栈的序列为12345、13452等42个。
*/
#include<iostream>
#include<stdlib.h>
#include <vector>  

 using namespace std;
#define max 100
typedef int element;
   typedef struct sStack {
    element data[max];
    int top;
}seqStack;
void initialStack(seqStack& S) {
    S.top = -1;
}
bool stackEmpty(seqStack& S) {
    if (S.top == -1)
        return true;
    else
        return false;
}
bool stackFull(seqStack& S) {
    if (S.top == max - 1)
        return true;
    else
        return false;
}
bool pushStack(seqStack& S, element x) {//入栈
    if (stackFull(S))
        return false;
    else
    {
        S.top++;
        S.data[S.top] = x;
        return true;
    }
}
bool popStack(seqStack& S) {//出栈
    if (stackEmpty(S))
        return true;
    else {
        element x;
        x = S.data[S.top];
        S.top--;
        return true;
    }
}
int sizeStack(seqStack& S) {//求栈中元素个数
    int count=0;
     while (!stackEmpty(S)) {
        popStack(S);
        count++;
     }
    return count;
}
bool stackTop(seqStack& S, element& x) {//取栈顶元素
    if (stackEmpty(S))
        return false;
    else {
        x = S.data[S.top];
        return true;
    }
}
//a存放输入序列，S是中间栈，b存放输出序列
int fun( seqStack& a, int n, seqStack& S,  vector<int>b) {
    if (n <= 0 || stackEmpty(a) && stackEmpty(S) && b.empty()) {
        return 0;
    }
    if (sizeStack(a) == n) {
         for (int i = 0; i < b.size();i++) {
             cout <<b[i] << " ";
          }
        cout << endl;
        return 0;
    }
    else if (!stackEmpty(S)&& stackEmpty(a)) {//中间栈满，出栈进容器b
        element y;//存放S栈顶元素
         stackTop(S, y);
        b.push_back(y);
        popStack(S);
        fun(a, n, S, b);
    }
    else if (!stackEmpty(a) && stackEmpty(S)) {//中间栈空，入栈
        element z = 0;//存放输入序列元素
         stackTop(a, z);
        pushStack(S, z);
        popStack(a);
     fun(a, n, S, b);
    }
    else {
        seqStack aCopy = a;
        seqStack Scopy = S;
        element y; 
        stackTop(S, y);
        b.push_back(y);
        popStack(S);
        fun(a, n, S, b);
 
        element z = 0; 
        stackTop(a, z);
        pushStack(S, z);
        popStack(a);
        fun(a, n, S, b);
    }
    return 0;
}
int main() {
    seqStack a, S;
    vector<int>b;
    initialStack(S);
    initialStack(a);
     int n;
     cout << "输入序列最后一个数：";
    cin >> n;
     for (int i = 1; i <= n; i++) {
        pushStack(a, i);
     }
    fun(a, n, S, b);
    return 0;
} 
 

想问一下哪里出问题了，编译不报错，输完序列最后一个 数后，打印不出任何东西

Answer 1

在你的代码中，函数fun()的返回值是0，所以即使fun()递归完成，它也不会打印任何东西。你需要将输出操作移动到fun()中，这样才能输出结果。你可以将函数fun()的返回类型更改为void，然后在函数中直接输出结果，例如：

void fun(seqStack& a, int n, seqStack& S, vector<int>& b) {
    if (n <= 0 || (stackEmpty(a) && stackEmpty(S) && b.empty())) {
        for (int i = 0; i < b.size(); i++) {
            cout << b[i] << " ";
        }
        cout << endl;
        return;
    }
    if (sizeStack(a) == n) {
        fun(a, n - 1, S, b);
    }
    else if (!stackEmpty(S) && stackEmpty(a)) {
        element y;
        stackTop(S, y);
        b.push_back(y);
        popStack(S);
        fun(a, n, S, b);
        b.pop_back();
        pushStack(S, y);
    }
    else if (!stackEmpty(a) && stackEmpty(S)) {
        element z = 0;
        stackTop(a, z);
        pushStack(S, z);
        popStack(a);
        fun(a, n, S, b);
        popStack(S);
        pushStack(a, z);
    }
    else {
        seqStack aCopy = a;
        seqStack Scopy = S;
        element y;
        stackTop(S, y);
        b.push_back(y);
        popStack(S);
        fun(a, n, S, b);
        b.pop_back();
        pushStack(S, y);
        element z = 0;
        stackTop(a, z);
        pushStack(S, z);
        popStack(a);
        fun(a, n, S, b);
        popStack(S);
        pushStack(a, z);
    }
}

在上面的代码中，我们使用了void作为fun()函数的返回类型，并将输出操作移动到函数中。此外，我们还进行了一些其他的修改，例如将参数b声明为vector&类型（注意&符号表示引用），这样我们就可以在fun()函数中修改b，并使其在函数递归返回时保留修改。我们还更改了fun()函数中的一些细节，例如：在if (sizeStack(a) == n)分支中，我们现在递归调用fun()函数，并将n-1作为参数；在if (!stackEmpty(S) && stackEmpty(a))分支中，我们现在将b的最后一个元素弹出，并将S的栈顶元素推回S；在if (!stackEmpty(a) && stackEmpty(S))分支中，我们现在将S的栈顶元素弹出，并将其推回a。

希望这可以帮助你。