《第三章栈队列和递归PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第三章栈队列和递归PPT讲稿.ppt（73页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章栈队列和递归第1页，共73页，编辑于2022年，星期二特殊线性表特殊线性表 栈栈队队 列列 串串栈的定义栈的定义操作特性操作特性ADTADT定义定义队列定义队列定义操作特性操作特性ADTADT定义定义串的定义串的定义基本概念基本概念ADTADT定义定义顺顺序序栈栈链链栈栈循循环环队队列列链链队队列列顺顺序序存存储储链链接接存存储储逻辑结构逻辑结构存储结构存储结构逻辑逻辑结构结构逻辑逻辑结构结构存储存储结构结构存储存储结构结构比比 较较模式匹配模式匹配比较比较比较比较基本操作的实现基本操作的实现时间复杂度时间复杂度基本操作的实现基本操作的实现时间复杂度时间复杂度第2页，共73页，编辑于20
2、22年，星期二3.13.1栈栈（Stack）3.2 3.2 队列队列 （Queue）.逻辑结构逻辑结构.存储结构与实现存储结构与实现.应用实例应用实例.逻辑结构逻辑结构.存储结构与实现存储结构与实现.应用实例应用实例第3页，共73页，编辑于2022年，星期二.1 .1 栈栈栈栈1 1、栈的逻辑结构、栈的逻辑结构空栈：空栈：不含任何数据元素的栈。不含任何数据元素的栈。（a1,a2,an）栈：栈：限定仅在限定仅在一端一端进行进行插入和删除插入和删除操作的操作的线性表线性表。栈顶栈顶栈底栈底允许允许插入和删除插入和删除的的一端一端称为称为栈顶栈顶，另一端另一端称为称为栈底栈底。数据元素之间的逻辑关系
3、：数据元素之间的逻辑关系：一对一一对一 。第4页，共73页，编辑于2022年，星期二注：注：栈的运算规则栈的运算规则只能在只能在栈顶栈顶运算，且访问结点时依照运算，且访问结点时依照后进先出后进先出（LIFO）或或先进后出（先进后出（FILO）的原则。的原则。入栈：入栈：插入元素到栈顶（即表尾）的操作。插入元素到栈顶（即表尾）的操作。出栈：出栈：从栈顶（即表尾）删除最后一个元素的操作。从栈顶（即表尾）删除最后一个元素的操作。问：栈问：栈与与一般线性表一般线性表有什么不同？有什么不同？一般线性表一般线性表 （堆）栈（堆）栈逻辑结构：一对一逻辑结构：一对一 逻辑结构：一对一逻辑结构：一对一存储结构：
4、顺序表、链表存储结构：顺序表、链表 存储结构：顺序栈、链栈存储结构：顺序栈、链栈运算规则：运算规则：随机存取随机存取 运算规则：运算规则：后进先出后进先出(LIFO)入栈操作演示入栈操作演示出出栈栈操作演示操作演示第5页，共73页，编辑于2022年，星期二a1a2a3入栈入栈栈底栈底栈顶栈顶插入：入栈、进栈、压栈插入：入栈、进栈、压栈栈顶栈顶栈顶栈顶入栈的操作示图：入栈的操作示图：栈顶栈顶第6页，共73页，编辑于2022年，星期二a1a2a3栈底栈底栈顶栈顶删除：出栈、弹栈删除：出栈、弹栈栈顶栈顶栈顶栈顶出栈的操作示图：出栈的操作示图：栈顶栈顶栈的操作特性：栈的操作特性：后进先出后进先出出栈出
5、栈第7页，共73页，编辑于2022年，星期二思考题：思考题：一个栈的输入序列为一个栈的输入序列为123123，若在入栈的过程，若在入栈的过程中允许出栈，且每个元素只允许进一次栈，则可能得中允许出栈，且每个元素只允许进一次栈，则可能得到的出栈序列有哪些？到的出栈序列有哪些？答：答：可以通过穷举所有可能性来求解：可以通过穷举所有可能性来求解：1 1入入1 1出，出，2 2入入2 2出，出，3 3入入3 3出，出，即即123123；1 1入入1 1出，出，2 2、3 3入入3 3、2 2出，出，即即132132；1 1、2 2入，入，2 2出，出，3 3入入3 3出，出，即即231231；1 1、2
6、 2入，入，2 2、1 1出，出，3 3入入3 3出，出，即即213213；1 1、2 2、3 3入，入，3 3、2 2、1 1出，出，即即321321；合计有合计有5 5种可能性。种可能性。第8页，共73页，编辑于2022年，星期二思考题：思考题：设依次进入一个栈的元素序列为设依次进入一个栈的元素序列为c，a，b，d，则可则可得到出栈的元素序列是：得到出栈的元素序列是：）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，bA、D可以可以（B、C不行）。不行）。讨论：有无通用的判别原则讨论：有无通用的判别原则？有。有。若输入序列若输入序列i i，j j，k k，则不存在输出序例
7、，则不存在输出序例k k、i i、j;j;答：答：第9页，共73页，编辑于2022年，星期二2、栈的存储结构、栈的存储结构顺序栈、链式栈顺序栈、链式栈（）顺序栈（）顺序栈栈的栈的顺序存储顺序存储结构结构(重点重点)如何改造数组实现栈的顺序存储？如何改造数组实现栈的顺序存储？0 1 2 3 4 5 6 7 8a1确定确定用数组的哪一端表示用数组的哪一端表示栈底栈底。附设指针附设指针top指示栈顶元素在数组中的位置。指示栈顶元素在数组中的位置。topS第10页，共73页，编辑于2022年，星期二进栈核心语句：进栈核心语句：top+;Stop=a1;栈空：栈空：top=-1 0 1 2 3 4 5
8、6 7 8topa1topa2top进栈的操作步骤如何？进栈的操作步骤如何？第11页，共73页，编辑于2022年，星期二 0 1 2 3 4 5 6 7 8a1a2栈满：栈满：top=MAX_SIZE-1栈满的如何判断？栈满的如何判断？topa3a4a5a6a7a8a9第12页，共73页，编辑于2022年，星期二动态栈动态栈类的定义：类的定义：template /定义模板类定义模板类DSeqStackclass DSeqStackpublic:DSeqStack(int size);/构造函数，栈的初始化构造函数，栈的初始化DSeqStack()delete S;/析构函数析构函数 void
9、Push(const type&item);/将元素将元素item入栈入栈 type Pop();/将栈顶元素弹出将栈顶元素弹出 type GetTop();/取栈顶元素（并不删除）取栈顶元素（并不删除）int Empty()return top=-1;/判断栈是否为空判断栈是否为空int full()constreturn top=MaxSize-1;/为满则返回为满则返回1，否则返回，否则返回0void clear()top=-1;/清空栈清空栈private:type*S;/存放栈元素的数组起始地址存放栈元素的数组起始地址 int top;/栈顶指针，指示栈顶元素在数组中的下标栈顶指针，
10、指示栈顶元素在数组中的下标int MaxSize;/栈最大可容纳元素个数栈最大可容纳元素个数;第13页，共73页，编辑于2022年，星期二顺序栈的顺序栈的构造函数算法构造函数算法实现实现template DSeqStack:DSeqStack(int size):top(-1),MaxSize(size)/建立一个最大尺寸为建立一个最大尺寸为size的空栈的空栈S=new typeMaxSize;/创建存储栈的数组创建存储栈的数组if(S=NULL)/分配不成功分配不成功 cerr动态存储失败！动态存储失败！endl;exit(1);/stdlib.h操作接口：操作接口：template DS
11、eqStack:DSeqStack(int size);算法实现：算法实现：第14页，共73页，编辑于2022年，星期二顺序栈的顺序栈的入栈操作算法入栈操作算法实现实现template void DSeqStack:Push(const type&item)if(top=MaxSize-1)throw 栈满！栈满！;top+;/栈未满，则入栈栈未满，则入栈 Stop=item;操作接口：操作接口：template void DSeqStack:Push(const type&item)算法实现：算法实现：时间复杂度？时间复杂度？O(1)第15页，共73页，编辑于2022年，星期二出栈核心语句：
12、出栈核心语句：Item=Stop;top-;边界条件边界条件栈空：栈空：top=-1;0 1 2 3 4 5 6 7 8topa1topa2top出栈的操作步骤如何？出栈的操作步骤如何？第16页，共73页，编辑于2022年，星期二顺序栈的顺序栈的出栈操作算法出栈操作算法实现实现template type DSeqStack:Pop()type item;if(top=-1)throw 栈空！栈空！;item=Stop-;/等价于等价于item=Stop;top-;return item;操作接口：操作接口：template type DSeqStack:Pop();算法实现：算法实现：时间复杂
13、度？时间复杂度？O(1)第17页，共73页，编辑于2022年，星期二其它类型栈举例：如两栈共享空间其它类型栈举例：如两栈共享空间 解决方案解决方案1 1：直接解决：为每个栈开辟一个数组空间。直接解决：为每个栈开辟一个数组空间。解决方案解决方案2 2：使使用用一一个个数数组组来来存存储储两两个个栈栈。使使用用一一个个数数组组来来存存储储两两个个栈栈，让让一一个个栈栈的的栈栈底底为为该该数数组组的的始始端端，另另一一个个栈栈的的栈栈底底为为该该数数组组的的末末端端，两两个个栈栈从从各各自自的的端端点点向向中中间间延伸。延伸。在一个程序中需要在一个程序中需要同时同时使用具有使用具有相同相同数据类型的
14、数据类型的两个栈两个栈，如何顺序存储这两个栈？如何顺序存储这两个栈？会出现什么问题？如何解决？会出现什么问题？如何解决？第18页，共73页，编辑于2022年，星期二栈栈1的的栈底栈底:固定靠下标为固定靠下标为0的这一端；的这一端；栈栈2的的栈底栈底:固定靠下标为固定靠下标为MaxSize-1的这一端。的这一端。top1和和top2分别为栈分别为栈1和栈和栈2的栈顶指针；的栈顶指针；MaxSize:整个数组空间的大小（图中用整个数组空间的大小（图中用S表示）；表示）；a1 a2 aitop10 1 2 S-1top2bj b2 b1栈栈1底底栈栈2底底两栈共享空间栈顶与栈底如何设置？两栈共享空间
15、栈顶与栈底如何设置？第19页，共73页，编辑于2022年，星期二栈栈1为空条件：为空条件：top1=-1栈栈2为空条件：为空条件：top2=MaxSize什么时候两栈为空？什么时候两栈为空？0 1 2 S-1top2top1第20页，共73页，编辑于2022年，星期二a1 a2 aitop10 1 2 S-1top2bj b2 b1栈满条件栈满条件为：为：top2=top1+1什么时候栈为满？什么时候栈为满？第21页，共73页，编辑于2022年，星期二（）链式栈（）链式栈栈的栈的链式存储链式存储结构结构如何改造链表实现栈的链接存储？链栈需要加如何改造链表实现栈的链接存储？链栈需要加头结点吗？将
16、哪一端作为栈顶？头结点吗？将哪一端作为栈顶？注：注：链栈不需要附设头结点。链栈不需要附设头结点。(栈底栈底)(栈顶栈顶)topa3a2a4a1第22页，共73页，编辑于2022年，星期二链栈链栈类的定义：类的定义：template class LinkStack;/声明声明template class Node friend class LinkStack;private:type data;Node*next;/此处此处也可以省略也可以省略;template class LinkStackpublic:LinkStack();/构造函数，置空链栈构造函数，置空链栈 LinkStack();/
17、析构函数，释放链栈中各结点的存储空间析构函数，释放链栈中各结点的存储空间 void Push(type item);/将元素将元素item入栈入栈 type Pop();/将栈顶元素出栈将栈顶元素出栈 type GetTop();/取栈顶元素（并不删除）取栈顶元素（并不删除）bool Empty();/判断链栈是否为空栈判断链栈是否为空栈private:Node*top;/栈顶指针即链栈的头指针栈顶指针即链栈的头指针;第23页，共73页，编辑于2022年，星期二链栈的链栈的构造函数算法构造函数算法实现实现template LinkStack:LinkStack()top=NULL;/初始化空栈
18、初始化空栈操作接口：操作接口：template LinkStack:LinkStack();算法实现：算法实现：第24页，共73页，编辑于2022年，星期二算法实现：算法实现：template void inkStack:Push(type x)Node*s;s=new Node;s-data=x;s-next=top;top=s;topanan-1a1链栈的入栈算法实现链栈的入栈算法实现 xstop操作接口：操作接口：template void LinkStack:Push(type x)；为为什什么么没没有有判判断断栈栈满满？第25页，共73页，编辑于2022年，星期二算法实现：算法实现：
19、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();topanan-1a1topp top+可以吗？可以吗？第26页，共73页，编辑于2022年，星期二顺序栈和链栈的比较顺序栈和链栈的比较时间性能：时间性能：相同，都是常数时间相同，都是常数时间O(1)。空间性能：空间性能：顺序栈：顺序栈：有元素个数的限制和空
20、间浪费的问题。有元素个数的限制和空间浪费的问题。链栈：链栈：没有没有栈满栈满的问题，只有当内存没有可用空间时的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个才会出现栈满，但是每个元素都需要一个指针域指针域，从而，从而产生了结构性产生了结构性开销开销。总之，采用总之，采用顺序栈存储顺序栈存储方式，方式，可可使多个栈使多个栈共享空间共享空间；当栈中元素当栈中元素个数变化个数变化较较大大，且存在多个栈的情况下，且存在多个栈的情况下，链链栈栈是栈的首选存储方式。是栈的首选存储方式。第27页，共73页，编辑于2022年，星期二1.调用函数或子程序非它莫属；调用函数或子程序非它莫属；2
21、.递归运算的有力工具；递归运算的有力工具；3.用于保护现场和恢复现场；用于保护现场和恢复现场；4.简化了程序设计的问题；简化了程序设计的问题；5.其它应用：如括号匹配问题、表达其它应用：如括号匹配问题、表达式计算问题等。式计算问题等。答：答：3 3、栈的应用举例、栈的应用举例为什么要设计栈？它有什么独特用途？为什么要设计栈？它有什么独特用途？第28页，共73页，编辑于2022年，星期二数制转换（十转八进制）数制转换（十转八进制）设计思路：设计思路：用用栈栈暂暂存存低位值低位值算法分析：算法分析：N N div 8 N mod 8 74 9 2 9 1 1 1 0 1栈的应用实例栈的应用实例：如
22、：如：(74)10=(112)8第29页，共73页，编辑于2022年，星期二void conversion()/对于输入的任意一个非负十进制整数，对于输入的任意一个非负十进制整数，/打印输出与其等值的八进制数；打印输出与其等值的八进制数；SeqStack s1(10);int N,n;int e;cout请输入一十进制数：请输入一十进制数：N;n=N;while(n)s1.Push(n%);n=n/;while(!s1.Empty()e=s1.Pop();coute;coutendl;第30页，共73页，编辑于2022年，星期二3.13.1栈栈（Stack）3.2 3.2 队列队列 （Queu
23、e）.逻辑结构逻辑结构.存储结构与实现存储结构与实现.应用实例应用实例.逻辑结构逻辑结构.存储结构与实现存储结构与实现第31页，共73页，编辑于2022年，星期二.2 .2 队列队列队列队列1 1、队列的逻辑结构、队列的逻辑结构空队：空队：不含任何数据元素的队列。不含任何数据元素的队列。（a1,a2,an）队列：队列：只允许在只允许在一端一端进行进行插入插入操作，而在操作，而在另一端另一端进行进行删删除除操作的操作的线性表线性表。队尾队尾队头队头允许允许插入插入的的一端一端称为称为队尾队尾，另一端另一端允许允许删除删除的称为的称为队头队头。数据元素之间的逻辑关系：数据元素之间的逻辑关系：一对一
24、一对一 。第32页，共73页，编辑于2022年，星期二注：注：队列队列的的运算规则运算规则只能在只能在队尾队尾进行进行插入插入运算，在运算，在队头队头进行进行删除删除运算运算;且访问结点时依照且访问结点时依照先进先出（先进先出（FIFO）或或后进后出后进后出（LILO）的原则。的原则。入队：入队：插入元素到队列的队尾的操作。插入元素到队列的队尾的操作。出队：出队：从队头删除一个元素的操作。从队头删除一个元素的操作。问：队列问：队列与与一般线性表一般线性表有什么不同？有什么不同？一般线性表一般线性表 队列队列逻辑结构：一对一逻辑结构：一对一 逻辑结构：一对一逻辑结构：一对一存储结构：顺序表、链表
25、存储结构：顺序表、链表 存储结构：顺序队、链队存储结构：顺序队、链队运算规则：运算规则：随机存取随机存取 运算规则：运算规则：先进先出先进先出(FIFO)第33页，共73页，编辑于2022年，星期二队列的操作特性：队列的操作特性：先进先出先进先出a1a2a3入队入队队尾队尾队头队头出队出队队头队头入队出队操作示意图入队出队操作示意图:队尾队尾队尾队尾队尾队尾第34页，共73页，编辑于2022年，星期二2、队列的存储结构与实现、队列的存储结构与实现顺序队列、链式队列顺序队列、链式队列（）顺序队列（）顺序队列队列的队列的顺序存储顺序存储结构结构(重点重点)如何改造数组实现队列的顺序存储？如何改造数
26、组实现队列的顺序存储？0 1 2 3 4 5 6 7 8a1确定确定用数组如何表示用数组如何表示队头、队尾队头、队尾。附设指示器附设指示器rear指示队尾元素（在数组中最后一个元素的指示队尾元素（在数组中最后一个元素的位置），指示器位置），指示器front指示队头（队头元素所在位置的前指示队头（队头元素所在位置的前一位置）。一位置）。rearSfront第35页，共73页，编辑于2022年，星期二0 1 2 3 4 入队入队出队出队实例实例1：a1a2a3a4依次入队依次入队a1a2a3a4rearrear rear rear入队操作时间性能为入队操作时间性能为O(1)front第36页，共7
27、3页，编辑于2022年，星期二实例实例2：a1a2依次出队依次出队0 1 2 3 4 入队入队出队出队a1a2a3a4rearfront front front出队操作时间性能为出队操作时间性能为O(1)队列的移动有什么特点？队列的移动有什么特点？整个队列向数组下标较大方向移动整个队列向数组下标较大方向移动单向移动性单向移动性第37页，共73页，编辑于2022年，星期二假溢出：假溢出：当元素被插入到数组中下标最大的位置上之后，当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽队列的空间就用尽了，了，尽管尽管此时数组的低端此时数组的低端还有空闲空间还有空闲空间，这，这种现象叫做假溢出。种
28、现象叫做假溢出。继续入队会出现什么情况？继续入队会出现什么情况？0 1 2 3 4 入队入队出队出队a3a4rearfronta5rear第38页，共73页，编辑于2022年，星期二循环队列：循环队列：将存储队列的将存储队列的数组头尾相接数组头尾相接。如何解决假溢出？如何解决假溢出？0 1 2 3 4 入队入队出队出队a3a4fronta5rearreara6第39页，共73页，编辑于2022年，星期二a3a2a10123N-1rearfront循环队列（臆造）循环队列（臆造）循环队列（臆造）循环队列（臆造）顺序队列顺序队列顺序队列顺序队列a3a2a1frontrear 0 1 2 3 .N-
29、1新问题：新问题：在循环队列中，空队特征是在循环队列中，空队特征是front=rear；队满；队满时也会有时也会有front=rear；判决条件将出现判决条件将出现二义性二义性！解决方案有三：解决方案有三：加设加设标志位标志位，让删除动作使其为，让删除动作使其为1,插入动作使其为插入动作使其为0,则可识别当前则可识别当前front=rear 使用一个使用一个计数器记录队列计数器记录队列中中元素个数元素个数（即（即队列长度队列长度）；）；人为人为浪费一个单元浪费一个单元，令，令队满特征为队满特征为front=(rear+1)%N；第40页，共73页，编辑于2022年，星期二队空条件队空条件:fr
30、ont=rear (初始化时：初始化时：front=rear)队满条件队满条件：front=(rear+1)%N (N=maxsize)队列长度：队列长度：L=（Nrearfront）%N J2 J3J1 J4 J5frontrear问问2：在具有在具有n个单元的循环队列个单元的循环队列中，队满时共有多少个元素？中，队满时共有多少个元素？n-1个个5 问问1：左图中队列长度左图中队列长度L=？第41页，共73页，编辑于2022年，星期二例例1 1：一循环队列如下图所示，若先删除一循环队列如下图所示，若先删除4 4个元素，接着再插入个元素，接着再插入4 4个元个元素，请问队头和队尾指针分别指向哪
31、个位置素，请问队头和队尾指针分别指向哪个位置?front J5rear解：解：由图可知，初始状态由图可知，初始状态,队头和队尾指针的初态分别为队头和队尾指针的初态分别为front=0和和rear=5。删除删除4个元素后个元素后(front+4)%6=4；再插入再插入4个元素后，个元素后，r=(rear+4)%6=(5+4)%6=3 frontfrontfrontfrontJ1J1J2 J5rearfrontrearrearrearrear J6 J7 J8 J9J3J4第42页，共73页，编辑于2022年，星期二动态循环队列动态循环队列类的定义：类的定义：（重点）（重点）/DCirQueue.
32、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 Isf
33、ull()constreturn(rear+1)%maxsize=front;/队列满则返回队列满则返回1，否则返回，否则返回0private:T*queue;/存放队列元素的数组存放队列元素的数组 int front,rear;/队头和队尾指针，分别指向队头元素的前一个位队头和队尾指针，分别指向队头元素的前一个位置和队尾元素的位置置和队尾元素的位置 int maxsize;/队列最大可容纳元素个数为队列最大可容纳元素个数为maxsize-1;#endif第43页，共73页，编辑于2022年，星期二循环队列的循环队列的构造函数算法构造函数算法实现实现template DCirQueue:DCi
34、rQueue(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 rearfront第44页，共73页，编辑于2022年，星期二循环队列的循环队列的入队算法入队算法实现实现template void DCirQueue:EnQueue(T x)if(rear+1)%maxsize=front)throw“队满队满;rear=(r
35、ear+1)%maxsize;/队尾指针在循环意义下加队尾指针在循环意义下加1 queuerear=x;/在队尾处插入元素在队尾处插入元素操作接口：操作接口：template void DCirQueue:EnQueue(T x)算法实现：算法实现：0 1 2 3 4 rearfrontreara1第45页，共73页，编辑于2022年，星期二循环队列的循环队列的出队算法出队算法实现实现template T DCirQueue:DeQueue()if(rear=front)throw 下溢下溢;front=(front+1)%maxsize;/队头指针在循环意义下加队头指针在循环意义下加1 re
36、turn queuefront;/读取并返回出队前的队头元素，注意队头指针读取并返回出队前的队头元素，注意队头指针操作接口：操作接口：template T DCirQueue:DeQueue()算法实现：算法实现：a10 1 2 3 4 入队入队a4a5a6出队出队frontrearfronta3第46页，共73页，编辑于2022年，星期二循环队列的循环队列的读队头元素算法读队头元素算法实现实现template T DCirQueue:GetQueue()int i;if(rear=front)throw“队空队空!;i=(front+1)%maxsize;/注意不要给队头指针赋值注意不要给队
37、头指针赋值 return queuei;操作接口：操作接口：template T DCirQueue:GetQueue()算法实现：算法实现：a10 1 2 3 4 a4a5a6出队出队frontreara3 i入队入队第47页，共73页，编辑于2022年，星期二（2 2）队列的链接存储结构及实现）队列的链接存储结构及实现 链队列：链队列：队列的链接存储结构队列的链接存储结构 队头指针即为链表的头指针；队头指针即为链表的头指针；常用不带头结点链表结构。常用不带头结点链表结构。a1a2an如何改造单链表实现队列的链接存储？如何改造单链表实现队列的链接存储？rearfront第48页，共73页，编
38、辑于2022年，星期二front=NULL;front=rear;空链队列如何表示？空链队列如何表示？rearfrontNULLNULL链队列满如何表示？链队列满如何表示？无需考虑满的情况。无需考虑满的情况。第49页，共73页，编辑于2022年，星期二链式队列链式队列类的定义：类的定义：template struct Node T data;Node*next;/此处此处也可以省略也可以省略;template class LinkQueuepublic:LinkQueue();/构造函数，初始化一个空的链队列构造函数，初始化一个空的链队列 LinkQueue();/析构函数，释放链队中各结点的
39、存储空间析构函数，释放链队中各结点的存储空间 void EnQueue(T x);/将元素将元素x入队入队 T DeQueue();/将队头元素出队将队头元素出队 T GetQueue();/取链队列的队头元素取链队列的队头元素 bool Empty();/判断链队列是否为空判断链队列是否为空private:Node*front,*rear;/队头和队尾指针，分别指向头结点和终端结点队头和队尾指针，分别指向头结点和终端结点;第50页，共73页，编辑于2022年，星期二链队的链队的构造函数算法构造函数算法实现实现template LinkQueue:LinkQueue()front=rear=N
40、ULL;操作接口：操作接口：template LinkQueue:LinkQueue()；算法实现：算法实现：第51页，共73页，编辑于2022年，星期二 xs链队列的实现链队列的实现入队入队fronta1anrearrearfront xsrearrear队不空核心算法描述：队不空核心算法描述：Node*s=new Node;s-data=x;s-next=NULL;rear-next=s;rear=s;操作接口：操作接口：template void LinkQueue:EnQueue(T x)NULLfront队空时核心算法描述：队空时核心算法描述：Node*s=new Node;s-da
41、ta=x;s-next=NULL;front=rear=s;第52页，共73页，编辑于2022年，星期二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;算法实现：算法实现：第53页，共73页，编辑于2022年，星期二链队列的实现链队列的实
42、现出队出队操作接口：操作接口：template T LinkQueue:DeQueue()fronta2anrearNode*p=front;x=p-data;Front=NULL;rear=front;delete p;p a2rear队列不空时算法描述：队列不空时算法描述：Node*p=front;x=p-data;front=front-next;delete p;队列只有一个元素时队列只有一个元素时?a1frontfrontP第54页，共73页，编辑于2022年，星期二链队的链队的出队操作算法出队操作算法实现实现template T LinkQueue:DeQueue()Node *p
43、;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()；算法实现：算法实现：第55页，共73页，编辑于2022年，星期二链队的链队的获得队首元素操作算法获得队首元素操作算法实现实现template T LinkQueue:Ge
44、tQueue()if(front!=NULL)return front-data;操作接口：操作接口：template T LinkQueue:GetQueue()算法实现：算法实现：第56页，共73页，编辑于2022年，星期二队列的其它链接存储结构队列的其它链接存储结构用带头结点的单链表实现队列的链接存储？用带头结点的单链表实现队列的链接存储？队头指针即为链表的头指针，指向头结点。队头指针即为链表的头指针，指向头结点。a1a2anrearfront空链队列空链队列frontrear第57页，共73页，编辑于2022年，星期二 xsfronta1anrearrearfront xsrearre
45、ar核心算法描述：核心算法描述：Node*s=front-next;s-data=x;s-next=NULL;rear-next=s;rear=s;队列为空时如何入队如何操作？队列为空时如何入队如何操作？用带头结点的单链表如何实现队列的入队操用带头结点的单链表如何实现队列的入队操作？作？第58页，共73页，编辑于2022年，星期二fronta1anrearfronta1prearrear核心算法描述：核心算法描述：Node*p=front-next;x=p-data;front-next=p-next;delete p;队列中仅有一个元素时出队如何操作？队列中仅有一个元素时出队如何操作？用带头
46、结点的单链表如何实现队列的出队操用带头结点的单链表如何实现队列的出队操作？作？a2p核心算法描述：核心算法描述：rear=front;第59页，共73页，编辑于2022年，星期二练习练习1：数组数组n用来表示一个循环队列，用来表示一个循环队列，f 为当前队列首元素的为当前队列首元素的前一前一位位置，置，r 为队尾元素的位置。假定队列中元素的个数小于为队尾元素的位置。假定队列中元素的个数小于n，计算队列中元素，计算队列中元素个数的公式为个数的公式为:（）（）rf （）（）（nfr）%n （）（）nrf （）（）（nrf）%n4种公式哪种合理？种公式哪种合理？当当 r f 时（时（A）合理；）合理
47、；当当 r 10 1 1 2 3 5 8 13 第70页，共73页，编辑于2022年，星期二递归算法递归算法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。第71页，共73页，编辑于2022年，星期二例、问题的解法是递归的：例、问题的解法是递归的：利用利用递归思想递归思想来求解某类问题（本身没有明显来求解某类问题（本身没有明显的递归结构，但的递归结构，但操作方法可操作方法可以以用递归用递归很
48、好的很好的描述描述）使其更为简单。使其更为简单。如：汉诺塔问题、背包问题、八皇后问题等。如：汉诺塔问题、背包问题、八皇后问题等。（3）有的数据结构如二叉树、广义表、图等（如树）有的数据结构如二叉树、广义表、图等（如树的遍历、图的搜索）定义。的遍历、图的搜索）定义。第72页，共73页，编辑于2022年，星期二小结：小结：递归算法的递归算法的缺点缺点：费时、费内存空间，效率往：费时、费内存空间，效率往往很低。往很低。递归算法的递归算法的优点优点：它能使一个蕴含递归关系且结：它能使一个蕴含递归关系且结构复杂的程序简洁、清晰、精炼、增加可读性。构复杂的程序简洁、清晰、精炼、增加可读性。第73页，共73页，编辑于2022年，星期二