《数据结构教程第3章栈和队列ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构教程第3章栈和队列ppt课件.ppt（102页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第第第第3 3章章章章 栈和队列栈和队列栈和队列栈和队列本章的基本内容是：本章的基本内容是：栈栈栈与递归栈与递归队列队列优先级队列优先级队列双端队列双端队列 数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3.13.1栈栈栈
2、栈3.1.1栈的定义栈的定义空栈：空栈：不含任何数据元素的栈。不含任何数据元素的栈。（a1,a2,an）栈：栈：限定仅在限定仅在表尾表尾进行插入和删除操作的进行插入和删除操作的线性表线性表。栈顶栈顶栈底栈底允许插入和删除的一端称为允许插入和删除的一端称为栈顶栈顶，另一端称为，另一端称为栈底栈底。数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用a1a2a3入栈入栈出栈出栈栈底栈底栈顶栈顶插入：入栈、进栈、压栈插入：入栈、进栈、压栈删除
3、：出栈、弹栈删除：出栈、弹栈栈顶栈顶栈顶栈顶栈的示意图栈的示意图栈的操作特性：栈的操作特性：后进先出后进先出3.1.1栈的定义栈的定义3.13.1栈栈栈栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用栈的操作特性：栈的操作特性：后进先出后进先出a1a2a3入栈入栈出栈出栈栈底栈底插入：入栈、进栈、压栈插入：入栈、进栈、压栈删除：出栈、弹栈删除：出栈、弹栈栈顶栈顶栈的示意图栈的示意图3.1.1栈的定义栈的定义3.13.1栈栈栈栈数据
4、结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈底栈顶栈顶ab栈顶栈顶c栈顶栈顶情况情况1：3.1.1栈的定义栈的定义3.13.1栈栈栈栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，
5、应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用栈底栈底栈顶栈顶ab栈顶栈顶c栈顶栈顶出栈序列：出栈序列：c出栈序列：出栈序列：c、b出栈序列：出栈序列：c、b、a例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？情况情况1：3.1.1栈的定义栈的定义3.13.1栈栈栈栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的
6、损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用栈底栈底栈顶栈顶ab栈顶栈顶出栈序列：出栈序列：b情况情况2：例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？3.1.1栈的定义栈的定义3.13.1栈栈栈栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用栈底栈底a出栈序列：出栈序列：b出栈序列：出
7、栈序列：b、c出栈序列：出栈序列：b、c、ac栈顶栈顶栈顶栈顶注意：注意：栈只是对表插入和删除操作的位置进行了限栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。制，并没有限定插入和删除操作进行的时间。例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？情况情况2：3.1.1栈的定义栈的定义3.13.1栈栈栈栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的
8、要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用constintmaxSize=50enumboolfalse,true;templateclassStackpublic:Stack();virtualvoidPush(constT&x)=0;virtualboolPop(T&x)=0;virtualboolgetTop(T&x)const=0;virtualboolIsEmpty()const=0;virtualboolIsFull()const=0;virtualintgetSize()const=0;3.1.1栈的定义栈的定义栈栈的的类类定定义义3.13.1
9、栈栈栈栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3.1.2顺序栈顺序栈顺序栈顺序栈栈的顺序存储结构栈的顺序存储结构如何改造数组实现栈的顺序存储？如何改造数组实现栈的顺序存储？012345678a1确定用数组的哪一端表示栈底。确定用数组的哪一端表示栈底。附设指针附设指针top指示栈顶元素在数组中的位置。指示栈顶元素在数组中的位置。top3.13.1栈栈栈栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信
10、息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用出栈：出栈：top减减1进栈：进栈：top加加1栈空：栈空：top=-1 012345678a1topa2topa3top栈满：栈满：top=MAX_SIZE3.13.1栈栈栈栈3.1.2顺序栈顺序栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用顺顺序序栈栈类类定定义义templateclas
11、sSeqStack:publicStackpublic:SeqStack(intsz=50);SeqStack()deleteelements;voidPush(constT&x);boolPop(T&x);boolgetTop(T&x);boolIsEmpty()constreturn(top=-1)?true:false;boolIsFull()constreturn(top=maxSize-1)?true:false;intgetSize()constreturntop+1;voidMakeEmpty()top=-1;private:T*elements;inttop,maxSize;v
12、oidoverflowProcess();3.13.1栈栈栈栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用顺序栈的实现顺序栈的实现构造函数构造函数templateSeqStack:SeqStack(intsz):top(-1),maxSize(sz)elements=newTmaxSize;assert(elements!=NULL);/断言：动态存储分配成功与否断言：动态存储分配成功与否注意断言的使用！注意断言的使用！3.13
13、.1栈栈栈栈3.1.2顺序栈顺序栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用顺序栈的实现顺序栈的实现入栈入栈templatevoidSeqStack:Push(constT&x)if(IsFull()=true)overflowProcess();elements+top=x;时间复杂度？时间复杂度？3.13.1栈栈栈栈3.1.2顺序栈顺序栈具体实现见P90数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院
14、信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用顺序栈的实现顺序栈的实现出栈出栈templateboolSeqStack:Pop(T&x)if(IsEmpty()=true)returnfalse;x=elementstop-;returntrue;时间复杂度？时间复杂度？3.13.1栈栈栈栈3.1.2顺序栈顺序栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品
15、的价款或接受服务的费用两栈共享空间两栈共享空间解决方案解决方案1：直接解决：为每个栈开辟一个数组空间。直接解决：为每个栈开辟一个数组空间。解决方案解决方案2：顺序栈单向延伸顺序栈单向延伸使用一个数组来存储两个栈使用一个数组来存储两个栈在一个程序中需要在一个程序中需要同时同时使用具有使用具有相同相同数据类型的数据类型的两个栈两个栈，如何顺序存储这两个栈？如何顺序存储这两个栈？会出现什么问题？如何解决？会出现什么问题？如何解决？3.13.1栈栈栈栈3.1.2顺序栈顺序栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费
16、者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用两栈共享空间：两栈共享空间：使用一个数组来存储两个栈，让一个使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。的末端，两个栈从各自的端点向中间延伸。两栈共享空间两栈共享空间3.13.1栈栈栈栈3.1.2顺序栈顺序栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的
17、价款或接受服务的费用栈栈0的底固定在下标为的底固定在下标为0的一端；的一端；栈栈1的底固定在下标为的底固定在下标为maxSize-1的一端。的一端。t0和和t1分别为栈分别为栈0和栈和栈1的栈顶指针；的栈顶指针；b0和和b1分别为栈分别为栈0和栈和栈1的栈底；的栈底；maxSize为整个数组空间的大小；为整个数组空间的大小；t00 1 2 maxSize-1t1b0b13.13.1栈栈栈栈两栈共享空间两栈共享空间3.1.2顺序栈顺序栈Vector数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受
18、到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用t0=b0什么时候栈什么时候栈0为空？为空？0 1 2 maxSize-1t1t03.13.1栈栈栈栈两栈共享空间两栈共享空间3.1.2顺序栈顺序栈Vectorb0b1数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用t0=b0什么时候栈什么时候栈0为空？为空？t00 1 2 maxSize-1什么时候栈什么时候栈1为空？为空？b1t1=b13.13.1栈栈栈栈两栈共享空间
19、两栈共享空间3.1.2顺序栈顺序栈Vectorb0t1数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用t0=b0什么时候栈什么时候栈0为空？为空？t00 1 2 maxSize-1t1什么时候栈什么时候栈1为空？为空？t1=b1什么时候栈满？什么时候栈满？t1=t0+13.13.1栈栈栈栈两栈共享空间两栈共享空间3.1.2顺序栈顺序栈Vectorb0b1数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学
20、院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用boolPush(DualStack&DS,Tx,intd)/在双栈中插入元素在双栈中插入元素x，d=0，插在栈插在栈0中，否则，插在栈中，否则，插在栈1中中if(DS.t0+1=DS.t1)returnfalse;if(d=0)DS.t0+;elseDS.t1-;DS.VectorDS.ti=x;returntrue;两栈共享空间的实现两栈共享空间的实现入栈入栈3.13.1栈栈栈栈3.1.2顺序栈顺序栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信
21、息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用两栈共享空间的实现两栈共享空间的实现退栈退栈3.13.1栈栈栈栈3.1.2顺序栈顺序栈boolPop(DualStack&DS,Tx,intd)/从双栈中推出栈顶元素从双栈中推出栈顶元素，d=0，从栈从栈0中退，否则，从栈中退，否则，从栈1中退中退if(DS.ti=DS.bi)returnfalse;x=DS.VectorDS.ti;if(d=0)DS.t0-;elseDS.t1+;returntrue;数据结构（数据结构（C版）版）南京中医药
22、大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3.1.3链式栈链式栈链栈：链栈：栈的链接存储结构栈的链接存储结构firsta1a2anai链栈需要加头结点吗？链栈需要加头结点吗？如何改造链表实现栈的链接存储？如何改造链表实现栈的链接存储？将哪一端作为栈顶？将哪一端作为栈顶？将链头作为栈顶，方便操作。将链头作为栈顶，方便操作。链栈不需要附设头结点。链栈不需要附设头结点。3.13.1栈栈栈栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经
23、营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用栈顶栈顶栈底栈底链栈：链栈：栈的链接存储结构栈的链接存储结构topanan-1a1firsta1a2anai两种示意图在内存中两种示意图在内存中对应同一种状态对应同一种状态topa1an-1an栈顶栈顶栈底栈底3.13.1栈栈栈栈3.1.3链式栈链式栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用链链栈栈
24、的的类类定定义义templateclassLinkedStack:publicStackpublic:LinkedStack():top(NULL)LinkedStack()makeEmpty();voidPush(constT&x);boolPop(T&x);boolgetTop(T&x)const;boolIsEmpty()constreturn(top=NULL)?true:false;intgetSize()const;voidMakeEmpty();private:LinkNode*top;3.13.1栈栈栈栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息
25、技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用算法描述：算法描述：templatevoidLinkedStack:Push(constT&x)top=newLinkNode(x,top);assert(top!=NULL);topanan-1a1链栈的实现链栈的实现入栈入栈 xtop3.13.1栈栈栈栈3.1.3链式栈链式栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者
26、购买商品的价款或接受服务的费用算法描述：算法描述：templateboolLinkedStack:Pop(constT&x)if(IsEmpty=true)returnfalse;LinkNode*p=top;top=top-link;x=p-data;deletep;returntrue;链栈的实现链栈的实现退栈退栈topanan-1a1topp top+可以吗？可以吗？3.13.1栈栈栈栈3.1.3链式栈链式栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者
27、购买商品的价款或接受服务的费用顺序栈和链栈的比较顺序栈和链栈的比较时间性能：时间性能：相同，都是常数时间相同，都是常数时间O(1)。空间性能：空间性能：顺序栈：有元素个数的限制和空间浪费的问题。顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。域，从而产生了结构性开销。总之，当栈的使用过程中元素总之，当栈的使用过程中元素个数变化个数变化较大时，用较大时，用链栈是适宜的，反之，应该采用顺序栈。链栈是适宜的，反
28、之，应该采用顺序栈。3.13.1栈栈栈栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3.23.2栈与递归栈与递归栈与递归栈与递归3.2.1递归的概念递归的概念子程序（或函数）直接调用自己或通过一系列调子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种用语句间接调用自己，是一种描述问题描述问题和和解决问解决问题题的基本方法。的基本方法。递归的基本思想递归的基本思想问题分解：问题分解：把一个不能或不好解决的大问题转
29、化把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分为一个或几个小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解成更小的小问题，直至每个小问题都可以直接解决。解决。递归的定义递归的定义数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用递归的要素递归的要素 递归边界条件：递归边界条件：确定递归到何时终止，确定递归到何时终止，也称也称为递归出口；为递归出口；递归模式：大问题是如何分解为小问
30、题的，递归模式：大问题是如何分解为小问题的，也称为递归体。也称为递归体。3.23.2栈与递归栈与递归栈与递归栈与递归3.2.1递归的概念递归的概念数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用以下以下3中情况需要用到递归的方法中情况需要用到递归的方法 定义是递归的；定义是递归的；数据结构是递归的；数据结构是递归的；问题的解法是递归的。问题的解法是递归的。3.23.2栈与递归栈与递归栈与递归栈与递归3.2.1递归的概念递归的概念数据
31、结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例例1 1 阶乘函数阶乘函数递归算法递归算法intfact(intn)if(n=0)return1;elsereturnn*fact(n-1);-*=时时当当时时当当)!1(1!n1n1nnn3.23.2栈与递归栈与递归栈与递归栈与递归数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损
32、失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用求解阶乘求解阶乘 n!n!的过程的过程计算计算计算计算fact(4)计算计算4*fact(3)计算计算3*fact(2)计算计算2*fact(1)计算计算fact(1)递递递递归归归归调调调调用用用用回回回回归归归归求求求求值值值值返回返回24返回返回6返回返回2返回返回13.23.2栈与递归栈与递归栈与递归栈与递归数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n n 一个结
33、点，它的指针域为一个结点，它的指针域为NULL，是是一个单链表一个单链表;n n 一个结点，它的指针域指向单链表，一个结点，它的指针域指向单链表，仍是一个单链表。仍是一个单链表。单链表结构单链表结构f f 3.23.2栈与递归栈与递归栈与递归栈与递归数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用搜索链表最后一个结点的算法搜索链表最后一个结点的算法LinkNode*FindRear(LinkNode*f)if(f=NULL)retu
34、rn NULL;elseif(f-link=NULL)return f;else return FindRear(f-link);f f f f f a0a1a2a3a4递归找链尾3.23.2栈与递归栈与递归栈与递归栈与递归数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用递归的经典问题递归的经典问题汉诺塔问题汉诺塔问题 在世界刚被创建的时候有一座钻石宝塔（塔在世界刚被创建的时候有一座钻石宝塔（塔A），），其其上有上有64个金碟。所有
35、碟子按从大到小的次序从塔底堆放至个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔和塔C）。）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔上的碟子移动到塔C上去，其间借助于塔上去，其间借助于塔B的帮助。每次只的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。的碟子上面。当牧师们完成任务时，世界末日也就到了。3.23.2栈与递归栈与递
36、归栈与递归栈与递归数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用汉诺塔问题的递归求解汉诺塔问题的递归求解:如如果果n=1，则则将将这这一一个个盘盘子子直直接接从从塔塔A移移到到塔塔C上。否则，执行以下三步：上。否则，执行以下三步：将塔将塔A上的上的n-1个碟子借助塔个碟子借助塔C先移到塔先移到塔B上；上；把塔把塔A上剩下的一个碟子移到塔上剩下的一个碟子移到塔C上；上；将将n-1个碟子从塔个碟子从塔B借助于塔借助于塔A移到塔移到塔C
37、上。上。3.23.2栈与递归栈与递归栈与递归栈与递归数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用voidHanoi(intn,charA,charB,charC)if(n=1)Move(A,C);elseHanoi(n-
38、1,A,C,B);Move(A,C);Hanoi(n-1,B,A,C);3.23.2栈与递归栈与递归栈与递归栈与递归数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用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)Hanio(1,A,B,C)Hanio(2,A,C,B)Move(C,B)Hanio(1,C,A,B)Move(A,C)Ha
39、nio(2,B,A,C)Hanio(1,B,C,A)Move(B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move(A,C)Hanio(2,B,A,C)Move(B,A)Hanio(1,A,B,C)结束结束数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3.2.2递归过程与递归工作栈递归过程与递归工作栈3.23.2栈与递归栈与递归栈与递归栈与递归n n递归过程在实现时，需要自己调用自己。递归过程在实现时，需要自己
40、调用自己。n n层层向下递归，退出时的次序正好相反：层层向下递归，退出时的次序正好相反：递归调用递归调用 n!(n-1)!(n-2)!1!0!=1返回次序返回次序n n主程序第一次调用递归过程为主程序第一次调用递归过程为外部调用外部调用；n n递归过程每次递归调用自己为递归过程每次递归调用自己为内部调用内部调用。n n它们它们返回返回调用它的过程的调用它的过程的地址地址不同。不同。数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n
41、n每一次递归调用时，需要为过程中使用每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。的参数、局部变量等另外分配存储空间。n n每层递归调用需分配的空间形成递归工每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。作记录，按后进先出的栈组织。局部变量局部变量返回地址返回地址参参数数活动活动记录记录框架框架递归递归工作记录工作记录3.23.2栈与递归栈与递归栈与递归栈与递归3.2.2递归过程与递归工作栈递归过程与递归工作栈递归工作栈递归工作栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照
42、消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用.Function().调用块函数块返回地址(下一条指令)局部变量 参数3.2栈与递归栈与递归3.2.2递归过程与递归工作栈递归过程与递归工作栈函函数数递递归归调调用用时时的的活活动动记记录录数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用long Factorial(long n)int temp;if(n=0)return 1;/活动记录退栈活
43、动记录退栈else temp=n*Factorial(n-1);/新记录入栈新记录入栈 RetLoc2 /返回地址返回地址RetLoc1在计算语句在计算语句return temp;voidmain()longn;/调用调用Fact(4)时的记录进栈时的记录进栈n=Factorial(4);/返回地址返回地址RetLoc1在赋值语句在赋值语句RetLoc1coutnendl;3.2栈与递归栈与递归3.2.2递归过程与递归工作栈递归过程与递归工作栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到
44、的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用计算计算计算计算FactFact时活动记录的内容时活动记录的内容时活动记录的内容时活动记录的内容递递归归调调用用序序列列4RetLoc124参数参数参数参数 返回地址返回地址返回地址返回地址 局部变量局部变量局部变量局部变量 返回时的指令返回时的指令返回时的指令返回时的指令RetLoc2return4*6/返回返回返回返回2424RetLoc2return3*2/返回返回返回返回6 6RetLoc2return1/返回返回返回返回1 1RetLoc2return1*1/返回返回返回返回1 1RetLoc2return2*1/返回返回返
45、回返回2 23.2栈与递归栈与递归3RetLoc262RetLoc221RetLoc210RetLoc21RetLoc1:n=Fact(4);/返回返回返回返回mainmain数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用递归过程变为非递归过程递归过程变为非递归过程n n递归过程简洁、易编、易懂递归过程简洁、易编、易懂n n递归过程递归过程效率低效率低，重复计算多，重复计算多n n改为非递归过程的目的是改为非递归过程的目的是提高效
46、率提高效率n n单向递归单向递归和和尾递归尾递归可直接用可直接用迭代迭代实现其实现其非递归过程非递归过程n n其他情形必须借助其他情形必须借助栈栈实现非递归过程实现非递归过程3.2栈与递归栈与递归3.2.2递归过程与递归工作栈递归过程与递归工作栈数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用用栈实现递归过程的非递归算法用栈实现递归过程的非递归算法3.2栈与递归栈与递归3.2.2递归过程与递归工作栈递归过程与递归工作栈如如F0=0,
47、F1=1,F2=1,F3=2,F4=3,F5=5求解斐波那契数列的递归算法求解斐波那契数列的递归算法long Fib(long n)if(n=1)returnn;elsereturn Fib(n-1)+Fib(n-2);数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用斐波那契数列的递归调用树斐波那契数列的递归调用树Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)
48、Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)3.2栈与递归栈与递归3.2.2递归过程与递归工作栈递归过程与递归工作栈用栈实现递归过程的非递归算法用栈实现递归过程的非递归算法数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)栈结点栈结点ntagtag=1,向左递归；向左递归；tag=2,向右递归向右递归3.2栈与递
49、归栈与递归3.2.2递归过程与递归工作栈递归过程与递归工作栈用栈实现递归过程的非递归算法用栈实现递归过程的非递归算法数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用long Fibnacci(long n)Stack S;Node*w;longsum=0;/反复执行直到所有终端结点数据累加完 do while(n 1)w-n=n;w-tag=1;S.push(w);n-;/向左递归到底,边走边进栈sum=sum+n;/执行求和 3.
50、2栈与递归栈与递归3.2.2递归过程与递归工作栈递归过程与递归工作栈用栈实现递归过程的非递归算法用栈实现递归过程的非递归算法数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 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();returnsu