第章栈和队列详解.ppt

  1. 1、本文档共61页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 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)

shuwkb + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档