- 1、本文档共61页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第3章 限定性线性表—栈和队列 ;3.1 什么是栈?;后缀表达式 ;对象: 6 (运算数 );栈(Stack):具有一定操作约束的线性表
?只在一端(栈顶,Top)做 插入、删除 ;图3.1 栈 ;栈的抽象数据类型描述
ADT Stack{
数据对象集:一个有0个或多个元素的有穷线性表。
基本操作:
(1) InitStack(S)
初始条件: S为未初始化的栈。
操作结果: 将S初始化为空栈。
(2) ClearStack(S)
初始条件: 栈S已经存在。
操作结果: 将栈S置成空栈。 ; (3) StackEmpty(S)
初始条件:栈S已经存在。
操作结果:若S为空栈,则函数值为TRUE,否则FALSE
(4) Push(S,e)
初始条件:栈S已经存在。
操作结果:在S的顶部插入(亦称压入)元素e;; (5) Pop(S, e)
初始条件:栈S已经存在。
操作结果:删除(亦称弹出)栈S的顶部元素,并用e带回该值。
(6) GetTop(S, e)
初始条件: 栈S已经存在。
操作结果:取栈S的顶部元素。与Pop(S, e)不同之处在于GetTop(S,e)不改变栈顶的位置。;Push 和 Pop 可以穿插交替进行;
按照操作系列
(1)Push(S,A), Push(S,B),Push((S,C),Pop(S),Pop(S),Pop(S)
栈输出是?
(2) 而Push(S,A), Pop(S),Push(S,B),Push((S,C),Pop(S),Pop(S)
栈输出是?
[例] 如果三个字符按ABC顺序压入堆栈
?ABC的所有排列都可能是出栈的序列吗?
?可以产生CAB这样的序列吗?
;3.1.2 栈的表示和实现 ;图3.2 顺序栈中的进栈和出栈 ;顺序栈基本操作的实现如下:
(1) 初始化。 ;(2) 取栈顶元素
Status GetTop(SqStack S, SElemType e){
if (S.top = = S.base) return ERROR;
e= * (S.top-1);
return OK;
};(3) 入栈。
Status Push(SqStack S, SElemType e){
if (S.top - S.base= S.stacksize){
S.base=(SElemType*)realloc(S.base,
(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
} ;(4) 出栈
Status Pop(SqStack S, SelemType e){
if( S.top= =S.base) return ERROR;
e=*--S.top;
return OK;
}; 在栈的共享技术中最常用的是两个栈的共享技术:它主要利用了栈“栈底位置不变,而栈顶位置动态变化”的特性。首先为两个栈申请一个共享的一维数组空间S[M],将两个栈的栈底分别放在一维数组的两端,分别是0、M-1。由于两个栈顶动态变化,这样可以形成互补,使得每个栈可用的最大空间与实际使用的需求有关。由此可见,两栈共享比两个栈分别申请M/2的空间利用率高。;图3.3 共享栈 ;2. 链栈 ;3.2 栈的应用:表达式求值
? 回忆:应用栈实现后缀表达式求值的基本过程:
从左到右读入后缀表达式的各项(运算符或运算数);
1.运算数:入栈;
2.运算符:从栈中弹出适当数量的运算数,计算并结果入栈;
3.最后,栈顶上的元素就是表达式的结果值。 ;中缀表达式求值
基本策略:将中缀表达式转换为后缀表达式,然后求值
如何将中缀表达式转换为后缀?
观察一个简单例子: 3 + 4 * 5 -6 ? 3 4 5 * + 6 –
1.运算数相对顺序不变
2.运算符号顺序发生改变
需要存储“等待中”的运算符号
要将当前运算符号与“等待中”的最后一个运算符号比较 ;〖例〗 3
文档评论(0)