《栈队列和递归》PPT课件.ppt

,第三章 栈、队列和递归,3.1栈（Stack）,3.2 队列（Queue）,.逻辑结构.存储结构与实现.应用实例,.逻辑结构.存储结构与实现.应用实例,.1 栈,1、栈的逻辑结构,空栈：不含任何数据元素的栈。,（a1,a2,an）,栈：限定仅在一端进行插入和删除操作的线性表。,允许插入和删除的一端称为栈顶，另一端称为栈底。数据元素之间的逻辑关系：一对一。,注：栈的运算规则只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。入栈：插入元素到栈顶（即表尾）的操作。出栈：从栈顶（即表尾）删除最后一个元素的操作。问：栈与一般线性表有什么不同？一般线性表（堆）栈逻辑结构：一对一 逻辑结构：一对一存储结构：顺序表、链表 存储结构：顺序栈、链栈运算规则：随机存取 运算规则：后进先出(LIFO)入栈操作演示出栈操作演示,a1,a2,a3,入栈,插入：入栈、进栈、压栈,入栈的操作示图：,a1,a2,a3,删除：出栈、弹栈,出栈的操作示图：,栈的操作特性：后进先出,出栈,思考题：一个栈的输入序列为123，若在入栈的过程中允许出栈，且每个元素只允许进一次栈，则可能得到的出栈序列有哪些？,答：,可以通过穷举所有可能性来求解：1入1出，2入2出，3入3出，即123；1入1出，2、3入3、2出，即132；1、2入，2出，3入3出，即231；1、2入，2、1出，3入3出，即213；1、2、3入，3、2、1出，即321；合计有5种可能性。,思考题：,设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：）a，b，c，d）c，d，a，b）b，c，d，a）a，c，d，b,A、D可以（B、C不行）。,讨论：有无通用的判别原则？有。若输入序列i，j，k，则不存在输出序例k、i、j;,答：,2、栈的存储结构顺序栈、链式栈（）顺序栈栈的顺序存储结构(重点),如何改造数组实现栈的顺序存储？,a1,确定用数组的哪一端表示栈底。,附设指针top指示栈顶元素在数组中的位置。,S,进栈核心语句：top+;Stop=a1;,栈空：top=-1,a1,a2,进栈的操作步骤如何？,a1,a2,栈满：top=MAX_SIZE-1,栈满的如何判断？,a3,a4,a5,a6,a7,a8,a9,动态栈类的定义：template/定义模板类DSeqStackclass DSeqStackpublic:DSeqStack(int size);/构造函数，栈的初始化DSeqStack()delete S;/析构函数 void Push(const type,顺序栈的构造函数算法实现,template DSeqStack:DSeqStack(int size):top(-1),MaxSize(size)/建立一个最大尺寸为size的空栈S=new typeMaxSize;/创建存储栈的数组if(S=NULL)/分配不成功 cerr动态存储失败！endl;exit(1);/stdlib.h,操作接口：template DSeqStack:DSeqStack(int size);算法实现：,顺序栈的入栈操作算法实现,template void DSeqStack:Push(const type,操作接口：template void DSeqStack:Push(const type&item)算法实现：,时间复杂度？,O(1),出栈核心语句：Item=Stop;top-;,边界条件栈空：top=-1;,a1,a2,出栈的操作步骤如何？,顺序栈的出栈操作算法实现,template type DSeqStack:Pop()type item;if(top=-1)throw 栈空！;item=Stop-;/等价于item=Stop;top-;return item;,操作接口：template type DSeqStack:Pop();算法实现：,时间复杂度？,O(1),其它类型栈举例：如两栈共享空间,解决方案2：,使用一个数组来存储两个栈。使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。,在一个程序中需要同时使用具有相同数据类型的两个栈，如何顺序存储这两个栈？,会出现什么问题？如何解决？,栈1的栈底:固定靠下标为0的这一端；栈2的栈底:固定靠下标为MaxSize-1的这一端。top1和top2分别为栈1和栈2的栈顶指针；MaxSize:整个数组空间的大小（图中用S表示）；,a1 a2 ai,0 1 2 S-1,bj b2 b1,两栈共享空间栈顶与栈底如何设置？,栈1为空条件：top1=-1栈2为空条件：top2=MaxSize,什么时候两栈为空？,0 1 2 S-1,a1 a2 ai,0 1 2 S-1,bj b2 b1,栈满条件为：top2=top1+1,什么时候栈为满？,（）链式栈栈的链式存储结构,如何改造链表实现栈的链接存储？链栈需要加头结点吗？将哪一端作为栈顶？,注：链栈不需要附设头结点。,链栈类的定义：template class LinkStack;/声明template class Node friend class LinkStack;private:type data;Node*next;/此处也可以省略;template class LinkStackpublic:LinkStack();/构造函数，置空链栈 LinkStack();/析构函数，释放链栈中各结点的存储空间 void Push(type item);/将元素item入栈 type Pop();/将栈顶元素出栈 type GetTop();/取栈顶元素（并不删除）bool Empty();/判断链栈是否为空栈private:Node*top;/栈顶指针即链栈的头指针;,链栈的构造函数算法实现,template LinkStack:LinkStack()top=NULL;/初始化空栈,操作接口：template LinkStack:LinkStack();算法实现：,算法实现：template void inkStack:Push(type x)Node*s;s=new Node;s-data=x;s-next=top;top=s;,an,an-1,a1,链栈的入栈算法实现,操作接口：template void LinkStack:Push(type x)；,为什么没有判断栈满？,算法实现：template type LinkStack:Pop()Node*p;type x;if(top=NULL)throw“栈空;x=top-data;p=top;top=top-next;delete p;return x;,链栈的出栈算法实现：,操作接口：template T LinkStack:Pop();,an,an-1,a1,top+可以吗？,顺序栈和链栈的比较,时间性能：相同，都是常数时间O(1)。,空间性能：顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。,总之，采用顺序栈存储方式，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。,调用函数或子程序非它莫属；递归运算的有力工具；用于保护现场和恢复现场；简化了程序设计的问题；其它应用：如括号匹配问题、表达式计算问题等。,答：,3、栈的应用举例,为什么要设计栈？它有什么独特用途？,数制转换（十转八进制）设计思路：用栈暂存低位值算法分析：N N div 8 N mod 8 74 9 2 9 1 1 1 0 1,栈的应用实例：,如：(74)10=(112)8,void conversion()/对于输入的任意一个非负十进制整数，/打印输出与其等值的八进制数；SeqStack s1(10);int N,n;int e;coutN;n=N;while(n)s1.Push(n%);n=n/;while(!s1.Empty()e=s1.Pop();coute;coutendl;,3.1栈（Stack）,3.2 队列（Queue）,.逻辑结构.存储结构与实现.应用实例,.逻辑结构.存储结构与实现,.2 队列,1、队列的逻辑结构,空队：不含任何数据元素的队列。,（a1,a2,an）,队列：只允许在一端进行插入操作，而在另一端进行删除操作的线性表。,允许插入的一端称为队尾，另一端允许删除的称为队头。数据元素之间的逻辑关系：一对一。,注：队列的运算规则只能在队尾进行插入运算，在队头进行删除运算;且访问结点时依照先进先出（FIFO）或后进后出（LILO）的原则。入队：插入元素到队列的队尾的操作。出队：从队头删除一个元素的操作。问：队列与一般线性表有什么不同？一般线性表 队列逻辑结构：一对一 逻辑结构：一对一存储结构：顺序表、链表 存储结构：顺序队、链队运算规则：随机存取 运算规则：先进先出(FIFO),队列的操作特性：先进先出,a1,a2,a3,入队,队尾,队头,出队,队头,入队出队操作示意图:,队尾,队尾,队尾,2、队列的存储结构与实现顺序队列、链式队列（）顺序队列队列的顺序存储结构(重点),如何改造数组实现队列的顺序存储？,a1,确定用数组如何表示队头、队尾。,附设指示器rear指示队尾元素（在数组中最后一个元素的位置），指示器front指示队头（队头元素所在位置的前一位置）。,S,实例1：a1a2a3a4依次入队,a1,a2,a3,a4,入队操作时间性能为O(1),实例2：a1a2依次出队,a1,a2,a3,a4,出队操作时间性能为O(1),队列的移动有什么特点？,假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。,继续入队会出现什么情况？,a3,a4,a5,循环队列：将存储队列的数组头尾相接。,如何解决假溢出？,0 1 2 3 4,入队,出队,a3,a4,a5,a6,a3,a2,a1,0,1,2,3,N-1,rear,front,循环队列（臆造）,顺序队列,a3,a2,a1,front,rear,0 1 2 3.N-1,新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案有三：加设标志位，让删除动作使其为1,插入动作使其为0,则可识别当前front=rear 使用一个计数器记录队列中元素个数（即队列长度）；人为浪费一个单元，令队满特征为front=(rear+1)%N；,队空条件:front=rear(初始化时：front=rear)队满条件：front=(rear+1)%N(N=maxsize)队列长度：L=（Nrearfront）%N,J2 J3,J1 J4,J5,front,rear,问2：在具有n个单元的循环队列中，队满时共有多少个元素？,n-1个,5,问1：左图中队列长度L=？,例1：一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置?,解：由图可知，初始状态,队头和队尾指针的初态分别为front=0和rear=5。,删除4个元素后(front+4)%6=4；再插入4个元素后，r=(rear+4)%6=(5+4)%6=3,J1,J2,J5,J6,J7,J8,J9,J3,J4,动态循环队列类的定义：（重点）/DCirQueue.h#ifndef DCirQueue_H#define DCirQueue_Htemplate/定义模板类DCirQueueclass DCirQueuepublic:DCirQueue(int size=10);/构造函数，置空队 DCirQueue()delete queue;/析构函数 void EnQueue(T x);/将元素x入队 T DeQueue();/将队头元素出队 T GetQueue();/取队头元素（并不删除）bool IsEmpty();/判断队列是否为空 int Isfull()constreturn(rear+1)%maxsize=front;/队列满则返回1，否则返回0private:T*queue;/存放队列元素的数组 int front,rear;/队头和队尾指针，分别指向队头元素的前一个位置和队尾元素的位置 int maxsize;/队列最大可容纳元素个数为maxsize-1;#endif,循环队列的构造函数算法实现,template DCirQueue:DCirQueue(int size):front(0),rear(0),maxsize(size)queue=new Tmaxsize;if(queue=NULL)throw动态分配失败!;,操作接口：template DCirQueue:DCirQueue(int size);算法实现：,0 1 2 3 4,循环队列的入队算法实现,template void DCirQueue:EnQueue(T x)if(rear+1)%maxsize=front)throw“队满;rear=(rear+1)%maxsize;/队尾指针在循环意义下加1 queuerear=x;/在队尾处插入元素,操作接口：template void DCirQueue:EnQueue(T x)算法实现：,0 1 2 3 4,a1,循环队列的出队算法实现,template T DCirQueue:DeQueue()if(rear=front)throw 下溢;front=(front+1)%maxsize;/队头指针在循环意义下加1 return queuefront;/读取并返回出队前的队头元素，注意队头指针,操作接口：template T DCirQueue:DeQueue()算法实现：,a1,0 1 2 3 4,入队,a4,a5,a6,出队,a3,循环队列的读队头元素算法实现,template T DCirQueue:GetQueue()int i;if(rear=front)throw“队空!;i=(front+1)%maxsize;/注意不要给队头指针赋值 return queuei;,操作接口：template T DCirQueue:GetQueue()算法实现：,a1,0 1 2 3 4,a4,a5,a6,出队,a3,入队,（2）队列的链接存储结构及实现,链队列：队列的链接存储结构,队头指针即为链表的头指针；常用不带头结点链表结构。,如何改造单链表实现队列的链接存储？,front=NULL;front=rear;,空链队列如何表示？,NULL,NULL,链队列满如何表示？,无需考虑满的情况。,链式队列类的定义：template struct Node T data;Node*next;/此处也可以省略;template class LinkQueuepublic:LinkQueue();/构造函数，初始化一个空的链队列 LinkQueue();/析构函数，释放链队中各结点的存储空间 void EnQueue(T x);/将元素x入队 T DeQueue();/将队头元素出队 T GetQueue();/取链队列的队头元素 bool Empty();/判断链队列是否为空private:Node*front,*rear;/队头和队尾指针，分别指向头结点和终端结点;,链队的构造函数算法实现,template LinkQueue:LinkQueue()front=rear=NULL;,操作接口：template LinkQueue:LinkQueue()；算法实现：,链队列的实现入队,front,front,队不空核心算法描述：Node*s=new Node;s-data=x;s-next=NULL;rear-next=s;rear=s;,操作接口：template void LinkQueue:EnQueue(T x),NULL,队空时核心算法描述：Node*s=new Node;s-data=x;s-next=NULL;front=rear=s;,template void LinkQueue:EnQueue(T x)Node*s;s=new Node;s-data=x;/申请一个数据域为x的结点s s-next=NULL;if(front=NULL)/空队列，新结点既是队头，又是队尾 front=rear=s;else rear-next=s;/将结点s插入到队尾 rear=s;,算法实现：,链队列的实现出队,操作接口：template T LinkQueue:DeQueue(),Node*p=front;x=p-data;Front=NULL;rear=front;delete p;,p,队列不空时算法描述：Node*p=front;x=p-data;front=front-next;delete p;,队列只有一个元素时?,链队的出队操作算法实现,template T LinkQueue:DeQueue()Node*p;int x;if(front=NULL)throw“队空;p=front;x=p-data;/暂存队头元素 front=front-next;/将队头元素所在结点摘链 if(front=NULL)rear=front;/判断出队前队列长度是否为1 delete p;return x;,操作接口：template T LinkQueue:DeQueue()；算法实现：,链队的获得队首元素操作算法实现,template T LinkQueue:GetQueue()if(front!=NULL)return front-data;,操作接口：template T LinkQueue:GetQueue()算法实现：,队列的其它链接存储结构,用带头结点的单链表实现队列的链接存储？,队头指针即为链表的头指针，指向头结点。,空链队列,front,rear,front,front,核心算法描述：Node*s=front-next;s-data=x;s-next=NULL;rear-next=s;rear=s;,队列为空时如何入队如何操作？,用带头结点的单链表如何实现队列的入队操作？,front,front,p,核心算法描述：Node*p=front-next;x=p-data;front-next=p-next;delete p;,队列中仅有一个元素时出队如何操作？,用带头结点的单链表如何实现队列的出队操作？,核心算法描述：rear=front;,练习1：数组n用来表示一个循环队列，f 为当前队列首元素的前一位置，r 为队尾元素的位置。假定队列中元素的个数小于n，计算队列中元素个数的公式为:,（）rf（）（nfr）%n（）nrf（）（nrf）%n,4种公式哪种合理？当 r f 时（A）合理；当 r f 时（C）合理；,分析：,综合2种情况，以（D）的表达最为合理,练习2：在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中删除一个元素时，其操作是 先，后。,移动队首指针,取出元素,离散事件的模拟（模拟事件发生的先后顺序）；操作系统中多道作业的处理（一个CPU执行多个作业）；3.简化程序设计。,答：,为什么要设计队列？它有什么独特用途？,小结,线性表、栈与队的异同点相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。不同点：运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。,3.3递归(栈的应用),.递归的定义.基本思想.递归要素.递归应用举例阶乘函数,.递归,1、递归（recursion）的定义,递归：子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。,递归按其调用方式可分为直接递归和间接递归：1、直接递归:自己调用自己。如：void f(n)f(n/2);2、间接递归：P调用D，D调用P；如：void P(int n)void D(int n)D(n/3);P(n/2);,2、递归的基本思想问题分解：把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解决。,3、递归的要素,递归边界条件：确定递归到何时终止，也称为递归出口；递归模式：大问题是如何分解为小问题的，也称为递归体。,例1、定义是递归的：（）阶乘函数,递归算法long unsigned fact(int n)if(n=0)return 1;else return n*fact(n-1);,、递归应用举例,求解阶乘 n!的过程,计算 fact(4),递归调用,回归求值,（2）Fibonacci数列 0 n=0Fib(n)=1 n=1 Fib(n-1)+Fib(n-2)n10 1 1 2 3 5 8 13,递归算法long unsigned Fib(int n)if(n=0|n=1)return n;/递归出口else return Fib(n-1)+Fib(n-2);/递归调用注：累计递归调用次数：2*Fib(n+1)-1。,例、问题的解法是递归的：利用递归思想来求解某类问题（本身没有明显的递归结构，但操作方法可以用递归很好的描述）使其更为简单。如：汉诺塔问题、背包问题、八皇后问题等。,（3）有的数据结构如二叉树、广义表、图等（如树的遍历、图的搜索）定义。,小结：递归算法的缺点：费时、费内存空间，效率往往很低。递归算法的优点：它能使一个蕴含递归关系且结构复杂的程序简洁、清晰、精炼、增加可读性。,