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