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

第3章 栈和队列,本章的基本内容是：,栈栈与递归队列优先级队列双端队列,3.1 栈,3.1.1 栈的定义,空栈：不含任何数据元素的栈。,（a1, a2, , an）,栈：限定仅在表尾进行插入和删除操作的线性表。,允许插入和删除的一端称为栈顶，另一端称为栈底。,a1,a2,a3,入栈,出栈,插入：入栈、进栈、压栈删除：出栈、弹栈,栈的示意图,栈的操作特性：后进先出,3.1.1 栈的定义,3.1 栈,栈的操作特性：后进先出,a1,a2,a3,入栈,出栈,插入：入栈、进栈、压栈删除：出栈、弹栈,栈的示意图,3.1.1 栈的定义,3.1 栈,例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？,a,b,c,情况1：,3.1.1 栈的定义,3.1 栈,a,b,c,出栈序列：c,出栈序列：c、b,出栈序列：c、b、a,例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？,情况1：,3.1.1 栈的定义,3.1 栈,a,b,出栈序列：b,情况2：,例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？,3.1.1 栈的定义,3.1 栈,a,出栈序列：b,出栈序列：b、c,出栈序列： b、 c、a,c,注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。,例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？,情况2：,3.1.1 栈的定义,3.1 栈,const int maxSize=50 enum boolfalse,true; template class Stack public: Stack( ) ; virtual void Push(const T,3.1.1 栈的定义,栈的类定义,3.1 栈,3.1.2 顺序栈,顺序栈栈的顺序存储结构,如何改造数组实现栈的顺序存储？,a1,确定用数组的哪一端表示栈底。,附设指针top指示栈顶元素在数组中的位置。,3.1 栈,出栈：top减1,进栈：top加1,栈空：top= -1,a1,a2,a3,栈满：top= MAX_SIZE,3.1 栈,3.1.2 顺序栈,顺序栈类定义,template class SeqStack:public Stackpublic: SeqStack(int sz=50) ; SeqStack( ) deleteelements; void Push(const T,3.1 栈,顺序栈的实现构造函数,template SeqStack:SeqStack(int sz):top(-1),maxSize(sz)elements=new TmaxSize;assert(elements!=NULL); /断言：动态存储分配成功与否,注意断言的使用！,3.1 栈,3.1.2 顺序栈,顺序栈的实现入栈,template void SeqStack:Push(const T ,时间复杂度？,3.1 栈,3.1.2 顺序栈,具体实现见P90,顺序栈的实现出栈,template bool SeqStack: Pop (T,时间复杂度？,3.1 栈,3.1.2 顺序栈,两栈共享空间,解决方案2：,顺序栈单向延伸使用一个数组来存储两个栈,在一个程序中需要同时使用具有相同数据类型的两个栈，如何顺序存储这两个栈？,会出现什么问题？如何解决？,3.1 栈,3.1.2 顺序栈,两栈共享空间：使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。,两栈共享空间,3.1 栈,3.1.2 顺序栈,栈0的底固定在下标为0的一端；栈1的底固定在下标为maxSize-1的一端。t0和t1分别为栈0和栈1的栈顶指针；b0和b1分别为栈0和栈1的栈底；maxSize为整个数组空间的大小；,0 1 2 maxSize-1,3.1 栈,两栈共享空间,3.1.2 顺序栈,Vector,t0= b0,什么时候栈0为空？,0 1 2 maxSize-1,t0,3.1 栈,两栈共享空间,3.1.2 顺序栈,Vector,t0= b0,什么时候栈0为空？,0 1 2 maxSize-1,什么时候栈1为空？,t1= b1,3.1 栈,两栈共享空间,3.1.2 顺序栈,Vector,t1,t0= b0,什么时候栈0为空？,0 1 2 maxSize-1,什么时候栈1为空？,t1= b1,什么时候栈满？,t1= t0+1,3.1 栈,两栈共享空间,3.1.2 顺序栈,Vector,bool Push(DualStack,两栈共享空间的实现入栈,3.1 栈,3.1.2 顺序栈,两栈共享空间的实现退栈,3.1 栈,3.1.2 顺序栈,bool Pop(DualStack,3.1.3 链式栈,链栈：栈的链接存储结构,链栈需要加头结点吗？,如何改造链表实现栈的链接存储？,将哪一端作为栈顶？,将链头作为栈顶，方便操作。,链栈不需要附设头结点。,3.1 栈,栈顶,栈底,链栈：栈的链接存储结构,两种示意图在内存中对应同一种状态,栈顶,栈底,3.1 栈,3.1.3 链式栈,链栈的类定义,template class LinkedStack:public Stackpublic: LinkedStack( ):top(NULL) LinkedStack( )makeEmpty( ); void Push(const T,3.1 栈,算法描述：template void LinkedStack:Push(constT,an,an-1,a1,链栈的实现入栈,x,3.1 栈,3.1.3 链式栈,算法描述：template bool LinkedStack:Pop(const T,链栈的实现退栈,an,an-1,a1,top+可以吗？,3.1 栈,3.1.3 链式栈,顺序栈和链栈的比较,时间性能：相同，都是常数时间O(1)。,空间性能：顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。,总之，当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。,3.1 栈,3.2 栈与递归,3.2.1 递归的概念,子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。,递归的基本思想,问题分解：把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解决。,递归的定义,递归的要素, 递归边界条件：确定递归到何时终止，也称为递归出口； 递归模式：大问题是如何分解为小问题的，也称为递归体。,3.2 栈与递归,3.2.1 递归的概念,以下3中情况需要用到递归的方法, 定义是递归的； 数据结构是递归的； 问题的解法是递归的。,3.2 栈与递归,3.2.1 递归的概念,例1 阶乘函数,递归算法int fact ( int n ) if ( n = 0 ) return 1; else return n * fact (n-1);,3.2 栈与递归,求解阶乘 n! 的过程,计算 fact(4),递归调用,回归求值,3.2 栈与递归,一个结点，它的指针域为NULL，是一个单链表; 一个结点，它的指针域指向单链表，仍是一个单链表。,单链表结构,f,f,3.2 栈与递归,搜索链表最后一个结点的算法LinkNode* FindRear ( LinkNode* f ) if( f = NULL ) return NULL; else if(f-link=NULL) return f; else return FindRear( f -link );,f,f,f,f,f,a0,a1,a2,a3,a4,递归找链尾,3.2 栈与递归,递归的经典问题汉诺塔问题,在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。,3.2 栈与递归,汉诺塔问题的递归求解:如果 n = 1，则将这一个盘子直接从 塔A移到塔 C 上。否则，执行以下三步： 将塔A上的n-1个碟子借助塔C先移到塔B上； 把塔A上剩下的一个碟子移到塔C上； 将n-1个碟子从塔B借助于塔A移到塔C上。,3.2 栈与递归,void Hanoi(int n, char A, char B, char C) if (n=1) Move(A, C); else Hanoi(n-1, A, C, B); Move(A, C); Hanoi(n-1, B, A, C); ,3.2 栈与递归,Hanio(3,A,B,C),Hanio(2,A,C,B),Hanio(1,A,B,C),Move (A,C),Move (A,B),Hanio(1,C,A,B),Move (C,B),Move (A,C),Hanio(2,B,A,C),Hanio(1,B,C,A),Move (B,C),Hanio(1,A,B,C),Move (A,C),Move (B,A),3.2.2 递归过程与递归工作栈,3.2 栈与递归,递归过程在实现时，需要自己调用自己。层层向下递归，退出时的次序正好相反： 递归调用 n! (n-1)! (n-2)! 1! 0!=1 返回次序主程序第一次调用递归过程为外部调用；递归过程每次递归调用自己为内部调用。它们返回调用它的过程的地址不同。,每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。,局部变量返回地址参 数,活动记录框架,递归工作记录,3.2 栈与递归,3.2.2 递归过程与递归工作栈,递归工作栈,.,Function() .,调用块,函数块,返回地址(下一条指令) 局部变量 参数,3.2 栈与递归,3.2.2 递归过程与递归工作栈,函数递归调用时的活动记录,long Factorial ( long n ) int temp; if ( n = 0 ) return 1; /活动记录退栈 else temp = n * Factorial (n-1); /新记录入栈 RetLoc2 /返回地址RetLoc1在计算语句return temp; ,void main ( ) long n; /调用Fact(4)时的记录进栈 n = Factorial (4);/返回地址RetLoc1在赋值语句RetLoc1 coutnendl;,3.2 栈与递归,3.2.2 递归过程与递归工作栈,计算Fact时活动记录的内容,递归调用序列,4 RetLoc1 24,参数 返回地址 局部变量 返回时的指令,RetLoc2 return 4*6 /返回24,RetLoc2 return 3*2 /返回6,RetLoc2 return 1 /返回1,RetLoc2 return 1*1 /返回1,RetLoc2 return 2*1 /返回2,3.2 栈与递归,3 RetLoc2 6,2 RetLoc2 2,1 RetLoc2 1,0 RetLoc2 1,RetLoc1: n=Fact(4); /返回main,递归过程变为非递归过程,递归过程简洁、易编、易懂递归过程效率低，重复计算多改为非递归过程的目的是提高效率单向递归和尾递归可直接用迭代实现其非递归过程其他情形必须借助栈实现非递归过程,3.2 栈与递归,3.2.2 递归过程与递归工作栈,用栈实现递归过程的非递归算法,3.2 栈与递归,3.2.2 递归过程与递归工作栈,如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5,求解斐波那契数列的递归算法 long Fib ( long n ) if ( n = 1 ) return n; else return Fib (n-1) + Fib (n-2); ,斐波那契数列的递归调用树,Fib(1),Fib(0),Fib(1),Fib(2),Fib(3),Fib(4),Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(1),Fib(2),Fib(3),Fib(5),3.2 栈与递归,3.2.2 递归过程与递归工作栈,用栈实现递归过程的非递归算法,Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(2),Fib(1),Fib(3),Fib(4),栈结点,n tag,tag = 1, 向左递归；tag = 2, 向右递归,3.2 栈与递归,3.2.2 递归过程与递归工作栈,用栈实现递归过程的非递归算法,long Fibnacci ( long n ) Stack S; Node *w; long sum = 0; /反复执行直到所有终端结点数据累加完 do while ( n 1 ) w-n = n; w-tag = 1; S.push ( w ); n-; /向左递归到底, 边走边进栈 sum = sum + n; /执行求和,3.2 栈与递归,3.2.2 递归过程与递归工作栈,用栈实现递归过程的非递归算法,while ( !S.IsEmpty( ) ) w = S.getTop( ); S.Pop( ); if ( w-tag = 1 ) /改为向右递归 w-tag = 2; S.push ( w ); n = w-n 2; /F(n)右侧为F(n-2) break; while ( !S.IsEmpty( ) );return sum;,3.2 栈与递归,3.2.2 递归过程与递归工作栈,用栈实现递归过程的非递归算法,long FibIter ( long n ) if ( n = 1 ) return n; long twoback = 0, oneback = 1, Current; for ( int i = 2; i = n; i+ ) Current = twoback + oneback; twoback = oneback; oneback = Current; return Current;,3.2 栈与递归,3.2.2 递归过程与递归工作栈,单向递归用迭代法实现,void recfunc ( int A , int n ) if ( n = 0 ) cout An “,”; n-; recfunc ( A, n ); ,25 36 72 18 99 49 54 63,尾递归用迭代法实现,3.2 栈与递归,3.2.2 递归过程与递归工作栈,void sterfunc ( int A , int n ) /消除了尾递归的非递归函数 while ( n = 0 ) cout An “,”; n-; ,尾递归用迭代法实现,3.2 栈与递归,3.2.2 递归过程与递归工作栈,考虑使用递归算法求解的思路,递归算法的一般形式 void p ( 参数表 ) if ( 递归结束条件) 可直接求解步骤； 基本项 else p ( 较小的参数 ); 递归项,3.2 栈与递归,3.2.2 递归过程与递归工作栈,3.3.1 队列的概念,空队列：不含任何数据元素的队列。,队列：只允许在一端进行插入操作，而另一端进行删除操作的线性表。,允许插入（也称入队、进队）的一端称为队尾，允许删除（也称出队）的一端称为队头。,（a1, a2, , an）,3.3 队列,队列的操作特性：先进先出,a1,a2,a3,入队,队尾,队头,出队,3.3 队列,队头,3.3.1 队列的概念,队列的类定义,const int maxSize=50; enum boolfalse,true; template class Queue public: Queue( ) ; Queue( ) ; virtual void EnQueue(const T,3.3 队列,3.3.1 队列的概念,队列的顺序存储结构及实现,顺序队列：队列的顺序存储结构,如何改造数组实现队列的顺序存储？,例：a1a2a3a4依次入队,a1,a2,a3,a4,入队操作时间性能为O(1),3.3 队列,如何改造数组实现队列的顺序存储？,例：a1a2依次出队,3.3.2 循环队列,a1,a2,a3,a4,3.3 队列,如何改造数组实现队列的顺序存储？,例：a1a2依次出队,a2,a3,a4,3.3 队列,3.3.2 循环队列,如何改造数组实现队列的顺序存储？,例：a1a2依次出队,a3,a4,出队操作时间性能为O(n),3.3 队列,3.3.2 循环队列,如何改进出队的时间性能？,3.3 队列,3.3.2 循环队列,例：a1a2a3a4依次入队,a1,a2,a3,a4,入队操作时间性能仍为O(1),front,3.3 队列,3.3.2 循环队列,例：a1a2依次出队,a1,a2,a3,a4,出队操作时间性能提高为O(1),3.3 队列,3.3.2 循环队列,例：a1a2依次出队,a3,a4,队列的移动有什么特点？,3.3 队列,3.3.2 循环队列,例：a1a2依次出队,3.3 队列,3.3.2 循环队列,a3,a4,假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。,继续入队会出现什么情况？,a3,a4,a5,3.3 队列,3.3.2 循环队列,循环队列：将存储队列的数组头尾相接。,如何解决假溢出？,0 1 2 3 4,入队,出队,a3,a4,a5,a6,3.3 队列,3.3.2 循环队列,不存在物理的循环结构，用软件方法实现。求模：（41）mod 50,如何实现循环队列？,0 1 2 3 4,入队,出队,a3,a4,a6,3.3 队列,3.3.2 循环队列,如何判断循环队列队空？,队空的临界状态,0 1 2 3 4,入队,出队,a3,3.3 队列,3.3.2 循环队列,如何判断循环队列队空？,执行出队操作,队空：front=rear,0 1 2 3 4,入队,出队,a3,3.3 队列,3.3.2 循环队列,如何判断循环队列队满？,队满的临界状态,0 1 2 3 4,入队,出队,a3,a4,a5,a6,3.3 队列,3.3.2 循环队列,如何判断循环队列队满？,执行入队操作,队满：front=rear,0 1 2 3 4,入队,出队,a3,a4,a5,a6,a7,3.3 队列,3.3.2 循环队列,方法一：附设一个存储队列中元素个数的变量num，当num=0时队空，当num=QueueSize时为队满；方法二：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元；方法三：设置标志tag，当front=rear且tag=0时为队空，当front=rear且tag=1时为队满。,如何确定不同的队空、队满的判定条件？为什么要将队空和队满的判定条件分开？,3.3 队列,3.3.2 循环队列,队满的条件：(rear+1) mod QueueSize=front,0 1 2 3 4,入队,rearfront,a3,a4,a5,a6,出队,0 1 2 3 4,入队,rearfront,a3,a4,a5,a6,出队,3.3 队列,3.3.2 循环队列,循环队列类定义,template class SeqQueue:public Queue public: SeqQueue(int sz=10)； SeqQueue( )delete elements; bool EnQueue(const T,3.3 队列,3.3.3 链式队列,链队列：队列的链接存储结构,队头指针即为链表的头指针,first,如何改造单链表实现队列的链接存储？,3.3 队列,非空链队列,front,rear,空链队列,front=rear=NULL,3.3 队列,3.3.3 链式队列,链队列类定义,template class LinkedQueue:public Queue public: LinkedQueue( ):rear(NULL),front(NULL) ; LinkedQueue(makeEmpty( ); bool EnQueue(const T,3.3 队列,链队列的实现入队,front,算法描述：rear-link=new LinkNOde(x);,3.3 队列,3.3.3 链式队列,front,算法描述：front=rear=new LinkNOde(x);,链队列的实现出队,front,rear,算法描述：p=front; front=front-link;x=p-data;delete p;,3.3 队列,3.3.3 链式队列,时间性能:循环队列和链队列的基本操作都需要常数时间O (1)。,空间性能:循环队列：必须预先确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。链队列：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，但是每个元素都需要一个指针域，从而产生了结构性开销。,3.3 队列,i,3.3.3队列的应用举例 逐行打印 二项展开式 (a + b)i 的系数,3.3 队列,分析第 i 行元素与第 i+1行元素的关系,从前一行的数据可以计算下一行的数据,i = 2,i = 3,i = 4,0 1 3 3 1 0,1 4 6 4 1,0 1 2 1 0,0 1 1 0,s,t,s+t,3.3 队列,从第 i 行数据计算并存放第 i+1 行数据,1 2 1 0 1 3 3 1 0 1 4 6,s=0 t=1 t=2 t=1 t=0 t=1 t=3 t=3 t=1 t=0 t=1,s+t s=t s=t s=t s=t s=t s=t s=t s=t,s+t s+t s+t s+t s+t s+t s+t s+t,3.3 队列,利用队列实现逐行打印杨辉三角形的前n行的算法 #include #include #include queue.h void YANGVI ( int n ) Queue q(n+1); /队列初始化 int i=1, j, s=k=0, t, u; q.EnQueue (i); q.EnQueue (i);,3.3 队列,for (i = 1; i = n; i+ ) /逐行计算 cout endl; q.EnQueue (k); /各行间插入一个0 for (j = 1; j = i+2; j+ ) /下一行q.DeQueue (t);u=s+t; q.EnQueue (u);s=t;if ( j != i+2 ) cout s ; ,3.3 队列,3.4 优先级队列(概念）,优先级队列 每次从队列中取出的是具有最高优先权的元素如下表：任务优先权及执行顺序的关系,数字越小，优先权越高,#include #include #include const int DefaultPQSize = 50; /缺省元素个数enum boolfalse,truetemplate class PQueue public: PQueue (int sz=DefaultPQSize);PQueue ( ) delete pqelements; bool Insert ( const T,优先队列的类定义,3.4 优先级队列(概念）,bool * GetFront (T,优先队列的类定义,3.5 双端队列,双端队列（Deque) 可以在队列的两端进行插入和删除。,3.5.1 双端队列的概念,Initialization,3.5 双端队列,注意：在Deque类的公共接口中包括了从基类Queue继承来的EnQueue和DeQueue函数。但在Deque类中只提供EnQueue和DeQueue的默认功能，只不过EnQueue仅仅调用了EnQueueTail（在尾部插入）， DeQueue函数仅仅调用了DeQueueHead（在头部删除）。,3.5.1 双端队列的概念,3.5 双端队列,3.5.2 双端队列的数组表示,SeqDeque类的定义#include “Deque.h”#include “SeqQueue.h”template class SeqDeque:public Deque, public SeqQueuepublic: SeqDeque(int sz);/ ;,3.5 双端队列,3.5.2 双端队列的数组表示,成员函数getHead、EnQueueTail和DeQueueHead的实现templatebool SeqDeque:getHead(T,3.5 双端队列,3.5.2 双端队列的数组表示,成员函数getTail、EnQueueHead和DeQueueTail的实现templatebool SeqDeque:getTail(T,templatebool SeqDeque:DeQueueTail(T,3.5 双端队列,3.5.3 双端队列的链表表示,LinkedQueue类的定义#include “Deque.h”#include “LinkedQueue.h”#include “LinkedList.h”template class LinkedDeque:public Deque, public LinkedQueuepublic: LinkedDeque( );/ ;,3.5 双端队列,成员函数getHead、EnQueueTail和DeQueueHead的实现templatebool LinkedDeque:getHead(T,3.5.3 双端队列的链表表示,3.5 双端队列,成员函数getTail、EnQueueHead和DeQueueTail的实现templatebool LinkedDeque:getTail(T,templatebool LinkedDeque:DeQueueTail(T,3.5.3 双端队列的链表表示,作业：1.设输入元素为1,2,3,a,b，输入次序为123ab，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可作为高级语言变量名。,特殊线性表,栈,队 列,栈的定义操作特性ADT定义,队列定义操作特性ADT定义,顺序栈,链栈,循环队列,链队列,逻辑结构,存储结构,逻辑结构,存储结构,比 较,比较,比较,基本操作的实现时间性能,基本操作的实现时间性能,第3章 栈和队列,