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

1、 第三章第三章 栈和队列栈和队列主要内容主要内容v栈的概念、存储结构及其基本操作栈的概念、存储结构及其基本操作v栈的应用栈的应用v队列的概念、存储结构及其基本操作队列的概念、存储结构及其基本操作 3.1 3.1 栈栈栈的定义栈的定义v栈作为一种限定性线性表，是将线性表的插入和栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行。删除运算限制为仅在表的一端进行。v通常将表中允许进行插入、删除操作的一端称为通常将表中允许进行插入、删除操作的一端称为栈顶栈顶(Top)(Top)，因此栈顶的当前位置是动态变化的，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。

2、同时它由一个称为栈顶指针的位置指示器指示。同时表的另一端被称为栈底表的另一端被称为栈底(Bottom)(Bottom)。v当栈中没有元素时称为空栈。当栈中没有元素时称为空栈。v栈的插入操作被形象地称为进栈或入栈，删除操栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。作称为出栈或退栈。栈的定义续栈的定义续v假设栈假设栈S=(aS=(a1 1，a a2 2，a a3 3，aan n)，则，则a a1 1称为栈底元素，称为栈底元素，a an n为栈顶元素。栈中元素按为栈顶元素。栈中元素按a a1 1，a a2 2，a a3 3，aan n的次的次序进栈，退栈的第一个元素应为栈顶元素。换句

3、序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出（此，栈称为后进先出（LIFOLIFO）的线性表。）的线性表。a1a2an入栈入栈出栈出栈栈顶栈顶栈底栈底入栈入栈出栈出栈火火车车调调度度栈的定义续栈的定义续v栈的抽象数据类型定义栈的抽象数据类型定义 ADT StackADT Stack 数据对象：数据对象：D=aD=ai i|a|ai i ElemSet,i=1,2,n,n0ElemSet,i=1,2,n,n0,数据关系：数据关系：R R1 1=a ai-1i-1,a,ai i|a|ai-1i-1,

4、a,ai i D,i=2,nD,i=2,n，约定约定a an n端为栈顶，端为栈顶，a a1 1端为栈底。端为栈底。基本操作：基本操作：InitStack(&S)InitStack(&S)：将：将S S初始化为空栈。初始化为空栈。DestroyStack(&S)DestroyStack(&S)：栈：栈S S被销毁。被销毁。ClearStack(&S)ClearStack(&S)：将栈：将栈S S置成空栈。置成空栈。StackEmpty(S)StackEmpty(S)：若空栈，则返回真，否则假。：若空栈，则返回真，否则假。StackLength(S)StackLength(S)：返回元素个数，即

5、栈的长度。：返回元素个数，即栈的长度。GetTop(S,&e)GetTop(S,&e)：用：用e e返回返回S S的栈顶元素。的栈顶元素。Push(&S,e)Push(&S,e)：插入元素：插入元素e e为新的栈顶元素。为新的栈顶元素。Pop(&S,&e)Pop(&S,&e)：删除：删除S S的栈顶元素，值给的栈顶元素，值给e e。StackTraverse(S,visit()StackTraverse(S,visit()：遍历栈。：遍历栈。ADT StackADT Stack栈的顺序存储栈的顺序存储v顺序栈的定义顺序栈的定义v顺序栈是用顺序存储结构实现的栈，即利用一组地址连续顺序栈是用顺序存

6、储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。的存储单元依次存放自栈底到栈顶的数据元素。v栈的顺序存储结构定义栈的顺序存储结构定义#define STACK_INIT_SIZE 100 /存储空间初始分配量存储空间初始分配量#define STACKINCREMENT 10 /存储空间分配增量存储空间分配增量 typedef struct SElemType *base;/栈底指针栈底指针 SElemType *top /栈顶指针栈顶指针 int stacksize;/当前已分配的存储容量当前已分配的存储容量 SqStack;称称basebase为栈底指针，在顺序

7、栈中，它始终指向栈底的位置，为栈底指针，在顺序栈中，它始终指向栈底的位置，若若basebase的值为的值为NULLNULL，则表明栈结构不存在。，则表明栈结构不存在。称称toptop为栈顶指针，其初始值指向栈底，即为栈顶指针，其初始值指向栈底，即top=basetop=base可作为可作为栈空的标记，每当插入新的栈顶元素时，指针栈空的标记，每当插入新的栈顶元素时，指针toptop增增1 1；删除；删除栈顶元素时，指针栈顶元素时，指针toptop减减1 1。因此，非空栈中的栈顶指针始终。因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。在栈顶元素的下一个位置上。basetopbasetopA

8、basetopABCDbasetopABC栈的链式存储栈的链式存储v若是栈中元素的数目变化范围较大或若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使不清楚栈元素的数目，就应该考虑使用用链式存储结构链式存储结构。v将用链式存储结构表示的栈称作将用链式存储结构表示的栈称作“链链栈栈”。链栈通常用一个无头结点的单。链栈通常用一个无头结点的单链表表示。链表表示。v由于栈的插入删除操作只能在一端进由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶所

9、以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指端，即将单链表的头指针作为栈顶指针。针。topdatanext3.2 3.2 栈的应用举例栈的应用举例1.1.数制转换数制转换【例】十进制数转换成二进制数【例】十进制数转换成二进制数 使用展转相除法将一个十进使用展转相除法将一个十进制数值转换成二进制数值。即用制数值转换成二进制数值。即用该十进制数值除以该十进制数值除以2 2，并保留其余，并保留其余数；重复此操作，直到该十进制数；重复此操作，直到该十进制数值为数值为0 0为止。最后将所有的余数为止。最后将所有的余数反向输出就是所对应的二进制数反向输出就是所对应的二进制数值。值。例如：

10、例如：(692)(692)1010=(1010110100)=(1010110100)2 2 先把余数一味地入栈，完成后进行先把余数一味地入栈，完成后进行一边出栈一边输出即可。一边出栈一边输出即可。2 2 括号匹配检查括号匹配检查v程序中经常用到括号：圆括号程序中经常用到括号：圆括号()()，中括号，中括号 和花括号和花括号 。v正确地使用括号是要配对，其嵌套任意。正确地使用括号是要配对，其嵌套任意。v正确格式如：正确格式如：()()、()()。v不正确格式如：不正确格式如：()()、()()。v可以使用括号栈来完成括号匹配检查。可以使用括号栈来完成括号匹配检查。3 3 行编辑程序行编辑程序v

11、一个简单的行编辑程序的功能是：接受用户从一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。终端输入的程序或数据，并存入用户的数据区。由于用户在终端上进行输入时，不能保证不出由于用户在终端上进行输入时，不能保证不出差错，因此，若在编辑程序中，差错，因此，若在编辑程序中，“每接受一个每接受一个字符即存入用户数据区字符即存入用户数据区”的做法显然不是最恰的做法显然不是最恰当的。当的。v例如：当用户发现刚刚键入的一个字符是错的例如：当用户发现刚刚键入的一个字符是错的时，可以补进一个时，可以补进一个退格符退格符“#”“#”，以表示前一个，以表示前一个字符无效；如果发现当前

12、输入的行内差错较多字符无效；如果发现当前输入的行内差错较多或难以补救，则可以键入一个或难以补救，则可以键入一个退行符退行符“”“”，以，以表示当前行中的字符均无效。表示当前行中的字符均无效。行编辑程序续行编辑程序续例如：假设从终端接收了如下两行字符：例如：假设从终端接收了如下两行字符：whli#ilr#e(s#whli#ilr#e(s#*s)s)outchaputchar(outchaputchar(*s=#+);s=#+);则实际有效的是下列两行：则实际有效的是下列两行：while(while(*s)s)putchar(putchar(*s+);s+);可设一个存放一行的栈，每当从终端接受了

13、一个字符之可设一个存放一行的栈，每当从终端接受了一个字符之后作如下判别：后作如下判别：如果它既不是如果它既不是退格符退格符也不是也不是退行符退行符，则将该字符压入栈；，则将该字符压入栈；如果是一个退格符，则从栈顶删去一个字符；如果是一个退格符，则从栈顶删去一个字符；如果它是一个退行符，则将字符栈清空。如果它是一个退行符，则将字符栈清空。一行结束，表示行编辑完成。一行结束，表示行编辑完成。4 4 迷宫求解迷宫求解v迷宫求解通常用迷宫求解通常用“穷举求解穷举求解”的方法。的方法。v从入口出发，顺某一方向向前探索，若能走通，从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一

14、个方向则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为再继续探索，直至所有可能的通路都探索到为止。止。v为了保证在任何位置上都能沿原路退回，显然为了保证在任何位置上都能沿原路退回，显然需要一个后进先出栈来保存沿路的位置信息。需要一个后进先出栈来保存沿路的位置信息。入口入口出口出口5 5 表达式求值表达式求值v表达式求值是高级语言编译中的一个基本问题，表达式求值是高级语言编译中的一个基本问题，即即“算符优先法算符优先法”，是栈的典型应用实例。，是栈的典型应用实例。v任何一个表达式都是由操作数任何一个表达式都是由操作数(operand)(operand)、运运算符算

15、符(operator)(operator)和界限符和界限符(delimiter)(delimiter)组成的。组成的。v操作数既可以是常数，操作数既可以是常数，也可以是被说明为变量也可以是被说明为变量或常量的标识符；或常量的标识符；v运算符可以分为算术运算符、关系运算符和逻运算符可以分为算术运算符、关系运算符和逻辑运算符三类；辑运算符三类；v基本界限符有左右括号和表达式结束符等。基本界限符有左右括号和表达式结束符等。表达式求值续表达式求值续假设操作数是整型常数，运算符只含加、减、乘、假设操作数是整型常数，运算符只含加、减、乘、除等四种运算符，界限符有左右括号和表达式起始、除等四种运算符，界限符

16、有左右括号和表达式起始、结束符结束符“”，引入表达式起始、结束符是为了方，引入表达式起始、结束符是为了方便。便。要对一个简单的算术表达式求值，首先要了解算术要对一个简单的算术表达式求值，首先要了解算术四则运算的规则。四则运算的规则。先乘除，后加减；先乘除，后加减；从左算到右；从左算到右；先括号内，后括号外。先括号内，后括号外。1 1与与2 2的优先关系表的优先关系表/()#/(#=1215步骤操作数栈操作符栈输入串动作1#(7+15)*(23-28/4)#(,7,+,15分别进栈2#7 15#(+)*(23-28/4)#运算，7+15=223#22#()*(23-28/4)#(出栈，*进栈4#

17、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=35210#352#弹出结果352如求表达式值：（如求表达式值：（7+157+15）*（23-28/423-28/4）。）。3.3 3.3 栈与递归的实现栈与递归的实现v栈在程序设计中实现递归调用，即直接调用自己的函数，称为递归函数。v如阶乘函数：v2阶Fibonacci数列：vAckerman函数：其它若若 )1,(,

18、1(0 )1,1(0 1),(nmAckmAcknmAckmnnmAck1 )1()1(1 10 0)(nnFibnFibnnnFib若若若0 )1(0 1)(nnFactnnnFact若若17v例，n阶汉诺塔问题。假设有3个分别命名为X、Y和Z的塔座，在X塔座上插有n个直径各不相同、依小到大编号的圆盘。现要求将X塔座上的n个圆盘移到这塔座上并仍按同样的顺序排，圆盘移动时必须遵循以下规则：1）每次只能移动一个圆盘；2）圆盘可以插在任一XYZ塔座上；3）任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。3阶汉诺塔abcdefghv例，n阶汉诺塔问题的C函数实现。void hanoi(int n,

19、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 3.4 3.4 队列队列队列的定义队列的定义v队列队列(Queue)(Queue)是另一种限定性的线性表，它只允是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，许在表的一端插入元素，而在另一端删除元素，所以队列具有所以

20、队列具有先进先出先进先出(Fist In Fist Out(Fist In Fist Out，缩缩写为写为FIFO)FIFO)的特性。的特性。v在队列中，允许插入的一端叫做在队列中，允许插入的一端叫做队尾队尾(rear)(rear)，允，允许删除的一端则称为许删除的一端则称为队头队头(front)(front)。v当队列中没有元素时称为当队列中没有元素时称为空队列空队列。队列的定义续队列的定义续v假设队列为假设队列为q=(aq=(a1 1,a,a2 2,a,an n)，那么，那么a a1 1就是队头元就是队头元素，素，a an n则是队尾元素。队列中的元素是按照则是队尾元素。队列中的元素是按照

21、a a1 1,a,a2 2,a,an n的顺序进入的，的顺序进入的，退出队列也必须按照退出队列也必须按照同样的次序依次出队，也就是说，只有在同样的次序依次出队，也就是说，只有在a a1 1,a,a2 2,a,an-1n-1都离开队列之后，都离开队列之后，a an n才能退出队列。才能退出队列。入队列入队列出队列出队列a1 a2 an队队尾尾队队头头队列的定义续队列的定义续v队列的抽象数据类型定义队列的抽象数据类型定义 ADT Queue ADT Queue 数据对象：数据对象：D=aD=ai i|a|ai i ElemSet,i=1,2,n,n0ElemSet,i=1,2,n,n0,数据关系：

22、数据关系：R R1 1=a ai-1i-1,a,ai i|a|ai-1i-1,a,ai i D,i=2,nD,i=2,n，约定其中约定其中a a1 1端为队头，端为队头，a an n端为队尾。端为队尾。基本操作：基本操作：InitQueue(&Q)InitQueue(&Q)：将：将Q Q初始化为空队列。初始化为空队列。DestroyQueue(&Q)DestroyQueue(&Q)：队列：队列Q Q被销毁。被销毁。ClearQueue(&Q)ClearQueue(&Q)：将：将Q Q清为空队列。清为空队列。QueueEmpty(Q)QueueEmpty(Q)：若：若Q Q为空队列，则返回真，否

23、则返回假。为空队列，则返回真，否则返回假。QueueLength(Q)QueueLength(Q)：返回：返回Q Q的元素个数，即队列的长度。的元素个数，即队列的长度。GetHead(Q,&e)GetHead(Q,&e)：用：用e e返回返回Q Q的队头元素。的队头元素。EnQueue(&Q,e)EnQueue(&Q,e)：插入元素：插入元素e e为为Q Q的新的队尾元素。的新的队尾元素。DeQueue(&Q,&e)DeQueue(&Q,&e)：删除：删除Q Q的队头元素，并用的队头元素，并用e e返回其值。返回其值。QueueTraverse(Q,visit():QueueTraverse(

24、Q,visit():遍历队列。遍历队列。ADT Queue ADT Queue链队列队列的链式表示和实现链队列队列的链式表示和实现v链队列的定义链队列的定义v用链表表示的队列简称为用链表表示的队列简称为链队列链队列。一个链队列需要两个指针一个链队列需要两个指针才能唯一确定，它们分别指才能唯一确定，它们分别指示队头和队尾（分别称为示队头和队尾（分别称为头头指针指针和和尾指针尾指针）。）。与线性表的单链表一样，与线性表的单链表一样，为了操作方便起见，为了操作方便起见，给链给链队列添加一个头结点，并令队列添加一个头结点，并令头指针指向头结点。由此，头指针指向头结点。由此，空的链队列的判别条件为头空的

25、链队列的判别条件为头指针和尾指针均指向头结点。指针和尾指针均指向头结点。链队列续链队列续链队列的操作即为单链表的插入和删除操作的特链队列的操作即为单链表的插入和删除操作的特殊情况，只是需要修改尾指针或头指针殊情况，只是需要修改尾指针或头指针。Q.frontQ.rear(a)空队列AQ.frontQ.rear(b)元素A入队Q.frontABQ.rear(c)元素B入队ABABQ.frontQ.rear(d)元素A出队链队列续链队列续链队列存储结构定义链队列存储结构定义 循环队列队列的顺序表示和实现循环队列队列的顺序表示和实现v队列的顺序存储结构队列的顺序存储结构v队列的顺序存储结构和顺序栈类似

26、，在队列的顺序队列的顺序存储结构和顺序栈类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，还需要设置头存放从队列头到队列尾的元素之外，还需要设置头尾两个指针尾两个指针frontfront和和rearrear，分别指示队列头元素及，分别指示队列头元素及队尾元素的位置。队尾元素的位置。v约定：初始化建立空队列时，令约定：初始化建立空队列时，令front=rear=0front=rear=0，每，每当插入新的队尾元素时，当插入新的队尾元素时，“尾指针增尾指针增1”1”；每当删；每当删除队头元素时，除队头元素时，“

27、头指针增头指针增1”1”。v在非空队列中，头指针始终指向队列头元素，尾指在非空队列中，头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置。针始终指向队列尾元素的下一个位置。Q.front 540123Q.rear(b)J(b)J1 1、J J2 2、J J3 3相继入队相继入队J1J2J3 Q.front 540123Q.rear(a)(a)空队列空队列 Q.front 540123Q.rear(c)J(c)J1 1、J J2 2相相继出队继出队J3 Q.front 540123Q.rear(d)J(d)J4 4、J J5 5、J J6 6相继入队后，相继入队后，J J3 3、J

28、J4 4相继出队相继出队J5J6循环队列续循环队列续因为在入队和出队的操作中，头尾指针只增加因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现超出向量空间的上界而不能做入队操作。该现象称为象称为假溢出假溢出。解决办法：将顺序队列臆造为一个环状的空间，解决办法：将顺序队列臆造为一个环状的空间，称之为称之为循环队列循环队列。在在C

29、C语言中，不能用动态分配的一维数组来实现语言中，不能用动态分配的一维数组来实现循环队列。循环队列。如果应用程序中设有循环队列，则必须为它设如果应用程序中设有循环队列，则必须为它设定一个最大队列长度；若无法预估所用队列的定一个最大队列长度；若无法预估所用队列的最大长度，则宜采用链队列。最大长度，则宜采用链队列。循环队列续循环队列续012354rearfront(c)空队列012354(a)一般情况J3J4J5frontrear012354J7J3(b)队列满frontrearJ4J5J6J8此时，此时，Q.front=Q.rearQ.front=Q.rear此时，此时，Q.front=Q.rea

30、rQ.front=Q.rear问题：只凭等式问题：只凭等式Q.front=Q.front=Q.rearQ.rear无法判别队列空间无法判别队列空间是空还是满。是空还是满。循环队列续循环队列续解决办法：解决办法：可再设置一个布尔变量来区分队空和队满。可再设置一个布尔变量来区分队空和队满。或者不设布尔变量，而把尾指针加或者不设布尔变量，而把尾指针加 1 1 后等于头指针作后等于头指针作为队满的标志。这意味着损失一个空间，或者反过来为队满的标志。这意味着损失一个空间，或者反过来说，说，必须用有必须用有MAXSIZE+1MAXSIZE+1个元素的数组才能表示一个个元素的数组才能表示一个长度为长度为MA

31、XSIZEMAXSIZE的循环队列。的循环队列。循环队列队列的顺序存储结构定义循环队列队列的顺序存储结构定义#define MAXSIZE 100#define MAXSIZE 100 /最大队列长度最大队列长度typedef struct typedef struct QElemType QElemType*base;base;/初始化的动态分配存储空间基址初始化的动态分配存储空间基址 int front;int front;/头指针，若队列不为空，指向队列头元素头指针，若队列不为空，指向队列头元素 int rear;int rear;/尾指针，若队列不为空，尾指针，若队列不为空，/指向队列尾元素的下一个位置指向队列尾元素的下一个位置SeqQueue;SeqQueue;