[研究生入学考试]第三章 栈和队列.ppt

  1. 1、本文档共101页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[研究生入学考试]第三章 栈和队列

第三章 栈和队列 3.1 栈 3.1.1 栈的定义 3.1.2 栈的表示和实现 3.2 栈的应用举例 3.1 栈 3.1.1 栈的定义及基本运算 栈(Stack)是限制在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(Top),另一端为栈底(Bottom)。当表中没有元素时称为空栈。 假设栈S=(a1,a2,a3,…an),则a1称为栈底元素,an为栈顶元素。栈中元素按a1,a2,a3,…an的次序进栈,退栈的第一个元素应为栈顶元素。因此,栈的修改是按后进先出的原则进行的,所以,栈称为后进先出(先进后出)表(LIFO,FILO)。 3.1.2 顺序存储栈 栈是线性表的特例,因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈,可用数组来实现顺序栈。因为栈底位置是固定不变的,所以可以将栈底位置设置在数组的两端的任何一个端点;栈顶位置是随着进栈和退栈操作而变化的,故需用一个整型变量top(栈顶指针)来指出栈顶。 栈顶 栈底 例、一叠盘子、弹夹等。 入 出 -1 空栈 为指示当前栈顶的位置,需top为栈顶指针( MAXSIZE代表栈容量)。 初始化: x进栈: 退栈: top=-1; if(top= =MAXSIZE-1 上溢处理; else { top++; stack[top]=x;} if(top==-1) 下溢处理; else { y=stack[top]; top--;} 3.1.3 链栈 栈的链式存储结构称为链栈,插入和删除操作仅限制在链头位置上进行。栈顶指针就是链表的头指针。 3.2 栈的应用举例 由于栈结构具有的后进先出的固有特性,致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。 3.2.1 数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n / d)*d+n % d 例如 (1348)10=(2504)8,其运算过程如下: n n /8 n % 8 1348 168 4 168 21 0 21 2 5 2 0 2 void conversion( ) { initstack(s); cinn; while(n){ push(s,n%8); n=n/8; } while(! Stackempty(s)){ pop(s,e); coute; } } 3.2.2 括号匹配的检验 假设在表达式中 ([]())或[([ ][ ])] 等为正确的格式, [( ])或([( ))或 (()]) 均为不正确的格式。 算法的设计思想: 1)凡出现左括弧,则进栈; 2)凡出现右括弧,首先检查栈是否空 若栈空,则表明该“右括弧”多余, 否则和栈顶元素比较, 若相匹配,则“左括弧出栈” , 否则表明不匹配。 3)表达式检验结束时, 若栈空,则表明表达式中匹配正确, 否则表明“左括弧”有余。 3.2.3 行编辑程序 在编辑程序中,设立一个输入缓冲区,用于接受用户输入的一行字符,然后逐行存入用户数据区。允许用户输入错误,并在发现有误时可以及时更正。 出口 3.2.4 迷宫求解 入口 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫

文档评论(0)

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

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

1亿VIP精品文档

相关文档