@yifeng152：
这是CSDN上的，13楼、18楼、19楼应该能看懂！两年多没看数据结构了╮(╯▽╰)╭
我们先说两个数学结论：
设置推送序列为 I(n):1,2,…,n
1进栈序列为abcd有多少种出栈，I(n) 有 C(2n,n)-C(2n,n-1) 弹出序列。
2、L(n)是I(n)的弹出序列当且仅当：对于L(n)的任意一个数字M，下列数字按降序排列。
注：[1]，Conclusion 1是教材《数据结构》中的原话，所以没有错，根据加泰罗尼亚数的几何意义也很容易证明。
[2]，结论2是我自己的观察，我觉得应该是对的。这是一个例子：
判断序列L(6): 4,3,5,2,1,6是否是I(6)的pop序列。
解法：4后小于4的数字3、2、1按降序排列； 3后小于3的数字2、1按降序排列； 5后小于5的数字2、1按降序排列； 2 小于2的数φ按降序排列； 1后小于1的数φ按降序排列； 6 后小于 6 的数 φ 按降序排列。所以 L(6) 是 I(6).
的弹出序列
—
接下来是程序：
1、决策函数bool ju(L)：输入序列L判断是否是I的pop序列。可以使用结论2的思想，可以优化。
2、过程恢复函数Ls proc(L)：输入I的弹出序列L，输出完整的入栈出栈过程。如果输入的L不是I的弹出序列，会给出提示进栈序列为abcd有多少种出栈，所以proc也有判断功能。
3、列出I(n)的所有pop序列
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用？
- 本站所有资源版权均属于原作者所有，这里所提供资源均只能用于参考学习用，请勿直接商用。若由于商用引起版权纠纷，一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了？
- 找不到素材资源介绍文章里的示例图片？
- 欧资源网
