没有合适的资源?快使用搜索试试~ 我知道了~
在栈大小不受限制和栈大小受限制两种情况下,分析在给定入栈序列(1 2 … n)的情况下,出栈序列应满足的性质,并据此给出基于穷举法和模拟入栈出栈过程的方法判断序列a1a2…an是否是出栈序列的算法及程序实现。算法较直观,易于理解,程序均经过测试,输出正确。
资源推荐
资源详情
资源评论
出栈序列判断问题研究出栈序列判断问题研究
在栈大小不受限制和栈大小受限制两种情况下,分析在给定入栈序列(1 2 … n)的情况下,出栈序列应满足的
性质,并据此给出基于穷举法和模拟入栈出栈过程的方法判断序列a1a2…an是否是出栈序列的算法及程序实
现。算法较直观,易于理解,程序均经过测试,输出正确。
摘摘 要要: 在
关键词关键词: 栈;出栈序列;
0 引言引言
栈是限定仅在表尾端进行插入或删除操作的特殊线性表。通常称表尾端为栈顶,向栈中插入元素称为进栈,从栈中删除元
素称为出栈。由于插入和删除运算仅在栈顶一端进行,因此栈具有后进先出的特性,这种特性使得栈有着十分广泛的应用。在
参考文献[1-9]中,对给定一个入栈序列,求出栈序列数量、输出全部出栈序列、判断一个序列是否为出栈序列等问题进行了研
究,得出了相应的研究结果。然而,以上研究结果均基于一个前提:栈的大小是不受限制的,即栈的大小大于等于入栈序列的
长度。而在某些情况下,栈的大小会受到限制,即栈的大小小于入栈序列的长度,此时有关栈的入栈出栈算法会发生变化。因
此,本文对栈大小不受限制和栈大小受限制两种情况下,判断一个序列是否为出栈序列的问题进行分析研究,并给出了相应的
算法和程序实现。
为方便分析,将本文研究的有关栈的问题描述如下:给定入栈序列(1 2 … n),判断序列a1a2…an是否是出栈序列。
1 出栈序列性质出栈序列性质
当栈大小不受限制时,即栈的大小大于等于入栈序列的长度时,依据栈的特点,较容易得出出栈序列应该满足的性质。
性质1:当栈大小不受限制时,序列a1a2…an是(1 2 … n)的一个全排列, 则a1a2…an为出栈序列的充要条件是:对于
任意的ai, 在它后面的且比它小的数是降序排列的。
当栈的大小受限制,即栈的大小k小于入栈序列长度n时,出栈序列首先需要满足性质1,然后考虑栈大小受限对出栈序列
的要求。例如有长度n=6的入栈序列123456,栈的大小k=4,此时出栈序列的第1位不能超过元素4,即出栈序列第1位小于等
于4,第2位小于等于5。
一般情况下,第1位小于等于k,第2位小于等于k+1,依次类推,直到出栈序列第n-k位小于等于n-1。
性质2:当栈大小受限制,即栈大小k小于入栈序列长度n时,序列a1a2…an是(1 2 … n)的一个全排列, 则a1a2…an为
出栈序列的充要条件是满足性质1并且序列的第j位小于等于k+j-1。
2 栈大小不受限制时的判断栈大小不受限制时的判断
给定入栈序列12…n,判断序列a1a2…an是否是出栈序列。此时可以对序列直接判断是否满足性质1。满足则为出栈序
列,否则不是出栈序列。
算法1:入栈序列为12…n,待判断序列为a1a2…an。
(1)输入待判断序列,i=1。
(2)若i>n,转(3);否则判断序列a1a2…an第i位ai后比ai小的元素是否降序排列,若是则i++,转(2);否则转
(3)。
(3)若i>n,则判断该序列为出栈序列;否则,判断该序列不是出栈序列。
程序如下:
#include "iostream.h"
#include "string.h"
int pd(char a[],int n)
{ int u,v,w,flag=1;
for(u=0;u<=n-2;u++)
for(v=u+1;v<=n-1;v++)
for(w=v+1;w<=n;w++)
if((a[v]<a[w])&&(a[w]<a[u]))
flag=0;
资源评论
weixin_38612811
- 粉丝: 5
- 资源: 933
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功