当前课程知识点:数据结构(上) > 第四章 栈与队列 > (c3)栈应用:栈混洗 > 04C3-3 甄别
我们再来讨论栈混洗的甄别问题
也就是说 对于输入序列的任何一个排列
我们如何来判断它究竟是
还不是一个合法的栈混洗
我们先从简单的例子入手
考虑由三个元素所构成的一个输入序列
套用刚才所得的结果
我们知道第3个catalan数为5
同时我们也知道 三个数的全排列
也就是3的阶乘 应该是6
这就意味着 对于这种情况而言
有一种排列并非栈混洗
那么少的是哪一种呢?
我们说是它 3 1 2 mi do rui
为什么是它呢?我们来看一下
输入栈A中 如果最初是1 2 3 do rui mi
我们将注意力放在最末尾的那个元素3上
为了能够将这个元素转入最终的栈B中
我们需要首先将它转入中转的S栈
而为了保证3能够作为第一个元素
被推入栈B中
在3被转入栈B的时候
元素2和1应该恰好依次排列在
S栈中3的下方
因此在3被转入栈B之后
接下来的情节是固定的
也就是说 2以及1将会相继地被转入栈B中
从而固定地得到一个mi rui do序列
而不是mi do rui
这个例子虽然简单 但是却非常的本质
因为接下来 我们可以发现
其实任意的三个元素
能否按照某种相对的次序
出现在最终的栈混洗中
与其它的元素实际上是无关的
因此推而广之
对于任何三个互异的整数 i j k
如果在某个排列中出现了 k i j
其实也就对应着
我们刚才所说的3 1 2的情况
那么它就必然不是栈混洗
换而言之 这是栈混洗
所必须禁止的一种特征
我们也不妨称之为禁形
那么反过来 如果某个排列中
不含任何的mi do rui式的禁形
那么它就一定是一个栈混洗吗?
也就是说 不含禁形的必要条件
是否反过来也是一个充分的条件呢?
-选课之前
--写在选课之前
--宣传片
-考核方式
--考核方式
-OJ系统说明
--关于OJ
--1-注册与登录
--2-界面与选课
--3-提交测试
-关于课程教材与讲义
--课程教材与讲义
-关于讨论区
--关于讨论区
-微信平台
--html
-PA晋级申请
--PA晋级
-(a)计算
--演示
--(a)计算--作业
-(b)计算模型
-(b)计算模型--作业
-(c)大O记号
-(c)大O记号--作业
-(d)算法分析
-(d)算法分析--作业
-(e)迭代与递归
-(e)迭代与递归--作业
-(xc)动态规划
-- 演示
-(xc)动态规划--作业
-本章测验--作业
-(a)接口与实现
--02A-5 复制
-(a)接口与实现--作业
-(b)可扩充向量
-(b)可扩充向量--作业
-(c)无序向量
--02C-1 概述
--02C-3 插入
--02C-6 查找
--02C-8 遍历
-(c)无序向量--作业
-(d1)有序向量:唯一化
-(d1)有序向量:唯一化--作业
-(d2)有序向量:二分查找
-(d2)有序向量:二分查找--作业
-(d3)有序向量:Fibonacci查找
-(d3)有序向量:Fibonacci查找--作业
-(d4)有序向量:二分查找(改进)
-(d4)有序向量:二分查找(改进)--作业
-(d5)有序向量:插值查找
-第二章 向量(下)--(d5)有序向量:插值查找
-(e)起泡排序
--02E-2 改进
--02E-3 反例
-(e)起泡排序--作业
-(f)归并排序
-(f)归并排序--作业
-本章测验--作业
-(a)接口与实现
--03A-4 实现
-(a)接口与实现--作业
-(b)无序列表
--03B-2 查找
-(b)无序列表--作业
-(c)有序列表
--03C-3 查找
-(c)有序列表--作业
-(d)选择排序
--03D-1 构思
--03D-2 实例
--03D-3 实现
--03D-4 推敲
--03D-6 性能
-(d)选择排序--作业
-(e)插入排序
--03E-1 经验
--03E-2 构思
--03E-3 对比
--03E-4 实例
--03E-5 实现
-(e)插入排序--作业
-(xd)习题辅导:LightHouse
-本章测验--作业
- (a)栈接口与实现
--04A-1 栈
--04A-2 实例
--04A-3 实现
- (a)栈接口与实现--作业
-(c1)栈应用:进制转换
-第四章 栈与队列--(c1)栈应用:进制转换
-(c2)栈应用:括号匹配
-(c2)栈应用:括号匹配--作业
-(c3)栈应用:栈混洗
-第四章 栈与队列--(c3)栈应用:栈混洗
-(c4)栈应用:中缀表达式求值
-(c4)栈应用:中缀表达式求值--作业
-(c5)栈应用:逆波兰表达式
-第四章 栈与队列--(c5)栈应用:逆波兰表达式
-(d)队列接口与实现
--04D-1 接口
--04D-2 实例
--04D-3 实现
-第四章 栈与队列--本章测验
-(a)树
--05A-1 动机
--05A-2 应用
-(a)树--作业
-(b)树的表示
--05B-2 父亲
--05B-3 孩子
-第五章 二叉树--(b)树的表示
-(c)二叉树
-(c)二叉树--作业
-(d)二叉树实现
-(d)二叉树实现--作业
-(e1)先序遍历
-(e1)先序遍历--作业
-(e2)中序遍历
-第五章 二叉树--(e2)中序遍历
-(e4)层次遍历
-第五章 二叉树--(e4)层次遍历
-(e5)重构
-(e5)重构--作业
-本章测验--作业
-(a)概述
-(a)概述--作业
-(b1)邻接矩阵
-(b1)邻接矩阵--作业
-(c)广度优先搜索
--06C-2 策略
--06C-3 实现
--06C-5 实例
-(c)广度优先搜索--作业
-(d)深度优先搜索
--06D-1 算法
--06D-2 框架
--06D-3 细节
-(d)深度优先搜索--作业
-第六章 图--本章测验