课件第三章栈和队列

1、3.2 栈与递归递归的概念1、定义是递归的2、数据结构是递归的3、问题的解法是递归的递归过程与递归工作栈Call Function()Function()return返回位置(递归调用的下一条指令)局部变量参数的副本空间工作记录递归算法有两个基本特性：一是递归算法是一种分而治之的、把复杂问题分解为简单问题的求解问题方法,对求解某些复杂问题,递归算法分析问题的方法是十分有效的；二是递归算法的时间/空间效率通常比较差。因此,在求解某些问题时,我们希望用递归算法分析问题,用非递归算法具体求解问题。这就需要把递归算法转换为非递归算法。把递归算法转化为非递归算法有如下三种基本方法：(1) 通过分析，跳过

2、分解过程，直接用循环结构的算法实现求值过程。(2) 自己用栈模拟系统的运行时栈，通过分析只保存必须保存的信息，从而用非递归算法替代递归算法。(3) 利用栈保存参数，由于栈的后进先出特性吻合递归算法的执行过程，因而可以用非递归算法替代递归算法。递归算法化为非递归算法1、用栈实现递归过程的非递归算法long Fib(long n)if (n 1栈结点定义struct Node long n; int tag;Fib(4)Fib(3)Fib(2)Fib(2)Fib(1)Fib(1)Fib(0)Fib(1)Fib(0)long Fib(long n)Stack S; Node *w; long sum

3、 = 0; do while (n1) w.n = n; w.tag = 1; S.Push(w); n- 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( ); return sum;2、用迭代法实现递归过程 适用于尾递归情形（递归调用只有一次、且位置在过程的最后）。如逆向输出数组内容：void recfunc(int A, int n) if (n=0) 输出An; n-; recfun(A, n); 用迭代

4、法实现void recfunc(int A, int n) while(n=0) 输出An; n-; 3.3 队列 ( Queue )在日常生活中队列很常见，如，我们经常排队购物或购票，排队是体现了“先来先服务”（即“先进先出”）的原则。队列在计算机系统中的应用也非常广泛。例如：操作系统中的作业排队。在多道程序运行的计算机系统中，可以同时有多个作业运行，它们的运算结果都需要通过通道输出，若通道尚未完成输出，则后来的作业应排队等待，每当通道完成输出时，则从队列的队头退出作业作输出操作，而凡是申请该通道输出的作业都从队尾进入该队列。计算机系统中输入输出缓冲区的结构也是队列的应用。在计算机系统中经常

5、会遇到两个设备之间的数据传输，不同的设备通常处理数据的速度是不同的，当需要在它们之间连续处理一批数据时，高速设备总是要等待低速设备，这就造成计算机处理效率的大大降低。为了解决这一速度不匹配的矛盾，通常就是在这两个设备之间设置一个缓冲区。这样，高速设备就不必每次等待低速设备处理完一个数据，而是把要处理的数据依次从一端加入缓冲区，而低速设备从另一端取走要处理的数据。定义队列是只允许在一端删除，在另一端插入的顺序表。允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO, First In First Out)队列的进队和出队 进队时队尾指针先进一 rear

6、 = rear + 1，再将新元素按 rear 指示位置加入(队列不空时，队尾指针指向最后一个元素)。出队时队头指针先进一 front = front + 1，再将下标为 front 的元素取出。 (队列不空时，队头指针指向第一个元素的前面)队满时再进队将溢出出错；队空时再出队将做队空处理。队列为空时，队尾指针对头指针。（1）初始化：初始化一个新的队列。（2）队列非空判断 IsEmpty( )：若队列不空，则返回TRUE；否则，返回FALSE。（3）入队列 EnQueue(x)：在队列的尾部插入元素x，使元素x成为新的队尾。若队列满，则返回FALSE；否则，返回TRUE。（4）出队列 DeQu

7、eue( )：若队列不空，则返回队头元素，并从队头删除该元素，队头指针指向原队头的后继元素；否则，返回空元素NULL。（5）取队头元素 GetFront( )：若队列不空，则返回队头元素；否则返回空元素NULL。（6）求队列长度 Length( )：返回队列的长度。队列的基本运算队列是一种特殊的线性表，因此队列可采用顺序存储结构存储，也可以使用链式存储结构存储。template class Queue public: Queue ( int=10 );/构造函数 void EnQueue ( const Type & item); /进队 Type DeQueue ( );/出队列 Type

8、GetFront ( );/取队头元素值 void MakeEmpty ( );/置空队列 int IsEmpty ( ) const ;/判队列空否 int IsFull ( ) const;/判队列满否队列的抽象数据类型循环队列 (Circular Queue)在顺序队列中，当队尾指针已经指向了队列的最后一个位置时，此时若有元素入列，就会发生“溢出”。也就是说，队列的存储空间并没有满，但队列却发生了溢出，我们称这种现象为假溢出。解决这个问题有两种可行的方法：（1）采用平移元素的方法，当发生假溢出时，就把整个队列的元素平移到存储区的首部，然后再插入新元素。这种方法需移动大量的元素，因而效率是

9、很低的。（2）将顺序队列的存储区假想为一个环状的空间。我们可假想q-queue0接在q-queueMAXNUM-1的后面。当发生假溢出时，将新元素插入到第一个位置上，这样做，虽然物理上队尾在队首之前，但逻辑上队首仍然在前。入队和出队仍按“先进先出”的原则进行，这就是循环队列。很显然，方法二中不需要移动元素，操作效率高，空间的利用率也很高。存储队列的数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize -1直接进到0，可用语言的取模(余数)运算实现。队头指针进1: front = (front + 1) % maxSize;队尾指针进1: rear = (rear + 1) % ma

10、xSize;队列初始化：front = rear = 0;队空条件：front = rear;队满条件：(rear + 1) % maxSize = front 循环队列的进队和出队#include template class Queue public: Queue ( int=10 ); Queue ( ) delete elements; void EnQueue ( const Type & item); Type DeQueue ( ); Type GetFront ( ); void MakeEmpty ( ) front = rear = 0; 队列的数组表示 循环队列的类定义

11、int IsEmpty ( ) const return front = rear; int IsFull ( ) const return (rear+1) % maxSize = front; int Length ( ) const return (front-rear+maxSize) % maxSize;private: int rear, front; Type *elements; int maxSize;template Queue:Queue ( int sz ) : front (0), rear (0), maxSize (sz) elements = new Typem

12、axSize; assert ( elements != 0 );template void Queue:EnQueue ( const Type & item ) assert ( !IsFull ( ) ); rear = (rear+1) % MaxSize; elementsrear = item; 循环队列部分成员函数的实现template Type Queue:DeQueue ( ) assert ( !IsEmpty ( ) ); front = ( front+1) % MaxSize; return elementsfront;template Type Queue:GetF

13、ront ( ) assert ( !IsEmpty ( ) ); return elementsfront;链式队列：链式队列的操作函数可以类似定义。队列的应用举例 逐行打印二项展开式 (a + b)i 的系数杨辉三角形 (Pascals triangle) 1 1 i = 1 1 2 1 2 1 3 3 1 3 1 4 6 4 1 4 1 5 10 10 5 1 5 1 6 15 20 15 6 1 6分析第 i 行元素与第 i+1行元素的关系目的是从前一行的数据可以计算下一行的数据从第 i 行数据计算并存放第 i+1 行数据void YANGVI ( int n ) Queue q; /

14、队列初始化 q.MakeEmpty ( ); q.EnQueue (1); q.EnQueue (1); int s = 0; for ( int i=1; i=n; i+ ) /逐行计算 cout endl; q.EnQueue (0); for ( int j=1; j=i+2; j+ ) /处理第i行 int t = q.DeQueue ( ); q.EnQueue ( s+t ); s = t; if ( j != i+2 ) cout s ; 利用队列打印二项展开式系数的程序110121013310Initialize the queue and add (x, y, 0) to t

15、he queue; / x, y are the coordinate of maze entrance.While (queue is not empty) (i,j,pre) = coordinates and the index of the previous step dequeue from queue; for (all of eight directions of current position) (g, h, p) = coordinates of next move and index of current position (i, j); if (g = m) &(h =

16、 n) success and output the path; if (!mazegh) /legal move & (!markgh) /havent been here before markgh = 1; add (g, h, p) to the queue; Cout“no path found”endl;队列的应用举例求解迷宫问题0110011000011001110011101111001001010101111011101 2 3 4 5 6 7 8123456-1011223123123412334410 1 2 3 4 5 6 7 8 013710131 2 3 4 5 6

17、 7 8 9 10 11 12 13 14 15restore path reversedDepth first search: stack (need go back)Width first search: queue (do not need go back)问题：在此方案中有无回朔？如何输出路径？队列的应用举例 电路布线32211a12212b23489567867891010构造路径：从终点作为开始的检查点，搜索周围网格，检查其值是否比检查点的值小1，如是，则以此网格作为新的检查点，继续查找。因为0表示可走线，1表示不可走线。为方便区别，起点以2表示。因此，路径的长度为终点数字-2。b

18、ool FongPath(Position start, Position finish, int& PathLen, Position *& path) if (start.row=finish.row&start.col=finish.col) (PathLen = 0; return true) /到达终点int NumOfNbrs = 4, i, j; /一个网格的相邻位置数for (i=0; i=m; i+) /初始化网格外围墙 grid0i=gridm+1i=1; gridi0=gridim+1=1; Position offset4; /偏移量表offset0.row=0; of

19、fset0.col=1;offset1.row=1; offset1.col=0;offset2.row=0; offset2.col=-1;offset3.row=-1; offset3.col=0;Position here, nbr;here.row=start.row; here.col=sart.col;gridstart.rowstart.col=2; /封锁标记可到达的网格位置LinkedQueue Q; /链式队列do /一圈圈向外标记 for (i=0; i=0; j- -) pathi=here; /记下当前位置 for (i=0; iNumOfNbrs; i+) /寻找前

20、一个位置 nbr.row=here.row + offseti.row; nbr.col=here.col + offseti.col; if (gridnbr.rownbr.col=j+2) break; here = nbr; /移动到前一位置return true;1、搜索过程（完成网格编号的过程）的时间开销为O(m2)（或O(mn)）;2、重构路径过程的时间开销为O(PathLen)，最坏情况下为O(m)（或O(m+n)）;2、所以，算法的总的时间复杂度为O(m2)（或O(mn)） 。分析：3.4 优先级队列 (Priority Queue)优先级队列 是不同于先进先出队列的另一种队列

21、。每次从队列中取出的是具有最高优先权的元素。例如下表：任务的优先权及执行顺序的关系数字越小，优先权越高存储表示：顺序存储方式；链接存储方式。实现方式：1、队尾入队，通过搜索确定出队元素。 入队：O(1) 出队：O(n)2、队头出队，元素入队时调整排列次序。 入队：O(nlog2n) 出队：O(1)优先级队列的存储表示和实现方式#include #include $include const int maxPQSize = 50; /缺省元素个数template class PQueue public: PQueue ( ); PQueue ( ) delete pqelements; void PQInsert ( const Type & item ); Type PQRemove ( ); 优先队列的类定义 void makeEmpty ( ) count = -1; int IsEmpty ( ) const return count = -1; int IsFull ( ) const