1、线性结构特点线性结构特点概念：线性表，记录，文件，表概念：线性表，记录，文件，表长，空表，位序长，空表，位序线性表的顺序存储和链式存储线性表的顺序存储和链式存储从从数据类型角度数据类型角度看，它们是和线性表大不相看，它们是和线性表大不相同的抽象数据类型。同的抽象数据类型。从从数据结构角度数据结构角度看，栈和队列是两种特殊看，栈和队列是两种特殊的线性表，它们是操作受限的线性表，故的线性表，它们是操作受限的线性表，故也称为限定性的数据结构。也称为限定性的数据结构。4 4 第三章栈与队列内容介绍第三章栈与队列内容介绍 栈和队列的定义和特点栈和队列的定义和特点 熟练掌握栈类型的实现方法，特别应注熟练掌
2、握栈类型的实现方法，特别应注意意栈满和栈空的条件栈满和栈空的条件以及它们的描述方法。熟练以及它们的描述方法。熟练掌握循环队列和链队列的基本操作实现算法，特掌握循环队列和链队列的基本操作实现算法，特别注意别注意队满和队空的描述方法队满和队空的描述方法。能在相应的应用问题中正确选用它们。能在相应的应用问题中正确选用它们。l 栈栈l 栈的应用举例栈的应用举例l 栈和递归的实现栈和递归的实现 l 队列队列第十讲第十讲数据结构栈及其实现主讲：刘立嘉主讲：刘立嘉举例举例1：家里吃饭的碗，通常在洗干净后一个一个：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，地落在一起存放，在
3、使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。面的那只碗。举例举例2：在建筑工地上，使用的砖块从底往上一层：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地一层地码放，在使用时，将从最上面一层一层地拿取。拿取。1 1 生活中的栈生活中的栈 a1 a2 .an进栈进栈出栈出栈栈顶栈顶栈底栈底用铁路调度站表示栈用铁路调度站表示栈1.定义定义 限定只能在表的限定只能在表的进行插入和删除操进行插入和删除操作的线性表。特点：后进先出。作的线性表。特点：后进先出。2.2.逻辑结构逻辑结构 与线性表相同，
4、仍为一对一关系与线性表相同，仍为一对一关系。3.3.存储结构存储结构 用用或或存储均可，但以顺存储均可，但以顺序栈更常见序栈更常见4.4.运算规则运算规则 只能在只能在运算，且访问结点依照运算，且访问结点依照（LIFOLIFO）或）或（FILOFILO）的原则。）的原则。5.5.实现方式实现方式 关键是编写关键是编写和和函数，具体函数，具体实现依顺序栈或链栈的存储结构有别而不同。实现依顺序栈或链栈的存储结构有别而不同。基本操作有基本操作有：建栈、判断栈满或栈空、入栈、出建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值等等。栈、读栈顶元素值等等。2 2 栈的基本概念栈的基本概念6、栈、栈“上溢上溢
5、”在栈满时还进行入栈运算，必定会产生空间的溢在栈满时还进行入栈运算，必定会产生空间的溢出出7 7、栈、栈“下溢下溢”当栈空时仍进行出栈运算，必定会产生空间的溢当栈空时仍进行出栈运算，必定会产生空间的溢出。出。上溢是一种出错状态，应该设法避免之；下溢则上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。控制转移的条件。是仅在是仅在表尾表尾进行插入、删除操作的线性表。进行插入、删除操作的线性表。表尾表尾(即即 an 端端)称为
6、称为栈顶栈顶/top;表头表头(即即 a1 端端)称为称为栈底栈底/base例如：例如：栈栈=(a ,a2 ,a3 ,.,an-1 ,an)插入元素到栈顶的插入元素到栈顶的操作，称为操作，称为入栈入栈。从栈顶删除最后一从栈顶删除最后一个元素的操作，称个元素的操作，称为为出栈出栈。a an n称为栈顶元素称为栈顶元素a a1 1称为栈底元素称为栈底元素插入和删除都只能在表插入和删除都只能在表的一端（栈顶）进行！的一端（栈顶）进行！注：堆栈可以完成比较复杂的数据元素特定序列的转换任务，但它不能完成任何输入输出序列的转换任务。例例1 1：堆栈是什么？它与一般线性表有什么不同？：堆栈是什么？它与一般线
7、性表有什么不同？堆栈是一种特殊的线性表，它只能在表的堆栈是一种特殊的线性表，它只能在表的一端（即一端（即栈顶）栈顶）进行插入和删除运算。进行插入和删除运算。与一般线性表的区别：仅在于与一般线性表的区别：仅在于不同。不同。逻辑结构：逻辑结构：1:1 逻辑结构：逻辑结构：1:1 存储结构：顺序存储结构：顺序表表、链、链表表 存储结构：顺序存储结构：顺序栈栈、链、链栈栈运算规则：运算规则：运算规则：运算规则：(LIFO)“进进”插入插入=压入压入“出出”删除删除=弹弹出出例例2 2、一个栈的输入序列为一个栈的输入序列为1,2,3，若在，若在入栈的过程中允入栈的过程中允许出栈许出栈，则可能得到的出栈序
8、列是什么？，则可能得到的出栈序列是什么？解：可以通过穷举所有可能性来求解：可以通过穷举所有可能性来求解：1 1入入1 1出，出，2 2入入2 2出，出，3 3入入3 3出，出，即即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种可能性。种可能性。例例3 3、一个栈的输入序列是一个栈的输入序列是12345，若在，若在
9、入栈的过入栈的过程中允许出栈程中允许出栈，则栈的输出序列则栈的输出序列43512可能实现可能实现吗？吗？12345的输出呢？的输出呢？解：解：4351243512不可能实现，主要是其中的不可能实现，主要是其中的1212顺序不顺序不能实现；能实现；1234512345的输出可以实现，每压入一数便立即的输出可以实现，每压入一数便立即弹出即可。弹出即可。ADT Stack 数据对象：数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系：数据关系：R1|ai-1,aiD,i=2,.,n 约定约定an 端为端为栈顶栈顶，a1 端为端为栈底栈底。3 3 栈的抽象数据类型定义栈的抽象
10、数据类型定义InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit()ADT Stack基本操作：基本操作：InitStack(&S)操作结果：构造一个空栈操作结果：构造一个空栈 S。DestroyStack(&S)初始条件：栈初始条件：栈 S 已存在。已存在。操作结果：栈操作结果：栈 S 被销毁。被销毁。StackEmpty(S)初始条件：栈初始条件：栈 S 已存在。已存在。操作结果：若栈操作结果：若栈
11、S 为空栈，则返回为空栈，则返回 TRUE，否，否则则 FALE。StackLength(S)初始条件：栈初始条件：栈 S 已存在。已存在。操作结果：返回操作结果：返回 S 的元素个数，即栈的长度。的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈初始条件：栈 S 已存在且非空。已存在且非空。操作结果：用操作结果：用 e 返回返回 S 的栈顶元素。的栈顶元素。a1a2an ClearStack(&S)初始条件：栈初始条件：栈 S 已存在。已存在。操作结果：将操作结果：将 S 清为空栈。清为空栈。Push(&S,e)初始条件：栈初始条件：栈 S 已存在。已存在。操作结果：插入元素操作结
12、果：插入元素 e 为新的栈顶元素。为新的栈顶元素。a1a2ane Pop(&S,&e)初始条件：栈初始条件：栈 S 已存在且非空。已存在且非空。操作结果：删除操作结果：删除 S 的栈顶元素，并用的栈顶元素，并用 e 返回其返回其值。值。a1a2anan-1 栈有两种存储表示方法：顺序栈、链栈。栈有两种存储表示方法：顺序栈、链栈。顺序栈：即栈的顺序存储结构是利用一组地址连顺序栈：即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针素，同时附设指针top指示栈顶元素在顺序栈中指示栈顶元素在顺序栈中的存储位置。的存储位置。
13、习惯做法是以习惯做法是以top0表示空栈，由于表示空栈，由于c语言中数语言中数组的下标约定从组的下标约定从0开始，则当以开始，则当以c作描述语言时，作描述语言时，如此设定会带来很大不便，另一方面，由于栈如此设定会带来很大不便，另一方面，由于栈在使用过程中所需最大空间的大小很难估计，在使用过程中所需最大空间的大小很难估计，因此，在初始化设空栈时不应限定栈的最大容因此，在初始化设空栈时不应限定栈的最大容量。量。4 4 栈的顺序表示和实现栈的顺序表示和实现顺序（堆）栈顺序（堆）栈 顺序存储结构的堆栈。顺序存储结构的堆栈。顺序栈的存储结构顺序栈的存储结构 它是利用一组地址连续的存储它是利用一组地址连续
14、的存储单元依次存放自栈底到栈顶的数单元依次存放自栈底到栈顶的数据元素，同时设指针据元素，同时设指针top指示栈顶指示栈顶元素的当前位置。用元素的当前位置。用C语言定义：语言定义：typedef struct DataType stackMaxStackSize;int top;SeqStack;a0 a1 an-1顺序栈顺序栈S ai an栈底栈底栈顶栈顶top a0 a1 an-1顺序栈顺序栈S ai问：顺序表和顺序栈的操作有何区别？问：顺序表和顺序栈的操作有何区别？表头表头表尾表尾低地址低地址高地址高地址写入：写入：Si=ai读出：读出：e=Si压入压入(SStop+top+=a=an n
15、弹出弹出(e=Se=S-top-top 低地址低地址高地址高地址Si a0 a1 ai an-1 顺序表顺序表S an以线性表以线性表 S=(a0,a1 ,.,an-2,an-1)为例为例栈底栈底栈顶栈顶前提：一定要前提：一定要栈顶指针栈顶指针栈顶栈顶 top空栈toptoptoptoptopa 进栈b 进栈aababcdee 进栈abcdef 进栈溢出abdee 退栈ctopc 退栈b 退栈abaa 退栈空空栈topabdd 退栈ctopabctoptop栈不存在的条件：栈不存在的条件：base=NULL;栈为空栈为空 的条件的条件：base=top;栈满的条件栈满的条件 ：top-base
16、=MaxSize;a0 a1 an-1顺序栈顺序栈S ai低地址低地址高地址高地址 an栈底栈底栈顶栈顶入栈入栈口诀：堆栈指针口诀：堆栈指针top“先先压后加压后加”:SStop+=a=an n出栈出栈口诀：堆栈指针口诀：堆栈指针top“先先减后弹减后弹”:e=Se=S-top 顺序栈的操作实现顺序栈的操作实现(1)初始化栈void StackInitiate(SeqStack*S)/*初始化顺序堆栈S*/S-top=0;/*定义初始栈顶下标值*/(2)(2)判栈非空否判栈非空否 int StackNotEmpty(SeqStack S)/*判顺序堆栈S非空否，非空则返回1，否则返回0*/if
17、(S.top top=MaxStackSize)printf(堆栈已满无法插入!n);return 0;else S-stackS-top=x;S-top+;return 1;(4)(4)出栈出栈int StackPop(SeqStack*S,DataType*d)/*弹出顺序堆栈S的栈顶数据元素值到参数d，出栈成功则返回1，否则返回0*/if(S-top top-;*d=S-stackS-top;return 1;(5)(5)取栈顶数据元素取栈顶数据元素int StackTop(SeqStack S,DataType*d)/*取顺序堆栈S的当前栈顶数据元素值到参数d，成功则返回1，否则返回0
18、*/if(S.top stackS-top=x;S-top+;toptoptoptop低地址低地址L高地址高地址MBCD例：从栈中取出例：从栈中取出 AtoptopABCAtopDCAtop低地址低地址L高地址高地址MD顺序栈出栈函数的核心语句：顺序栈出栈函数的核心语句：S-top-;*d=S-stackS-top;注：DataType*d；SeqStack*S；两个堆栈共享空间b0 t0 t1 b10 maxSize-1V变化：考虑栈大小通常无法确定的情况下（1）首先确定一个基本容量STACK_INIT_SIZE，（2）一旦超过，每次再增加一定容量STACKINCREMENT。改进的顺序栈结
19、构改进的顺序栈结构#define STACK_INIT_SIZE 100#define STACKINCREMENT 10Typedef structdatatype*base,*top;int stacksize;SqStack;第十一讲第十一讲数据结构栈的链式实现及栈的应用(1)主讲：刘立嘉主讲：刘立嘉1、链栈的存储结构链栈的存储结构 以头结点为栈顶，以头结点为栈顶，在在头结点头结点处处插入或删除插入或删除.栈也可以用链式结构来表示，用链式结构来表示的栈就是栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈链栈链栈中每个结点由两个域构成：链栈中每个结点由两个域构成：datadata域和
20、域和nextnext域，其定义为：域，其定义为：typedef struct snode DataType data;struct snode *next;LSNode;栈底栈底 a0 a1an头结点nextdata栈顶栈顶1 1、栈的链式表示和实现栈的链式表示和实现2 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-
21、next;/*新结点链入栈顶*/head-next=p;/*新结点成为新的栈顶*/return 1;(2)(2)出栈出栈int StackPop(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指向栈顶元素，则指向栈
22、顶元素，则head=NULL head=NULL 表示栈空表示栈空1)1)在链栈中的头结点对操作的实现影响不大，栈顶（表在链栈中的头结点对操作的实现影响不大，栈顶（表头）操作频繁，头）操作频繁，可不设头结点可不设头结点链栈。链栈。2)2)一般一般不会出现栈满不会出现栈满情况；除非没有空间导致情况；除非没有空间导致mallocmalloc分分配失败。配失败。3)3)链栈的入栈、出栈操作就是栈顶的插入与删除操作，链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成修改指针即可完成。4)4)采用链栈存储方式的优点是，可使采用链栈存储方式的优点是，可使多个栈共享空间多个栈共享空间；当栈中元素
23、个数变化较大，且存在多个栈的情况下，当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。链栈是栈的首选存储方式。几点说明几点说明:由于栈结构具有的后进先出的固有特性，致由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几使栈成为程序设计中常用的工具。以下是几个栈应用的例子。个栈应用的例子。十进制十进制N N和其它进制数的转换是计算机实现计和其它进制数的转换是计算机实现计算的基本问题算的基本问题,其解决方法很多其解决方法很多,其中一个简单其中一个简单算法基于下列原理算法基于下列原理:N=(N div d)N=(N div d)*d+N mod dd+N
24、mod d(其中其中:div:div为整除运算为整除运算,mod,mod为求余运算）为求余运算）2 2、栈的应用举例栈的应用举例 N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2计算顺序计算顺序从低到高从低到高输出顺序输出顺序从高到低从高到低例如：（例如：（1348)10=(2504)8，其运算过程如下：，其运算过程如下：十进制数N和d进制数之间转换的算法原理：N=(N/d)*d+N%d即an-1a1a0topN%dN/d N1122110nndadadaaNvoid conversion()initstack(S);scanf(“%d”,n)
25、;while(n)push(S,n%8);n=n/8;while(!Stackempty(S)pop(S,e);printf(“%d”,e);2 25 50 04 4栈栈s sN N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2假设在表达式中假设在表达式中（）或（）或（）等为等为正确正确的格式，的格式，（）或（）或（）或）或（）（）均为均为不正确不正确的格式。的格式。我们可以利用一个栈结构保存每个出现的左括号，我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验
26、过程中，若遇到以下几种情况之一，情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。就可以得出括号不匹配的结论。（1）当遇到某一个右括号时，栈已空，说明）当遇到某一个右括号时，栈已空，说明到目前为止，到目前为止，右括号多于左括号右括号多于左括号；（2）从栈中弹出的左括号与当前检验的右括）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了号类型不同，说明出现了括号交叉括号交叉情况；情况；（3）算术表达式输入完毕，但栈中还有没有）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明匹配的左括号，说明左括号多于右括号左括号多于右括号。例如：考虑下列括号序列：例如：考虑下列括
27、号序列：()1 2 3 4 5 6 7 8(n回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，回文字符串：“madam im adam”如何实现行编辑程序？如何实现行编辑程序？“每接受一个字符即存入存储器每接受一个字符即存入存储器”?并不恰当！并不恰当！合理的作法是：设立一个合理的作法是：设立一个输入缓冲区输入缓冲区，用，用以接受用户输入的一行字符，然后逐行存入以接受用户输入的一行字符，然后逐行存入用户数据区用户数据区，并假设，并假设“#”为退格符，为退格符，“”为为退行符。退行
28、符。在用户输入一行的过程中，允许用户输入在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。出差错，并在发现有误时可以及时更正。假设从终端接受了这样两行字符：假设从终端接受了这样两行字符：whli#ilr#e（s#*s)outchaputchar(*s=#+);则实际有效的是下列两行：则实际有效的是下列两行：while(*s)putchar(*s+);行编辑程序算法如下行编辑程序算法如下:void LineEdit()initstack(s);ch=getchar();while(ch!=eof)while(ch!=eof&ch!=n)/EOF为全文结束符 switch(c
29、h)case#:pop(s,c);case :clearstack(s);/重置S为空栈 default:push(s,ch);ch=getchar();/从终端接收下一个字符从终端接收下一个字符 /将从栈底到栈顶的字符传送至调用过程的数据区；将从栈底到栈顶的字符传送至调用过程的数据区；clearstack(s);if(ch!=eof)ch=getchar();destroystack(s);本节结束本节结束第十二讲第十二讲数据结构栈的应用(2)主讲：刘立嘉主讲：刘立嘉 出出口口入口入口1 1、栈的应用举例栈的应用举例通常用的是通常用的是“穷举求解穷举求解”的方法的方法#$#$#$#设定当前位
30、置的初值为入口位置；设定当前位置的初值为入口位置；do 若当前位置可通，若当前位置可通，则将则将当前位置插入栈顶当前位置插入栈顶；若该位置是出口位置，则算法结束；若该位置是出口位置，则算法结束；否则切换否则切换当前位置的东邻方块为新的当前位置的东邻方块为新的 当前位置当前位置；求迷宫中一条从入口到出口的路径的算法：求迷宫中一条从入口到出口的路径的算法：若栈不空且栈顶位置尚有其他方向未被探索，若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为沿则设定新的当前位置为沿顺时针方向旋转顺时针方向旋转找到的栈找到的栈顶位置的下一相邻块；顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，若栈
31、不空但栈顶位置的四周均不可通，则则删去栈顶位置删去栈顶位置；/从路径中删去该通道块从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置，直至找若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；到一个可通的相邻块或出栈至栈空；若栈空，则表明迷宫没有通路。若栈空，则表明迷宫没有通路。while(栈不空）；栈不空）；否则否则 Typedef struct Int ord;/通道块在路径上的通道块在路径上的“序号序号”PosType seat;/通道块在迷宫的通道块在迷宫的“坐标位置坐标位置”Int di;/从此通道块走向下一通道块的从此通道块走向下一通道块的“方方向向”SEl
32、emType;/栈的元素类型栈的元素类型Status MazePath(MazeType maze,PosType start,PosType end)InitStack(S);curpos=start;/设置设置“当前位置当前位置”为为“入口位置入口位置”Curstep=1;/探索第一步探索第一步DoIf(Pass(curpos)/当前位置当前位置可通可通，即是未曾走到过的通道块，即是未曾走到过的通道块footPrint(curpos);/留下足迹留下足迹e=(curstep,curpos,1);Push(S,e);/加入路径加入路径If(curpos=end)return(TRUE);/到
33、达终点到达终点curpos=NextPos(curpos,1);/下一位置是当前位置的东邻下一位置是当前位置的东邻Curstep+;/探索下一步探索下一步Else当前位置当前位置不可通不可通If(!StackEmpty(S)Pop(S,e);While(e.di=4&!StackEmpty(S)MarkPrint(e.seat);Pop(S,e);/留下不能通过的标记，并退回一步留下不能通过的标记，并退回一步If(e.di4)e.di+;Push(S,e);/换下一个方向搜索换下一个方向搜索curpos=NextPos(e.seat e.di);/设定当前位置是该新方向上的相邻块设定当前位置是
34、该新方向上的相邻块while(!StackEmpty(S);Return(FALSE);用不多于四种的颜色对地图着色，使相邻的行政区域不重色 基本思想：行政区与颜色分别编号，从（1）号行政区开始，每个区域依次用颜色进行试探，若当前颜色与周围区域不重色，则用栈记下该区域的颜色序号，否则用下一颜色进行试探；若用四种颜色试探均重色，则需退栈回溯，修改栈顶颜色序号，再进行试探。直到满足要求。(1)(2)(4)(5)(6)(7)(3)n地图四染色问题R 7 7 1 2 3 4 5 6 71 2 3 4 5 6 7 1 0 0 0 0 1 00 1 1 1 1 1 01 0 1 0 1 1 01 0 1
35、1 0 1 01 1 0 1 1 0 01 0 0 1 1 0 00 0 0 0 0 0 01 2 3 4 5 6 7 122 3414334231#紫色紫色 2#黄色黄色3#红色红色4#绿色绿色 已知n件物品各自的体积，背包容积为T，要求从n件中找出若干物物品，其体积之各恰好等于背包容积，看是否有解。解决思路：解决思路：顺序栈S用来存放放入背包内的物品序号（最多有n个元素）；参数T动态计算背包还可装入的重量；依次装入试验，不满足时从后往前回溯。初始容量T=10，6件物品重分别为(4,7,3,5,4,2)473542WST=10top4735421WST=6top47354213WST=3to
36、p4735421WST=6top47354214WST=1top4735421WST=6top47354215WST=2top473542156WST=6topu中缀中缀(infix)表示表示 如如 A+B；u前缀前缀(prefix)表示表示 ，如如+AB；u后缀后缀(postfix)表示表示 ，如如 AB+；rst1rst2rst3rst4rst5rst6rst1rst2rst3rst4rst5rst6n顺序扫描表达式的每一项，根据它的类顺序扫描表达式的每一项，根据它的类型做如下相应操作：型做如下相应操作：u若该项是若该项是操作数操作数，则将其，则将其压栈压栈；u若该项是若该项是操作符操作符
37、，则，则连续从栈连续从栈中退出两个操作数中退出两个操作数Y和和X，形成运算形成运算指令指令XY，并将计算结果重新，并将计算结果重新压压栈栈。n当表达式的所有项都扫描并处理完后，当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。栈顶存放的就是最后的计算结果。后缀表达式的处理过程后缀表达式的处理过程操作顺序后缀表达式ABCD/E+T1 C/DABT1E+T2 B T1AT2E+T3 T2 EAT3+T4 A+T3T4中缀表达式：A+(B C/D)E后缀表达式：ABCD/E+本节结束本节结束第十三讲第十三讲数据结构栈的应用(3)与递归函数主讲：刘立嘉主讲：刘立嘉1 1、栈的应用举例栈的
38、应用举例中缀表达式转换为后缀表达式中缀表达式转换为后缀表达式()#(#+#/+#/#+#=#表达式为表达式为#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运算符栈运算符栈InitStack(OPTR);Push(OPTR,#);/OPTR运算符栈，运算符栈，OPND运算数栈运算数栈InitStack(OPND);c=getchar();While(c!=#|GetTop(OPTR
39、)!=#)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;return GetTop(OPND);OPTR运算符栈，运算符栈，OPND运算数栈运算数栈n将所有的将所有的实在参数、返回地址实在参数、返回地址等信息传递给被等信息传递给被调用函数保存；调用函数保存；n为被调用函
40、数的为被调用函数的局部变量局部变量分配存储区；分配存储区；n将将控制控制转移到被调用函数的入口。转移到被调用函数的入口。当在一个函数的运行期间调用另一个函数时，当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：在运行该被调用函数之前，需先完成三项任务：2 2、栈与函数调用机制栈与函数调用机制n保存保存被调函数的被调函数的计算结果计算结果；n释放释放被调函数的被调函数的数据区数据区；n依照被调函数保存的返回地址将依照被调函数保存的返回地址将控制转移控制转移到到调调用函数用函数。从被调用函数返回调用函数之前，应该完成下从被调用函数返回调用函数之前，应该完成下列三项任
41、务：列三项任务：多个函数嵌套调用的规则是：多个函数嵌套调用的规则是：此时的内存管理实行此时的内存管理实行“栈式管理栈式管理”后调用先返回后调用先返回！例如：例如：void main()a();/mainMain的数据区函数a的数据区函数b的数据区 void a()b();/avoid b()/br主程序主程序srrrs子程序子程序1rst子程序子程序2rst子程序子程序3函数的嵌套函数的嵌套n递归函数：递归函数：一个直接调用自己或一个直接调用自己或通过一系列的调用语句间接地调用通过一系列的调用语句间接地调用自己的函数。自己的函数。n递归算法：递归算法：描述递归定义的函数或描述递归定义的函数或求
42、解递归问题的过程称为递归算法。求解递归问题的过程称为递归算法。递归算法的实质，是将较复杂的处理递归算法的实质，是将较复杂的处理归结为较简单的处理，直到最简单的归结为较简单的处理，直到最简单的处理。处理。3 3、栈结构与递归函数栈结构与递归函数递归算法优缺点：递归算法优缺点：n优点：结构清晰，易读，在高级语言中，优点：结构清晰，易读，在高级语言中，由系统管理堆栈，用户编程调试方便。由系统管理堆栈，用户编程调试方便。n缺点：运行效率低，执行过程中反复入栈、缺点：运行效率低，执行过程中反复入栈、出栈，时间、空间开销大，算法优化困难。出栈，时间、空间开销大，算法优化困难。递归工作栈：递归工作栈：整个递
43、归函数运行期间使用的数整个递归函数运行期间使用的数据存储区。据存储区。递归函数运行过程类似于多个函数的嵌套调用，递归函数运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数。只是调用函数和被调用函数是同一个函数。当前环境指针：当前环境指针：活动记录的栈顶指针。活动记录的栈顶指针。工作记录：工作记录：每一层递归所需信息。包括每一层递归所需信息。包括实在参实在参数数、所有、所有局部变量局部变量以及上一层的以及上一层的返回地址返回地址。活动记录：活动记录：当前执行层的工作记录必是递归当前执行层的工作记录必是递归工作栈栈顶的工作记录。工作栈栈顶的工作记录。递归函数递归函数int f(
44、x)int x;int y,z;.z=f(x);return(2*z);f函数函数调用调用f函数函数n直接调用直接调用int f1(x)int x;int y,z;.z=f2(y);return(2*z);int f2(t)int t;int a,c;.c=f1(a);return(3+c);n间接调用间接调用n特点特点:是无终止的递归调用，因此，应该给定一是无终止的递归调用，因此，应该给定一个限制递归次数的条件。个限制递归次数的条件。f 1函数调用 f2函数f 2函数调用 f1函数 float fac(int n)float f;if(n0)printf(“n1n1时，需利用塔座时，需利用塔
45、座y y作辅助塔座，若能设法将压作辅助塔座，若能设法将压在编号为在编号为n n的圆盘之上的的圆盘之上的n-1n-1个圆盘从塔座个圆盘从塔座x(x(依照上依照上述法则述法则)移至塔座移至塔座y y上，则可先将编号为上，则可先将编号为n n的圆盘从塔的圆盘从塔座座x x移至塔座移至塔座z z上，然后再将塔座上，然后再将塔座y y上的上的n-1n-1个圆盘个圆盘(依依照上述法则照上述法则)移至塔座移至塔座z z上。而如何将上。而如何将n-1n-1个圆盘从一个圆盘从一个塔座移至另一个塔座的问题是一个和原问题具有个塔座移至另一个塔座的问题是一个和原问题具有相同特征属性的问题，只是问题的规模变小，因此相同
46、特征属性的问题，只是问题的规模变小，因此可以用同样的方法求解。可以用同样的方法求解。由此可得如算法所示的求解由此可得如算法所示的求解n n阶阶HanoiHanoi塔问题的递归塔问题的递归函数。函数。算法分析算法分析void hanoi(int n,char x,char y,char z)/将塔座将塔座x上按直径由小到大且至上而下编号为上按直径由小到大且至上而下编号为1至至n/的的n个圆盘按规则搬到塔座个圆盘按规则搬到塔座z上，上，y可用作辅助塔座。可用作辅助塔座。1 2 if(n=1)3 move(x,1,z);/将编号为的圆盘从将编号为的圆盘从x移到移到z4 else 5 hanoi(n-
47、1,x,z,y);/将将x上编号为至上编号为至n-1的的 /圆盘移到圆盘移到y,z作辅助塔作辅助塔6 move(x,n,z);/将编号为将编号为n的圆盘从的圆盘从x移到移到z7 hanoi(n-1,y,x,z);/将将y上编号为至上编号为至n-1的的 /圆盘移到圆盘移到z,x作辅助塔作辅助塔8 9 0 3 a b c返址 n x y z6 2 a c b6 1 a b c8 1 c a bvoid hanoi(int n,char x,char y,char z)12 if(n=1)3 move(x,1,z);4 else 5 hanoi(n-1,x,z,y);6 move(x,n,z);7
48、hanoi(n-1,y,x,z);8 9 递归工作栈（工作记录，活动记录，当前环境指针）递归工作栈（工作记录，活动记录，当前环境指针）main()int m;printf(Input number of disks”);scanf(%d,&m);printf(”Steps:%3d disks”,m);hanoi(m,A,B,C);(0)void hanoi(int n,char x,char y,char z)(1)(2)if(n=1)(3)move(1,x,z);(4)else(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)
49、(9)ABC1233 A B C 03 A B C 02 A C B 63 A B C 02 A C B 61 A B C 6ABC3 A B C 02 A C B 6 main()int m;printf(Input the number of disks scanf(%d,&m);printf(The steps to moving%3d hanoi(m,A,B,C);(0)void hanoi(int n,char x,char y,char z)(1)(2)if(n=1)(3)move(1,x,z);(4)else(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(
50、7)hanoi(n-1,y,x,z);(8)(9)ABC3 A B C 02 A C B 61 C A B 8ABC3 A B C 02 A C B 63 A B C 03 A B C 02 A C B 6 main()int m;printf(Input the number of disks scanf(%d,&m);printf(The steps to moving%3d hanoi(m,A,B,C);(0)void hanoi(int n,char x,char y,char z)(1)(2)if(n=1)(3)move(1,x,z);(4)else(5)hanoi(n-1,x,z,
