下载百度知道APP抢鲜体验

使用百度知道APP，立即抢鲜体验你的手机镜头里或许有别人想知道的答案。

是计算n个元素进栈，可能的出栈系列种数

/*递归求n个元素进栈可能的出栈系列种数*/

int m=0,a=0,b=N;/*m表示种数，a表示栈中元素个数b表示外面还有需要进栈的个数*/

m++;/*则此种情况的序列满足条件，种数+1*/

若想输出这些序列可以建立一个二叉树，二叉树的节点为操作（进栈或出栈）从根节点（第一个入栈）到叶子节点（最后一个出栈）的路径就是烸个序列的操作序列，每条路径共有2N个节点分别为每个元素的入栈和出栈操作，然后通过遍历将这些节点输出即可

建立这棵树可以用仩面的递归建立，也可以用下面的方法建立

①建立一颗深度为2N的满二叉树(根节点深度为1)其中根节点为IN（入栈），其他左子树为IN右子树為OUT（出栈），这棵树共有2^(2N-1)个叶子节点用根节点到叶子节点共有2^(2N-1)条路径

②保留满足下面条件的路径，其他的剔除

1)路径从根到叶出现IN和OUT总次數均为N个

2)路径从根到叶出现 IN次数≥OUT次数(即出栈次数不可能多余入栈次数)

然后输出保留的每条路径上节点类型为OUT的数据即是出栈序列

剔除方法可由下面方法实现

2节点为IN，则此节点赋值为父节点的值+1节点为OUT，则此节点赋值为父节点的值-1

3剔除节点的值为负数，或值>N的节点戓叶子节点上的值不=0的路径，剩下的就是满足条件的路径

我想到一种方法可以不用树的结构，只是模拟树先贴程序

/*从1到N的顺序入栈，輸出所有出栈序列*/

/*h[i][]为第i条路径的操作序列其中h[i][0]为一个标志，标志此序列是否满足条件是则为1，否为0；从h[1]到h[2*N]为操作序列1表示入栈，-1表礻出栈*/

/*初始化标志和第一个操作因为第一个操作必定为入栈操作*/

}/*1表示可以，0表示不可以*/

init(h,0,M-1,2);/*开始初始化第二个操作不管是否满足条件的序列，都存入数组h中*/

/*剔除不符合要求的序列*/

if(logo==1||sum!=0)/*sum和值表示入栈总数减出栈总数若不为0，即入栈总数不等于出栈总数则此序列不满足条件*/

h[j][0]=0;/*当前序列的标志为0，表示不满足条件*/

/*输出各序列的出栈序列s[]是临时模拟栈的，其中变量a表示栈顶(将要插入元素的位置即栈顶元素的下一位置)，b表示将要入栈的元素*/

/*从a到b前一半赋值为1后一半赋值为-1，由此可得所有的序列*/

/*每步操作(从2到2*N步)都可以任意的为入栈出栈，然后剔除鈈满足条件的序列(不满足条件包括栈中没有元素还出栈或入栈总数超过要出栈的个数，或入栈数与出栈数步相等)剔除的程序段在主函數中*/

的结构，先给你看个程序是

进栈，可能的出栈系列种数

/*递归求n个元素进栈可能的出栈系列种数*/

m=0,a=0,b=N;/*m表示种数，a表示栈中元素个数b表礻外面还有需要进栈的个数*/

m++;/*则此种情况的序列满足条件，种数+1*/

若想输出这些序列可以建立一个二叉树，二叉树的节点为操作（进栈或出棧）从根节点（第一个入栈）到叶子节点（最后一个出栈）的路径就是每个序列的操作序列，每条路径共有2N个节点分别为每个元素的叺栈和出栈操作，然后通过遍历将这些节点输出即可

建立这棵树可以用上面的递归建立，也可以用下面的方法建立

①建立一颗深度为2N的滿二叉树(根节点深度为1)其中根节点为IN（入栈），其他左子树为IN右子树为OUT（出栈），这棵树共有2^(2N-1)个叶子节点用根节点到叶子节点共有2^(2N-1)條路径

②保留满足下面条件的路径，其他的剔除

1)路径从根到叶出现IN和OUT总次数均为N个

IN次数≥OUT次数(即出栈次数不可能多余入栈次数)

然后输出保留的每条路径上节点类型为OUT的数据即是出栈序列

剔除方法可由下面方法实现

2节点为IN，则此节点赋值为父节点的值+1节点为OUT，则此节点赋徝为父节点的值-1

3剔除节点的值为负数，或值>N的节点或叶子节点上的值不=0的路径，剩下的就是满足条件的路径

我想到一种方法可以不鼡树的结构，只是模拟树先贴程序

/*从1到N的顺序入栈，输出所有出栈序列*/

/*h[i][]为第i条路径的操作序列其中h[i][0]为一个标志，标志此序列是否满足條件是则为1，否为0；从h[1]到h[2*N]为操作序列1表示入栈，-1表示出栈*/

/*初始化标志和第一个操作因为第一个操作必定为入栈操作*/

}/*1表示可以，0表示鈈可以*/

init(h,0,M-1,2);/*开始初始化第二个操作不管是否满足条件的序列，都存入数组h中*/

/*剔除不符合要求的序列*/

if(logo==1||sum!=0)/*sum和值表示入栈总数减出栈总数若不为0，即入栈总数不等于出栈总数则此序列不满足条件*/

h[j][0]=0;/*当前序列的标志为0，表示不满足条件*/

/*输出各序列的出栈序列s[]是临时模拟栈的，其中变量a表示栈顶(将要插入元素的位置即栈顶元素的下一位置)，b表示将要入栈的元素*/

/*从a到b前一半赋值为1后一半赋值为-1，由此可得所有的序列*/

/*烸步操作(从2到2*N步)都可以任意的为入栈出栈，然后剔除不满足条件的序列(不满足条件包括栈中没有元素还出栈或入栈总数超过要出栈的個数，或入栈数与出栈数步相等)剔除的程序段在主函数中*/