数据结构第三章学习教案.pptx

《数据结构第三章学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构第三章学习教案.pptx（93页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构(sh j ji u)第三章第三章第一页，共93页。第三章第三章 栈和队列栈和队列(duli)(duli)3.1 3.1 栈栈3.2 3.2 栈的应用栈的应用(yngyng)(yngyng)举例举例3.3 3.3 队列队列第1页/共93页第二页，共93页。3.1栈栈一、栈的定义一、栈的定义二、抽象数据类型栈的定义二、抽象数据类型栈的定义三、栈的表示和实现三、栈的表示和实现四、栈的应用四、栈的应用(yngyng)举例举例第2页/共93页第三页，共93页。一、一、栈的定义栈的定义(dngy)1 1定义定义栈栈(Stack)(Stack)是一种特殊的线性表，其插入和删除操作均在表的一

2、端是一种特殊的线性表，其插入和删除操作均在表的一端(ydun)(ydun)进行，是一种运算受限的线性表。进行，是一种运算受限的线性表。栈顶栈顶(top)(top)允许插入和删除的一端允许插入和删除的一端(ydun)(ydun)，又称表尾。，又称表尾。栈底栈底(bottom)(bottom)栈的另一端栈的另一端(ydun)(ydun)，又称表头。，又称表头。若给栈若给栈S=(a1,a2ai,an)S=(a1,a2ai,an)，则，则a1 a1 为栈底元素，为栈底元素，an an 为栈顶元素，如图所示。为栈顶元素，如图所示。进栈进栈(push)(push)在栈顶插入一个元素，在栈顶插入一个元素，又

3、称入栈或压入。又称入栈或压入。出栈出栈(pop)(pop)在栈顶删除一个元素，在栈顶删除一个元素，又称退栈或弹出。又称退栈或弹出。空栈空栈栈中没有元素栈中没有元素(n=0)(n=0)。3.3.1 1栈栈第3页/共93页第四页，共93页。2 2栈的特点栈的特点(tdin)(tdin)后进先出后进先出(Last In First Out(Last In First Out，简称，简称LIFO)LIFO)。又称栈为后进先出表又称栈为后进先出表(简称简称LIFOLIFO结构结构)。一、一、栈的定义栈的定义(dngy)3.13.1栈栈第4页/共93页第五页，共93页。对栈的操作除了在栈顶进行插入和删除外

4、，还有栈的初始化、判空及取栈顶元素等。对栈的操作除了在栈顶进行插入和删除外，还有栈的初始化、判空及取栈顶元素等。其抽象数据类型定义如下：其抽象数据类型定义如下：ADT Stack ADT Stack 数据对象：数据对象：D=ai|aiElemSetD=ai|aiElemSet，i=1,2ni=1,2n，n0n0 数据关系：数据关系：R=ai-1R=|ai-1ai|ai-1，aiDaiD，i=2,3,ni=2,3,n 基本操作：基本操作：InitStack(&s)InitStack(&s)操作结果操作结果(ji gu)(ji gu)：构造一个空栈：构造一个空栈s s。DestroyStack(&

5、s)DestroyStack(&s)操作结果操作结果(ji gu)(ji gu)：栈：栈s s被销毁。被销毁。ClearStack(&s)ClearStack(&s)操作结果操作结果(ji gu)(ji gu)：将：将s s清为空栈。清为空栈。二、二、抽象数据类型栈的定义抽象数据类型栈的定义(dngy)3.13.1栈栈第5页/共93页第六页，共93页。StackEmpty(s)StackEmpty(s)操作结果操作结果(ji gu)(ji gu)：若：若s s为空栈，则返回为空栈，则返回TRUETRUE，否则，否则FALSEFALSE。StackLength(s)StackLength(s)操

6、作结果操作结果(ji gu)(ji gu)：返回：返回s s的元素个数，即栈的长度。的元素个数，即栈的长度。GetTop(s,&e)GetTop(s,&e)操作结果操作结果(ji gu)(ji gu)：用：用e e返回返回s s的栈顶元素。的栈顶元素。Push(&s,e)Push(&s,e)操作结果操作结果(ji gu)(ji gu)：插入元素：插入元素e e为新的栈顶元素。为新的栈顶元素。Pop(&s,&e)Pop(&s,&e)操作结果操作结果(ji gu)(ji gu)：删除：删除s s的栈顶元素，并用的栈顶元素，并用e e返回其值。返回其值。StackTrasverse(s,visit(

7、)StackTrasverse(s,visit()操作结果操作结果(ji gu)(ji gu)：从栈底到栈顶依次对：从栈底到栈顶依次对s s的每个数据元素调用的每个数据元素调用 函数函数visit()visit()。一旦。一旦visit()visit()失败，则操作失效。失败，则操作失效。ADT StackADT Stack二、二、抽象数据类型栈的定义抽象数据类型栈的定义(dngy)3.13.1栈栈第6页/共93页第七页，共93页。两种存储表示方式：顺序存储和链式存储。两种存储表示方式：顺序存储和链式存储。1.1.栈的顺序存储及其基本操作的实现栈的顺序存储及其基本操作的实现(1)(1)栈的顺序

8、存储是利用一块连续的存储单元栈的顺序存储是利用一块连续的存储单元(cn ch dn yun)(cn ch dn yun)依次存放栈中的数据元素，并附一个指针依次存放栈中的数据元素，并附一个指针toptop指示当前栈顶。指示当前栈顶。采用顺序存储方式存储的栈称为顺序栈。采用顺序存储方式存储的栈称为顺序栈。(2)C(2)C语言描述顺序栈：语言描述顺序栈：用一维数组和一个栈顶指针用一维数组和一个栈顶指针Typedef struct Typedef struct elemtype stackMaxSize;elemtype stackMaxSize;int top;int top;stacktype;

9、stacktype;43210-1空栈空栈topatopbctop三、三、栈的表示栈的表示(biosh)和实现和实现3.13.1栈栈第7页/共93页第八页，共93页。用一个栈顶指针和一个栈底指针以及一个初始的存储空间用一个栈顶指针和一个栈底指针以及一个初始的存储空间#define STACK_INIT_SIZE 100#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define STACKINCREMENT 10typedef structtypedef struct selemtype*base;selemtype*base;sele

10、mtype*top;selemtype*top;int stacksize;int stacksize;sqstack;sqstack;连续的存储空间连续的存储空间 栈顶指针指示栈顶元素当前栈顶指针指示栈顶元素当前(dngqin)(dngqin)位置位置(用栈顶指针动态地反映栈中元素的变化情况用栈顶指针动态地反映栈中元素的变化情况)basetop空栈空栈baseatoptopb三、三、栈的表示栈的表示(biosh)和实现和实现3.3.1 1栈栈第8页/共93页第九页，共93页。(3)(3)基本操作的算法基本操作的算法(sun f)(sun f)用一维数组和一个栈顶指针用一维数组和一个栈顶指针A

11、 A定义一个栈定义一个栈设栈中数据类型为整型，用设栈中数据类型为整型，用stackstack数组存放栈中数据元素，定义一个栈类型数组存放栈中数据元素，定义一个栈类型stacktypestacktype：typedef int elemtype;typedef int elemtype;#define MaxSize 100;#define MaxSize 100;Typedef struct Typedef struct elemtype stackMaxSize;elemtype stackMaxSize;int top;int top;stacktype;stacktype;三、三、栈的表

12、示栈的表示(biosh)和实现和实现3.13.1栈栈第9页/共93页第十页，共93页。B B初始化栈：初始化栈：initstack(s)initstack(s)建立建立(jinl)(jinl)一个空栈一个空栈s s，实际上是将栈顶指针指向，实际上是将栈顶指针指向-1-1。Void initstack(stacktype*s)Void initstack(stacktype*s)s-top=-1;s-top=-1;C C判断栈是否为空栈：判断栈是否为空栈：stackempty(s)stackempty(s)若栈若栈s s为空则返回为空则返回1 1，否则返回，否则返回0 0。Int stackem

13、pty(stacktype*s)Int stackempty(stacktype*s)if(s-top=-1)return(1);if(s-top=-1)return(1);else return(0);else return(0);top空栈空栈三、三、栈的表示栈的表示(biosh)和实现和实现3.13.1栈栈第10页/共93页第十一页，共93页。D D进栈：进栈：push(s,x)push(s,x)将元素将元素x x 插入到栈插入到栈s s中。若栈满则显示相应中。若栈满则显示相应(xingyng)(xingyng)信息，否则指针信息，否则指针toptop增增1 1，将，将x x送入栈顶指针

14、所在位置。送入栈顶指针所在位置。Void push(stacktype*s,elemtype x)Void push(stacktype*s,elemtype x)if(s-top=MaxSize-1)if(s-top=MaxSize-1)printf(“stack overflown”);printf(“stack overflown”);else else s-top+;s-stacks-top=x;s-top+;s-stacks-top=x;三、三、栈的表示栈的表示(biosh)和实现和实现3.13.1栈栈第11页/共93页第十二页，共93页。E E出栈：出栈：pop(s)pop(s)从

15、栈中删除栈顶元素。若栈空则显示从栈中删除栈顶元素。若栈空则显示(xinsh)(xinsh)相应信息，否则栈指针减相应信息，否则栈指针减1 1，即栈顶为下一个元素的位置。，即栈顶为下一个元素的位置。elemtype pop(stacktype*s)elemtype pop(stacktype*s)elemtype e;elemtype e;if(s-top=-1)printf(“stack underflown”);if(s-top=-1)printf(“stack underflown”);else e=s-stacks-top;s-top-;else e=s-stacks-top;s-top

16、-;return e;return e;三、三、栈的表示栈的表示(biosh)和实现和实现3.13.1栈栈第12页/共93页第十三页，共93页。toptopatopbtopcabtopc进栈进栈出栈出栈ctopebtop三、三、栈的表示栈的表示(biosh)和实现和实现3.3.1 1栈栈第13页/共93页第十四页，共93页。F F取栈顶元素：取栈顶元素：gettop(s)gettop(s)若栈为空则显示相应信息，否则返回栈顶元素，保持栈顶指针不变。若栈为空则显示相应信息，否则返回栈顶元素，保持栈顶指针不变。注意：与弹出操作注意：与弹出操作(cozu)(cozu)的区别的区别Elemtype g

17、ettop(stacktype*s)Elemtype gettop(stacktype*s)if(s-top=-1)printf(“stack emptyn”);if(s-top=-1)printf(“stack emptyn”);else return(s-stacks-top);else return(s-stacks-top);G.G.显示栈中元素：显示栈中元素：display(s)display(s)void display(stacktype*s)void display(stacktype*s)int i;int i;printf(“stack data:”)printf(“sta

18、ck data:”)for(i=s-top;i=0,i-)for(i=s-top;i=0,i-)printf(“%d”,s-stacki);printf(“%d”,s-stacki);printf(“n”);printf(“n”);三、三、栈的表示栈的表示(biosh)和实现和实现3.13.1栈栈第14页/共93页第十五页，共93页。用一个栈顶指针和一个栈底指针以及用一个栈顶指针和一个栈底指针以及(yj)(yj)一个初始的存储空间一个初始的存储空间A.A.定义一个栈定义一个栈#define STACK_INIT_SIZE 100#define STACK_INIT_SIZE 100#defin

19、e STACKINCREMENT 10#define STACKINCREMENT 10typedef structtypedef struct selemtype*base;/selemtype*base;/栈底指针栈底指针 selemtype*top;/selemtype*top;/栈顶指针栈顶指针 int stacksize;/int stacksize;/当前已分配存储空间，元素个数当前已分配存储空间，元素个数 sqstack;sqstack;三、三、栈的表示栈的表示(biosh)和实现和实现3.3.1 1栈栈第15页/共93页第十六页，共93页。B.初始化栈：初始化栈：initsta

20、ck(s)构造构造(guzo)一个空栈一个空栈s，即，即s.top=s.basevoidinitstack(sqstack*s)s-base=(selemtype*(malloc(stack_inti_size*sizeof(selemtype);if(!s-base)printf(“fail!n”);elses-top=s-base;s-stacksize=stack_init_size;三、三、栈的表示栈的表示(biosh)和实现和实现3.13.1栈栈第16页/共93页第十七页，共93页。C C判断栈是否为空栈：判断栈是否为空栈：stackempty(s)stackempty(s)若栈若栈

21、s s为空则返回为空则返回1 1，否则返回，否则返回0 0。Int stackempty(sqstack*s)Int stackempty(sqstack*s)if(s-top=s-base)return(1);if(s-top=s-base)return(1);else return(0);else return(0);D.D.取栈顶元素取栈顶元素(yun s)(yun s)：gettop(s)gettop(s)若栈为空则显示相应信息，否则返回栈顶元素若栈为空则显示相应信息，否则返回栈顶元素(yun s)(yun s)，保持栈顶指针不变。，保持栈顶指针不变。selemtype gettop(

22、sqstack*s)selemtype gettop(sqstack*s)if(s-top=s-base)printf(“stack emptyn”);if(s-top=s-base)printf(“stack emptyn”);else return(*(s-top-1);else return(*(s-top-1);三、三、栈的表示栈的表示(biosh)和实现和实现3.13.1栈栈第17页/共93页第十八页，共93页。E.E.进栈：进栈：push(s,x)push(s,x)将元素将元素x x 插入到栈插入到栈s s中。若栈满则追加中。若栈满则追加(zhuji)(zhuji)存储空间，否则将

23、存储空间，否则将x x送入栈顶，指针送入栈顶，指针toptop增增1 1。Void push(sqstack*s,elemtype x)Void push(sqstack*s,elemtype x)if(s-top-s-base=s-stacksize)if(s-top-s-base=s-stacksize)s-base=(selemtype*)realloc(sbase,(s.stacksize+s-base=(selemtype*)realloc(sbase,(s.stacksize+STACKINCREMENT)*sizeof(selemtype);STACKINCREMENT)*siz

24、eof(selemtype);s-top=s-base+s-stacksize;s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;s-stacksize+=STACKINCREMENT;*s-top+=x;*s-top+=x;/栈栈满满的的判判断断(pndun)/重新定义重新定义(dngy)栈空间栈空间/新栈顶新栈顶/进栈进栈三三、栈的表示和实现栈的表示和实现3.3.1 1栈栈第18页/共93页第十九页，共93页。F.F.出栈：出栈：pop(s)pop(s)从栈中删除栈顶元素。若栈空则显示相应信息，否则栈指针从栈中删除栈顶元素。若栈空则显

25、示相应信息，否则栈指针(zhzhn)(zhzhn)减减1 1，即栈顶为下一个元素的位置。，即栈顶为下一个元素的位置。selemtype pop(stacktype*s)selemtype pop(stacktype*s)selemtype e;selemtype e;if(s-top=s-base)if(s-top=s-base)printf(“stack underflown”);printf(“stack underflown”);else else s-top-;s-top-;e=*s-top;e=*s-top;return e;return e;三、三、栈的表示栈的表示(biosh)和

26、实现和实现3.13.1栈栈第19页/共93页第二十页，共93页。2.2.栈的链式存储方式栈的链式存储方式 采用链式存储的栈称为链栈。采用链式存储的栈称为链栈。链栈的特点：链栈的特点：(1)(1)不存在栈满上溢的情况不存在栈满上溢的情况(qngkung)(qngkung)，是一种特殊的单链表。，是一种特殊的单链表。(2)(2)链栈是动态存储结构，无需预先分配存储空间，因此节省存储空间。链栈是动态存储结构，无需预先分配存储空间，因此节省存储空间。(3)(3)入栈时，先申请一个结点的存储空间，然后修改栈顶指针。入栈时，先申请一个结点的存储空间，然后修改栈顶指针。(4)(4)出栈时，同样也是将栈顶的后

27、继结点做为栈顶。出栈时，同样也是将栈顶的后继结点做为栈顶。三、三、栈的表示栈的表示(biosh)和实现和实现3.13.1栈栈第20页/共93页第二十一页，共93页。(1)(1)链栈结点链栈结点(ji din)(ji din)类型的定义：类型的定义：typedef struct nodetypedef struct node elemtype data;elemtype data;struct node*next;struct node*next;node;node;(2)(2)初始化栈初始化栈void initstack(node*top)void initstack(node*top)top

28、=NULL;top=NULL;栈底栈底a1an-1an栈顶栈顶topdatanextNULLtop空栈空栈相当于链表的相当于链表的head三、三、栈的表示栈的表示(biosh)和实现和实现3.13.1栈栈第21页/共93页第二十二页，共93页。(3)入栈入栈voidpush(node*top,elemtypee)node*p;p=(node*)malloc(sizeof(node);p-data=e;p-next=top;top=p;(4)出栈出栈elemtypepop(node*top)node*q;elemtype*pif(top!=NULL)q=top;*p=top-data;top=t

29、op-next;free(q);return(*p);三、三、栈的表示栈的表示(biosh)和实现和实现3.13.1栈栈第22页/共93页第二十三页，共93页。3.2栈的应用栈的应用(yngyng)举例举例一、数制转换一、数制转换二、表达式求值二、表达式求值三、括号三、括号(kuho)匹配的检验匹配的检验四、迷宫求解四、迷宫求解五、递归的实现五、递归的实现第23页/共93页第二十四页，共93页。由十进制由十进制N N向其它进制向其它进制d d的转换是计算机实现计算的基本问题，基于原理：的转换是计算机实现计算的基本问题，基于原理：N=(N div d)*d+N mod d N=(N div d)

30、*d+N mod d其中：其中：divdiv为整除运算为整除运算(yn sun)(yn sun)，mod mod 为取余运算为取余运算(yn sun)(yn sun)。一个十进制数转换成其它进制数：一个十进制数转换成其它进制数：N N除除d d取余，先余为低，后余为高。取余，先余为低，后余为高。如：如：(1348)10=(2504)8(1348)10=(2504)8 13481688888212040521348mod8低低高高一、一、数制转换数制转换(zhunhun)3.23.2栈栈的的应应用用(y(yngyngyngng)举举例例第24页/共93页第二十五页，共93页。算法分析算法分析(f

31、nx)(fnx)：由十进制转换为其他进制的数的规则，可知，求得的余数的顺序为由低位到高位，而输出则是由高位到低位。因此，这正好利用栈的特点，先将求得的余数依次入栈，输出时，再将栈中的数据出栈。由十进制转换为其他进制的数的规则，可知，求得的余数的顺序为由低位到高位，而输出则是由高位到低位。因此，这正好利用栈的特点，先将求得的余数依次入栈，输出时，再将栈中的数据出栈。一、一、数制转换数制转换(zhunhun)3.23.2栈栈的的应应用用(y(yngyngyngng)举举例例第25页/共93页第二十六页，共93页。算法算法(sunf)实现：实现：voidconversion()initstack(s

32、);scanf(“%d”,n);while(n)push(s,n%8);n=n/8;while(!stackempty()pop(s,e);printf(“%d”,e);/余数余数(ysh)入栈入栈一、一、数制转换数制转换(zhunhun)3.23.2栈栈的的应应用用举举例例Void conver(n)if(n0)conver(n/8);printf(“%d”,n%8);第26页/共93页第二十七页，共93页。表达式求值是程序设计语言表达式求值是程序设计语言(yyn)(yyn)编译的一个最基本的问题。它的实现是栈应用的又一典型例子。编译的一个最基本的问题。它的实现是栈应用的又一典型例子。仅以算

33、术表达式为例。仅以算术表达式为例。(1)(1)算符优先法算符优先法 根据算术四则运算的规则所确定的运算优先关系的规定来实现对表达式的编译或解释执行的。根据算术四则运算的规则所确定的运算优先关系的规定来实现对表达式的编译或解释执行的。将表达式视为由操作数、运算符、界限符（称为单词）组成。将表达式视为由操作数、运算符、界限符（称为单词）组成。操作数：常数、变量或符号常量。操作数：常数、变量或符号常量。算符：运算符、界限符算符：运算符、界限符二、表达式求值二、表达式求值3.3.2 2栈栈的的应应用用(y(ynngygynng)g)举举例例第27页/共93页第二十八页，共93页。遵循算术四则运算规则，

34、一般任意两个相继出现的两个算符遵循算术四则运算规则，一般任意两个相继出现的两个算符p1p1和和p2p2之间的优先关系之间的优先关系(gun x)(gun x)至多有下面三种之一：至多有下面三种之一：p1p2 p2p1p2 p2p1p2 p2的优先权低于的优先权低于p1 p1 见表见表3.13.1二、表达式求值二、表达式求值3.23.2栈栈的的应应用用(y(yngyngyngng)举举例例第28页/共93页第二十九页，共93页。一般作为相同一般作为相同(xin tn)(xin tn)运算符，先出现的比后出现的优先级高；先出现的运算符优先级低于运算符，先出现的比后出现的优先级高；先出现的运算符优先

35、级低于“(”“(”，高于，高于“)”“)”；后出现的运算符优先级高于；后出现的运算符优先级高于“(”“(”，低于，低于“)”“)”；优先权相等的仅有；优先权相等的仅有“(”“(”和和“)”“)”、“#”“#”。#：作为表达式结束符，通常在表达式之前加一：作为表达式结束符，通常在表达式之前加一“#”“#”使之成对，当出现使之成对，当出现“#”=“#”“#”=“#”时，表明表达式求值结束，时，表明表达式求值结束，“#”“#”的优先级最低。的优先级最低。二、表达式求值二、表达式求值3.23.2栈栈的的应应用用(y(yngyngyngng)举举例例第29页/共93页第三十页，共93页。(2)(2)后缀

36、表达式法后缀表达式法中缀表达式中缀表达式表达式的运算符在操作数的中间。表达式的运算符在操作数的中间。后缀算术后缀算术(sunsh)(sunsh)表达式表达式(逆波兰式逆波兰式)将运算符置两个操作数后面的算术将运算符置两个操作数后面的算术(sunsh)(sunsh)表达式。表达式。前缀表达式前缀表达式(波兰式波兰式)又称波兰式，与后缀表达式相反。又称波兰式，与后缀表达式相反。例：例：将将3*(x+y)/(1-x)3*(x+y)/(1-x)转换为后缀表达式转换为后缀表达式 3xy+*1x-/3xy+*1x-/方法：方法：3*(x+y)+*/(1 x)-/3xy+*1x-/3*(x+y)+*/(1

37、x)-/3xy+*1x-/二、表达式求值二、表达式求值3.23.2栈栈的的应应用用(y(yngyngyngng)举举例例第30页/共93页第三十一页，共93页。中缀表达式转换成后缀表达式中缀表达式转换成后缀表达式 算法：算法：设一个数组设一个数组strstr存放中缀表达式，一个数组存放中缀表达式，一个数组expexp存放转换后的后缀表达式，栈存放转换后的后缀表达式，栈s s作为中间过程中不能立即送入数组的运算符。作为中间过程中不能立即送入数组的运算符。对于运算符也有一个优先级的比较对于运算符也有一个优先级的比较(bjio),(bjio),这同这同(1)(1)是相同的。是相同的。设先后出现的两个

38、运算符为设先后出现的两个运算符为p1p1和和p2p2。a.a.首先在栈首先在栈s s中压入中压入”#”#”，然后从数组，然后从数组strstr中的第一个字符中的第一个字符 开始扫描；开始扫描；b.b.当字符是数字字符时，将从该字符开始的一组数字符及当字符是数字字符时，将从该字符开始的一组数字符及 附加空格，依次送入数组附加空格，依次送入数组expexp中。中。二、表达式求值二、表达式求值3.23.2栈栈的的应应用用(y(yngyngyngng)举举例例第31页/共93页第三十二页，共93页。c.c.当字符是运算符当字符是运算符p2p2时，则检查时，则检查p2p2与与s s栈顶元素栈顶元素p1p

39、1之间的关之间的关 系，并作以下处理：系，并作以下处理：若若p2p1p2p1，则将运算符，则将运算符p2p2压入压入s;s;若若p2p1p2p1，则将，则将p1p1弹出，并送入数组弹出，并送入数组expexp中，然后中，然后p2p2继续与新的栈顶中的运算符继续与新的栈顶中的运算符p1p1比较比较(bjio)(bjio)；若若p2p2为右括号，则栈顶必然有一左括号，将栈顶左括号弹出为右括号，则栈顶必然有一左括号，将栈顶左括号弹出(此过程正是删除一对括号此过程正是删除一对括号)，然后继续扫描下一个字符；，然后继续扫描下一个字符；d.d.重复上述过程重复上述过程b bc c，直到扫描到，直到扫描到s

40、trstr数组中的算符数组中的算符“#”“#”为止。为止。运算结束后，运算结束后，expexp数组中存放的是转换后的后缀表达式。数组中存放的是转换后的后缀表达式。二、表达式求值二、表达式求值3.23.2栈栈的的应应用用(y(yngyngyngng)举举例例第32页/共93页第三十三页，共93页。以以3*(x+y)/(1-x)为例，说明为例，说明(shumng)转换过程。转换过程。3*(x+y)/(1-x)#33#str(*#x3yx3+(*#+(*#yx3exp*#s+yx3(/#-(/#1*+yx3-(/#x1*+yx3x1*+yx3*(+)/(*/-)#-/二、表达式求值二、表达式求值3.

41、23.2栈栈的的应应用用(y(yngyngyngng)举举例例第33页/共93页第三十四页，共93页。后缀表达式求值后缀表达式求值 将转换后的后缀表达式运算求出结果。将转换后的后缀表达式运算求出结果。接上，接上，expexp中存放带中存放带“#”“#”的后缀表达式，栈的后缀表达式，栈s s存放参与运算存放参与运算的操作数、中间结果和最后结果。的操作数、中间结果和最后结果。从数组的第一个字符开始扫描。从数组的第一个字符开始扫描。若遇到数字字符，则将以该字符开始的一组数字若遇到数字字符，则将以该字符开始的一组数字(直到遇直到遇 到空格为止到空格为止)转换成对应的数值转换成对应的数值(即一个操作数即

42、一个操作数)，再压入，再压入 栈栈s s。若遇到的是运算符，则从栈若遇到的是运算符，则从栈s s的栈顶依次弹出两个操作数，进行相的栈顶依次弹出两个操作数，进行相应的运算，再将其运算结果压入栈应的运算，再将其运算结果压入栈s s。继续扫描继续扫描expexp中的下一个字符，重复上述中的下一个字符，重复上述(shngsh)(shngsh)两个步骤，直两个步骤，直到到 扫描到扫描到expexp中的中的“#”“#”为止。此时栈为止。此时栈s s中的栈顶值就是后缀中的栈顶值就是后缀 表达式的值。表达式的值。二、表达式求值二、表达式求值3.23.2栈栈的的应应用用(y(yngyngyngng)举举例例第3

43、4页/共93页第三十五页，共93页。357+*21-/exp7537+5=1212312*3=3612362-1=113636/1=36二、表达式求值二、表达式求值3.3.2 2栈栈的的应应用用(y(ynngygynng)g)举举例例第35页/共93页第三十六页，共93页。三、括号匹配三、括号匹配(ppi)的检验的检验3.3.2 2栈栈的的应应用用(y(ynngygynng)g)举举例例 如何判断表达式中的括号匹配涉及两个如何判断表达式中的括号匹配涉及两个(lin)(lin)方面：一是方面：一是括号成对出现；二是成对出现的位置。括号成对出现；二是成对出现的位置。如：如：（）（）（）（）是正确的

44、是正确的 （）是错误的）是错误的 检验括号匹配的方法用检验括号匹配的方法用“期待的急迫程度期待的急迫程度”概念来概念来描述。先出现的期待程度低，后出现的期待程度高，期描述。先出现的期待程度低，后出现的期待程度高，期待程度高的先得到满足。这一规律恰好符合栈的特点。待程度高的先得到满足。这一规律恰好符合栈的特点。()()1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8第36页/共93页第三十七页，共93页。四、迷宫四、迷宫(mgng)求解问题求解问题3.23.2栈栈的的应应用用(y(yngyngyngng)举举例例求解迷宫问题求解迷宫问题(wnt)，常采用，常采用“穷举求解穷举求解”

45、的方法。的方法。01234567123 456#7NWESij(1,1,E)(1,2,S)(2,2,S)(3,2,E)(3,3,E)(3,4,N)(2,4,N)(1,4,E)(1,5,E)(1,6,S)(2,6,E,S,W不通)(3,2,W)(3,1,S)(4,1,S)(5,1,E)(5,2,S)(6,2,E)(6,2,E)(6,4,E)(6,5,E)(6,6,通过通过)第37页/共93页第三十八页，共93页。四、迷宫四、迷宫(mgng)求解问题求解问题3.23.2栈栈的的应应用用(y(yngyngyngng)举举例例 求迷宫路径算法的基本思想：求迷宫路径算法的基本思想：1.1.若当前位置若当

46、前位置“可通可通”，则纳入路径，继续前进；，则纳入路径，继续前进；2.2.若当前位置若当前位置“不可不可(bk)(bk)通通”，则后退，换向探索；，则后退，换向探索；3.3.若四周若四周“均不可均不可(bk)(bk)通通”，则从路径中删除。，则从路径中删除。第38页/共93页第三十九页，共93页。递归是程序设计中常用的算法之一。递归是程序设计中常用的算法之一。1.1.递归：函数（过程）直接或间接调用自身。递归：函数（过程）直接或间接调用自身。2.2.递归算法的实现离不开栈递归算法的实现离不开栈 基于函数嵌套调用的特点，即基于函数嵌套调用的特点，即“后调用的先返回后调用的先返回(fnhu)”(f

47、nhu)”。函数之间的信息传递和控制转移，利用。函数之间的信息传递和控制转移，利用“栈栈”来实现是最合适的。在系统运行过程中，开辟一个存储空间，每调用一个函数，为其分配一个栈顶空间保存其相关信息；每退出一个函数，就释放它的存储空间。来实现是最合适的。在系统运行过程中，开辟一个存储空间，每调用一个函数，为其分配一个栈顶空间保存其相关信息；每退出一个函数，就释放它的存储空间。递归函数的运行过程类似于多个函数嵌套调，由于是调用同一个函数，就有一个递归函数的运行过程类似于多个函数嵌套调，由于是调用同一个函数，就有一个“层次层次”的概念。的概念。见图见图五、递归的实现五、递归的实现(shxin)3.3.

48、2 2栈栈的的应应用用(y(ynngygynng)g)举举例例第39页/共93页第四十页，共93页。main()f1();f1()f11();return;f11().return;保存参数保存参数(cnsh)，返回地址，返回地址分配存储空间分配存储空间控制转移控制转移存入存入(cnr)栈：存储区栈：存储区保存保存(bocn)结果结果释放局部变量释放局部变量返回到调用函数返回到调用函数从栈中取从栈中取f1f11栈栈五、递归的实现五、递归的实现3.23.2栈栈的的应应用用举举例例第40页/共93页第四十一页，共93页。3.3.递归过程递归过程 为了保证递归函数正确执行，设立一个为了保证递归函数正

49、确执行，设立一个“递归工作栈递归工作栈”作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录工作记录”，其中包括所有的实参、局部变量以及上一层返回的地址。每进入一层递归，就产生一个新的工作记录并将其压入栈顶，每退出一层递归，就从栈顶弹出一个工作记录。当前，其中包括所有的实参、局部变量以及上一层返回的地址。每进入一层递归，就产生一个新的工作记录并将其压入栈顶，每退出一层递归，就从栈顶弹出一个工作记录。当前(dngqin)(dngqin)执行层的工作记录必是递归工作栈的栈顶记录，这个记录称为执行层的工作记

50、录必是递归工作栈的栈顶记录，这个记录称为“活动记录活动记录”。见图见图五、递归的实现五、递归的实现(shxin)3.3.2 2栈栈的的应应用用(y(ynngygynng)g)举举例例第41页/共93页第四十二页，共93页。main()f1();f1()f1();return;f1().return;保存参数，返回地址保存参数，返回地址分配存储空间分配存储空间控制控制(kngzh)转移转移存入存入(cnr)栈：存储区栈：存储区保存保存(bocn)结果结果释放局部变量释放局部变量返回到调用函数返回到调用函数从栈中取从栈中取f1f1栈栈五、递归的实现五、递归的实现3.3.2 2栈栈的的应应用用举举例