单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第三章,栈和队列,1,第三章 栈和队列1,主要内容,栈的概念、存储结构及其基本操作,栈的应用,队列的概念、存储结构及其基本操作,2,主要内容栈的概念、存储结构及其基本操作2,3.1 栈,栈的定义,栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行。,通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端被称为栈底(Bottom)。,当栈中没有元素时称为空栈。,栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。,3,3.1 栈栈的定义3,栈的定义续,假设栈S=(a,1,，a,2,，a,3,，a,n,)，则a,1,称为栈底元素，a,n,为栈顶元素。栈中元素按a,1,，a,2,，a,3,，a,n,的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出（LIFO）的线性表。,a,1,a,2,a,n,入栈,出栈,栈顶,栈底,入栈,出栈,火车调度,4,栈的定义续假设栈S=(a1，a2，a3，an)，则a1称,栈的定义续,栈的抽象数据类型定义,ADT Stack,数据对象：,D=a,i,|a,i,ElemSet,i=1,2,n,n0,数据关系：,R,1,=,a,i-1,a,i,|a,i-1,a,i,D,i=2,n，,约定a,n,端为栈顶，a,1,端为栈底。,基本操作：,InitStack(&S)：将S初始化为空栈。,DestroyStack(&S)：栈S被销毁。,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 Stack,5,栈的定义续栈的抽象数据类型定义5,栈的顺序存储,顺序栈的定义,顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。,栈的顺序存储结构定义,#define STACK_INIT_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。因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。,base,top,base,top,A,base,top,A,B,C,D,base,top,A,B,C,7,称base为栈底指针，在顺序栈中，它始终指向栈底的位置，若b,栈的链式存储,若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用,链式存储结构,。,将用链式存储结构表示的栈称作“,链栈,”。链栈通常用一个无头结点的单链表表示。,由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。,top,data,next,8,栈的链式存储topdatanext8,3.2 栈的应用举例,1.数制转换,【例】十进制数转换成二进制数,使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。,例如：(692),10,=(1010110100),2,先把余数一味地入栈，完成后进行一边出栈一边输出即可。,9,3.2 栈的应用举例1.数制转换【例】十进制数转换成二进制,2 括号匹配检查,程序中经常用到括号：圆括号()，中括号 和花括号。,正确地使用括号是要配对，其嵌套任意。,正确格式如：()、()。,不正确格式如：()、()。,可以使用括号栈来完成括号匹配检查。,10,2 括号匹配检查10,3 行编辑程序,一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。由于用户在终端上进行输入时，不能保证不出差错，因此，若在编辑程序中，“每接受一个字符即存入用户数据区”的做法显然不是最恰当的。,例如：当用户发现刚刚键入的一个字符是错的时，可以补进一个,退格符,“#”，以表示前一个字符无效；如果发现当前输入的行内差错较多或难以补救，则可以键入一个,退行符,“”，以表示当前行中的字符均无效。,11,3 行编辑程序11,行编辑程序续,例如：假设从终端接收了如下两行字符：,whli#ilr#e(s#*s),outchaputchar(*s=#+);,则实际有效的是下列两行：,while(*s),putchar(*s+);,可设一个存放一行的栈，每当从终端接受了一个字符之后作如下判别：,如果它既不是,退格符,也不是,退行符,，则将该字符压入栈；,如果是一个退格符，则从栈顶删去一个字符；,如果它是一个退行符，则将字符栈清空。,一行结束，表示行编辑完成。,12,行编辑程序续例如：假设从终端接收了如下两行字符：则实际有效,4 迷宫求解,迷宫求解通常用“穷举求解”的方法。,从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。,为了保证在任何位置上都能沿原路退回，显然需要一个后进先出栈来保存沿路的位置信息。,入口,出口,13,4 迷宫求解入口出口13,5 表达式求值,表达式求值是高级语言编译中的一个基本问题，即“算符优先法”，是栈的典型应用实例。,任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。,操作数既可以是常数，也可以是被说明为变量或常量的标识符；,运算符可以分为算术运算符、关系运算符和逻辑运算符三类；,基本界限符有左右括号和表达式结束符等。,14,5 表达式求值14,表达式求值续,假设操作数是整型常数，运算符只含加、减、乘、除等四种运算符，界限符有左右括号和表达式起始、结束符“”，引入表达式起始、结束符是为了方便。,要对一个简单的算术表达式求值，首先要了解算术四则运算的规则。,先乘除，后加减；,从左算到右；,先括号内，后括号外。,1,与,2,的优先关系表,/,(,),#,/,(,#,=,15,表达式求值续假设操作数是整型常数，运算符只含加、减、乘、除,步骤,操作数栈,操作符栈,输入串,动作,1,#,#,(7+15)*(23-28/4)#,(,7,+,15,分别进栈,2,#7 15,#(+,)*(23-28/4)#,运算，,7+15=22,3,#22,#(,)*(23-28/4)#,(,出栈，*进栈,4,#22,#*,(23-28/4)#,(,23,-,28,分别进栈,5,#22 23 28,#*(-,/4)#,/,和,4,分别进栈,6,#22 23 28 4,#*(-/,)#,运算，,28/4=7,7,#22 23 7,#*(-,)#,运算，,23-7=16,8,#22 16,#*(,)#,(,出栈,9,#22 16,#*,#,出栈，,22*16=352,10,#352,#,#,弹出结果,352,如求表达式值：（7+15）*（23-28/4）。,16,步骤操作数栈操作符栈输入串动作1#(7+15)*(23-2,3.3 栈与递归的实现,栈在程序设计中实现递归调用，即直接调用自己的函数，称为递归函数。,如阶乘函数：,2阶Fibonacci数列：,Ackerman函数：,17,3.3 栈与递归的实现栈在程序设计中实现递归调用，即直接调用,例，n阶汉诺塔问题。假设有3个分别命名为X、Y和Z的塔座，在X塔座上插有n个直径各不相同、依小到大编号的圆盘。现要求将X塔座上的n个圆盘移到这塔座上并仍按同样的顺序排，圆盘移动时必须遵循以下规则：,1）每次只能移动一个圆盘；,2）圆盘可以插在任一XYZ塔座上；,3）任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。,3阶汉诺塔,18,例，n阶汉诺塔问题。假设有3个分别命名为X、Y和Z的塔座，在,a,b,c,d,e,f,g,h,19,abcdefgh19,例，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);/将y上编号为1n-1的圆盘借助x移到z,20,例，n阶汉诺塔问题的C函数实现。20,3.4 队列,队列的定义,队列,(Queue)是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有,先进先出,(Fist In Fist Out，缩写为FIFO)的特性。,在队列中，允许插入的一端叫做,队尾,(rear)，允许删除的一端则称为,队头,(front)。,当队列中没有元素时称为,空队列,。,21,3.4 队列队列的定义21,队列的定义续,假设队列为q=(a,1,a,2,a,n,)，那么a,1,就是队头元素，a,n,则是队尾元素。队列中的元素是按照a,1,a,2,a,n,的顺序进入的，退出队列也必须按照同样的次序依次出队，也就是说，只有在a,1,a,2,a,n-1,都离开队列之后，a,n,才能退出队列。,入队列,出队列,a,1,a,2,a,n,队尾,队头,22,队列的定义续假设队列为q=(a1,a2,an)，那么a,队列的定义续,队列的抽象数据类型定义,ADT Queue,数据对象：D=a,i,|a,i,ElemSet,i=1,2,n,n0,数据关系：R,1,=,a,i-1,a,i,|a,i-1,a,i,D,i=2,n，,约定其中a,1,端为队头，a,n,端为队尾。,基本操作：,InitQueue(&Q)：将Q初始化为空队列。,DestroyQueue(&Q)：队列Q被销毁。,ClearQueue(&Q)：将Q清为空队列。,QueueEmpty(Q)：若Q为空队列，则返回真，否则返回假。,QueueLength(Q)：返回Q的元素个数，即队列的长度。,GetHead(Q,&e)：用e返回Q的队头元素。,EnQueue(&Q,e)：插入元素e为Q的新的队尾元素。,DeQueue(&Q,&e)：删除Q的队头元素，并用e返回其值。,QueueTraverse(Q,visit():遍历队列。,ADT Queue,23,队列的定义续队列的抽象数据类型定义23,链队列队列的链式表示和实现,链队列的定义,用链表表示的队列简称为,链队列,。,一个链队列需要两个指针才能唯一确定，它们分别指示队头和队尾（分别称为,头指针,和,尾指针,）。,与线性表的单链表一样，为了操作方便起见，给链队列添加一个头结点，并令头指针指向头结点。由此，空的链队列的判别条件为头指针和尾指针均指向头结点。,24,链队列队列的链式表示和实现一个链队列需要两个指针才能唯一确,链队列续,链队列的操作即为单链表的插入和删除操作的特殊情况，只是需要修改尾指针或头指针,。,Q.front,Q.rear,(a)