数据结构第3章-栈和队列课件

1、 第三章 栈和队列1 第三章 栈和队列1主要内容栈的概念、存储结构及其基本操作栈的应用队列的概念、存储结构及其基本操作 2主要内容栈的概念、存储结构及其基本操作23.1 栈栈的定义栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行。通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。 33.1 栈栈的定义3栈的定义续假设栈S=(a1，a2，a3，an)，则a1称为栈底元素

2、，an为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出（LIFO）的线性表。a1a2an入栈出栈栈顶栈底入栈出栈火车调度4栈的定义续假设栈S=(a1，a2，a3，an)，则a1称栈的定义续栈的抽象数据类型定义 ADT Stack 数据对象：D=ai|aiElemSet,i=1,2,n,n0, 数据关系：R1=ai-1,ai|ai-1,aiD,i=2,n， 约定an端为栈顶，a1端为栈底。 基本操作： InitStack(&S)：将S初始化为空栈。 DestroyStack(&S)：栈S被销毁。

3、 ClearStack(&S)：将栈S置成空栈。 StackEmpty(S)：若空栈，则返回真，否则假。 StackLength(S)：返回元素个数，即栈的长度。 GetTop(S,&e)：用e返回S的栈顶元素。 Push(&S,e)：插入元素e为新的栈顶元素。 Pop(&S,&e)：删除S的栈顶元素，值给e。 StackTraverse(S,visit( )：遍历栈。 ADT Stack5栈的定义续栈的抽象数据类型定义5栈的顺序存储顺序栈的定义顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈的顺序存储结构定义 #define STACK_INIT

4、_SIZE 100 / 存储空间初始分配量 #define STACKINCREMENT 10 / 存储空间分配增量 typedef struct SElemType *base; / 栈底指针 SElemType *top / 栈顶指针 int stacksize; / 当前已分配的存储容量 SqStack;6栈的顺序存储6称base为栈底指针，在顺序栈中，它始终指向栈底的位置，若base的值为NULL，则表明栈结构不存在。称top为栈顶指针，其初始值指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1。因此，非空栈中的栈顶指针

5、始终在栈顶元素的下一个位置上。basetopbasetopAbasetopABCDbasetopABC7称base为栈底指针，在顺序栈中，它始终指向栈底的位置，若b栈的链式存储若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。topdatanext8栈的链式存储topdatanext83.2 栈的应用举例1.数制转换【例】十进制数

6、转换成二进制数 使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。例如：(692)10 = (1010110100)2 先把余数一味地入栈，完成后进行一边出栈一边输出即可。93.2 栈的应用举例1.数制转换【例】十进制数转换成二进制2 括号匹配检查程序中经常用到括号：圆括号( )，中括号 和花括号 。正确地使用括号是要配对，其嵌套任意。正确格式如：( )、( )。不正确格式如：( )、( )。可以使用括号栈来完成括号匹配检查。102 括号匹配检查103 行编辑程序一个简单的

7、行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。由于用户在终端上进行输入时，不能保证不出差错，因此，若在编辑程序中，“每接受一个字符即存入用户数据区”的做法显然不是最恰当的。例如：当用户发现刚刚键入的一个字符是错的时，可以补进一个退格符“#”，以表示前一个字符无效；如果发现当前输入的行内差错较多或难以补救，则可以键入一个退行符“”，以表示当前行中的字符均无效。113 行编辑程序11行编辑程序续例如：假设从终端接收了如下两行字符： whli#ilr#e(s#*s) outchaputchar(*s=#+); 则实际有效的是下列两行： while(*s) putchar(*

8、s+);可设一个存放一行的栈，每当从终端接受了一个字符之后作如下判别：如果它既不是退格符也不是退行符，则将该字符压入栈；如果是一个退格符，则从栈顶删去一个字符；如果它是一个退行符，则将字符栈清空。一行结束，表示行编辑完成。12行编辑程序续例如：假设从终端接收了如下两行字符：则实际有效4 迷宫求解迷宫求解通常用“穷举求解”的方法。 从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要一个后进先出栈来保存沿路的位置信息。 入口出口134 迷宫求解入口出口135 表达式求值表达式求值

9、是高级语言编译中的一个基本问题，即“算符优先法”，是栈的典型应用实例。 任何一个表达式都是由操作数(operand)、 运算符(operator)和界限符(delimiter)组成的。操作数既可以是常数， 也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符三类；基本界限符有左右括号和表达式结束符等。 145 表达式求值14表达式求值续假设操作数是整型常数，运算符只含加、减、乘、除等四种运算符，界限符有左右括号和表达式起始、结束符“”，引入表达式起始、结束符是为了方便。要对一个简单的算术表达式求值，首先要了解算术四则运算的规则。 先乘除，后加减；从左算到右； 先

10、括号内，后括号外。1与2的优先关系表/()#/(#=15表达式求值续假设操作数是整型常数，运算符只含加、减、乘、除步骤操作数栈操作符栈输入串动作1#(7+15)*(23-28/4)#(,7,+,15分别进栈2#7 15#(+)*(23-28/4)#运算，7+15=223#22#()*(23-28/4)#(出栈，*进栈4#22#*(23-28/4)#(,23,-,28分别进栈5#22 23 28#*(-/4)#/和4分别进栈6#22 23 28 4#*(-/)#运算，28/4=77#22 23 7#*(-)#运算，23-7=168#22 16#*()#(出栈9#22 16#*#出栈，22*16=

11、35210#352#弹出结果352如求表达式值：（7+15）*（23-28/4）。16步骤操作数栈操作符栈输入串动作1#(7+15)*(23-23.3 栈与递归的实现栈在程序设计中实现递归调用，即直接调用自己的函数，称为递归函数。如阶乘函数： 2阶Fibonacci数列：Ackerman函数：173.3 栈与递归的实现栈在程序设计中实现递归调用，即直接调用例，n阶汉诺塔问题。假设有3个分别命名为X、Y和Z的塔座，在X塔座上插有n个直径各不相同、依小到大编号的圆盘。现要求将X塔座上的n个圆盘移到这塔座上并仍按同样的顺序排，圆盘移动时必须遵循以下规则： 1）每次只能移动一个圆盘； 2）圆盘可以插在

12、任一XYZ塔座上； 3）任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。3阶汉诺塔18例，n阶汉诺塔问题。假设有3个分别命名为X、Y和Z的塔座，在abcdefgh19abcdefgh19例，n阶汉诺塔问题的C函数实现。 void hanoi(int n,char x,char y,char z) / 将x上编号为1n的圆盘借助y移到z if (n=1) move(x,1,z) / 将编号为1的圆盘从x到z else hanoi(n-1,x,z,y); / 将x上编号为1n-1的圆盘借助z移到y move(x,n,z); / 将编号为n的圆盘从x到z hanio(n-1,y,x,z); / 将

13、y上编号为1n-1的圆盘借助x移到z 20例，n阶汉诺塔问题的C函数实现。203.4 队列队列的定义队列 (Queue)是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出(Fist In Fist Out， 缩写为FIFO)的特性。在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。当队列中没有元素时称为空队列。 213.4 队列队列的定义21队列的定义续假设队列为q=(a1,a2,an)，那么a1就是队头元素，an则是队尾元素。队列中的元素是按照a1,a2,an的顺序进入的， 退出队列也必须按照同样的次序依次出队，也

14、就是说，只有在a1,a2,an-1都离开队列之后，an才能退出队列。入队列出队列a1 a2 an队尾队头22队列的定义续假设队列为q=(a1,a2,an)，那么a队列的定义续队列的抽象数据类型定义 ADT Queue 数据对象：D=ai|aiElemSet,i=1,2,n,n0, 数据关系：R1=ai-1,ai|ai-1,aiD,i=2,n， 约定其中a1端为队头，an端为队尾。 基本操作： InitQueue(&Q)：将Q初始化为空队列。 DestroyQueue(&Q)：队列Q被销毁。 ClearQueue(&Q)：将Q清为空队列。 QueueEmpty(Q)：若Q为空队列，则返回真，否则

15、返回假。 QueueLength(Q)：返回Q的元素个数，即队列的长度。 GetHead(Q,&e)：用e返回Q的队头元素。 EnQueue(&Q,e)：插入元素e为Q的新的队尾元素。 DeQueue(&Q,&e)：删除Q的队头元素，并用e返回其值。 QueueTraverse(Q,visit( ):遍历队列。 ADT Queue23队列的定义续队列的抽象数据类型定义23链队列队列的链式表示和实现链队列的定义用链表表示的队列简称为链队列。一个链队列需要两个指针才能唯一确定，它们分别指示队头和队尾（分别称为头指针和尾指针）。与线性表的单链表一样，为了操作方便起见， 给链队列添加一个头结点，并令头

16、指针指向头结点。由此，空的链队列的判别条件为头指针和尾指针均指向头结点。24链队列队列的链式表示和实现一个链队列需要两个指针才能唯一确链队列续链队列的操作即为单链表的插入和删除操作的特殊情况，只是需要修改尾指针或头指针。Q.frontQ.rear(a)空队列AQ.frontQ.rear(b)元素A入队Q.frontABQ.rear(c)元素B入队ABABQ.frontQ.rear(d)元素A出队25链队列续链队列的操作即为单链表的插入和删除操作的特殊情况，链队列续链队列存储结构定义typedef struct QNode /链队列结点的类型 QElemType data; struct QNo

17、de *next;QNode; *QueuePtr;typedef struct / 链队列指针类型 QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;26链队列续链队列存储结构定义typedef struct Q循环队列队列的顺序表示和实现队列的顺序存储结构队列的顺序存储结构和顺序栈类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，还需要设置头尾两个指针front和rear，分别指示队列头元素及队尾元素的位置。约定：初始化建立空队列时，令front=rear=0，每当插入新的队尾元素时，“

18、尾指针增1”；每当删除队头元素时，“头指针增1”。在非空队列中，头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置。27循环队列队列的顺序表示和实现27 Q.front 540123Q.rear(b)J1、J2、J3相继入队J1J2J3 Q.front 540123Q.rear(a)空队列 Q.front 540123Q.rear(c)J1、J2相继出队J3 Q.front 540123Q.rear(d)J4、J5、J6相继入队后，J3、J4相继出队J5J628 Q.front 540123Q.rear(b)J1、J2循环队列续因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假溢出。解决办法：将顺序队列臆造为一个环状的空间，称之为循环队列。在C语言中，不能用动态分配