第三章 栈和队列.ppt

1、1,第三章 栈和队列,2,通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。,线性表 栈 队列 Insert(L, i,x) Insert(S, n+1,x) Insert(Q,n+1,x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in,栈和队列是两种常用的数据类型,3,3.1 栈的类型定义,3.2 栈的应用举例,3.3 栈类型的实现,3.4 队列的类型定义,3.5 队列类型的实现,4,3.1 栈的类型定义,ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | a

2、i-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。,基本操作：, ADT Stack,5,InitStack( #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;,类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。,18,Status InitStack (SqStack ,19,Status GetTop (SqStack S, SElemType ,20,Status Push (SqStack ,21,Statu

3、s Pop (SqStack ,22,栈顶指针,链栈,a1,an,注意: 链栈中指针的方向是从an到a1,an-1,23,typedef SElemType ElemType; /* 栈结点类型和链表结点类型一致 */ typedef LinkStack LinkList; /* LinkStack是指向栈结点的指针类型 */ #define InitStack InitList #define DestroyStack DestroyList #define ClearStack ClearList #define StackEmpty ListEmpty #define StackLeng

4、th ListLength,由于链栈是无头结点单链表的特例，所以链栈的大部分基本操作均可使用单链表的基本操作来代替。,24,Status Push(LinkStack ,25,Status Pop (LinkStack ,26,3.2 栈的应用举例,例一、 数制转换,例二、 括号匹配的检验,例三、 行编辑程序问题,例四、 迷宫求解,例五、 表达式求值,例六、 实现递归,27,例一、 数制转换 算法基于原理： N = (N div d)d + N mod d,28,例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 2

5、1 0 21 2 5 2 0 2,计算顺序,输出顺序,29,void conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion,30,该数制转化问题应用采用数组不也很简单吗？为什么还要引入栈来实现？,31,仔细分析，栈的引入简化了程序设计的问题，划分了不同的关注层次，使思考的范围缩小了。而采用数组不仅掩盖了问题的本质，还要分散精力去考虑数组下标增减等细节问题。,32,例二、

6、括号匹配的检验 假设在表达式中 （）或（ ） 等为正确的格式， （ ）或（ ）或 ( ) 均为不正确的格式。,33,分析可能出现的不匹配的情况:,到来的右括弧是非所“期待”的;,例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8,到来的是“不速之客”;,直到结束，也没有到来所“期待”的括弧;,34,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” 否则表明不匹配,3）表达式检验结束时， 若栈空，则表明表达式中匹配正确 否则表明“左括弧”有余,课堂练习：请同学们写出该算

7、法的类c语言描述,35,Status matching(string .,36,预习题,1.迷宫问题中的“当前位置”是指什么？ 2.队列和线性表有什么不同？ 3.实现循环队列的“判队空或满”的方法有哪些？ 4.在链队列中如何“判队空”和“判队满”？,在搜索过程中某一时刻所在图中的某个方块位置,队列限定插入只能在表的一端和删除只能在表的另一端进行,使用循环队列的最主要的技术问题是如何判断其“满”和“空”的状态。 1）另设一布尔变量区别队列的空和满。 2）使用一个计数器记录队列中元素的总数 3）少用一个元素的存储空间，约定以“队列头指针在队列尾指针的下一位置上” 作为队列满的标志。,队空条件：Q.

8、front = Q.rear 链队列不需判队满,37,例三、行编辑程序问题,如何实现？,“每接受一个字符即存入存储器” ?,并不恰当！,38,设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区; 并假设“#”为退格符，“”为退行符。,在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。,合理的作法是：,39,假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);,则实际有效的是下列两行： while (*s) putchar(*s+);,40,while (ch != EOF / 从终端接收下一个字符

9、 ,ClearStack(S); / 重置S为空栈 if (ch != EOF) ch = getchar();,while (ch != EOF) /EOF为全文结束符,将从栈底到栈顶的字符传送至调用过程的数据区;,41,例四、迷宫求解,常用“穷举求解”的方法,42,求迷宫路径算法的基本思想是：,若当前位置“可通”，则纳入路径，继续前进;,若当前位置“不可通”，则后退，换方向继续探索;,若四周“均无通路”，则将当前位置从路径中删除出去。,43,设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为 新的当

10、前位置； 否则 while (栈不空）；,求迷宫中一条从入口到出口的路径的算法：,44,若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块；,若栈不空但栈顶位置的四周均不可通， 则删去栈顶位置；/ 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； ,若栈空，则表明迷宫没有通路。,45,表达式示例: 4(23)105 构成：操作数、运算符、界限符 规则： （1）先乘除，后加减； （2）从左算到右； （3）先括号内，后括号外。,例五、 表达式求值,46,算符：运算符、界限符的统称 运算每一步

11、中，任意相继出现的算符1和2之间优先关系是以下3种： （1） 1 2 。,47,算符间的优先关系,48,【思路】 设置两个工作栈。一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。 首先置OPND为空栈，表达式起始符“”为运算符栈的栈底元素；依次读入表达式中每个字符，若是操作数则进OPND，若是运算符则和OPTR的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。,49,SElemType EvaluateExpression() /* 算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈 */ InitStack( ,50,case

12、:Pop(,51,3.3 栈与递归的实现,很多数学函数是递归定义的，如求阶乘、Fibonnacci数列（黄金比率）; 很多数据结构是递归定义的，如树、广义表; 很多问题用递归求解比迭代求解更简单直观，如Hanoi塔、八皇后。,一个直接调用自己或通过一系列的调用语句间接地调用自己的函数称为递归函数。是程序设计中一个强有力的工具。,52,Hanoi塔问题,这是一个非常古老的问题 ，最早提出者是古印度一寺庙僧侣，他设定的盘子数目为64，当任务完成后世界将会毁灭（经证明，最少的移动次数是2n-1，n为盘子的数目），264-1 =18446744073709551615次移动，假设计算机每秒钟能够计算1

13、0,000,000（一千万）次，那也需要58494年 。,53,如何用递归来解决这个问题？,如果只有一个盘子，直接移过去就行了，这是递归的边界条件。 如果要移动N个盘子，就要分三步走： （1）把N-1个盘子移动到中间的杆子上（把右边的杆子作为临时存放盘子的位置）。 （2）把最后一个盘子直接移到右边的杆子上。 （3）最后把中间杆子上的N-1个盘子移到右边的杆子上（把左边的杆子作为临时存放盘子的位置）。 上面第一、三步用到了递归。我们看到，通过递归把n个盘子的问题变成了两个n-1个盘子的问题。如此下去，最后就变成了2n-1个一个盘子的问题了。,54,void hanoi (int n, char

14、x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至n / 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。 if (n=1) move(x, 1, z); / 将编号为的圆盘从x移到z else hanoi(n-1, x, z, y); / 将x上编号为至n-1的 /圆盘移到y, z作辅助塔 move(x, n, z); / 将编号为n的圆盘从x移到z hanoi(n-1, y, x, z); / 将y上编号为至n-1的 /圆盘移到z, x作辅助塔 ,完整实现及调用代码：,55,将所有的实参数、返回地址等信息传递给被调用函数保存; 为被调用函数的局部变量分配

15、存储区; 将控制转移到被调用函数的入口。,当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：,56,保存被调函数的计算结果; 释放被调函数的数据区; 依照被调函数保存的返回地址将控制转移到调用函数。,从被调用函数返回调用函数之前，应该完成下列三项任务：,57,多个函数嵌套调用的规则是:,此时的内存管理实行“栈式管理”,后调用先返回 ！,例如： void main( ) void a( ) void b( ) a( ); b( ); /main / a / b,Main的数据区,函数a的数据区,函数b的数据区,58,递归工作栈：递归过程执行过程中占用的 数据区。

16、递归工作记录：每一层的递归参数合成 一个记录。 当前活动记录：栈顶记录指示当前层的 执行情况。 当前环境指针：递归工作栈的栈顶指针。,递归函数执行的过程可视为同一函数进行嵌套调用,参看多媒体算法演示课件,59,ADT Queue 数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头， an 端为队列尾,基本操作：,3.4 队列的类型定义, ADT Queue,60,队列的基本操作：,InitQueue( struct QNode *next; QNode, *QueuePtr;,链队列链

17、式映象,70,typedef struct / 链队列类型 QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;,a1,an,Q.front Q.rear,Q.front Q.rear,空队列,71,Status InitQueue (LinkQueue ,72,Status EnQueue (LinkQueue ,73,Status DeQueue (LinkQueue ,74,#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存储空间 int fro

18、nt; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素 SqQueue;,队列顺序映象,75,初始化顺序队列时，令front=rear=0，每当插入新的队列元素时，尾指针rear加1，每当删除对头元素时，头指针front也加1。因此该顺序队列再经过多次插入或删除元素操作之后将会导致指针到达队列的最大长度而不能继续使用！ 称为顺序队列的“假上溢”。,76,为解决“假上溢”问题，可以把向量空间想象为一个首尾相连的原环，称为“循环队列”。使用循环队列的最主要的技术问题是如何判断其“满”和“空”的状态。我们可有以下三种方法： 1）另设一布

19、尔变量区别队列的空和满。 2）使用一个计数器记录队列中元素的总数（队列长度） 3）少用一个元素的存储空间，约定以“队列头指针在队列尾指针的下一位置上”（即尾指针在循环意义下加1后等于头指针。注意尾指针rear所指单元始终为空）作为队列满的标志。,77,#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素 的下一个位置 SqQueue;,循环队列顺序映象,78,Status

20、InitQueue (SqQueue ,79,Status EnQueue (SqQueue ,80,Status DeQueue (SqQueue ,81,利用循环队列的算法思想，解决约瑟夫环问题。 用顺序表（数组）存储约瑟夫环结构，当进行密码报数时，采用循环意义下的报数，即： m=m%(L.length) 请使用该思路编辑程序实现约瑟夫环！,82,1. 掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。 2. 熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。 3. 熟练掌握循环队列和链队列的基本操作与实现算法，特别注意队满和队空的描述方法。 4. 理解递归算法执行过程中栈的状态变化过程。,本章小结,83,实验三 栈和队列及其应用（题集P96 2.1）,实验目的 深入了解栈和队列的特性，以便在实际问题