第三章 栈和队列.docx

1、第三章 栈和队列第三章 栈和队列引入：栈是线性表的子类或受限的线性表。 （不受限的一般线性表操作情形）头部或尾部 尾部或头部线性表的可能扩展情形：3-1 栈(stack)的概念3-1-1现实生活中的例子例1 串碟问题例2 铁路调度问题例3 死胡同问题（单人行）例4 饼干筒问题例5 弹夹中装子弹问题思考题：再想若干与此相似的例子。3-1-2 栈的特点push(入栈/压入) pop(出栈/弹出) 栈顶元素 栈顶(Top) 栈中的一般元素 栈底(Bottom)栈底元素图3-1 栈结构示意图仅在线性表的尾部进行插入、删除操作的线性表。如图3-1所示：3-1-3 相关术语LIFO(Last In Fir

2、st Out)-后进先出 (或FILO)。栈顶(Top)、栈底(Bottom)、栈顶元素(Top Element)、栈底元素(Bottom Element)。入栈或压栈或压入(Push)、出栈或弹出(Pop)。3-1-4 栈结构的抽象数据类型定义设S是一个栈结构，e表示栈中元素，则其抽象数据类型定义如下：ADT Stack 数据对象：数据关系：，其中为栈顶，为栈底。基本操作：InitStack(&S)-构造空栈S。/栈结构通过指针型参数S返回。DestroyStack(&S)-销毁栈S。ClearStack(&S)-清空栈S。StackEmpty(S)-若S为空栈，则返回TRUE，否则返回FA

3、LSE。Push(&S,e)-压栈。 /将元素e压入S的当前栈顶。Pop(&S,&e)-出栈。/将栈S中栈顶元素弹出并放入e中。GetTop(S,&e)-获得栈顶元素e。但栈顶位置不变。StackLen(S)-返回栈S中元素的个数，或栈的长度。StackTraverse(S,visit()-从栈底到栈顶，依次对每个元素用visit()处理，一旦visit()失败，则操作失败。 ADT Stack注：栈中数据元素的类型根据应用的需要具体定义。3-1-5 栈结构的表示与实现方法3-1-5-1 顺序栈的存储结构(1) 基本思想：用一组连续的存储单元，依次存放栈之元素。设指向栈顶的元素之指针为Top，

4、指向栈底的元素指针为Bottom。如图3-2所示。 aTop a1 a0 baseBottom=0图3-2 顺序栈的存储结构(2) 栈的基本结构描述typedef struct SElemType *base;/Bottom指针 SElemType *top;/Top指针 int stackSize;/当前栈的大小 sqStack；(3) 其它假设其中，可以设置两个基本的常量如下：STACK_INIT_SIZE-栈的初始大小。表示对栈存储结构进行初始分配空间的数据元素个数。STACKINCREMENT-栈的增量步长。表示对栈的存储空间进行一次增、减时的元素个数。Top所指的位置是栈顶元素的下一

5、相邻单元。因此，在此假设下，进栈和出栈的栈顶元素操作如下：进栈：a Top=e; Top+=1;出栈：e=aTop-1; Top-;3-1-5-2 顺序栈的实现算法描述顺序栈的ADT定义(见教材P46-47)。(1) 空栈判定方法Status StackEmpty(SqStack S) /栈为空返回TRUE，否则返回FALSEif (S.top=S.base) return TRUE;else return FALSE;/StackEmpty(2) 获取栈顶元素的方法Status GetTop(SqStack S, SelemType &e) /若栈不空，栈顶元素存入e，返回OK。否则，返回E

6、RROR。if (S.top=S.base) return ERROR;/栈空时返回ERRORe=*(S.top-1);return OK; /GetTop(3) 压栈操作方法Stack Push(SqStack &S, SelemType e)if(S.top-S.base)=S.stackSize) /栈满处理：增加新单元S.base=(ElemType*)realloc(S.base,(S.stackSize+STACKINCREMENT)*sizeof(ElemType);if(!S.base) exit(OVERFLOW); /重新分配时失败S.top=S.base+S.stackS

7、ize; /重新设置栈顶及栈的大小信息S.stackSize+=STACKINCREMENT;*S.top+=e;return OK; /Push(4) 出栈操作方法Stack Pop(SqStack &S, SelemType &e)if(S.top=S.base) return ERROR; /栈空处理e=*-S.top;return OK; /Pop(5) 栈的初始化方法1) 顺序分配长度为STACK_INIT_SIZE的空间；其中单元空间的大小由类型ElemType决定。S.base为空间之底部地址。2) S.top=S.base;/置为空栈3) S.stackSize=STACK_I

8、NIT_SIZE;/记录栈的大小4) 返回栈结构的指针值&S;/sqStack S类型(6) 其它基本操作的实现方法（作为课外作业和上机作业）3-1-5-3 栈结构的实现方法的进一步讨论栈结构的具体实现可以用数组的方法、简单链表的方法和教材中的方法。以下分别加以讨论：1) 数组的方法设top,base为a数组的下标数据类型，数组的大小为aN。则:栈的初始状态为top=base=0；栈满状态为top=N；栈空状态为top=0或top=base；其它操作类似。优点：直接采用程序语言内部支持的简单数据结构表示栈结构。缺点：栈的大小不能改变，必须预先分配好。空间利用率不高，且不灵活。关键操作：Pop(

9、): top-;e=atop;Push():atop=e;top+;GetTop():e=atop-1;2) 链表的方法设top,base为结点类型的指针，在此结构下栈的大小是可变的。栈的初始状态为top=base=NULL；栈满状态时表示整个可用内存空间已用完；栈空表示为top=base；其它操作类似，但Push()和Pop()操作时，要注意内存空间的及时申请与回收。优点：内存空间分配时不用分配多余的空间预留。栈的大小是可变的。缺点：每一次Push()或Pop()都要申请或释放空间，操作太频繁。关键操作：Pop(): top1=top;top=top-next;e=top-data;free

10、(top1);Push():top1=top;top-data=e;top=new();top-next=top1;GetTop():e=(top-next)-data;3) 教材上的方法采用SqStack,SelemType等结构，利用STACKINCREMENT增量控制栈大小的改变步长。是前面两种方法的折中。优点：栈的大小是可改变的，同时，对内存空间的分配与释放频率又是人为可控的，比简单链表的方法好。缺点：空间利用率稍次于简单链表法，但好于简单数组法。关键操作：见3-1-5-2节算法描述。思考题：多个栈同时存在时，如何充分利用有限的内存空间？课外作业：以以上三种结构中的一种为准，完成栈结构

11、的基本操作算法，并上机实现之。3-2 栈的应用举例例3-1 数制之间的转换问题（即10#2#）。规则：除2取余倒排序。分析：转换关系为 。当时，打印出d#数。由于人们书写数时是从高位向低位方向进行（左右），但计算时是从低位向高位方向进行（右左），因此，实现时自然想到用栈结构来描述之。例如：(83)10=(1100101)2其中，除2取余的计算过程可以用将余数进栈的方法实现，而倒排序的过程用出栈的方法实现。如图3-3所示。 Top 输出顺序：1100101 1 1 83 0 1 41 1 0 20 push 0 pop 0 10 0 1 5 1 0 2 1 除2取余顺序 1base图3-3 除2

12、取余倒排序的进栈和出栈过程示意图余数出栈余数进栈初始化输出结果图3-4 使用栈结构实现2#-10#转换的流程图结构使用栈结构实现2#-10#转换的好处：简化了程序设计问题。使问题变成了简单的顺序模块化结构。如下所示：课外作业：1) 用其它方法实现这一转换过程，并比较两者的差异 2) 栈以不同的方法实现，如数组、链表、可变顺序结构等。例3-2 括号匹配检查问题：“(” 和“)”匹配“” 和“”嵌套使用时的配对匹配问题。基本规则：匹配对象按先内后外原则。要求：括号对完全匹配时返回TRUE，否则返回FALSE。基本思想（分析）：对给定的带括号字符串，按以下规则扫描进行进栈、出栈操作，如果扫描结束时，

13、栈为空则说明给定的字符串中括号是匹配的，否则说明括号不匹配。进栈、出栈处理规则：当栈顶括号与当前括号匹配时，栈顶数据或元素或括号出栈，否则，当前括号进栈。例如：“()”的处理过程如图3-5所示。 top “” “” “” “)” “” ( ( ( ( top base base图3-5 括号匹配检查问题的进栈和出栈过程操作示意图课外作业：画出本例问题的以栈为数据结构的程序处理流程图，并上机实现之。例3-3 行编辑程序问题。假设：按字符行接受输入，并存入数据区。其中，#表示退格符号（即表示前一输入符号是无效字符）；表示退行符号（即表示当前行已有的输入内容无效）。例如：whil#ilr#e(s#*

14、s) while(*s) outchaputchar(*s=#+) putchar(*s+)实现思想：设用一个N行的字符数组ppN存放未经处理的N行原始字符串，pp_okN分别存放处理后的字符串，则循环N次可分别处理每一行。每一行的处理过程根据假设，可以借助栈结构来完成之。如图3-6所示。 whli#ilr#e(s#*s) )s*(elihw while(*s)base top base top (顺序线性表结构) (处理之前的pp栈) (处理过后的pp_ok_temp栈) (最后的结果pp_ok)图3-6 行编辑程序借助栈结构处理一行的过程示意图课外作业：1) 画出本例两个串的进栈、出栈处理

15、过程。2) 以栈为数据结构，给出本例的程序处理流程图，并上机实现之。例3-4 迷宫求解问题：求迷宫的入口到出口所经过的路径。问题还可分细为很多：一是有无到达出口的路径，二是有多少条路径，三是最短路径和最长路径。本例只解决如何求出一条从入口到出口的一条路径问题。问题分析：假设从当前点要向前探索一条路径时，有四个方向（东、南、西、北）分别用1、2、3、4编号表示，则每次探索可以依此顺序进行。在探索失败后退回时，其表现出的特点是后探索的地方要先退到用栈结构来表示已探索的路径信息。另外，对迷宫中的任一点，数据结构应当能够表示出：1) 该点是可通路径还是墙面(0和1)；2) 该点是否走过(但不通)(用-

16、2表示)；3) 该点已探索过的路径方向(即东、南、西、北) 4) 标记该点是否是通向出口的点(用2表示)。最后，对探索过程而言，必须随时知道当前位置，用(x,y)表示。入口012345678901o2345678o9迷宫的存储结构设计分析：以二维数组a方式表示迷宫问题。元素的取值类型为：墙用1表示，通道用0表示，已走过不通用-2表示，已走过且通的用+2表示。当前正在探索的位置：curpos(x,y)序对。已探索过的路径信息结构：(x,y,探索方向，点的状态值)探索的方法：当前路径如果可通，则将当前点入栈：(curpos，方向，点的状态值)。否则，试探该点下一方向。如果当前点4个方向都不通，则取

17、出栈顶元素作为当前点。重复以上过程。栈结构：探索点(x,y)，探索方向，点的状态值。 出口算法过程描述：do /start-迷宫出口；end-迷宫入口if (当前位置可通)将当前位置插入栈顶；if (当前位置是maze_out时) 程序结束；else 将当前位置的东邻通道作为新的当前位置；elseif (栈不空，且栈顶位置的4个方向没有探索完)当前位置的置为栈顶位置的下一相邻通道(东邻)if (栈不空，且栈顶位置的4个方向没有已经探索完)删除栈顶位置元素；从栈中找一个可通的栈顶位置或出栈直到栈空为止； while (栈不空)算法的实现描述：typedef struct /通道块的位置类型int

18、 x;int y; PosType; typedef struct /迷宫的数据结构类型int maze1010; MazeType;typedef struct /栈元素的类型int ord; /通道块在路径上的序号PosType seat; /通道块在迷宫中的“坐标位置”int di; /通道块走向下一块的“方向序号” SelemType; typedef struct /栈结构类型定义SElemType *base;SElemType *top;int stacksize; SqStack; /*/Status MazePath(MazeType maze, PosType start,

19、 PosType end)/如maze中有从start到end的通道，则将其放在栈中，并返回TRUE，否则，返回FALSEInitStack(S); curpos=start; curstep=1; /初始化doif (Pass(curpos) /当前位置未走过，且可以通过FootPrint(curpos); /在当前位置留下足迹或做标记e=(curstep,curpos,1) ; /1表示探索方向为东Push(S,e);if (curpos=end) return TRUE; /成功时返回curpos=NextPos(curpos,1); /当前位置的东邻作为新的当前位置curstep+;

20、/ifelse /当前位置不能通过时if (!StackEmpty(S) Pop(S,e);while (e.di=4 & !StackEmpty(S) /已经到第4个方向，则留下不能通过标志，并后退一步MarkPrint(e.seat);/对e.seat做不能通过标志,对应的迷宫数组元素值为-2Pop(S,e); /whileif (e.di-*/(#”:P进OPTR栈；读入下一字符；break;case “”:/栈顶优先时 取OPTR栈顶元素OP； 取OPND中的操作数a,b；/如a,b 将a OP b运算的结果送入OPND； break;case “=”:弹出运算符栈OPTR中的栈顶元素

21、； 读入下一字符P； break;3) 转2)继续处理思考题：请仔细阅读并理解教材P53页EvaluateExpression()算法。3-3* 栈与递归的实现过程3-3-1 递归函数概念递归函数：自己调用自己的现象。如果自己直接调用自己，称为直接递归，如果经过第3者调用自己，称为间接递归。递归实例：例1 画中画（绘画作品、电视画面等）。例2 山里和尚的故事。例3 数学函数现象，如Fibonacci数列公式Ackerman函数公式例4 回旋针图形结构。例5 数型结构的递归(递归描述见教材P118)。例6 8皇后问题，Hanoi塔问题等问题的递归。例7 广义表(参见第5章P106)。注1：这类函

22、数和问题用递归描述和求解比爹带与循环容易。注2：递归的问题都可以化为循环去等价地实现。3-3-2 n阶Hanoi塔问题 A B C 1 3 2 4图3-3-2 4阶Hanoi塔问题的初始状态问题的描述：设有3个塔座分别称为A,B,C，在A上有n个直径大小各不相同的圆盘，并从小到大编号(如图示)。要求将此n圆盘按以下规则移到C上： 1) 3塔中的圆盘随时保持上小下大的原则；2) 每次只能移动一个圆盘；3) 每一圆盘都可出现在A,B,C上;问题的分析：(FTTB逐步求精与抽象，大问题小问题)整个问题有下面几个子问题：(1) A上面的n-1个B;(2) A最下面的第n个C;(3) B上的n-1个C;

23、显然，经过上面的一次分解，(2)已经可解，(1)和(3)的问题规模则降为n-1个圆盘问题了。重复以上过程，总是可以将其简化成一个圆盘问题的！子问题(1)可以描述成：将A上面的n-1个圆盘借助C移到B。子问题(3)可以描述成将B上n-1个圆盘借助A移到C。算法描述：/从递归函数的参数需要涉及圆盘原在塔号，圆盘个数，辅助塔号，目标塔号4个参数。/塔号的表示用字符类型数据表示，圆盘个数用整型数类型表示/圆盘的移动动作用move(原塔a，盘号n，目标c)实现，step为步数(初值为0)/printf(“%i. Move disk %i from %c to %cn”,+step,n,a,c);void Hanoi(int n, char a, char b, char c)if (n=1) move(a,1,c) /如果只有一个圆盘，则直接从a移到celsehanoi(n-1,a,c,b); /将a上面n-1个圆盘借助c移到bmove(a,n,c); /将a上的圆盘n移到chanoi(n-1,b,a,c); /将b上面n-1个圆盘借助a移到c/Hanoi函数调用的实质问题：f(x,y) firstElem();return;firstElem()main() f(x,y);ff(z,x,y);