数据结构第三章.pptx

第三章第三章 栈和队列栈和队列3.1 3.1 栈栈3.2 3.2 栈的应用举例栈的应用举例3.3 3.3 队列队列第1页/共93页3.1栈一、栈的定义一、栈的定义二、抽象数据类型栈的定义二、抽象数据类型栈的定义三、栈的表示和实现三、栈的表示和实现四、栈的应用举例四、栈的应用举例第2页/共93页一、栈的定义1 1定义定义栈栈(Stack)(Stack)是是一一种种特特殊殊的的线线性性表表，其其插插入入和和删删除除操操作作均均在在表表的的一一端端进进行行，是是一种一种运算受限运算受限的线性表。的线性表。栈顶栈顶(top)(top)允许插入和删除的一端，又称允许插入和删除的一端，又称表尾。表尾。栈底栈底(bottom)(bottom)栈的另一端，又称栈的另一端，又称表头表头。若给栈若给栈S=(aS=(a1 1,a,a2 2a ai i,a an n)，则，则a a1 1 为栈底元素，为栈底元素，a an n 为栈顶元素，如图所示。为栈顶元素，如图所示。进栈进栈(push)(push)在栈顶插入一个元素，在栈顶插入一个元素，又称又称入栈或压入入栈或压入。出栈出栈(pop)(pop)在栈顶删除一个元素，在栈顶删除一个元素，又称又称退栈或弹出退栈或弹出。空栈空栈栈中没有元素栈中没有元素(n=0)(n=0)。3.13.1栈栈第3页/共93页2 2栈的特点栈的特点后进先出后进先出(Last In First Out(Last In First Out，简称，简称LIFOLIFO)。又称栈为后进先出表又称栈为后进先出表(简称简称LIFOLIFO结构结构)。一、栈的定义3.13.1栈栈第4页/共93页 对对栈栈的的操操作作除除了了在在栈栈顶顶进进行行插插入入和和删删除除外外，还还有有栈栈的的初初始始化化、判判空空及及取取栈顶元素等。栈顶元素等。其抽象数据类型定义如下：其抽象数据类型定义如下：ADT Stack ADT Stack 数据对象：数据对象：D=aD=ai i|a|ai iElemSetElemSet，i=1,2i=1,2n n，n0n0 数据关系：数据关系：R=aR=|a|ai-1i-1，a ai iDD，i=2,3,i=2,3,n,n 基本操作：基本操作：InitStack(&s)InitStack(&s)操作结果：构造一个空栈操作结果：构造一个空栈s s。DestroyStack(&s)DestroyStack(&s)操作结果：栈操作结果：栈s s被销毁。被销毁。ClearStack(&s)ClearStack(&s)操作结果：将操作结果：将s s清为空栈。清为空栈。二、抽象数据类型栈的定义3.13.1栈栈第5页/共93页StackEmpty(s)StackEmpty(s)操作结果：若操作结果：若s s为空栈，则返回为空栈，则返回TRUETRUE，否则，否则FALSEFALSE。StackLength(s)StackLength(s)操作结果：返回操作结果：返回s s的元素个数，即栈的长度。的元素个数，即栈的长度。GetTop(s,&e)GetTop(s,&e)操作结果：用操作结果：用e e返回返回s s的栈顶元素。的栈顶元素。Push(&s,e)Push(&s,e)操作结果：插入元素操作结果：插入元素e e为新的栈顶元素。为新的栈顶元素。Pop(&s,&e)Pop(&s,&e)操作结果：删除操作结果：删除s s的栈顶元素，并用的栈顶元素，并用e e返回其值返回其值。StackTrasverse(s,visit()StackTrasverse(s,visit()操作结果：从栈底到栈顶依次对操作结果：从栈底到栈顶依次对s s的每个数据元素调用的每个数据元素调用 函数函数visit()visit()。一旦。一旦visit()visit()失败，则操作失效。失败，则操作失效。ADT StackADT Stack二、抽象数据类型栈的定义3.13.1栈栈第6页/共93页两种存储表示方式：两种存储表示方式：顺序存储和链式存储顺序存储和链式存储。1.1.栈的顺序存储及其基本操作的实现栈的顺序存储及其基本操作的实现 (1)(1)栈栈的的顺顺序序存存储储是是利利用用一一块块连连续续的的存存储储单单元元依依次次存存放放栈栈中中的的数数据据元元素素，并并附附一个指针一个指针toptop指示当前指示当前栈顶栈顶。采用顺序存储方式存储的栈称为采用顺序存储方式存储的栈称为顺序栈顺序栈。(2)C(2)C语言描述顺序栈：语言描述顺序栈：用一维数组和一个栈顶指针用一维数组和一个栈顶指针Typedef struct Typedef struct elemtype stackMaxSize;elemtype stackMaxSize;int top;int top;stacktype;stacktype;43210-1空栈topatopbctop三、栈的表示和实现3.13.1栈栈第7页/共93页用一个栈顶指针和一个栈底指针以及一个初始的存储空间用一个栈顶指针和一个栈底指针以及一个初始的存储空间#define STACK_INIT_SIZE 100#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define STACKINCREMENT 10typedef structtypedef struct selemtype*base;selemtype*base;selemtype*top;selemtype*top;int stacksize;int stacksize;sqstack;sqstack;连续的存储空间连续的存储空间 栈顶指针指示栈顶元素当前位置栈顶指针指示栈顶元素当前位置(用栈顶指针动态地反映栈中元素的变化情况用栈顶指针动态地反映栈中元素的变化情况)basetop空栈baseatoptopb三、栈的表示和实现3.13.1栈栈第8页/共93页(3)(3)基本操作的算法基本操作的算法 用一维数组和一个栈顶指针用一维数组和一个栈顶指针A 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;三、栈的表示和实现3.13.1栈栈第9页/共93页B B初始化栈：初始化栈：initstack(s)initstack(s)建立一个空栈建立一个空栈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 stackempty(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空栈三、栈的表示和实现3.13.1栈栈第10页/共93页D D进栈：进栈：push(s,x)push(s,x)将将元元素素x x 插插入入到到栈栈s s中中。若若栈栈满满则则显显示示相相应应信信息息，否否则则指指针针toptop增增1 1，将将x x送入栈顶指针所在位置。送入栈顶指针所在位置。Void push(stacktype*s,elemtype x)Void push(stacktype*s,elemtype x)if(s-top=MaxSize-1)if(s-top=MaxSize-1)printf(printf(“stack overflownstack overflown”););else else s-top+;s-stacks-top=x;s-top+;s-stacks-top=x;三、栈的表示和实现3.13.1栈栈第11页/共93页E E出栈：出栈：pop(s)pop(s)从从栈栈中中删删除除栈栈顶顶元元素素。若若栈栈空空则则显显示示相相应应信信息息，否否则则栈栈指指针针减减1 1，即即栈顶为下一个元素的位置。栈顶为下一个元素的位置。elemtype pop(stacktype*s)elemtype pop(stacktype*s)elemtype e;elemtype e;if(s-top=-1)printf(if(s-top=-1)printf(“stack underflownstack underflown”););else e=s-stacks-top;s-top-;else e=s-stacks-top;s-top-;return e;return e;三、栈的表示和实现3.13.1栈栈第12页/共93页toptopatopbtopcabtopc进栈出栈ctopebtop三、栈的表示和实现3.13.1栈栈第13页/共93页F F取栈顶元素：取栈顶元素：gettop(s)gettop(s)若若栈栈为为空空则则显显示示相相应应信信息息，否否则则返返回回栈栈顶顶元元素素，保保持持栈栈顶顶指指针针不不变变。注意：与弹出操作的区别注意：与弹出操作的区别Elemtype gettop(stacktype*s)Elemtype gettop(stacktype*s)if(s-top=-1)printf(if(s-top=-1)printf(“stack emptynstack 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(printf(“stack data:stack data:”)for(i=s-top;i=0,i-)for(i=s-top;i=0,i-)printf(printf(“%d%d”,s-stacki);,s-stacki);printf(printf(“nn”););三、栈的表示和实现3.13.1栈栈第14页/共93页用一个栈顶指针和一个栈底指针以及一个初始的存储空间用一个栈顶指针和一个栈底指针以及一个初始的存储空间A.A.定义一个栈定义一个栈#define STACK_INIT_SIZE 100#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define STACKINCREMENT 10typedef structtypedef struct selemtype*base;/selemtype*base;/栈底指针栈底指针 selemtype*top;/selemtype*top;/栈顶指针栈顶指针 int stacksize;/int stacksize;/当前已分配存储空间，元素个数当前已分配存储空间，元素个数 sqstack;sqstack;三、栈的表示和实现3.13.1栈栈第15页/共93页B.初始化栈：initstack(s)构造一个空栈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;三、栈的表示和实现3.13.1栈栈第16页/共93页C C判断栈是否为空栈：判断栈是否为空栈：stackempty(s)stackempty(s)若栈若栈s s为空则返回为空则返回1 1，否则返回，否则返回0 0。Int stackempty(sqstack*s)Int stackempty(sqstack*s)if(if(s-top=s-bases-top=s-base)return(1);)return(1);else return(0);else return(0);D.D.取栈顶元素：取栈顶元素：gettop(s)gettop(s)若栈为空则显示相应信息，否则返回栈顶元素，保持栈顶指针不变。若栈为空则显示相应信息，否则返回栈顶元素，保持栈顶指针不变。selemtype gettop(sqstack*s)selemtype gettop(sqstack*s)if(s-top=s-base)printf(if(s-top=s-base)printf(“stack emptynstack emptyn”););else return(*(s-top-1);else return(*(s-top-1);三、栈的表示和实现3.13.1栈栈第17页/共93页E.E.进栈：进栈：push(s,x)push(s,x)将将元元素素x x 插插入入到到栈栈s s中中。若若栈栈满满则则追追加加存存储储空空间间，否否则则将将x x送送入入栈栈顶顶，指指针针toptop增增1 1。Voidpush(sqstack*s,elemtypex)if(s-top-s-base=s-stacksize)s-base=(selemtype*)realloc(sbase,(s.stacksize+STACKINCREMENT)*sizeof(selemtype);s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+=x;/栈满的判断/重新定义栈空间/新栈顶/进栈三、栈的表示和实现3.13.1栈栈第18页/共93页F.F.出栈：出栈：pop(s)pop(s)从从栈栈中中删删除除栈栈顶顶元元素素。若若栈栈空空则则显显示示相相应应信信息息，否否则则栈栈指指针针减减1 1，即栈顶为下一个元素的位置。即栈顶为下一个元素的位置。selemtypepop(stacktype*s)selemtypee;if(s-top=s-base)printf(“stackunderflown”);elses-top-;e=*s-top;returne;三、栈的表示和实现3.13.1栈栈第19页/共93页2.2.栈的链式存储方式栈的链式存储方式 采用链式存储的栈称为采用链式存储的栈称为链栈链栈。链栈的特点：链栈的特点：(1)(1)不存在栈满上溢的情况，是一种特殊的单链表。不存在栈满上溢的情况，是一种特殊的单链表。(2)(2)链栈是动态存储结构，无需预先分配存储空间，因此节省存储空间。链栈是动态存储结构，无需预先分配存储空间，因此节省存储空间。(3)(3)入栈时，先申请一个结点的存储空间，然后修改栈顶指针。入栈时，先申请一个结点的存储空间，然后修改栈顶指针。(4)(4)出栈时，同样也是将栈顶的后继结点做为栈顶。出栈时，同样也是将栈顶的后继结点做为栈顶。三、栈的表示和实现3.13.1栈栈第20页/共93页(1)(1)链栈结点类型的定义：链栈结点类型的定义：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=NULL;top=NULL;栈底a1an-1an栈顶topdatanextNULLtop空栈相当于链表的head三、栈的表示和实现3.13.1栈栈第21页/共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=top-next;free(q);return(*p);三、栈的表示和实现3.13.1栈栈第22页/共93页3.2栈的应用举例一、数制转换一、数制转换二、表达式求值二、表达式求值三、括号匹配的检验三、括号匹配的检验四、迷宫求解四、迷宫求解五、递归的实现五、递归的实现第23页/共93页 由十进制由十进制N N向其它进制向其它进制d d的转换是计算机实现计算的基本问题，基于原理：的转换是计算机实现计算的基本问题，基于原理：N=(N div d)*d+N mod dN=(N div d)*d+N mod d其中：其中：divdiv为整除运算，为整除运算，mod mod 为取余运算。为取余运算。一个十进制数转换成其它进制数：一个十进制数转换成其它进制数：N N除除d d取余，取余，先余为低，后余为高先余为低，后余为高。如：如：(1348)(1348)1010=(2504)=(2504)8 8 13481688888212040521348mod8低高一、数制转换3.23.2栈栈的的应应用用举举例例第24页/共93页算法分析：算法分析：由由十十进进制制转转换换为为其其他他进进制制的的数数的的规规则则，可可知知，求求得得的的余余数数的的顺顺序序为为由由低低位位到到高高位位，而而输输出出则则是是由由高高位位到到低低位位。因因此此，这这正正好好利利用用栈栈的的特特点点，先先将将求求得的余数依次入栈，输出时，再将栈中的数据出栈。得的余数依次入栈，输出时，再将栈中的数据出栈。一、数制转换3.23.2栈栈的的应应用用举举例例第25页/共93页算法实现：voidconversion()initstack(s);scanf(“%d”,n);while(n)push(s,n%8);n=n/8;while(!stackempty()pop(s,e);printf(“%d”,e);/余数入栈一、数制转换3.23.2栈栈的的应应用用举举例例Void conver(n)if(n0)conver(n/8);printf(“%d”,n%8);第26页/共93页 表表达达式式求求值值是是程程序序设设计计语语言言编编译译的的一一个个最最基基本本的的问问题题。它它的的实实现现是是栈栈应应用用的又一典型例子的又一典型例子。仅以算术表达式为例。仅以算术表达式为例。(1)(1)算符优先法算符优先法 根根据据算算术术四四则则运运算算的的规规则则所所确确定定的的运运算算优优先先关关系系的的规规定定来来实实现现对对表表达达式式的的编编译或解释执行的。译或解释执行的。将表达式视为由将表达式视为由操作数、运算符、界限符（称为单词操作数、运算符、界限符（称为单词）组成。组成。操作数：常数、变量或符号常量。操作数：常数、变量或符号常量。算符：运算符、界限符算符：运算符、界限符二、表达式求值3.23.2栈栈的的应应用用举举例例第27页/共93页遵遵循循算算术术四四则则运运算算规规则则，一一般般任任意意两两个个相相继继出出现现的的两两个个算算符符p1p1和和p2p2之之间间的的优先关系至多有下面三种之一：优先关系至多有下面三种之一：p1p2 p2p1p2 p2p1p2 p2的优先权低于的优先权低于p1p1 见表见表3.13.1二、表达式求值3.23.2栈栈的的应应用用举举例例第28页/共93页一一般般作作为为相相同同运运算算符符，先先出出现现的的比比后后出出现现的的优优先先级级高高；先先出出现现的的运运算算符符优优先先级级低低于于“(”，高高于于“)”；后后出出现现的的运运算算符符优优先先级级高高于于“(”，低低于于“)”；优优先权相等的仅有先权相等的仅有“(”和和“)”、“#”。#：作作为为表表达达式式结结束束符符，通通常常在在表表达达式式之之前前加加一一“#”使使之之成成对对，当当出出现现“#”=“#”时，表明表达式求值结束，时，表明表达式求值结束，“#”的优先级最低。的优先级最低。二、表达式求值3.23.2栈栈的的应应用用举举例例第29页/共93页(2)(2)后缀表达式法后缀表达式法中缀表达式中缀表达式表达式的运算符在操作数的中间。表达式的运算符在操作数的中间。后缀算术表达式后缀算术表达式(逆波兰式逆波兰式)将运算符置两个操作数后面的算术表达式。将运算符置两个操作数后面的算术表达式。前缀表达式前缀表达式(波兰式波兰式)又称波兰式又称波兰式，与后缀表达式相反。，与后缀表达式相反。例：例：将将3*(x+y)/(1-x)3*(x+y)/(1-x)转换为后缀表达式转换为后缀表达式 3xy+*1x-/方法：3*(x+y)+*/(1x)-/3xy+*1x-/二、表达式求值3.23.2栈栈的的应应用用举举例例第30页/共93页中缀表达式转换成后缀表达式中缀表达式转换成后缀表达式 算法：算法：设设一一个个数数组组strstr存存放放中中缀缀表表达达式式，一一个个数数组组expexp存存放放转转换换后后的的后后缀缀表表达达式式，栈栈s s作为中间过程中不能立即送入数组的运算符。作为中间过程中不能立即送入数组的运算符。对于运算符也有一个优先级的比较对于运算符也有一个优先级的比较,这同这同(1)(1)是相同的。是相同的。设先后出现的两个运算符为设先后出现的两个运算符为p1p1和和p2p2。a.a.首先在栈首先在栈s s中压入中压入”#”，然后从数组，然后从数组strstr中的第一个字符中的第一个字符 开始扫描；开始扫描；b.b.当字符是数字字符时，将从该字符开始的一组数字符及当字符是数字字符时，将从该字符开始的一组数字符及 附加空格，依次送入数组附加空格，依次送入数组expexp中。中。二、表达式求值3.23.2栈栈的的应应用用举举例例第31页/共93页c.c.当字符是运算符当字符是运算符p2p2时，则检查时，则检查p2p2与与s s栈顶元素栈顶元素p1p1之间的关之间的关 系，并作以下处理：系，并作以下处理：若若p2p1p2p1，则将运算符，则将运算符p2p2压入压入s;s;若若p2p1p2p1，则则将将p1p1弹弹出出，并并送送入入数数组组expexp中中，然然后后p2p2继继续续与与新新的的栈栈顶顶中中的的运运算算符符p1p1比较；比较；若若p2p2为为右右括括号号，则则栈栈顶顶必必然然有有一一左左括括号号，将将栈栈顶顶左左括括号号弹弹出出(此此过过程程正正是是删删除除一对括号一对括号)，然后继续扫描下一个字符；，然后继续扫描下一个字符；d.d.重复上述过程重复上述过程b bc c，直到扫描到，直到扫描到strstr数组中的算符数组中的算符“#”为止。为止。运算结束后，运算结束后，expexp数组中存放的是转换后的后缀表达式。数组中存放的是转换后的后缀表达式。二、表达式求值3.23.2栈栈的的应应用用举举例例第32页/共93页以3*(x+y)/(1-x)为例，说明转换过程。3*(x+y)/(1-x)#33#str(*#x3yx3+(*#+(*#yx3exp*#s+yx3(/#-(/#1*+yx3-(/#x1*+yx3x1*+yx3*(+)/(*/-)#-/二、表达式求值3.23.2栈栈的的应应用用举举例例第33页/共93页后缀表达式求值后缀表达式求值 将转换后的后缀表达式运算求出结果。将转换后的后缀表达式运算求出结果。接上，接上，expexp中存放带中存放带“#”的后缀表达式，栈的后缀表达式，栈s s存放参与运算存放参与运算的操作数、中间结果和最后结果。的操作数、中间结果和最后结果。从数组的第一个字符开始扫描。从数组的第一个字符开始扫描。若遇到数字字符，则将以该字符开始的一组数字若遇到数字字符，则将以该字符开始的一组数字(直到遇直到遇 到空格为止到空格为止)转换成对应的数值转换成对应的数值(即一个操作数即一个操作数)，再压入，再压入 栈栈s s。若若遇遇到到的的是是运运算算符符，则则从从栈栈s s的的栈栈顶顶依依次次弹弹出出两两个个操操作作数数，进行相应的运算，再将其运算结果压入栈进行相应的运算，再将其运算结果压入栈s s。继续扫描继续扫描expexp中的下一个字符，重复上述两个步骤，直到中的下一个字符，重复上述两个步骤，直到 扫描到扫描到expexp中的中的“#”为止。此时栈为止。此时栈s s中的栈顶值就是后缀中的栈顶值就是后缀 表达式的值。表达式的值。二、表达式求值3.23.2栈栈的的应应用用举举例例第34页/共93页357+*21-/exp7537+5=1212312*3=3612362-1=113636/1=36二、表达式求值3.23.2栈栈的的应应用用举举例例第35页/共93页三、括号匹配的检验3.23.2栈栈的的应应用用举举例例 如何判断表达式中的括号匹配涉及两个方面：一是如何判断表达式中的括号匹配涉及两个方面：一是括号成对出现；二是成对出现的位置。括号成对出现；二是成对出现的位置。如：如：（）（）（）（）是正确的是正确的 （）是错误的）是错误的 检验括号匹配的方法用检验括号匹配的方法用“期待的急迫程度期待的急迫程度”概念来概念来描述。先出现的期待程度低，后出现的期待程度高，期描述。先出现的期待程度低，后出现的期待程度高，期待程度高的先得到满足。这一规律恰好符合栈的特点。待程度高的先得到满足。这一规律恰好符合栈的特点。()()1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8第36页/共93页四、迷宫求解问题3.23.2栈栈的的应应用用举举例例求解迷宫问题，常采用求解迷宫问题，常采用“穷举求解穷举求解”的方法。的方法。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页四、迷宫求解问题3.23.2栈栈的的应应用用举举例例 求迷宫路径算法的基本思想：求迷宫路径算法的基本思想：1.1.若当前位置若当前位置“可通可通”，则纳入路径，继续前进；，则纳入路径，继续前进；2.2.若当前位置若当前位置“不可通不可通”，则后退，换向，则后退，换向探索探索；3.3.若四周若四周“均不可通均不可通”，则从路径中删除。，则从路径中删除。第38页/共93页 递归是程序设计中常用的算法之一。递归是程序设计中常用的算法之一。1.1.递归：函数（过程）直接或间接调用自身。递归：函数（过程）直接或间接调用自身。2.2.递归算法的实现离不开栈递归算法的实现离不开栈 基基于于函函数数嵌嵌套套调调用用的的特特点点，即即“后后调调用用的的先先返返回回”。函函数数之之间间的的信信息息传传递递和和控控制制转转移移，利利用用“栈栈”来来实实现现是是最最合合适适的的。在在系系统统运运行行过过程程中中，开开辟辟一一个个存存储储空空间间，每每调调用用一一个个函函数数，为为其其分分配配一一个个栈栈顶顶空空间间保保存存其其相相关关信信息息；每每退出一个函数，就释放它的存储空间。退出一个函数，就释放它的存储空间。递递归归函函数数的的运运行行过过程程类类似似于于多多个个函函数数嵌嵌套套调调，由由于于是是调调用用同同一一个个函函数数，就有一个就有一个“层次层次”的概念。的概念。见图五、递归的实现3.23.2栈栈的的应应用用举举例例第39页/共93页main()f1();f1()f11();return;f11().return;保存参数，返回地址保存参数，返回地址分配存储空间分配存储空间控制转移控制转移存入栈：存储区存入栈：存储区保存结果保存结果释放局部变量释放局部变量返回到调用函数返回到调用函数从栈中取从栈中取f1f11栈五、递归的实现3.23.2栈栈的的应应用用举举例例第40页/共93页 3.3.递归过程递归过程 为为了了保保证证递递归归函函数数正正确确执执行行，设设立立一一个个“递递归归工工作作栈栈”作作为为整整个个递递归归函函数数运运行行期期间间使使用用的的数数据据存存储储区区。每每一一层层递递归归所所需需信信息息构构成成一一个个“工工作作记记录录”，其其中中包包括括所所有有的的实实参参、局局部部变变量量以以及及上上一一层层返返回回的的地地址址。每每进进入入一一层层递递归归，就就产产生生一一个个新新的的工工作作记记录录并并将将其其压压入入栈栈顶顶，每每退退出出一一层层递递归归，就就从从栈栈顶顶弹弹出出一一个个工工作作记记录录。当当前前执执行行层层的的工工作作记记录录必必是是递递归归工工作作栈栈的的栈栈顶顶记记录录，这这个个记记录录称称为为“活动记录活动记录”。见图五、递归的实现3.23.2栈栈的的应应用用举举例例第41页/共93页main()f1();f1()f1();return;f1().return;保存参数，返回地址保存参数，返回地址分配存储空间分配存储空间控制转移控制转移存入栈：存储区存入栈：存储区保存结果保存结果释放局部变量释放局部变量返回到调用函数返回到调用函数从栈中取从栈中取f1f1栈五、递归的实现3.23.2栈栈的的应应用用举举例例第42页/共93页 4.4.递归的优点递归的优点 应用程序易于设计；应用程序易于设计；程程序序结结构构简简单单精精练练，只只需需描描述述递递归归关关系系和和终终止止条条件件，不不用用具具体体描描述述执行过程。执行过程。递归算法格式：递归算法格式：if(if(递归终止条件递归终止条件)返回结果；返回结果；elseelse 调用函数；调用函数；/用递归关系将程序分割为更简单的小程序用递归关系将程序分割为更简单的小程序 5.5.递归的缺点递归的缺点 程序较难理解，可读性差；程序较难理解，可读性差；运运算算速速度度较较慢慢而而且且占占用用较较多多的的存存储储空空间间，递递归归的的层层次次决决定定所所消消耗耗的的时间和空间，层次越多，消耗越多。时间和空间，层次越多，消耗越多。考虑两方面：考虑两方面：递归终止条件递归终止条件递归关系递归关系五、递归的实现3.23.2栈栈的的应应用用举举例例第43页/共93页6.6.常用的递归常用的递归(1)(1)定义是递归的定义是递归的 a.a.阶乘函数阶乘函数 b.Fibonaccib.Fibonacci数列数列(2)(2)数据结构是递归的数据结构是递归的 如如：链链表表、二二叉叉树树、广广义义表表等等数数据据结结构构本本身身固固有有递递归归的的特特性性，对对于于递递归归的的数据结构，采用递归的方法编写算法特别简单。数据结构，采用递归的方法编写算法特别简单。(3)(3)问题的解法是递归的问题的解法是递归的 八皇后问题、八皇后问题、HannoiHannoi塔问题等，用递归求解比迭代求解更简单。塔问题等，用递归求解比迭代求解更简单。五、递归的实现3.23.2栈栈的的应应用用举举例例第44页/共93页例：例：运用递归设计一个将字符串反转输出的程序。运用递归设计一个将字符串反转输出的程序。如：将如：将“ABCABC”反转输出为反转输出为“CBACBA”。算法：算法：递归结束条件：每个字符都输出。递归结束条件：每个字符都输出。递归执行部分：从后一个字符开始输出，字符串数组递归执行部分：从后一个字符开始输出，字符串数组下标后移到字符串长度。下标后移到字符串长度。已知：字符串内容及长度。已知：字符串内容及长度。设输入：设输入：ABCABC五、递归的实现3.23.2栈栈的的应应用用举举例例第45页/共93页1charstring30;2intlength;3Voidreverse(intn)4if(nlen)5reverse(n+1);6printf(“%c”,stringn);789Voidmain()10scanf(“%s”,string);11len=strlen(string);12reverse(0);13printf(“n”);14五、递归的实现3.23.2栈栈的的应应用用举举例例第46页/共93页Voidreverse(0)if(03)reverse(1);printf(“%c”,string0);Voidmain.reverse(0);printf(“n”);Voidreverse(1)if(13)reverse(2);printf(“%c”,string1);Voidreverse(3)if(33)/不满足条件;Voidreverse(2)if(2111235813Longfib(longn)longfiblter(longn)if(n=1)returnn;longf1=0,f2=1,f;elsereturnfib(n-1)+fib(n-2);if(n=1)returnn;elsefor(i=2;i=n;i+)f=f1+f2;f1=f2;f2=f;returnf;五、递归的实现3.23.2栈栈的的应应用用举举例例第49页/共93页3.3队列一、一、队列的定义队列的定义二、抽象数据类型队列的定义二、抽象数据类型队列的定义三、三、队列的表示和实现队列的表示和实现第50页/共93页1 1定义定义队队列列(Queue)(Queue)是是一一种种运运算算受受限限的的特特殊殊的的线线性性表表，它它只只允允许许在在表表的的一一端端进进行插入，而在表的另一端进行删除。行插入，而在表的另一端进行删除。队尾队尾(rear)(rear)允许插入的一端。允许插入的一端。队头队头(front)(front)允许删除的一端。允许删除的一端。设一队列设一队列:q=(a q=(a1 1,a,a2 2,a,an n)，a a1 1为队头元素，为队头元素，a an n为队尾元素，进入队列的顺序为为队尾元素，进入队列的顺序为a a1 1,a,a2 2,a,an n 一、队列的定义3.33.3队队列列第51页/共93页2.2.队列的特点队列的特点先进先出先进先出(First In First Out(First In First Out，简称，简称FIFO)FIFO)。又称队列为先进先出表。又称队列为先进先出表。3.3.应用例子应用例子操作系统中的作业排队，排队购物等。操作系统中的作业排队，排队购物等。一、队列的定义3.33.3队队列列第52页/共93页ADT QueueADT Queue 数据对象：数据对象：D=aD=ai i|a|ai iElemSetElemSet，i=1,2i=1,2n n，n0n0 数据关系：数据关系：R=aR=|a|ai-1i-1，a ai iDD，i=2,3,i=2,3,n,n 基本操作：基本操作：InitQueue(&q)InitQueue(&q)操作结果：构造一个空队列操作结果：构造一个空队列q q。DestroyQueue(&q)DestroyQueue(&q)操作结果：队列操作结果：队列q q被销毁。被销毁。ClearQueue(&q)ClearQueue(&q)操作结果：将操作结果：将q q清为空队列。清为空队列。二、抽象数据类型队列的定义3.33.3队队列列第53页/共93页 QueuEmpty(s)QueuEmpty(s)操作结果：若操作结果：若q q为空队列，则返回为空队列，则返回TR