数据结构(C语言版)严蔚敏清华大学出版社第三章栈和队列.ppt

《数据结构(C语言版)严蔚敏清华大学出版社第三章栈和队列.ppt》由会员分享，可在线阅读，更多相关《数据结构(C语言版)严蔚敏清华大学出版社第三章栈和队列.ppt（207页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性结构特点线性结构特点概念：线性表，记录，文件，表概念：线性表，记录，文件，表长，空表，位序长，空表，位序线性表的顺序存储和链式存储线性表的顺序存储和链式存储12/7/20221从从数数据据类类型型角角度度看看，它它们们是是和和线线性性表表大大不不相相同的抽象数据类型。同的抽象数据类型。从从数据结构角度数据结构角度看，栈和队列是两种特殊看，栈和队列是两种特殊的线性表，它们是操作受限的线性表，故的线性表，它们是操作受限的线性表，故也称为限定性的数据结构。也称为限定性的数据结构。4 4 第三章栈与队列内容介绍第三章栈与队列内容介绍12/7/20222 栈和队列的定义和特点栈和队列的定义和特点 熟

2、熟练练掌掌握握栈栈类类型型的的实实现现方方法法，特特别别应应注注意意栈栈满满和和栈栈空空的的条条件件以以及及它它们们的的描描述述方方法法。熟熟练练掌掌握握循循环环队队列列和和链链队队列列的的基基本本操操作作实实现现算算法法，特特别别注注意意队满和队空的描述方法队满和队空的描述方法。能在相应的应用问题中正确选用它们。能在相应的应用问题中正确选用它们。l 栈栈l栈的应用举例栈的应用举例l栈和递归的实现栈和递归的实现l队列队列12/7/20223第十讲第十讲数据结构栈及其实现主讲：刘立嘉主讲：刘立嘉12/7/20224举例举例1：家里吃饭的碗，通常在洗干净后一个一个：家里吃饭的碗，通常在洗干净后一个

3、一个地落在一起存放，在使用时，若一个一个地拿，一地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。那只碗。举例举例2：在建筑工地上，使用的砖块从底往上一层：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿一层地码放，在使用时，将从最上面一层一层地拿取。取。1 1 生活中的栈生活中的栈12/7/20225a1a2.an进栈进栈出栈出栈栈顶栈顶栈底栈底用用铁路调度站表示栈铁路调度站表示栈12/7/202261.定义定义 限定只能在表的限定只能在表的一端一端进行插入和删除操作进行

4、插入和删除操作的线性表。特点：后进先出。的线性表。特点：后进先出。2.2.逻辑结构逻辑结构 与线性表相同，仍为一对一关系与线性表相同，仍为一对一关系。3.3.存储结构存储结构 用用顺序栈顺序栈或或链栈链栈存储均可，但以顺序存储均可，但以顺序栈更常见栈更常见4.4.运算规则运算规则 只能在只能在栈顶栈顶运算，且访问结点依照运算，且访问结点依照后后进先出进先出（LIFOLIFO）或或先进后出先进后出（FILOFILO）的原则。的原则。5.5.实现方式实现方式 关键是编写关键是编写入栈入栈和和出栈出栈函数，具体实函数，具体实现依顺序栈或链栈的存储结构有别而不同。现依顺序栈或链栈的存储结构有别而不同。

5、基本操作有基本操作有：建栈、判断栈满或栈空、入栈、出栈、建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值等等。读栈顶元素值等等。2 2 栈的基本概念栈的基本概念12/7/202276、栈、栈“上溢上溢”在栈满时还进行入栈运算，必定会产生空间的溢出在栈满时还进行入栈运算，必定会产生空间的溢出7 7、栈、栈“下溢下溢”当栈空时仍进行出栈运算，必定会产生空间的溢出。当栈空时仍进行出栈运算，必定会产生空间的溢出。上溢是一种出错状态，应该设法避免之；下溢则可上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以

6、下溢常常用来作为程序控制转终态都是空栈，所以下溢常常用来作为程序控制转移的条件。移的条件。12/7/20228栈栈栈栈是仅在是仅在表尾表尾进行插入、删除操作的线性表。进行插入、删除操作的线性表。表尾表尾(即即an端端)称为称为栈顶栈顶/top;表头表头(即即a1端端)称为称为栈底栈底/base例如：例如：栈栈S S=(a,a2,a3,.,an-1,an)插入元素到栈顶的插入元素到栈顶的操作，称为操作，称为入栈入栈。从栈顶删除最后一从栈顶删除最后一个元素的操作，称个元素的操作，称为为出栈出栈。a an n称为栈顶元素称为栈顶元素a a1 1称为栈底元素称为栈底元素强调：强调：强调：强调：插入和删

7、除都只能在表插入和删除都只能在表的一端（栈顶）进行！的一端（栈顶）进行！注：堆栈可以完成比较复杂的数据元素特定序列的转换任务，但它不能完成任何输入输出序列的转换任务。12/7/20229例例1 1：堆栈是什么？它与一般线性表有什么不同？：堆栈是什么？它与一般线性表有什么不同？堆栈是一种特殊的线性表，它只能在表的堆栈是一种特殊的线性表，它只能在表的一端（即一端（即栈顶）栈顶）进行插入和删除运算。进行插入和删除运算。与一般线性表的区别：仅在于与一般线性表的区别：仅在于运算规则运算规则运算规则运算规则不同。不同。一般线性表一般线性表一般线性表一般线性表堆栈堆栈堆栈堆栈逻辑结构：逻辑结构：1:1逻辑结

8、构：逻辑结构：1:1存储结构：顺序存储结构：顺序表表、链、链表表存储结构：顺序存储结构：顺序栈栈、链、链栈栈运算规则：运算规则：随机存取随机存取随机存取随机存取运算规则：运算规则：后后后后进进进进先先先先出出出出(LIFO)“进进”插入插入=压入压入“出出”删除删除=弹弹出出12/7/202210例例2 2、一个栈的输入序列为一个栈的输入序列为1,2,3，若在，若在入栈的过程中允入栈的过程中允许出栈许出栈，则可能得到的出栈序列是什么？，则可能得到的出栈序列是什么？解：可以通过穷举所有可能性来求解：可以通过穷举所有可能性来求解：1 1入入1 1出，出，2 2入入2 2出，出，3 3入入3 3出，

9、出，即即123；1 1入入1 1出，出，2 2、3 3入，入，3 3、2 2出，出，即即132；1 1、2 2入，入，2 2出，出，3 3入入3 3出，出，即即231；1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出，即即213；1 1、2 2、3 3入，入，3 3、2 2、1 1出，出，即即321；合计有合计有5 5种可能性。种可能性。12/7/202211例例3 3、一个栈的输入序列是一个栈的输入序列是12345，若在，若在入栈的过入栈的过程中允许出栈程中允许出栈，则栈的输出序列则栈的输出序列43512可能实现可能实现吗？吗？12345的输出呢？的输出呢？解：解：4351

10、243512不可能实现，主要是其中的不可能实现，主要是其中的1212顺序不顺序不能实现；能实现；1234512345的输出可以实现，每压入一数便立即的输出可以实现，每压入一数便立即弹出即可。弹出即可。12/7/202212ADTStack数据对象：数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系：数据关系：R1|ai-1,aiD,i=2,.,n约定约定an端为端为栈顶栈顶，a1端为端为栈底栈底。3 3 栈的抽象数据类型定义栈的抽象数据类型定义12/7/202213InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s

11、)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit()ADTStack基本操作：基本操作：12/7/202214InitStack(&S)操作结果：构造一个空栈操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈初始条件：栈S已存在。已存在。操作结果操作结果：栈栈S被销毁。被销毁。12/7/202215StackEmpty(S)初始条件：栈初始条件：栈S已存在。已存在。操作结果：若栈操作结果：若栈S为空栈，则返回为空栈，则返回TRUE，否否则则FALE。StackLength(S)初始条件：栈

12、初始条件：栈S已存在。已存在。操作结果：返回操作结果：返回S的元素个数，即栈的长度。的元素个数，即栈的长度。12/7/202216GetTop(S,&e)初始条件：栈初始条件：栈S已存在且非空。已存在且非空。操作结果：用操作结果：用e返回返回S的栈顶元素。的栈顶元素。a1a2anClearStack(&S)初始条件：栈初始条件：栈S已存在。已存在。操作结果：将操作结果：将S清为空栈。清为空栈。12/7/202217Push(&S,e)初始条件：栈初始条件：栈S已存在。已存在。操作结果：插入元素操作结果：插入元素e为新的栈顶元素。为新的栈顶元素。a1a2ane12/7/202218Pop(&S,

13、&e)初始条件：栈初始条件：栈S已存在且非空。已存在且非空。操作结果：删除操作结果：删除S的栈顶元素，并用的栈顶元素，并用e返回其值。返回其值。a1a2anan-112/7/202219栈有两种存储表示方法：顺序栈、链栈。栈有两种存储表示方法：顺序栈、链栈。顺顺序序栈栈：即即栈栈的的顺顺序序存存储储结结构构是是利利用用一一组组地地址址连连续续的的存存储储单单元元依依次次存存放放自自栈栈底底到到栈栈顶顶的的数数据据元元素素，同同时时附附设设指指针针top指指示示栈栈顶顶元元素素在在顺顺序序栈栈中中的存储位置。的存储位置。习习惯惯做做法法是是以以top0表表示示空空栈栈，由由于于c语语言言中中数数

14、组组的的下下标标约约定定从从0开开始始，则则当当以以c作作描描述述语语言言时时，如如此此设设定定会会带带来来很很大大不不便便，另另一一方方面面，由由于于栈栈在在使使用用过过程程中中所所需需最最大大空空间间的的大大小小很很难难估估计计，因因此此，在在初初始始化化设设空空栈栈时时不不应应限限定定栈栈的的最最大大容容量。量。4 4 栈的顺序表示和实现栈的顺序表示和实现12/7/202220顺序（堆）栈顺序（堆）栈顺序存储结构的堆栈。顺序存储结构的堆栈。顺序栈的存储结构顺序栈的存储结构它是利用一组地址连续的存储它是利用一组地址连续的存储单元依次存放自栈底到栈顶的数单元依次存放自栈底到栈顶的数据元素，同

15、时设指针据元素，同时设指针top指示栈顶指示栈顶元素的当前位置。用元素的当前位置。用C语言定义：语言定义：typedefstructDataTypestackMaxStackSize;inttop;SeqStack;a0 a1 an-1顺序栈顺序栈Saian栈底栈底basebase栈顶栈顶top12/7/202221 a0 a1 an-1顺序栈顺序栈Sai问：顺序表和顺序栈的操作有何区别？问：顺序表和顺序栈的操作有何区别？表头表头表尾表尾低地址低地址高地址高地址写入：写入：Si=ai读出：读出：e=Si压入压入(PUSH)PUSH):SStop+top+=a=an n弹出弹出(POP)POP)

16、:e=Se=S-top-top 低地址低地址高地址高地址Si a0 a1ai an-1 顺序表顺序表S an以线性表以线性表S=(a0,a1,.,an-2,an-1)为为例例栈底栈底basebase栈顶栈顶toptop前提：一定要前提：一定要预设预设预设预设栈顶指针栈顶指针toptoptoptop栈顶栈顶toptop12/7/202222 top空栈toptoptoptoptopa 进栈b 进栈aababcdee 进栈abcdef 进栈溢出abdee 退栈c12/7/202223topc 退栈b 退栈abaa 退栈空空栈topabdd 退栈ctopabctoptop12/7/202224栈不存

17、在的条件：栈不存在的条件：base=NULL;栈为空栈为空的条件的条件：base=top;栈满的条件栈满的条件：top-base=MaxSize;a0 a1 an-1顺序栈顺序栈Sai低地址低地址高地址高地址an栈底栈底basebase栈顶栈顶toptop入栈入栈口诀：堆栈指针口诀：堆栈指针top“先先压后加压后加”:SStop+=a=an n出栈出栈口诀：堆栈指针口诀：堆栈指针top“先先减后弹减后弹”:e=Se=S-top 12/7/202225顺序栈的操作实现顺序栈的操作实现(1)初始化栈void StackInitiate(SeqStack*S)/*初始化顺序堆栈S*/S-top=0;

18、/*定义初始栈顶下标值*/12/7/202226(2)(2)判栈非空否判栈非空否 int StackNotEmpty(SeqStack S)/*判顺序堆栈S非空否，非空则返回1，否则返回0*/if(S.top top=MaxStackSize)printf(堆栈已满无法插入!n);return 0;else S-stackS-top=x;S-top+;return 1;12/7/202228(4)(4)出栈出栈int StackPop(SeqStack*S,DataType*d)/*弹出顺序堆栈S的栈顶数据元素值到参数d，出栈成功则返回1，否则返回0*/if(S-top top-;*d=S-s

19、tackS-top;return 1;12/7/202229(5)(5)取栈顶数据元素取栈顶数据元素int StackTop(SeqStack S,DataType*d)/*取顺序堆栈S的当前栈顶数据元素值到参数d，成功则返回1，否则返回0*/if(S.top stackS-top=x;S-top+;toptoptoptop低低地址地址L高地址高地址MBCD12/7/202231例：从栈中取出例：从栈中取出B B B BD DC CB BAtoptopD DC CABD DCB B B BAtopDCB B B BAtop低低地址地址L高地址高地址MD顺序栈出栈函数的核心语句：顺序栈出栈函数的

20、核心语句：S-top-;*d=S-stackS-top;注：DataType*d；SeqStack*S；12/7/202232两个堆栈共享空间b0t0t1b10maxSize-1V12/7/202233变化：考虑栈大小通常无法确定的情况下（1）首先确定一个基本容量STACK_INIT_SIZE，（2）一旦超过，每次再增加一定容量STACKINCREMENT。改进的顺序栈结构改进的顺序栈结构#define STACK_INIT_SIZE 100#define STACKINCREMENT 10Typedef structdatatype*base,*top;int stacksize;SqSta

21、ck;12/7/202234第十一讲第十一讲数据结构栈的链式实现及栈的应用(1)主讲：刘立嘉主讲：刘立嘉12/7/2022351、链栈的存储结构链栈的存储结构以头结点为栈顶，以头结点为栈顶，在在头结点头结点处处插入或删除插入或删除.栈也可以用链式结构来表示，用链式结构来表示的栈就是栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈链栈链栈中每个结点由两个域构成：链栈中每个结点由两个域构成：datadata域和域和nextnext域，其定义为：域，其定义为：typedefstructsnodeDataTypedata;structsnode*next;LSNode;栈底栈底h h a0 a1

22、an头结点nextdata栈顶栈顶1 1、栈的链式表示和实现栈的链式表示和实现12/7/2022362 2、链式堆栈的操作实现、链式堆栈的操作实现(1)入栈int StackPush(LSNode*head,DataType x)LSNode*p;if(p=(LSNode*)malloc(sizeof(LSNode)=NULL)printf(内存空间不足无法插入!n);return 0;p-data=x;p-next=head-next;/*新结点链入栈顶*/head-next=p;/*新结点成为新的栈顶*/return 1;12/7/202237(2)(2)出栈出栈int StackPop(

23、LSNode*head,DataType*d)LSNode*p=head-next;if(p=NULL)printf(堆栈已空出错！);return 0;head-next=p-next;/*删除原栈顶结点*/*d=p-data;/*原栈顶结点元素赋予d*/free(p);/*释放原栈顶结点内存空间*/return 1;注：由此可以看出：一个链栈由其由此可以看出：一个链栈由其栈顶指针唯一指定栈顶指针唯一指定 设设headhead指向栈顶元素，则指向栈顶元素，则head=NULL head=NULL 表示栈空表示栈空12/7/2022381)1)在链栈中的头结点对操作的实现影响不大，栈顶（表头）

24、在链栈中的头结点对操作的实现影响不大，栈顶（表头）操作频繁，操作频繁，可不设头结点可不设头结点链栈。链栈。2)2)一般一般不会出现栈满不会出现栈满情况；除非没有空间导致情况；除非没有空间导致mallocmalloc分配分配失败。失败。3)3)链栈的入栈、出栈操作就是栈顶的插入与删除操作，链栈的入栈、出栈操作就是栈顶的插入与删除操作，修修改指针即可完成改指针即可完成。4)4)采用链栈存储方式的优点是，可使采用链栈存储方式的优点是，可使多个栈共享空间多个栈共享空间；当；当栈中元素个数变化较大，且存在多个栈的情况下，链栈栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。是栈的首选存

25、储方式。几点说明几点说明:12/7/202239 由于栈结构具有的后进先出的固有特性，致由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个使栈成为程序设计中常用的工具。以下是几个栈应用的例子。栈应用的例子。十进制十进制N N和其它进制数的转换是计算机实现计和其它进制数的转换是计算机实现计算的基本问题算的基本问题,其解决方法很多其解决方法很多,其中一个简单其中一个简单算法基于下列原理算法基于下列原理:N=(N div d)*d+N mod dN=(N div d)*d+N mod d(其中其中:div:div为整除运算为整除运算,mod,mod为求余运算）为求余运算）

26、2 2、栈的应用举例栈的应用举例12/7/202240NNdiv8Nmod8134816841682102125202计计算算顺顺序序从从低低到到高高输输出出顺顺序序从从高高到到低低例如：（例如：（1348)10=(2504)8，其运算过程如下：，其运算过程如下：十进制数N和d进制数之间转换的算法原理：N=(N/d)*d+N%d即an-1a1a0topN%dN/d N12/7/202241voidconversion()initstack(S);scanf(“%d”,n);while(n)push(S,n%8);n=n/8;while(!Stackempty(S)pop(S,e);printf

27、(“%d”,e);2 25 50 04 4栈栈s sNNdiv8Nmod813481684168210212520212/7/202242假设在表达式中假设在表达式中（）或（）或（）等为等为正确正确的格式，的格式，（）或（）或（）或）或（）（）均为均为不正确不正确的格式。的格式。12/7/202243我们可以利用一个栈结构保存每个出现的左括号，我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。就可以得出

28、括号不匹配的结论。（1）当遇到某一个右括号时，栈已空，说明）当遇到某一个右括号时，栈已空，说明到目前为止，到目前为止，右括号多于左括号右括号多于左括号；（2）从栈中弹出的左括号与当前检验的右括）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了号类型不同，说明出现了括号交叉括号交叉情况；情况；（3）算术表达式输入完毕，但栈中还有没有）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明匹配的左括号，说明左括号多于右括号左括号多于右括号。12/7/202244例如：考虑下列括号序列：例如：考虑下列括号序列：()12345678(12/7/202245n回文游戏：顺读与逆读字符串一样（不含空

29、格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，回文字符串：“madam im adam”12/7/202246如何实现行编辑程序？如何实现行编辑程序？“每接受一个字符即存入存储器每接受一个字符即存入存储器”?并不恰当！并不恰当！12/7/202247合理的作法是：设立一个合理的作法是：设立一个输入缓冲区输入缓冲区，用，用以接受用户输入的一行字符，然后逐行存入以接受用户输入的一行字符，然后逐行存入用户数据区用户数据区，并假设，并假设“#”为退格符，为退格符，“”为退行符。为退行符。在用户输入一行的过程中，允许用户输入

30、在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。出差错，并在发现有误时可以及时更正。12/7/202248假设从终端接受了这样两行字符：假设从终端接受了这样两行字符：whli#ilr#e（s#*s)outchaputchar(*s=#+);则实际有效的是下列两行：则实际有效的是下列两行：while(*s)putchar(*s+);12/7/202249行编辑程序算法如下行编辑程序算法如下:voidLineEdit()initstack(s);ch=getchar();while(ch!=eof)while(ch!=eof&ch!=n)/EOF为全文结束符switch(c

31、h)case#:pop(s,c);case:clearstack(s);/重置S为空栈default:push(s,ch);12/7/202250ch=getchar();/从终端接收下一个字符从终端接收下一个字符/将从栈底到栈顶的字符传送至调用过程的数据区；将从栈底到栈顶的字符传送至调用过程的数据区；clearstack(s);if(ch!=eof)ch=getchar();destroystack(s);12/7/202251本节结束本节结束12/7/202252第十二讲第十二讲数据结构栈的应用(2)主讲：刘立嘉主讲：刘立嘉12/7/202253 出出口口入口入口1 1、栈的应用举例栈的应

32、用举例12/7/202254通常用的是通常用的是“穷举求解穷举求解”的方法的方法12/7/202255设定当前位置的初值为入口位置；设定当前位置的初值为入口位置；do若当前位置可通，若当前位置可通，则将则将当前位置插入栈顶当前位置插入栈顶；若该位置是出口位置，则算法结束；若该位置是出口位置，则算法结束；否则切换否则切换当前位置的东邻方块为新的当前位置的东邻方块为新的当前位置当前位置；求迷宫中一条从入口到出口的路径的算法：求迷宫中一条从入口到出口的路径的算法：12/7/202256若栈不空且栈顶位置尚有其他方向未被探索，若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为沿则设定新的当前

33、位置为沿顺时针方向旋转顺时针方向旋转找到的栈找到的栈顶位置的下一相邻块；顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，若栈不空但栈顶位置的四周均不可通，则则删去栈顶位置删去栈顶位置；/从路径中删去该通道块从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；一个可通的相邻块或出栈至栈空；若栈空，则表明迷宫没有通路。若栈空，则表明迷宫没有通路。while(栈不空）；栈不空）；否则否则12/7/202257TypedefstructIntord;/通道块在路径上的通道块在路径上的“序号序号”PosTypesea

34、t;/通道块在迷宫的通道块在迷宫的“坐标位置坐标位置”Intdi;/从此通道块走向下一通道块的从此通道块走向下一通道块的“方方向向”SElemType;/栈的元素类型栈的元素类型12/7/202258StatusMazePath(MazeTypemaze,PosTypestart,PosTypeend)InitStack(S);curpos=start;/设置设置“当前位置当前位置”为为“入口位置入口位置”Curstep=1;/探索第一步探索第一步DoIf(Pass(curpos)/当前位置当前位置可通可通，即是未曾走到过的通道块，即是未曾走到过的通道块footPrint(curpos);/留

35、下足迹留下足迹e=(curstep,curpos,1);Push(S,e);/加入路径加入路径If(curpos=end)return(TRUE);/到达终点到达终点curpos=NextPos(curpos,1);/下一位置是当前位置的东邻下一位置是当前位置的东邻Curstep+;/探索下一步探索下一步12/7/202259Else当前位置当前位置不可通不可通If(!StackEmpty(S)Pop(S,e);While(e.di=4&!StackEmpty(S)MarkPrint(e.seat);Pop(S,e);/留下不能通过的标记，并退回一步留下不能通过的标记，并退回一步If(e.di

36、4)e.di+;Push(S,e);/换下一个方向搜索换下一个方向搜索curpos=NextPos(e.seate.di);/设定当前位置是该新方向上的相邻块设定当前位置是该新方向上的相邻块while(!StackEmpty(S);Return(FALSE);12/7/202260 用不多于四种的颜色对地图着色，使相邻的行政区域不重色 基本思想：行政区与颜色分别编号，从（1）号行政区开始，每个区域依次用颜色进行试探，若当前颜色与周围区域不重色，则用栈记下该区域的颜色序号，否则用下一颜色进行试探；若用四种颜色试探均重色，则需退栈回溯，修改栈顶颜色序号，再进行试探。直到满足要求。12/7/2022

37、61(1)(2)(4)(5)(6)(7)(3)n地图四染色问题R77123456712345671 0 0 0 0 1 00 1 1 1 1 1 01 0 1 0 1 1 01 0 1 1 0 1 01 1 0 1 1 0 01 0 0 1 1 0 00 0 0 0 0 0 01234567122 3414334231#紫色紫色2#黄色黄色3#红色红色4#绿色绿色12/7/202262 已知n件物品各自的体积，背包容积为T，要求从n件中找出若干物物品，其体积之各恰好等于背包容积，看是否有解。解决思路：解决思路：顺序栈S用来存放放入背包内的物品序号（最多有n个元素）；参数T动态计算背包还可装入的

38、重量；依次装入试验，不满足时从后往前回溯。12/7/202263初始容量T=10，6件物品重分别为(4,7,3,5,4,2)473542WST=10top4735421WST=6top47354213WST=3top4735421WST=6top12/7/20226447354214WST=1top4735421WST=6top47354215WST=2top473542156WST=6top12/7/202265n n一一个个表表达达式式由由操操作作数数(亦亦称称运运算算对对象象)、操作符操作符(亦称运算符亦称运算符)和和分界符分界符组成。组成。n n算术表达式有三种表示：算术表达式有三种表

39、示：u中缀中缀(infix)表示表示 ，如如A+B；u前缀前缀(prefix)表示表示，如如+AB；u后缀后缀(postfix)表示表示，如如AB+；12/7/202266表达式的中缀表示表达式的中缀表示a+b*(c-d)-ef/gn n表达式中相邻两个操作符的计算次序为：表达式中相邻两个操作符的计算次序为：uu优先级高的先计算优先级高的先计算；uu优先级相同的自左向右计算优先级相同的自左向右计算；uu当使用括号时从最内层括号开始计算当使用括号时从最内层括号开始计算。rst1rst2rst3rst4rst5rst612/7/202267应用后缀表示计算表达式的值应用后缀表示计算表达式的值n n

40、从从左左向向右右顺顺序序地地扫扫描描表表达达式式，并并用用一一个个栈栈暂存扫描到的暂存扫描到的操作数操作数或或计算结果计算结果。n n在在后后缀缀表表达达式式的的计计算算顺顺序序中中已已隐隐含含了了加加括括号号的的优优先先次次序序，括括号号在在后后缀缀表表达达式式中中不出现。不出现。n n计算例计算例 abcd-*+efg/-rst1rst2rst3rst4rst5rst612/7/202268通过后缀表示计算表达式值的过程通过后缀表示计算表达式值的过程n顺序扫描表达式的每一项，根据它的类顺序扫描表达式的每一项，根据它的类型做如下相应操作：型做如下相应操作：u若该项是若该项是操作数操作数，则将

41、其，则将其压栈压栈；u若该项是若该项是操作符操作符，则则连续从栈连续从栈中退出两个操作数中退出两个操作数Y和和X，形成运算形成运算指令指令XY，并将计算结果重新并将计算结果重新压压栈栈。n当表达式的所有项都扫描并处理完后，当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。栈顶存放的就是最后的计算结果。12/7/202269后缀表达式的处理过程后缀表达式的处理过程操作顺序后缀表达式ABCD/E+T1 C/DABT1E+T2 B T1AT2E+T3 T2 EAT3+T4 A+T3T4中缀表达式：A+(B C/D)E后缀表达式：ABCD/E+12/7/202270本节结束本节结束12/

42、7/202271第十三讲第十三讲数据结构栈的应用(3)与递归函数主讲：刘立嘉主讲：刘立嘉12/7/202272利用栈将中缀表示转换为后缀表示利用栈将中缀表示转换为后缀表示n n使使用用栈栈可可将将表表达达式式的的中中缀缀表表示示转转换换成成它它的前缀表示和后缀表示。的前缀表示和后缀表示。n n为为了了实实现现这这种种转转换换，需需要要考考虑虑各各操操作作符符的优先级。的优先级。1 1、栈的应用举例栈的应用举例12/7/202273中缀表达式转换为后缀表达式中缀表达式转换为后缀表达式()#(#isp(op)，令令ch进进栈栈，读入下一个字符读入下一个字符ch。uu若若icp(ch)isp(OPT

43、R)，则则ch进进OPTR栈栈，从中缀表达式取下一字符送入，从中缀表达式取下一字符送入ch；若若icp(ch)#+#/+#/#+#=#12/7/202283表达式为表达式为#A*B+C/D#top2top1初态初态#(a)OSNSBA*#(b)NSOST1#(c)T1=A*BNSOSDCT1/+#(d)NSOS(g)NSOST2=C/DT2T1+#(e)NSOST3#(f)T3=T2+T1NSOSNSNS运算数栈，运算数栈，OSOS运算符栈运算符栈12/7/202284InitStack(OPTR);Push(OPTR,#);/OPTR运算符栈，运算符栈，OPND运算数栈运算数栈InitSta

44、ck(OPND);c=getchar();While(c!=#|GetTop(OPTR)!=#)If(!In(c,OP)Push(OPND,c);c=getchar();不是运算符则进栈不是运算符则进栈ElseSwitch(Precede(GetTop(OPTR),c)Case:/退栈并将运算结果入栈退栈并将运算结果入栈Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);Break;returnGetTop(OPND);OPTR运算符栈，运算符栈，OPND运算数栈运算数栈12/7/202286n将所有的将所有

45、的实在参数、返回地址实在参数、返回地址等信息传递给被等信息传递给被调用函数保存；调用函数保存；n为被调用函数的为被调用函数的局部变量局部变量分配存储区；分配存储区；n将将控制控制转移到被调用函数的入口。转移到被调用函数的入口。当在一个函数的运行期间调用另一个函数时，当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：在运行该被调用函数之前，需先完成三项任务：2 2、栈与函数调用机制栈与函数调用机制12/7/202287n保存保存被调函数的被调函数的计算结果计算结果；n释放释放被调函数的被调函数的数据区数据区；n依照被调函数保存的返回地址将依照被调函数保存的返回地址

46、将控制转移控制转移到到调调用函数用函数。从被调用函数返回调用函数之前，应该完成下列从被调用函数返回调用函数之前，应该完成下列三项任务：三项任务：12/7/202288多个函数嵌套调用的规则是：多个函数嵌套调用的规则是：此时的内存管理实行此时的内存管理实行“栈式管理栈式管理”后调用先返回后调用先返回！例如：例如：voidmain()a();/mainMain的数据区函数a的数据区函数b的数据区 voida()b();/avoidb()/b12/7/202289r主主程程序序srrrs子子程程序序1rst子子程程序序2rst子子程程序序3函数的嵌套函数的嵌套12/7/202290n递归函数：递归函

47、数：一个直接调用自己或通一个直接调用自己或通过一系列的调用语句间接地调用自过一系列的调用语句间接地调用自己的函数。己的函数。n递归算法：递归算法：描述递归定义的函数或求描述递归定义的函数或求解递归问题的过程称为递归算法。解递归问题的过程称为递归算法。递归算法的实质，是将较复杂的处理递归算法的实质，是将较复杂的处理归结为较简单的处理，直到最简单的归结为较简单的处理，直到最简单的处理。处理。3 3、栈结构与递归函数栈结构与递归函数12/7/202291递归算法优缺点：递归算法优缺点：n优点：结构清晰，易读，在高级语言中，优点：结构清晰，易读，在高级语言中，由系统管理堆栈，用户编程调试方便。由系统管

48、理堆栈，用户编程调试方便。n缺点：运行效率低，执行过程中反复入栈、缺点：运行效率低，执行过程中反复入栈、出栈，时间、空间开销大，算法优化困难。出栈，时间、空间开销大，算法优化困难。12/7/202292递归工作栈：递归工作栈：整个递归函数运行期间使用的数整个递归函数运行期间使用的数据存储区。据存储区。递归函数运行过程类似于多个函数的嵌套调用，递归函数运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数。只是调用函数和被调用函数是同一个函数。当前环境指针：当前环境指针：活动记录的栈顶指针。活动记录的栈顶指针。工作记录：工作记录：每一层递归所需信息。包括每一层递归所需信息。包括实

49、在参实在参数数、所有、所有局部变量局部变量以及上一层的以及上一层的返回地址返回地址。活动记录：活动记录：当前执行层的工作记录必是递归当前执行层的工作记录必是递归工作栈栈顶的工作记录。工作栈栈顶的工作记录。12/7/202293递归函数递归函数intf(x)intx;inty,z;.z=f(x);return(2*z);f函数函数调用调用f函数函数n直接调用直接调用12/7/202294intf1(x)intx;inty,z;.z=f2(y);return(2*z);intf2(t)intt;inta,c;.c=f1(a);return(3+c);n间接调用间接调用12/7/202295n特点特

50、点:是无终止的递归调用，因此，应该给定一是无终止的递归调用，因此，应该给定一个限制递归次数的条件。个限制递归次数的条件。f 1函数调用 f2函数f 2函数调用 f1函数12/7/202296floatfac(intn)floatf;if(n0)printf(“n1n1时，需利用塔座时，需利用塔座y y作辅助塔座，若能设法将压作辅助塔座，若能设法将压在编号为在编号为n n的圆盘之上的的圆盘之上的n-1n-1个圆盘从塔座个圆盘从塔座x(x(依照上依照上述法则述法则)移至塔座移至塔座y y上，则可先将编号为上，则可先将编号为n n的圆盘从塔的圆盘从塔座座x x移至塔座移至塔座z z上，然后再将塔座上