《第三章 栈和队列（2）》由会员分享，可在线阅读，更多相关《第三章 栈和队列（2）（43页珍藏版）》请在金锄头文库上搜索。
1、3.2 3.2 栈与递归栈与递归递归的概念递归的概念1 1、定义是递归的、定义是递归的2 2、数据结构是递归的、数据结构是递归的3 3、问题的解法是、问题的解法是递归的递归的递归过程与递归工作栈Call Function(Call Function(Call Function(Call Function() Function(Function(Function(Function()returnreturnreturnreturn返回位置返回位置返回位置返回位置( ( ( (递归调用的下一条指令递归调用的下一条指令递归调用的下一条指令递归调用的下一条指令) ) ) )局部变量局部变量局部变量局部
2、变量参数的副本空间参数的副本空间参数的副本空间参数的副本空间工作记录工作记录工作记录工作记录递归算法有两个基本特性：一是递归算法是一种递归算法有两个基本特性：一是递归算法是一种分而治之的、把复杂问题分解为简单问题的求解问题分而治之的、把复杂问题分解为简单问题的求解问题方法方法, ,对求解某些复杂问题对求解某些复杂问题, ,递归算法分析问题的方法递归算法分析问题的方法是十分有效的；二是递归算法的时间是十分有效的；二是递归算法的时间/ /空间效率通常空间效率通常比较差。比较差。因此因此, ,对求解某些问题时对求解某些问题时, ,我们希望用递归算法分我们希望用递归算法分析问题析问题, ,用非递归算法
3、具体求解问题。这就需要把递用非递归算法具体求解问题。这就需要把递归算法转换为非递归算法。归算法转换为非递归算法。把递归算法转化为非递归算法有如下三种基本把递归算法转化为非递归算法有如下三种基本方法：方法：(1)(1)通过分析，跳过分解过程，直接用循环结通过分析，跳过分解过程，直接用循环结构的算法实现求值过程。构的算法实现求值过程。(2)(2)自己用栈模拟系统的运行时栈自己用栈模拟系统的运行时栈, ,通过分析只通过分析只保存必须保存的信息保存必须保存的信息, ,从而用非递归算法替代递归从而用非递归算法替代递归算法。算法。(3)(3)利用栈保存参数利用栈保存参数, ,由于栈的后进先出特性吻由于栈的
4、后进先出特性吻合递归算法的执行过程合递归算法的执行过程, ,因而可以用非递归算法替因而可以用非递归算法替代递归算法。代递归算法。递归算法化为非递归算法递归算法化为非递归算法1 1、用栈实现递归过程的非递归算法、用栈实现递归过程的非递归算法longFib(longn)if(n1栈结点定义栈结点定义structNodelongn;inttag;Fib(4)Fib(3)Fib(2)Fib(2)Fib(1)Fib(1)Fib(0)Fib(1)Fib(0)longFib(longn)StackS;Node*w;longsum=0;dowhile(n1)w.n=n;w.tag=1;S.Push(w);n-
5、sum=sum+n；while(!S.IsEmpty()S.Pop(w);if(w.tag=1)w.tag=2;S.Push(w);n=w.n-2;break;while(!S.IsEmpty();returnsum;2 2、用迭代法实现递归过程、用迭代法实现递归过程 适用于尾递归情形（递归调用只有一次、且位适用于尾递归情形（递归调用只有一次、且位置在过程的最后）。如逆向输出数组内容：置在过程的最后）。如逆向输出数组内容：voidrecfunc(intA,intn)if(n=0)输出输出An;n-;recfun(A,n);用迭代法实现用迭代法实现voidrecfunc(intA,intn)wh
6、ile(n=0)输出输出An;n-;3.3 3.3 队列队列 ( Queue)在在日日常常生生活活中中队队列列很很常常见见，如如，我我们们经经常常排排队队购购物物或或购购票票，排排队是体现了队是体现了“先来先服务先来先服务”（即（即“先进先出先进先出”）的原则。）的原则。队队列列在在计计算算机机系系统统中中的的应应用用也也非非常常广广泛泛。例例如如：操操作作系系统统中中的的作作业业排排队队。在在多多道道程程序序运运行行的的计计算算机机系系统统中中，可可以以同同时时有有多多个个作作业业运运行行，它它们们的的运运算算结结果果都都需需要要通通过过通通道道输输出出，若若通通道道尚尚未未完完成成输输出出
7、，则则后后来来的的作作业业应应排排队队等等待待，每每当当通通道道完完成成输输出出时时，则则从从队队列列的的队队头头退退出出作作业业作作输输出出操操作作，而而凡凡是是申申请请该该通通道道输输出出的的作作业业都都从从队队尾尾进进入入该队列。该队列。计计算算机机系系统统中中输输入入输输出出缓缓冲冲区区的的结结构构也也是是队队列列的的应应用用。在在计计算算机机系系统统中中经经常常会会遇遇到到两两个个设设备备之之间间的的数数据据传传输输，不不同同的的设设备备通通常常处处理理数数据据的的速速度度是是不不同同的的，当当需需要要在在它它们们之之间间连连续续处处理理一一批批数数据据时时，高高速速设设备备总总是是
8、要要等等待待低低速速设设备备，这这就就造造成成计计算算机机处处理理效效率率的的大大大大降降低低。为为了了解解决决这这一一速速度度不不匹匹配配的的矛矛盾盾，通通常常就就是是在在这这两两个个设设备备之之间间设设置置一一个个缓缓冲冲区区。这这样样，高高速速设设备备就就不不必必每每次次等等待待低低速速设设备备处处理理完完一一个个数数据据，而而是是把把要要处处理理的的数数据据依依次次从从一一端端加加入入缓缓冲冲区区，而而低低速速设设备从另一端取走要处理的数据。备从另一端取走要处理的数据。定义定义定义定义队列是只允许在一端删除，在另一端插入的顺序表。队列是只允许在一端删除，在另一端插入的顺序表。队列是只允
9、许在一端删除，在另一端插入的顺序表。队列是只允许在一端删除，在另一端插入的顺序表。允许删除的一端叫做队头允许删除的一端叫做队头允许删除的一端叫做队头允许删除的一端叫做队头( ( ( (frontfrontfrontfront) ) ) )，允许插入的一允许插入的一允许插入的一允许插入的一端叫做队尾端叫做队尾端叫做队尾端叫做队尾( ( ( (rearrearrearrear) ) ) )。特性特性特性特性先进先出先进先出先进先出先进先出( ( ( (FIFOFIFOFIFOFIFO, , , , First In First OutFirst In First OutFirst In First
10、 OutFirst In First Out) ) ) )队列的进队和出队队列的进队和出队 n n进队时队尾指针先进一进队时队尾指针先进一进队时队尾指针先进一进队时队尾指针先进一 rear = rearrear = rear + 1 + 1，再将新元素按再将新元素按再将新元素按再将新元素按 rearrear 指示位置加入指示位置加入指示位置加入指示位置加入( (队列不空时，队尾指针指向最后一个元素队列不空时，队尾指针指向最后一个元素队列不空时，队尾指针指向最后一个元素队列不空时，队尾指针指向最后一个元素) )。n n出队时队头指针先进一出队时队头指针先进一出队时队头指针先进一出队时队头指针先进
11、一 front = frontfront = front + 1 + 1，再将下标为再将下标为再将下标为再将下标为 front front 的元素取出。的元素取出。的元素取出。的元素取出。 ( (队列不空时，队头指针指向第一个元素的前面队列不空时，队头指针指向第一个元素的前面队列不空时，队头指针指向第一个元素的前面队列不空时，队头指针指向第一个元素的前面) )n n队满时再进队将溢出出错；队空时再出队将做队空处理。队满时再进队将溢出出错；队空时再出队将做队空处理。队满时再进队将溢出出错；队空时再出队将做队空处理。队满时再进队将溢出出错；队空时再出队将做队空处理。n n队列为空时，队尾指针对头指
12、针。队列为空时，队尾指针对头指针。队列为空时，队尾指针对头指针。队列为空时，队尾指针对头指针。（1 1）初始化）初始化：初始化一个新的队列。初始化一个新的队列。（2 2）队队列列非非空空判判断断 IsEmptyIsEmpty( ( ) )：若若队队列列不不空空，则则返返回回TRUETRUE；否则，返回否则，返回FALSEFALSE。（3 3）入入队队列列 EnQueue(xEnQueue(x) )：在在队队列列的的尾尾部部插插入入元元素素x x，使使元元素素x x成成为为新新的的队队尾尾。若若队队列列满满，则则返返回回FALSEFALSE；否否则则，返返回回TRUETRUE。（4 4）出出队队
13、列列 DeQueueDeQueue( ( ) )：若若队队列列不不空空，则则返返回回队队头头元元素素，并并从从队队头头删删除除该该元元素素，队队头头指指针针指指向向原原队队头头的的后后继继元元素素；否则，返回空元素否则，返回空元素NULLNULL。（5 5）取取队队头头元元素素 GetFrontGetFront( ( ) )：若若队队列列不不空空，则则返返回回队队头头元元素；否则返回空元素素；否则返回空元素NULLNULL。（6 6）求队列长度求队列长度 Length( )Length( )：返回队列的长度。返回队列的长度。队列的基本运算队列的基本运算队列是一种特殊的线性表，因此队列可采用顺序
14、存储结构存队列是一种特殊的线性表，因此队列可采用顺序存储结构存储，也可以使用链式存储结构存储。储，也可以使用链式存储结构存储。templateclassQueuepublic:Queue(int=10);/构造函数构造函数voidEnQueue(constType&item);/进队进队TypeDeQueue();/出队列出队列TypeGetFront();/取队头元素值取队头元素值voidMakeEmpty();/置空队列置空队列intIsEmpty()const;/判队列空否判队列空否intIsFull()const;/判队列满否判队列满否队列的抽象数据类型队列的抽象数据类型队列的抽象数据
15、类型队列的抽象数据类型循环队列循环队列 (CircularQueue)在在顺顺序序队队列列中中，当当队队尾尾指指针针已已经经指指向向了了队队列列的的最最后后一一个个位位置置时时，此此时时若若有有元元素素入入列列，就就会会发发生生“溢溢出出”。也也就就是是说说，队队列列的的存存储储空空间间并并没没有有满满，但但队队列列却却发发生生了了溢溢出出，我我们们称称这这种种现现象象为为假假溢溢出出。解解决决这这个个问问题有两种可行的方法：题有两种可行的方法：（1 1）采用平移元素的方法，当发生假溢出时，就）采用平移元素的方法，当发生假溢出时，就把整个队列的元素平移到存储区的首部，然后再插入把整个队列的元素
16、平移到存储区的首部，然后再插入新元素。这种方法需移动大量的元素，因而效率是很新元素。这种方法需移动大量的元素，因而效率是很低的。低的。（2 2）将顺序队列的存储区假想为一个环状的空间。）将顺序队列的存储区假想为一个环状的空间。我们可假想我们可假想q-queue0接在接在q-queueMAXNUM-1的的后面。当发生假溢出时，将新元素插入到第一个位置后面。当发生假溢出时，将新元素插入到第一个位置上，这样做，虽然物理上队尾在队首之前，但逻辑上上，这样做，虽然物理上队尾在队首之前，但逻辑上队首仍然在前。入队和出队仍按队首仍然在前。入队和出队仍按“先进先出先进先出”的原则的原则进行，这就是循环队列。进
17、行，这就是循环队列。很显然，方法二中不需要移动元素，操作效率高，很显然，方法二中不需要移动元素，操作效率高，空间的利用率也很高。空间的利用率也很高。存储队列的数组被当作首尾相接的表处理。存储队列的数组被当作首尾相接的表处理。存储队列的数组被当作首尾相接的表处理。存储队列的数组被当作首尾相接的表处理。队头、队尾指针加队头、队尾指针加队头、队尾指针加队头、队尾指针加1 1时从时从时从时从maxSizemaxSize - - - -1 1直接进到直接进到直接进到直接进到0 0，可用语，可用语，可用语，可用语言的取模言的取模言的取模言的取模( (余数余数余数余数) )运算实现。运算实现。运算实现。运算
18、实现。队头指针进队头指针进队头指针进队头指针进1 1: : frontfront = ( = (frontfront + 1) % + 1) % maxSizemaxSize; ;队尾指针进队尾指针进队尾指针进队尾指针进1:1:rearrear = ( = (rear rear + 1) % + 1) % maxSizemaxSize; ;队列初始化：队列初始化：队列初始化：队列初始化：frontfront=rearrear=0;=0;队空条件：队空条件：队空条件：队空条件：frontfront=rearrear; ;队满条件：队满条件：队满条件：队满条件：( (rearrear + 1) %
19、 + 1) % maxSizemaxSize = = front front 循环队列的进队和出队循环队列的进队和出队循环队列的进队和出队循环队列的进队和出队#includetemplateclassQueuepublic:Queue(int=10);Queue()deleteelements;voidEnQueue(constType&item);TypeDeQueue();TypeGetFront();voidMakeEmpty()front=rear=0;队列的数组表示队列的数组表示队列的数组表示队列的数组表示 循环队列的类定义循环队列的类定义循环队列的类定义循环队列的类定义intIsE
20、mpty()constreturnfront=rear;intIsFull()constreturn(rear+1)%maxSize=front;intLength()constreturn(front-rear+maxSize)%maxSize;private:intrear,front;Type*elements;intmaxSize;templateQueue:Queue(intsz):front(0),rear(0),maxSize(sz)elements=newTypemaxSize;assert(elements!=0);templatevoidQueue:EnQueue(cons
21、tType&item)assert(!IsFull();rear=(rear+1)%MaxSize;elementsrear=item; 循环队列部分成员函数的实现循环队列部分成员函数的实现循环队列部分成员函数的实现循环队列部分成员函数的实现templateTypeQueue:DeQueue()assert(!IsEmpty();front=(front+1)%MaxSize;returnelementsfront;templateTypeQueue:GetFront()assert(!IsEmpty();returnelementsfront;链式队列：链式队列： 下面直接给出链式栈的定义及
22、其插入和删除函数，下面直接给出链式栈的定义及其插入和删除函数，链式队列可类似定义。链式队列可类似定义。队列的应用举例队列的应用举例队列的应用举例队列的应用举例 逐行打印二项展开式逐行打印二项展开式逐行打印二项展开式逐行打印二项展开式( (a a+b b) )i i 的系数的系数的系数的系数杨辉三角形杨辉三角形(Pascalstriangle) 1 1 1 1 i = 1i = 1 1 2 1 2 1 2 1 2 1 3 3 1 3 1 3 3 1 3 1 4 6 4 1 4 1 4 6 4 1 4 1 5 10 10 5 1 5 1 5 10 10 5 1 5 1 6 15 20 15 6 1
23、 61 6 15 20 15 6 1 6分析第分析第分析第分析第 i i 行元素与第行元素与第行元素与第行元素与第 i i+1+1行元素的关系行元素的关系行元素的关系行元素的关系目的是从前一行的数据可以计算下一行的数据目的是从前一行的数据可以计算下一行的数据目的是从前一行的数据可以计算下一行的数据目的是从前一行的数据可以计算下一行的数据从第从第从第从第 i i 行数据计算并存放第行数据计算并存放第行数据计算并存放第行数据计算并存放第 i i+1+1行数据行数据行数据行数据#include#include#includequeue.hvoidYANGVI(intn)Queueq;/队列初始化队列
24、初始化q.MakeEmpty();q.EnQueue(1);q.EnQueue(1);ints=0;for(inti=1;i=n;i+)/逐行计算逐行计算coutendl;q.EnQueue(0);for(intj=1;j=i+2;j+)/处理第处理第i行行intt=q.DeQueue();q.EnQueue(s+t);s=t;if(j!=i+2)couts;利用队列打印二项展开式系数的程序利用队列打印二项展开式系数的程序110121013310Initializethequeueandadd(x,y,0)tothequeue;/x,yarethecoordinateofmazeentranc
25、e.While(queueisnotempty)(i,j,pre)=coordinatesandtheindexofthepreviousstepdequeueformqueue;for(allofeightdirectionsofcurrentposition)(g,h,p)=coordinatesofnextmoveandindexofcurrentposition(i,j);if(g=m)&(h=n)successandoutputthepath;if(!mazegh)/legalmove&(!markgh)/haventbeenherebeforemarkgh=1;add(g,h,p)
26、tothequeue;Cout“nopathfound”endl;队列的应用举例队列的应用举例队列的应用举例队列的应用举例求解迷宫问题求解迷宫问题求解迷宫问题求解迷宫问题0110011000011001110011101111001001010101111011101 2 3 4 5 6 7 8123456-1011223123123412334410 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 01371013123456789101112131415restorepathreversedDept
27、h first search: stack (need go back)Width first search: queue (do not need go back)问题：问题：1)1)在此方案中有无回朔？在此方案中有无回朔？2)2)如何输出路径？如何输出路径？队列的应用举例队列的应用举例队列的应用举例队列的应用举例 电路布线电路布线3 3 3 32 2 2 22 2 2 21 1 1 11 1 1 1a a a a1 1 1 12 2 2 22 2 2 21 1 1 12 2 2 2b b b b2 2 2 23 3 3 34 4 4 48 8 8 89 9 9 95 5 5 56 6 6
28、67 7 7 78 8 8 86 6 6 67 7 7 78 8 8 89 9 9 91010101010101010构造路径：从终点作为开始的检查点，搜索周围网格，检构造路径：从终点作为开始的检查点，搜索周围网格，检构造路径：从终点作为开始的检查点，搜索周围网格，检构造路径：从终点作为开始的检查点，搜索周围网格，检查其值是否比检查点的值小查其值是否比检查点的值小查其值是否比检查点的值小查其值是否比检查点的值小1 1 1 1，如是，则以此，如是，则以此，如是，则以此，如是，则以此网格作为新的检查点，继续查找。网格作为新的检查点，继续查找。网格作为新的检查点，继续查找。网格作为新的检查点，继续查
29、找。因为因为因为因为0 0 0 0表示可走线，表示可走线，表示可走线，表示可走线，1 1 1 1表示不可走线。为方便区别，起点以表示不可走线。为方便区别，起点以表示不可走线。为方便区别，起点以表示不可走线。为方便区别，起点以2 2 2 2表示。因此，路径的长度为终点数字表示。因此，路径的长度为终点数字表示。因此，路径的长度为终点数字表示。因此，路径的长度为终点数字-2-2-2-2。boolFongPath(Positionstart,Positionfinish,int&PathLen,Position*&path)if(start.row=finish.row&start.col=finis
30、h.col)(PathLen=0;returntrue)/到达终点到达终点intNumOfNbrs=4,i,j;/一个网格的相邻位置数一个网格的相邻位置数for(i=0;i=m;i+)/初始化网格外围墙初始化网格外围墙grid0i=gridm+1i=1;gridi0=gridim+1=1;Positionoffset4;/偏移量表偏移量表offset0.row=0;offset0.col=1;offset1.row=1;offset1.col=0;offset2.row=0;offset2.col=-1;offset3.row=-1;offset3.col=0;Positionhere,nbr
31、;here.row=start.row;here.col=sart.col;gridstart.rowstart.col=2;/封锁标记可到达的网格位置封锁标记可到达的网格位置LinkedQueueQ;/链式队列链式队列do/一圈圈向外标记一圈圈向外标记for(i=0;i=0;j-)pathi=here;/记下当前位置记下当前位置for(i=0;iNumOfNbrs;i+)/寻找前一个位置寻找前一个位置nbr.row=here.row+offseti.row;nbr.col=here.col+offseti.col;if(gridnbr.rownbr.col=j+2)break;here=nb
32、r;/移动到前一位置移动到前一位置returntrue;1 1 1 1、搜索过程（完成网格编号的过程）的时间开销、搜索过程（完成网格编号的过程）的时间开销、搜索过程（完成网格编号的过程）的时间开销、搜索过程（完成网格编号的过程）的时间开销为为为为O(mO(m2 2) )（或（或（或（或O(mnO(mn) )）; ; ; ;2 2 2 2、重构路径过程的时间开销为、重构路径过程的时间开销为、重构路径过程的时间开销为、重构路径过程的时间开销为O(PathLenO(PathLen) )，最，最，最，最坏情况下为坏情况下为坏情况下为坏情况下为O(mO(m) )（或（或（或（或O(m+nO(m+n) )
33、）; ; ; ;2 2 2 2、所以，算法的总的时间复杂度为、所以，算法的总的时间复杂度为、所以，算法的总的时间复杂度为、所以，算法的总的时间复杂度为O(mO(m2 2) )（或（或（或（或O(mnO(mn) )） 。分析：分析：3.4优先级队列优先级队列(PriorityQueue)优先级队列优先级队列优先级队列优先级队列 是不同于先进先出队列的另一种队列。是不同于先进先出队列的另一种队列。是不同于先进先出队列的另一种队列。是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。例如每次从队列中取出的是具有最高优先权的元素。例如每次从队列中取出的是具有最高优先权的元素。例
34、如每次从队列中取出的是具有最高优先权的元素。例如下表：任务的优先权及执行顺序的关系下表：任务的优先权及执行顺序的关系下表：任务的优先权及执行顺序的关系下表：任务的优先权及执行顺序的关系数字越小，优先权越高数字越小，优先权越高数字越小，优先权越高数字越小，优先权越高存储表示：顺序存储方式；链接存储方式。存储表示：顺序存储方式；链接存储方式。存储表示：顺序存储方式；链接存储方式。存储表示：顺序存储方式；链接存储方式。实现方式：实现方式：实现方式：实现方式：1 1 1 1、队尾入队，通过搜索确定出队元素。、队尾入队，通过搜索确定出队元素。、队尾入队，通过搜索确定出队元素。、队尾入队，通过搜索确定出队
35、元素。 2 2 2 2、队头出队，元素入队时调整排列次序。、队头出队，元素入队时调整排列次序。、队头出队，元素入队时调整排列次序。、队头出队，元素入队时调整排列次序。优先级队列的存储表示和实现方式优先级队列的存储表示和实现方式优先级队列的存储表示和实现方式优先级队列的存储表示和实现方式#include#include$includeconstintmaxPQSize=50;/缺省元素个数缺省元素个数templateclassPQueuepublic:PQueue();PQueue()deletepqelements;voidPQInsert(constType&item);TypePQRemo
36、ve();优先队列的类定义优先队列的类定义优先队列的类定义优先队列的类定义voidmakeEmpty()count=-1;intIsEmpty()constreturncount=-1;intIsFull()constreturncount=maxPQSize;intLength()constreturncount;private:Type*pqelements;/存放数组存放数组intcount;/队列元素计数队列元素计数templatePQueue:PQueue():count(-1)pqelements=newTypemaxPQSize;assert(pqelements!=0);/分配
37、断言分配断言templatevoidPQueue:PQInsert(constType&item)assert(!IsFull();/判队满断言判队满断言count+；pqelementscount=item;优先队列部分成员函数的实现优先队列部分成员函数的实现templateTypePQueue:PQRemove()assert(!IsEmpty();/判队空断言判队空断言Typemin=pqelements0;intminindex=0;for(inti=1;icount;i+)/寻找最小元素寻找最小元素if(pqelementsimin)/存于存于minmin=pqelementsi;/
38、记住当前最小元素记住当前最小元素minindex=i;/及其位置及其位置pqelementsminindex=pqelementscount-1;/最后一个元素填补被取走的元素最后一个元素填补被取走的元素count-;/元素个数减元素个数减1returnmin;3.5双端队列双端队列(Double-endedQueue)p队列的两端各提供队列的两端各提供队列的两端各提供队列的两端各提供3 3 3 3个存取函数：读、插入、删除个存取函数：读、插入、删除个存取函数：读、插入、删除个存取函数：读、插入、删除p两种实现方式：顺序、链接两种实现方式：顺序、链接两种实现方式：顺序、链接两种实现方式：顺序、链接
