1,2,3,4依次进栈,出栈随时,写一算法求出所有可能出栈序列要求带注释,最好使用C或C++感谢一楼的回答,但是算法明显不正确,4元素应该有14出栈序列你的算法只显示8种,少了2143,2134,3214,3241

Question

1,2,3,4依次进栈,出栈随时,写一算法求出所有可能出栈序列
要求带注释,最好使用C或C++
感谢一楼的回答,但是算法明显不正确,4元素应该有14出栈序列
你的算法只显示8种,少了2143,2134,3214,3241

Answer 1

你要算法,从程序中归纳就行了
我想到一种方法,可是有点复杂,要用到树的结构,先给你看个程序,是计算n个元素进栈,可能的出栈系列种数
/*递归求n个元素进栈,可能的出栈系列种数*/
#define N 4
int m=0,a=0,b=N;/*m表示种数,a表示栈中元素个数,b表示外面还有需要进栈的个数*/
main()
{
inS(a,b);/*首先入栈*/
printf("%d",m);
getch();
}
int inS(int a,int b)/*入栈*/
{
a++;b--;/*入栈栈中元素+1,栈外元素-1 */
if(b>0)/*若栈外有元素,可以入栈*/
inS(a,b);
if(a>0)/*若栈中有元素,可以出栈*/
outS(a,b);
}
int outS(int a,int b)/*出栈*/
{
a--;/*出栈栈中元素-1*/
if(a==0&&b==0)/*若栈中元素和栈外元素都为0个*/
{
m++;/*则此种情况的序列满足条件,种数+1*/
return;
}
if(b>0)
inS(a,b);
if(a>0)
outS(a,b);
}
若想输出这些序列,可以建立一个二叉树,二叉树的节点为操作（进栈或出栈）,从根节点（第一个入栈）到叶子节点（最后一个出栈）的路径就是每个序列的操作序列,每条路径共有2N个节点,分别为每个元素的入栈和出栈操作,然后通过遍历,将这些节点输出即可
建立这棵树可以用上面的递归建立,也可以用下面的方法建立
①建立一颗深度为2N的满二叉树(根节点深度为1),其中根节点为IN（入栈）,其他左子树为IN,右子树为OUT（出栈）,这棵树共有2^(2N-1)个叶子节点,用根节点到叶子节点共有2^(2N-1)条路径
②保留满足下面条件的路径,其他的剔除
1)路径从根到叶出现IN和OUT总次数均为N个
2)路径从根到叶出现 IN次数≥OUT次数(即出栈次数不可能多余入栈次数)
然后输出保留的每条路径上节点类型为OUT的数据,即是出栈序列
剔除方法可由下面方法实现
1根节点赋值为1,
2节点为IN,则此节点赋值为父节点的值+1,节点为OUT,则此节点赋值为父节点的值-1,
3剔除节点的值为负数,或值>N的节点,或叶子节点上的值不=0的路径,剩下的就是满足条件的路径
-------------------------------------------------
我想到一种方法,可以不用树的结构,只是模拟树,先贴程序
/*从1到N的顺序入栈,输出所有出栈序列*/
#include "math.h"
#define N 4
main()
{
void init(int h[][],int a,int b,int k);
int i,j,sum,logo,h[1000][2*N+1],s[N],a,b,n;
int M=pow(2,2*N-1);/*共M条路径,每条有2*N个节点*/
/*h[i][]为第i条路径的操作序列,其中h[i][0]为一个标志,标志此序列是否满足条件,是则为1,否为0；从h[1]到h[2*N]为操作序列,1表示入栈,-1表示出栈*/
n=M;/*n为成功的序列计数*/
/*初始化标志和第一个操作,因为第一个操作必定为入栈操作*/
for(i=0;i