第三章 栈和队列.ppt

《第三章 栈和队列.ppt》由会员分享，可在线阅读，更多相关《第三章 栈和队列.ppt（86页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 栈和队列栈和队列 3.1 栈 3.2 栈的应用举例 3.3 递归 3.4 队列 3.5 队列应用举例【教学目的教学目的】掌握特殊的线性表桟与队列的工作原理，桟与掌握特殊的线性表桟与队列的工作原理，桟与队列的顺序、链式存储结构下操作的实现，理解计算机系队列的顺序、链式存储结构下操作的实现，理解计算机系统中桟和队列的重要作用和应用统中桟和队列的重要作用和应用【教学重点教学重点】桟与队列的工作原理及其操作实现桟与队列的工作原理及其操作实现【教学难点教学难点】入栈和出栈时的栈空和栈满，进栈和出栈时栈入栈和出栈时的栈空和栈满，进栈和出栈时栈顶指针修改的先后顺序，理解多栈，应用栈和利用栈来理

2、顶指针修改的先后顺序，理解多栈，应用栈和利用栈来理解递归，处理循环队列的队空和队满的确定，队列应用。解递归，处理循环队列的队空和队满的确定，队列应用。3.1 栈栈一一 栈的定义及基本操作栈的定义及基本操作栈栈：限定仅在表的一端进行插入和删除操作的线性表：限定仅在表的一端进行插入和删除操作的线性表栈顶栈顶：允许允许进行插入和删除的一端进行插入和删除的一端栈底栈底：不不允许进行插入和删除的一端允许进行插入和删除的一端空栈：不含元素的空表空栈：不含元素的空表入入/压压/进栈进栈：栈的：栈的插入插入操作操作退退/出栈出栈：栈的：栈的删除删除操作操作 例：栈例：栈s=(a1,a2,a3an)即：元素按即

3、：元素按a1 an顺序依次进栈，则第一个出栈的元素？顺序依次进栈，则第一个出栈的元素？栈的特点栈的特点:先进后出先进后出/后进先出后进先出（First In Last Out）又称为又称为FILO/LIFO线性表线性表ADT Stack 数据对象：数据对象：D ai|aiElemSet,i=1,2,.,n,n0 数据关系：数据关系：R1|ai1,aiD,i=2,.,n 约定约定an 端为栈顶，端为栈顶，a1 端为栈底。端为栈底。基本操作：基本操作：InitStack(&S)操作结果：构造一个空栈操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈初始条件：栈S已存在。已存在。

4、操作结果：栈操作结果：栈S被销毁。被销毁。ClearStack(&S)初始条件：栈初始条件：栈S已存在。已存在。操作结果：将操作结果：将S清为空栈。清为空栈。StackEmpty(S)初始条件：栈初始条件：栈S已存在。已存在。操作结果：若栈操作结果：若栈S为空栈，则返回为空栈，则返回TRUE，否则，否则FALE。StackLength(S)初始条件：栈初始条件：栈S已存在。已存在。操作结果：返回操作结果：返回S的元素个数，即栈的长度。的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈初始条件：栈S已存在且非空。已存在且非空。操作结果：用操作结果：用e返回返回S的栈顶元素。的栈顶元素。

5、Pop(&S,&e)初始条件：栈初始条件：栈S已存在且非空。已存在且非空。操作结果：删除操作结果：删除S的栈顶元素，并用的栈顶元素，并用e返回其值。返回其值。Push(&S,e)初始条件：栈初始条件：栈S已存在。已存在。操作结果：插入元素操作结果：插入元素e为新的栈顶元素。为新的栈顶元素。StackTraverse(S,visit()初始条件：栈初始条件：栈 S 已存在且非空，已存在且非空，visit()为元素的访问函数。为元素的访问函数。操作结果：从栈底到栈顶依次对操作结果：从栈底到栈顶依次对S的每个元素调用函数的每个元素调用函数visit()，一旦一旦visit()失败，则操作失败。失败，

6、则操作失败。ADT Stack栈结构的基本操作：栈结构的基本操作：1、栈初始化：、栈初始化：Init_Stack(S)初始条件：栈初始条件：栈S不存在不存在 操作结果：构造了一个空栈。操作结果：构造了一个空栈。2、销毁栈：、销毁栈：Destroy_Stack(S)初始条件：栈初始条件：栈S已存在已存在 操作结果：销毁一个已存在的栈。操作结果：销毁一个已存在的栈。3、判栈空：、判栈空：Empty_Stack(S)操作结果：若操作结果：若S为空栈返回为为空栈返回为1，否则返回为，否则返回为0。4、入栈：、入栈：Push_Stack(S，x)初始条件：栈初始条件：栈S已存在已存在 操作结果：在栈操作

7、结果：在栈s的顶部插入一个新元素的顶部插入一个新元素x，x成为新的栈顶元素。栈发生成为新的栈顶元素。栈发生 变化变化5、出栈：、出栈：Pop_Stack(S)初始条件：栈初始条件：栈S存在且非空存在且非空 操作结果：栈操作结果：栈S的顶部元素从栈中删除，栈中少了一个元素。栈发生变化的顶部元素从栈中删除，栈中少了一个元素。栈发生变化6、取栈顶元素：、取栈顶元素：GetTop_Stack(S)初始条件：栈初始条件：栈S存在且非空存在且非空 操作结果：栈顶元素作为结果返回，栈不变化操作结果：栈顶元素作为结果返回，栈不变化二、二、栈的顺序存储及操作的实现栈的顺序存储及操作的实现 用一组连续的存储单元依

8、次存放栈中的每个数据元素，并用用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。起始端作为栈底。（顺序栈）（顺序栈）类型定义如下所示：类型定义如下所示：#define MAXSIZE 100typedef struct DataType dataMAXSIZE;int top;SeqStack,*PSeqStack;1、初始化栈：、初始化栈：PSeqStack Init_SeqStack(void)/创建一顺序栈，入口参数无，返回一个指向顺序栈的指针，为零表示创建一顺序栈，入口参数无，返回一个指向顺序栈的指针，为零表示分配空间失败分配空间失败 PSeqStack S;S=(P

9、SeqStack)malloc(sizeof(SeqStack);if(S)Stop=1;return S;2、销毁栈：、销毁栈：顺序栈的销毁操作是初始化操作的逆运算。由于要修改栈顺序栈的销毁操作是初始化操作的逆运算。由于要修改栈的指针变量，所以要将指针地址传给该函数。的指针变量，所以要将指针地址传给该函数。void Destroy_ SeqStack(PSeqStack*S)/销毁顺序栈，入口参数：为要销毁的顺序栈指针地址销毁顺序栈，入口参数：为要销毁的顺序栈指针地址 if(*S)free(*S);*S=NULL;/return;主程序中如何调用主程序中如何调用main()PSeqStack

10、 S;S=Init_SeqStack();Destroy_ SeqStack(&S);3、判栈空：、判栈空：判断栈中是否有元素，只需判断判断栈中是否有元素，只需判断top是否等于是否等于1int Empty_SeqStack(PSeqStack S)/判断栈是否为空，入口参数：顺序栈，返回值：判断栈是否为空，入口参数：顺序栈，返回值：1表示为空，表示为空，0表示非空表示非空 if(Stop=1)return 1;else return 0;清空：清空：stop=1求栈的长度：求栈的长度：stop+14、入栈、入栈 入栈操作是在栈的顶部进行插入一个元素。首先判断栈入栈操作是在栈的顶部进行插入一个

11、元素。首先判断栈是否已满，若满退出，否则，由于栈的是否已满，若满退出，否则，由于栈的top指向栈顶，只要指向栈顶，只要将入栈元素赋到将入栈元素赋到top+1的位置同时的位置同时top+即可即可int Push_SeqStack(PSeqStack S,DataType x)/入口参数：顺序栈，返回值：入口参数：顺序栈，返回值：1表示入栈成功，表示入栈成功，0表示失败。表示失败。if(Stop=MAXSIZE1)/*栈满不能入栈栈满不能入栈*/return 0;else Stop+;SdataStop=x;return 1;5、出栈、出栈 出栈操作是在栈的顶部进行删除操作，首先判断栈是否出栈操作

12、是在栈的顶部进行删除操作，首先判断栈是否为空，若空退出，否则，由于栈的为空，若空退出，否则，由于栈的top指向栈顶，只要修改指向栈顶，只要修改top为为top 1即可：即可：int Pop_SeqStack(PSeqStack S,DataType*x)/删除栈顶元素并保存在删除栈顶元素并保存在*x，入口参数：顺序栈，返回值：入口参数：顺序栈，返回值：1表示出表示出栈成功，栈成功，0表示失败。表示失败。if(Empty_SeqStack(S)/*栈空不能出栈栈空不能出栈*/return 0;else *x=SdataStop;Stop;return 1;6、取栈顶元素、取栈顶元素 取栈顶元素操

13、作是取出栈顶指针取栈顶元素操作是取出栈顶指针top所指的元素值。先判所指的元素值。先判断栈是否为空，若空退出，否则返回断栈是否为空，若空退出，否则返回top 所指单元的值所指单元的值int GetTop_SeqStack(PSeqStack S,DataType*x)/取出栈顶元素，取出栈顶元素，入口参数：顺序栈，被取出的元素指针，这里用指针入口参数：顺序栈，被取出的元素指针，这里用指针带出栈顶值带出栈顶值;返回值：返回值：1表示成功，表示成功，0表示失败。表示失败。if(Empty_SeqStack(S)/*栈空栈空*/return 0;else *x=SdataStop;/*栈顶元素存入栈

14、顶元素存入*x中中*/return(1);若是栈中元素的数目变化范围较大或不清楚栈元素的若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用数目，就应该考虑使用链式存储结构链式存储结构“链栈链栈”。链栈通。链栈通常用一个常用一个无头结点的单链表表示无头结点的单链表表示。由于栈的插入删除操作只能在一端进行，而对于单链由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。指针作

15、为栈顶指针。三三 栈的链式存储及操作实现栈的链式存储及操作实现栈的链式存储在栈的链式存储在C中可用下列类型定义实现：中可用下列类型定义实现：定义栈的定义栈的节点节点：typedef struct node DataType data;struct node *next;StackNode,*PStackNode;定义定义栈栈：typedef struct PStackNode top;LinkStack,*PLinkStack;PLinkStack S;S=(PLinkStack)malloc(sizeof(LinkStack);1、初始化空栈、初始化空栈 PLinkStack Init_Li

16、nkStack（void）/初始化链栈，入口参数：空，返回值：链栈指针，初始化链栈，入口参数：空，返回值：链栈指针，null表示初始化失表示初始化失败败 PLinkStack S;S=(PLinkStack)malloc(sizeof(LinkStack);if(S)Stop=NULL;return(S);2、销毁栈、销毁栈void Destroy_LinkStack(PLinkStack *LS)/销毁链栈，入口参数：要销毁链栈指针地址，无返回值销毁链栈，入口参数：要销毁链栈指针地址，无返回值 PStackNode p,q；if(*LS)p=(*LS)top;while(p)q=p;p=pn

17、ext;free(q);free(*LS);*LS=NULL;/return;3、判栈空、判栈空int Empty_LinkStack（PLinkStack S）/判断链栈是否为空，入口参数：链栈指针，返回值：判断链栈是否为空，入口参数：链栈指针，返回值：1表示栈空，表示栈空，0表表示栈非空示栈非空 return(Stop=NULL);4、入栈、入栈 int LinkStack Push_LinkStack(PLinkStack S,DataType x)PStackNode p;p=(PStackNode)malloc(sizeof（StackNode）);if(!p)printf(“内存溢

18、出内存溢出”);return(0);pdata=x;pnext=Stop;Stop=p;return(1);5、出栈、出栈int Pop_LinkStack(PLinkStack S,DataType*x)PStackNode p;if(Empty_LinkStack(S)printf(“栈空，不能出栈栈空，不能出栈”);return(0);*x=S topdata;p=S top;Stop=Stopnext;free(p);return(1);6、取栈顶元素、取栈顶元素int GetTop_LinkStack(PLinkStack S,DataType *x)/返回值：返回值：1表示出栈成功

19、，表示出栈成功，0表示失败表示失败 if(Empty_LinkStack(S)printf(“栈空栈空”);return(0);*x=S topdata;return(1);例例3.1 数制转换问题数制转换问题 将十进制数将十进制数N转换为转换为r进制的数，其转换方法利用进制的数，其转换方法利用辗转相除法辗转相除法 算法思想如下：算法思想如下：（1）初始化栈，初始化）初始化栈，初始化N为要转换的数，为要转换的数，r为进制数为进制数（2）判断）判断N的值，为的值，为0转（转（4），否则），否则N%r 压入栈压入栈s中中（3）用）用N/r 代替代替 N转（转（2）（4）出栈，出栈序列即为结果）出栈

20、，出栈序列即为结果3.23.2栈的应用举例栈的应用举例typedef int DataType;int conversion(int N，int r)PSeqStack S;/*定义一个顺序栈定义一个顺序栈*/DataType x;if(!r)printf(“基数不能为基数不能为0”);return(0);S=Init_SeqStack();/*初始化栈初始化栈*/if(!S)printf(“栈初始化失败栈初始化失败”);return(0);while(N)Push_SeqStack(S，N%r);/*余数入栈余数入栈*/N=N/r;/*商作为被除数继续商作为被除数继续*/while(!Emp

21、ty_SeqStack(S)/*直到栈空退出循环直到栈空退出循环*/Pop_SeqStack(S,&x);/*弹出栈顶元素弹出栈顶元素*/printf(“%d”，x);/*输出栈顶元素输出栈顶元素*/Destroy_ SeqStack(&S);/*销毁栈销毁栈*/例例3.2 迷宫求解（回溯法）迷宫求解（回溯法）求解思想求解思想：从入口出发，按某一方向向前探索，：从入口出发，按某一方向向前探索，若能走通并且未走过，则继续往前走，若能走通并且未走过，则继续往前走，否则沿原路返回前一点，换下一个方向再继续试探否则沿原路返回前一点，换下一个方向再继续试探 直到找到一条通路，或无路可走又返回到入口点。直

22、到找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向。从该点前进的方向。1.表示迷宫的数据结构表示迷宫的数据结构2.测试方向测试方向 规定：从当前位置（规定：从当前位置（x，y）向前试探的方向）向前试探的方向从正东沿顺时针从正东沿顺时针方向进行方向进行从某点从某点(x，y)按某一方向按

23、某一方向 d(0v3)到达新点（到达新点（i，j）的坐标：）的坐标：i=x+moved.x;j=y+moved.y;3.栈的设计栈的设计 当到达了某点而无路可走时需返回前一点，再从前一当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向。且还要有从前一点到达本点的方向。栈中元素是一个由行、栈中元素是一个由行、列、方向组成列、方向组成栈元素的设计如下：栈元素的设计如下：typedef struct int x,y,d;/*横纵

24、坐标及方向横纵坐标及方向*/DataType;栈的定义仍然为：栈的定义仍然为：PSeqStack S;4.如何防止重复到达某点，以避免发生死循环如何防止重复到达某点，以避免发生死循环一种方法：另外设置一个标志数组一种方法：另外设置一个标志数组markmn，它的所有元素，它的所有元素 都初始化为都初始化为0，一旦到达了某一点，一旦到达了某一点(i,j)之后，使之后，使 markij 置置1，下次再试探这个位置时就不能再走，下次再试探这个位置时就不能再走 了。了。另一种方法：当到达某点（另一种方法：当到达某点（i,j）后使）后使mazeij 置置 1，以便区，以便区别别 未到达过的点，同样也能起到

25、防止走重复点的目未到达过的点，同样也能起到防止走重复点的目 的。的。本算法采用后者方法，算法结束前可恢复原迷宫。本算法采用后者方法，算法结束前可恢复原迷宫。迷宫求解算法思想如下：迷宫求解算法思想如下：（1）栈初始化）栈初始化;（2）将入口点坐标所走方向（）将入口点坐标所走方向（d设为）入栈设为）入栈（3）while(栈不空栈不空)栈顶元素（栈顶元素（x,y,d）出栈）出栈;求出下一个要试探的方向求出下一个要试探的方向d+;while （还有剩余试探方向时即（还有剩余试探方向时即d4）求新点坐标求新点坐标 (i,j);if（(i,j)可走）可走）则则 则将（则将（x,y,d）再次入栈）再次入栈;

26、将新点（将新点（i,j）切换为当前点（）切换为当前点（x,y）;if (x,)=(,n)打印路径，算法结束打印路径，算法结束;else 重置重置 d=0;else d+;（4）找不到通路，结束！）找不到通路，结束！#define m 6 /*迷宫的实际行迷宫的实际行 */#define n 8 /*迷宫的实际列迷宫的实际列*/int mazepath(int maze m+2n+2,item*move,int x0,int y0)/*求迷宫路径求迷宫路径,入口参数：指向迷宫数组的指针，指向移动方向的入口参数：指向迷宫数组的指针，指向移动方向的指针，开始点（指针，开始点（x0，y0），到达点（）

27、，到达点（m，n）,返回值：返回值：1表示求出表示求出路径，路径，0表示无路径表示无路径*/PSeqStack S;DataType temp;int x,y,d,i,j;temp.x=x0;temp.y=y0;temp.d=1;S=Init_SeqStack();/*初始化栈初始化栈*/if(!S)printf(“栈初始化失败栈初始化失败”);return(0);Push_SeqStack(S，temp);while(!Empty_SeqStack(S)Pop_SeqStack(S,&temp);x=temp.x;y=temp.y;d=temp.d+1;while (d4)i=x+moved

28、.x;j=y+moved.y;if (mazeij=0)temp=x,y,d;Push_SeqStack(S,temp);x=i;y=j;mazexy=1;if(x=m&y=n)/*迷宫有路迷宫有路*/while(!Empty_SeqStack(S)Pop_SeqStack(S,&temp)printf(“(%d,%d)”，temp.x,temp.y);Destroy_ SeqStack(&S);return 1;else d=0;else d+;/*while(d4)*/*while*/Destroy_ SeqStack(&S);return 0;/*迷宫无路迷宫无路*/例例3.3 表达式求

29、值表达式求值 表达式求值是程序设计语言编译中一个最基本的问题。它表达式求值是程序设计语言编译中一个最基本的问题。它的实现也是栈的应用中的一个典型的例子。的实现也是栈的应用中的一个典型的例子。表达式：由表达式：由操作数操作数、运算符运算符和和界限符界限符组成的有意义的式子。组成的有意义的式子。操作数：可以是常数，变量或常量。操作数：可以是常数，变量或常量。运算符：从运算对象的个数上分，有单目运算符、双目运算符和运算符：从运算对象的个数上分，有单目运算符、双目运算符和三目运算符；从运算类型上分，有算术运算、关系运算、逻三目运算符；从运算类型上分，有算术运算、关系运算、逻辑运算。辑运算。界限符：左右

30、括号和表达式结束符等。界限符：左右括号和表达式结束符等。运算符、界限符统称算符。运算符、界限符统称算符。为简单化，在这里，我们仅限于讨论只含二目运算符的加、为简单化，在这里，我们仅限于讨论只含二目运算符的加、减、乘、除算术表达式，并且操作数为一位字符表示的整数。减、乘、除算术表达式，并且操作数为一位字符表示的整数。在表达式求值时，一般表达式有以下三种表示形式：在表达式求值时，一般表达式有以下三种表示形式：（1）中缀表示：）中缀表示：（2）后缀表示：）后缀表示：(逆波兰表达式逆波兰表达式)（3）前缀表示：）前缀表示：(波兰表达式波兰表达式)1 中缀表达式求值中缀表达式求值 对于先后遇到的对于先后

31、遇到的2个算符个算符1、2，需先比较它们的优先级，才能，需先比较它们的优先级，才能决定先做那个算符决定先做那个算符算法：算法：（1）设置）设置2个空栈：操作数栈和运算符栈个空栈：操作数栈和运算符栈（2）将）将#压入运算符栈压入运算符栈（3）依次读入表达式中的字符）依次读入表达式中的字符 若为操作数，则压入数栈若为操作数，则压入数栈 若为运算符，则和运算符栈的栈顶运算符比较优先级若为运算符，则和运算符栈的栈顶运算符比较优先级 若高，则压入运算符栈若高，则压入运算符栈 若相等，则运算符栈中栈顶运算符出栈不要若相等，则运算符栈中栈顶运算符出栈不要 若低，则运算符栈中栈顶运算符出栈，同时从数若低，则运

32、算符栈中栈顶运算符出栈，同时从数 栈退出栈退出2个操作数，进行相应运算，并将结个操作数，进行相应运算，并将结 果压入数栈果压入数栈（4）最终数栈栈顶的值就是表达式的结果）最终数栈栈顶的值就是表达式的结果2.后缀表达式（也称逆波兰式）求值后缀表达式（也称逆波兰式）求值算法步骤：算法步骤：（1）设置一空的数栈）设置一空的数栈（2）依次读入表达式中字符）依次读入表达式中字符 若为操作数，就压入数栈若为操作数，就压入数栈 若为运算符，就从数栈退出若为运算符，就从数栈退出2个操作数，进行相应运个操作数，进行相应运 算，并将结果压入数栈算，并将结果压入数栈（3）最终数栈栈顶的值就是表达式的结果）最终数栈栈

33、顶的值就是表达式的结果int IsNum(char c)/*判断字符是否为操作数。若是返回判断字符是否为操作数。若是返回1，否则返回，否则返回0*/if(c=0&c=0&c=9)return(1);else return(0);int priority(char op)switch(op)case#:return(1);case):return(2);case+:case:return(3);case*:case/:return(4);case(:return(5);defalut:return(0);typedef char DataType;.int infix_exp_value(cha

34、r*infixexp,char*postfixexp)PSeqStack S;char c,w,topelement;S=Init_SeqStack();/*初始化栈初始化栈*/if(!S)printf(“栈初始化失败栈初始化失败”);return(0);Push_SeqStack(S，#);w=*infixexp;while(GetTop_SeqStack(S，&c),c)!=#|w!=#)if(IsNum(w)*postfixexp=w;postfixexp+;w=*(+infixexp);else if(GetTop_SeqStack(S,&c),c)=(&w=)Pop_SeqStack

35、(S,&topelement)；w=*(+infixexp);else if(GetTop_SeqStack(S,&c),c)=(|priority(GetTop_SeqStack(S,&c),c)1)long fact(int n)if(n=0|n=1)return 1;else return(n*fact(n1);通常使用递归的情况：通常使用递归的情况：（1）递归定义的数学函数）递归定义的数学函数（2）具有递归定义的数据结构）具有递归定义的数据结构（3）本身无明显递归结构，但用递归求解比迭代求解更简单）本身无明显递归结构，但用递归求解比迭代求解更简单的问题的问题 例：八皇后例：八皇后 汉诺

36、塔汉诺塔Hannoi(int n,char A,char B,char C)if(n=1)move(n,A,C);else Hanoi(n1,A,C,B);move(n,A,C);Hanoi(n1,B,A,C);例：求一维数组例：求一维数组aL.H中的最大值中的最大值算法思想：将算法思想：将aL.H一分为二，一分为二，M=(L+H)/2 求求aL.M最大数最大数 x 求求aM+1.H最大数最大数 y 若若L=H 则则aL就是最大值就是最大值终止终止int max(int a,int l,int h)int m,x,y;if (l=h)return al;m=(l+h)/2;x=max(a,l,

37、m);y=max(a,m+1,h);if(xy)return x;else return y;求最大值求最大值二二 递归和栈的关系递归和栈的关系递归函数的递归调用时系统需要的事：递归函数的递归调用时系统需要的事：保护现场：将返回地址、形参、局部变量的值压栈保护现场：将返回地址、形参、局部变量的值压栈 将实参的值传给被调函数，并转到被调函数入口处执行将实参的值传给被调函数，并转到被调函数入口处执行调用结束，需做的事：调用结束，需做的事：恢复现场：从栈顶取出被保存的信息恢复现场：从栈顶取出被保存的信息转到刚取出的返回地址处，继续向下执行转到刚取出的返回地址处，继续向下执行N!递归调用过程示意图递归

38、调用过程示意图递归函数的非递归化递归函数的非递归化 递归算法具有两个特性：递归算法具有两个特性：(1)递归算法是一种分而治之、把复杂问题分解为简单问题的求递归算法是一种分而治之、把复杂问题分解为简单问题的求解方法，对求解某些复杂问题，递归算法是有效的。解方法，对求解某些复杂问题，递归算法是有效的。(2)递归算法的时间效率差，因为需要不断地进栈和出栈。递归算法的时间效率差，因为需要不断地进栈和出栈。有两类消除递归方法有两类消除递归方法I.一类是简单递归问题的转换，用循环结构的算法替代一类是简单递归问题的转换，用循环结构的算法替代II.另一类是基于栈的方式，即将递归中隐含的栈机制转化为由另一类是基

39、于栈的方式，即将递归中隐含的栈机制转化为由用户直接控制的明显的栈，利用堆栈保存参数，由于堆栈的用户直接控制的明显的栈，利用堆栈保存参数，由于堆栈的后进先出特性吻合递归算法的执行过程，因而可以用非递归后进先出特性吻合递归算法的执行过程，因而可以用非递归算法替代递归算法算法替代递归算法三三 递归算法实例递归算法实例例例3.4 用递归写出求数组中用递归写出求数组中n个元素之和个元素之和 求求n个元素的和与求个元素的和与求n1个元素的和是相同的过程个元素的和是相同的过程int sum(int a,int n)/求数组求数组a中的中的n个元素之和个元素之和 if(n=0)/最小尺度当最小尺度当n1时，时

40、，Perm(R)由由(r1)Perm(R1),(r2)Perm(R2)，(rn)Perm(Rn)构成。构成。产生产生Perm(R)的递归算法如下，设的递归算法如下，设R为一整型数组为一整型数组int listNvoid Perm(int list,int k,int m)/求下标求下标k 至至m元素的全排列元素的全排列,num为为km的数的个数的数的个数 int i;if(k=m)for(i=0;i=m;i+)printf(%d,listi);printf(n);else for(i=k;i=m;i+)Swap(list,k,i);/依次将依次将(ri)与与rk交换交换 Perm(list,k

41、+1,m);/递归求递归求Perm(Ri)Swap(list,k,i);/将将(ri)换回原位置换回原位置 例例3.6 用递归写出字符串倒置的算法用递归写出字符串倒置的算法分析：将字符串倒置，可以将第一个元素和最后一个元素调换，再把分析：将字符串倒置，可以将第一个元素和最后一个元素调换，再把剩下的字符串倒置，而剩下的字符串长度就在原来的长度上减剩下的字符串倒置，而剩下的字符串长度就在原来的长度上减2 如果字符串的串长如果字符串的串长1则无需倒置直接返回则无需倒置直接返回void ConverseStrt(char *Str，int start，int end)/将字符串倒置，将字符串倒置，St

42、r为字符串，为字符串，strat和和end为字符数组的开始和结束下标为字符数组的开始和结束下标 if(endstart1)return;/Str的串长的串长1，字符串的首尾元素调换，再将去掉首尾元素的字符串调换，字符串的首尾元素调换，再将去掉首尾元素的字符串调换例例3.7 用递归对迷宫进行求解用递归对迷宫进行求解例例3.8 火车进站问题火车进站问题请大家自行阅读书上的例子请大家自行阅读书上的例子3.4 队列队列一、队列的定义一、队列的定义队列：限定在表的一端进行插入，在另外一端进行删除的线性表队列：限定在表的一端进行插入，在另外一端进行删除的线性表对尾：允许插入的一端对尾：允许插入的一端队首队

43、首/头：允许删除的一端头：允许删除的一端空队列：表中无元素空队列：表中无元素进进/入对：插入操作入对：插入操作退退/出队：删除操作出队：删除操作队列的特点：队列的特点：先进先出先进先出（First In First Out）简称为简称为FIFO线性表。线性表。例：队列例：队列Q=(a1,a2,an)元素按元素按a1,a2,an依次入队，出队顺序？依次入队，出队顺序？队列的基本操作：队列的基本操作：1队列初始化：队列初始化：Init_Queue()初始条件：初始条件：队队Q不存在。不存在。操作结果：操作结果：构造了一个空队构造了一个空队Q。2队列初始化：队列初始化：Destroy_Queue(Q

44、)初始条件：初始条件：队队Q不存在。不存在。操作结果：操作结果：构造了一个空队。构造了一个空队。3判队空操作：判队空操作：Empty_Queue(Q)初始条件：队初始条件：队Q存在存在 操作结果：若操作结果：若Q为空队则返回为为空队则返回为1，否则返回为，否则返回为0。4入队操作：入队操作：In_Queue(Q,x),初始条件：队初始条件：队Q存在。存在。操作结果：对已存在的队列操作结果：对已存在的队列Q，插入一个元素，插入一个元素x到队尾，队到队尾，队发生变化。发生变化。5出队操作：出队操作：Out_Queue(Q)初始条件：初始条件：队队Q存在且非空存在且非空 操作结果：删除队首元素，并返

45、回其值，队发生变化。操作结果：删除队首元素，并返回其值，队发生变化。6读队头元素：读队头元素：Front_Queue(Q,x)初始条件：初始条件：队队Q存在且非空存在且非空 操作结果：操作结果：读队头元素，并返回其值，队不变；读队头元素，并返回其值，队不变；二二 队列的顺序存储及操作实现队列的顺序存储及操作实现用一组地址连续的存储单元来用一组地址连续的存储单元来依次存放队列中的每个数据元素依次存放队列中的每个数据元素 顺序顺序队队 由于对头、队尾都是在动态变化的，需设置由于对头、队尾都是在动态变化的，需设置对头和队尾对头和队尾2个指针个指针定义队列定义队列#define MAXSIZE 100

46、 /*队列的最大容量队列的最大容量*/typedef struct DataType dataMAXSIZE;/*队列的存储空间队列的存储空间*/int front,rear;/*队头队尾指针队头队尾指针*/SeqQueue,*PSeqQueue;定义一个指向队列的指针：定义一个指向队列的指针：SeqQueue *Q;或或 PSeqQueue Q；Q=(PSeqQueue)malloc(sizeof(SeqQueue);初始对空：初始对空：Qfront=Qrear=1对头指针对头指针:指向对头元素前一个位置指向对头元素前一个位置队尾指针队尾指针：指向队尾元素：指向队尾元素 顺序队列的队满条件：

47、顺序队列的队满条件：Qrear=MAXSIZE1 假上溢假上溢如何解决？如何解决？循环队列循环队列队头指针队头指针:指向对头元素前一个位置指向对头元素前一个位置队尾指针队尾指针：指向队尾元素：指向队尾元素入队：入队：Qrear=(Qrear+1)%MAXSIZE 元素入队元素入队出队：出队：Qfront=(Qfront+1)%MAXSIZE 元素出队元素出队队空：队空：Qrear=Qfront队满：队满：Qrear=Qfront如何解决？如何解决？2种方法：种方法：（1）加一标志量）加一标志量f或计数量或计数量num以示区别以示区别 f=0 队空队空 f=1 队满队满 num=0 队空队空 n

48、um=MAXSIZE 队满队满（2）牺牲一个存储空间）牺牲一个存储空间 约定：队头指针指向的位置不存储元素约定：队头指针指向的位置不存储元素 (也可采用牺牲队尾指针指向的空间也可采用牺牲队尾指针指向的空间)队列空：队列空：Qfront=Qrear 队列满：队列满：(Q rear+1)%MAXSIZE=Q front 通常采用的通常采用的接下来，给出顺序存储的循接下来，给出顺序存储的循环队列操作算法：环队列操作算法：1、队列初始化、队列初始化PSeqQueue Init_SeqQueue()/*返回值：新顺序队列指针，返回值：新顺序队列指针，null表示失败表示失败*/PSeqQueue Q;Q

49、=(PSeqQueue)malloc(sizeof(SeqQueue);if(Q)Qfront=0;Qrear=0;return Q;2、销毁队列、销毁队列 void Destroy_SeqQueue(PSeqQueue*Q)if(*Q)free(*Q);*Q=NULL;清空：清空：Qfront=Qrear=0;main()PSeqQueue q;q=Init_ SeqQueue();Destroy_ SeqQueue(&q);3、判断队空、判断队空 int Empty_SeqQueue(PSeqQueue Q)/返回值：返回值：1表示为空，表示为空，0表示非空表示非空 if(Q&Qfront

50、=Qrear)return(1);else return(0);4、入队、入队int In_SeqQueue(PSeqQueue Q,DataType x)/返回值：返回值：1表示成功，表示成功，1表示队满溢出表示队满溢出 if(Qrear+1)%MAXSIZE=Qfront)printf(队满队满);return 1;/*队满不能入队队满不能入队*/else Qrear=(Qrear+1)%MAXSIZE;QdataQrear=x;return 1;/*入队完成入队完成*/5、出队、出队int Out_SeqQueue(PSeqQueue Q，DataType*x)/返回值：返回值：1表示成