[工学]数据结构与算法-第四章课件.ppt

1、4 栈和队列栈和队列 4.1 栈 4.1.1 栈的定义 栈（栈（stack）又称堆栈，）又称堆栈，它是一种运算受限的线性表，它是一种运算受限的线性表，其限制是仅允许在表的一端进其限制是仅允许在表的一端进行插入和删除运算。行插入和删除运算。人们把对栈进行运算的一人们把对栈进行运算的一端称为栈顶，栈顶的第一个元端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，素被称为栈顶元素，相对地，把另一端称为栈底。把另一端称为栈底。v向一个栈插入新元素又称为进栈或入栈，它是把向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶该元素放到栈顶元素的上面，使之成为新的栈顶元素；元

2、素；v从一个栈删除元素又称为出栈或退栈，它是把栈从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。顶元素。v由于栈的插入和删除运算仅在栈顶一端进行，后由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先出栈，所以又把栈称为后进先进栈的元素必定先出栈，所以又把栈称为后进先出表出表(Last In First Out,简称简称LIFO)。v栈的物理存储可以用顺序存储结构，也可以用链栈的物理存储可以用顺序存储结构，也可以用链式存储结构式存储结构v栈中没有任何元素称为空栈。栈中没有任何元素称为空栈。假定一个栈假定

3、一个栈S为为(a,b,c)，其中表尾的一端，其中表尾的一端为栈顶，字符为栈顶，字符c为栈顶元素。若向为栈顶元素。若向S压入一个压入一个元素元素d，则，则S变为变为(a,b,c,d)，此时字符，此时字符d为栈为栈顶元素；若接着从栈顶元素；若接着从栈S中依次删除两个元素，中依次删除两个元素，则首先删除的是元素则首先删除的是元素d，接着删除的是元素，接着删除的是元素c，栈栈S变为变为(a,b)，栈顶元素为，栈顶元素为b。4.1.2 栈的数据类型和运算栈的数据类型和运算v栈的抽象数据类型中的数据部分为具有ElemType元素类型的一个栈，它可以采用任一种存储结构实现；v栈的操作部分应包括元素进栈、元素

4、出栈、读取栈顶元素、检查栈是否为空等。栈的主要操作及程序：(1)初始化栈S，即把它置为空 void InitStack(S);(2)新元素x进栈，即把x值插入到栈顶 void Push(S,ElemType x);(3)删除栈顶元素并返回之 ElemType Pop(S);(4)返回栈顶元素的值，不会改变栈的状态 ElemType Peek(S);(5)判断栈S是否为空，若是则返回1表示真，否则返回0表示假 int EmptyStack(S);(6)清除栈S中的所有元素，使之成为一个空栈 void ClearStack(S);假定栈a的元素类型为int，下面为调用栈操作的一些例子。(1)Ini

5、tStack(a);/表示把栈a置空 (2)Push(a,18);/表示元素18进栈 (3)int x=46;Push(a,x);/表示x的值46进栈 (4)Push(a,x/3);/表示x除以3的整数值15进栈 (5)x=Pop(a);/表示栈顶元素15退栈并赋给x (6)printf(“%d”,Peek(a);/表示读取当前栈顶元素46并输出 (7)Pop(a);/栈顶元素46出栈，返回值46自动丢失 (8)EmptyStack(a);/因此时栈a非空，所以返回的值false (9)printf(“%dn”,Pop(a);/栈顶元素18退栈并输出，此时栈已空 (10)x=EmptyStac

6、k(a);/因栈为空，返回true，接着把对应的整数值1赋给x4.2 栈的顺序存储结构和操作实现栈的顺序存储结构和操作实现v栈的顺序存储结构也称为顺序栈，它是栈的顺序存储结构也称为顺序栈，它是一种运算受限的顺序表。一种运算受限的顺序表。v顺序栈具有栈的一切特点顺序栈具有栈的一切特点4.2.1 顺序栈的定义 1.利用普通数组加栈顶指针来实现栈的定义 栈的顺序存储结构需要使用一个数组和一个整型变量来实现，利用数组来顺序存储栈中的所有元素，利用整型变量来存储栈顶元素的下标位置。假定栈数组用stackMaxSize表示，指示栈顶位置的整型变量用top表示，则元素类型为ElemType的栈的顺序存储结构

7、可定义为：ElemType stackMaxSize;int top;其中，MaxSize为一个整型全局常量，需事先定义，由它确定顺序栈（即顺序存储的栈）的最大长度，又称为深度，即栈空间最多能够存储的元素个数；由于top用来指示栈顶元素的位置，所以把它称为栈顶指针栈顶指针。2.利用记录来实现栈的定义 假定该记录类型用StackSq表示，则定义为：struct StackSq ElemType stackMaxSize;int top;3.采用动态分配存储空间的方法来实现栈的定义 struct StackSq ElemType*stack;/*存栈元素的数组指针*/int top;/*存栈顶元素

8、的下标位置*/int MaxSize;/*存stack数组长度*/;v在顺序存储的栈中，top的值为-1表示栈空，v每次向栈中压入一个元素时，首先使top增1，用以指示新的栈顶位置，然后再把元素赋值到这个空位置上，每次从栈中弹出一个元素时，首先取出栈顶元素，然后使top减1，指示出前一个元素成为新的栈顶元素。v在一个顺序栈中，若top已经指向了MaxSize-1 的位置，则表示栈满，若再向其插入新元素时就需要进行栈满处理，v由于顺序栈的插入和删除运算相当于是在顺序表的表尾进行的，其时间复杂度为O(1)。设一个栈S为(a,b,c,d,e)，对应的顺序存储结构如下图(a)所示。若向S中插入一个元素

9、f，则对应如下图(b)所示。若接着执行两次出栈操作后，则栈S对应如下图(c)所示。若依次使栈S中的所有元素出栈，则s变为空，如下图(d)所示。MaxSize-10 a0 a1 b0 a1 b1 b2 2 c2 c2 c3 d3 d3 d4 e4 e5 f401234toptoptop(a)top=4(b)top=5(c)top=3(d)top=-1MaxSize-1MaxSize-1MaxSize-1栈在顺序存储结构下的操作实现：1.初始化栈初始化栈S为空为空 此操作可以包括两种情况，一种是置空并隐含分配固定大小的动态存储空间，另一种是置空并分配由参数指定大小的动态存储空间。首先给出第一种置空

10、的算法。void InitStack(struct StackSq*S)/*置栈空间初始最大长度为10*/S-MaxSize=10;/*动态存储空间分配*/S-stack=malloc(10*sizeof(ElemType);/*置栈为空*/S-top=-1;第二种置空栈的算法：void InitStack(struct StackSq*S,int ms)/*检查ms是否有效，若无效则退出运行*/if(msMaxSize=ms;/*动态存储空间分配，若分配失败则退出运行*/S-stack=malloc(ms*sizeof(ElemType);if(!S-stack)printf(动态存储分配失

11、败!n);exit(1);/*初始置栈为空*/S-top=-1;2.新元素进栈，即把它插入到栈顶新元素进栈，即把它插入到栈顶 在这个算法中，对栈满的处理方法是调用一个函数，使之得到大一倍的栈数组空间，接着进行新元素的插入操作。void Push(struct StackSq*S,ElemType x)/*若栈空间用完则重新分配更大的存储空间*/if(S-top=S-MaxSize-1)againMalloc(S);/*栈顶指针后移一个位置*/S-top+;/*将新元素插入到栈顶*/S-stackS-top=x;void againMalloc(struct StackSq*S)/*空间扩展为原

12、来的2倍，原内容被自动 拷贝到p所指向的存储空间中*/ElemType*p;p=realloc(S-stack,2*S-MaxSize*sizeof(ElemType);if(!p)/*分配失败退出运行*/printf(存储空间用完!n);exit(1);/*使stack指向新的栈空间*/S-stack=p;/*把栈空间大小修改为新的长度*/S-MaxSize=2*S-MaxSize;3.删除栈顶元素并返回值删除栈顶元素并返回值 ElemType Pop(struct StackSq*S)/*若栈空则退出运行*/if(S-top=-1)printf(栈空，无元素出栈!n);exit(1);/*

13、栈顶指针减1表示退栈*/S-top-;/*返回原栈顶元素的值*/return S-stackS-top+1;4.3 栈的链接存储结构和操作实现栈的链接存储结构和操作实现 栈的链接存储结构是通过由结点构成的单链表实现的，此时表头指针被称为栈顶指栈顶指针针，由栈顶指针指向的表头结点被称为栈顶栈顶结点结点，整个单链表被称为链栈链栈，即链接存储的栈。v当向一个链栈插入元素时，是把该元素插入到栈顶，即使该元素结点的指针域指向原来的栈顶结点，而栈顶指针则修改为指向该元素结点，使该结点成为新的栈顶结点。v当从一个链栈中删除元素时，是把栈顶元素结点删除掉，即取出栈顶元素后，使栈顶指针指向原栈顶结点的指针域所指

14、向的结点。v对链栈的插入和删除操作均是在单链表的表头进行的，其时间复杂度为O(1)。设一个栈为(a,b,c)，当采用链接存储时，对应的存储结构如下图(a)所示，其中HS表示栈顶指针，其值为存储元素c结点的地址。其插入和删除操作如图所示：data nextc(a)(b)(c)aabbdabcHSHSHS4.3.1 链栈中数据结点的定义v链栈中的结点仍采用以前已经定义的sNode结点类型，即：struct sNode ElemType data;/数据域数据域 struct sNode*next;/指针域指针域 Struct sNode*L；4.3.2 链栈的主要操作 假定链栈中的结点采用已经定义

15、的sNode结点类型，并假定栈顶指针用HS表示，链栈操作的算法有：1.初始化链栈为空Void InitStack(struct sNode*HS)*HS=NULL;如果 定义为 struct sNode*类型的栈顶变量p作为一个栈顶指针，则初始化程序可变为：Void InitStack(&p)p=NULL;2.向链栈中插入一个元素向链栈中插入一个元素 void Push(struct sNode*HS,ElemType x)/*为插入元素获取动态结点*/struct sNode*newp;newp=malloc(sizeof(struct sNode);if(newp=NULL)printf(

16、内存动态空间用完，退出运行!n);exit(1);/*给新分配的结点赋值*/newp-data=x;/*向栈顶插入新结点*/newp-next=*HS;*HS=newp;3.从链栈中删除一个元素并返回它从链栈中删除一个元素并返回它 ElemType Pop(struct sNode*HS)struct sNode*p;ElemType temp;/*对于空栈则退出运行*/if(*HS=NULL)printf(栈空无法删除!n);exit(1);/*暂存栈顶结点指针,并使栈顶指针指向下一结点*/p=*HS;*HS=p-next;/*暂存原栈顶元素以便返回,同时回收原栈顶结点*/temp=p-da

17、ta;free(p);/*返回原栈顶元素*/return temp;4.读取栈顶元素读取栈顶元素 ElemType Peek(sNode*HS)/HS为值参或引用形参均可 if(*HS=NULL)/无法从空栈中读取 printf(“栈空，无栈顶结点！n”)exit(1);return(*HS)-data;/返回栈顶结点的值 4.4 栈的简单应用举例 例例4-1 从键盘上输入一批整数，然后按照相反的次序打印出来 根据题意可知，后输入的整数将先被打印出来，这正好符合栈的后进先出的特点。所以此题很容易用栈来解决。假定采用顺序栈，其参考程序如下：#include#include typedef int

18、 ElemType;/*定义元素类型为整型*/struct StackSq ElemType*stack;/*存栈元素的动态数组指针*/int top;/*存栈顶元素的下标位置*/int MaxSize;/*存stack数组长度，亦即所能存储栈的最大长度*/;#include顺序栈操作.c /*假定对顺序栈各种操作的算法已经存于该程序文件中*/void main()struct StackSq a;int x;InitStack(&a);printf(输入一批整数，直到输入终止标志-1为止!n);scanf(%d,&x);while(x!=-1)Push(&a,x);scanf(%d,&x);

19、while(!EmptyStack(&a)/*栈不为空时依次退栈并输出*/printf(%d,Pop(&a);printf(n);v假定从键盘上输入为：v 78 63 45 82 91 34-1v则输出为：v 34 91 82 45 63 78 例例4-2 堆栈在计算机语言的编译过程中可用来进行语法检查。试编写一个算法，用来检查一个C/C+语言程序中的花括号、方括号和圆括号是否配对，若能够全部配对则返回1，否则返回0。编写出算法如下：int BracketsCheck(char*fname)/*对由fname所指字符串为文件名的程序文件进行括号配对检查*/Struct StackSq a;/*

20、定义一个顺序栈*/char ch;/*定义一个字符变量*/FILE*finstr;/*定义一个文件指针变量，即文件流*/finstr=fopen(fname,r);/*用文件流finstr打开以fname所指字符串为文件名的文件,并规定为读文件方式*/if(!finstr)/*没有找到对应的磁盘文件则退出运行*/printf(File%snot found!n,fname);exit(1);InitStack(&a);/*栈a初始化*/ch=fgetc(finstr);/*从文件中读取第一个字符到ch*/while(ch!=EOF)/*未读到文件最后的结束标志则循环*/printf(%c,ch

21、);/*向屏幕输出被读出的字符*/switch(ch)/*对读到的各种括号分情况处理*/case:case:case(:Push(&a,ch);/*出现以上三种左括号则进栈*/break;case:if(Peek(&a)=)Pop(&a);/*栈顶的左花括号出栈*/else return 0;break;case:if(Peek(&a)=)Pop(&a);/*栈顶的左中括号出栈*/else return 0;break;case):if(Peek(&a)=()Pop(&a);/*栈顶的左圆括号出栈*/else return 0;break;ch=fgetc(finstr);/*从文件中顺序读取

22、下一个字符到ch*/if(EmptyStack(&a)/*栈最后为空时返回1否则返回0*/return 1;else return 0;4.5 4.5 算术表达式的计算算术表达式的计算 4.5.1 算术表达式的两种表示v算术表达式是操作数（又叫运算对象）和运算符以及改变运算次序的括号（圆或方括号）所组成。v操作数可以是常量，变量和函数，同时还可以是另一个表达式。v而运算符可以是单目运算符和双目运算符。单目运算符只需一个操作数，双目运算符要求两个操作数，并被放在两个操作数的中间。v单目运算符有取正，取负，平方、开根等。而双目运算符有+、-、等。v双目运算符出现在两个操作数中间的这种习惯表示法叫做

23、算术表达式的中缀表示法（如 2+56）。这种算术表达式称为中缀表达式。v中缀表达式的计算必须遵守以下三条规则：(1)先计算括号内，后计算括号外；(2)在无括号或同层括号内，先进行乘除运算，后 进行加减运算，即乘除运算的优先级高于加减 运算的优先级；(3)同一优先级运算，从左向右依次进行。v运算符放在两个计算对象的后面的算式表示法叫做后缀表示法v在利用后缀表示法进行计算时，不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后次序来进行，整个计算过程只需前面的一个运算符的扫描排序过程。v采用后缀表示的计算表达式，可利用标准的计算程序来实现多种复杂的算术表达式的计算。例如，对于下列各中

24、缀表达式：(1)3/5+6 (2)16-9*(4+3)(3)2*(x+y)/(1-x)(4)(25+x)*(a*(a+b)+b)对应的后缀表达式分别为：(1)35/6+(2)16943+*-(3)2xy+*1x-/(4)25x+aab+*b+*4.5.2 后缀表达式求值的算法算法思想：1.利用堆栈对算式从头到尾进行扫描，来实现对算式的解释和计算。2.算式用一字符串来表示，并用空格来分隔各操作数和运算符3.在扫描时，遇到操作数就将其压入堆栈（如遇到小数点则将整个带小数点的数字转换为浮点数后再压入堆栈），直到遇到运算符4.在扫描时，遇到运算符，就将堆栈内的最上面的两个操作数弹出，并按其扫描到的运算

25、符进行计算。5.将计算结果存入一个结果变量中（如x)，并压入堆栈，以便作为后面运算的操作数6.依次向下扫描每一个字符直到遇到字符串结束符例子：假定有一个中缀算术表达式：(12+34)+(5/2)*2 该表达式用后缀表示法的表示字符串为：char*a=“12 34+5 2/+2*”;使用后缀表达式求值的算法计算后可得到与中缀表达式计算相同的结果值：97.v用后缀表示法进行求值过程中，其堆栈的变换如图所示：4.5.3 把中缀表达式转换为后缀表达式的算法算法思想：1.中缀表达式保存在字符串S1中，后缀表达式保存在S2中2.在转换过程中，设一保存运算符的堆栈，保存在扫描过程所遇到的运算符，3.在栈底放

26、一特殊字符（如），让它具有最低的运算符优先级，以便作为标志弹出运算符过程的结束符。4.在扫描时，遇到非运算符的数字时，将其直接添加到后缀表达式的字符串S2中，并加空格分隔符5.在扫描时，若遇到括号，则先将其左括号，压入堆栈保存，直到遇到右括号，则将左括号之后压入的运算符依次弹出并加入到S2中（每个运算符用空格符分隔），再将左括号弹出。6.在扫描时，若遇到运算符，则先与已压入堆栈并位于栈顶的运算符比较，若其优先级大于栈顶的运算符的优先级，表明该运算符的后一个运算对象还没有被扫描并放入到s2串中，应把它暂存于运算符栈中，待它的后一个运算对象从s1串中读出并写入到s2串中后，再另其出栈并写入s2串中

27、 7.若遇到的运算符的优先级小于等于栈顶运算符的优先级，这表明栈顶运算符的两个运算对象已经被保存到s2串中，应将栈顶运算符退栈并写入到s2串中。8.对于新的栈顶运算符仍继续进行比较和处理，直到被处理的运算符的优先级大于栈顶运算符的优先级为止，然后令该运算符进栈即可。9.扫描到s1串结束时，则弹出栈内的所有运算符加入到S2串中（除外）int precedence(char op)；/函数声明 void Change(char*s1,char*s2)/将字符串s1中的中缀表达式转换为s2字符串中的后缀表达式 /定义用于暂存运算符的栈R并初始化，该栈的元素类型为char Struct StackSq

28、 R;/定义 i,j分别用于扫描s1和指示s2串中相应字符的位置 int i=0,j=0;/定义ch保存s1串中扫描到的字符，初值为第一个字符 char ch=s1i;InitStack2(&R，5);/给栈底放入字符，它具有最低优先级0 Push(&R,);/依次处理中缀表达式中的每个字符 while(ch!=0)/对于空格字符不做任何处理，顺序读取下一个字符 if(ch=)ch=s1+i;/对于左括号，直接进栈 else if(ch=()Push(&R,ch);ch=s1+i;/对于右括号，使括号内的仍停留在栈中的运算符依次出栈并写入s2 else if(ch=)while(Peek(&R

29、)!=()s2j+=Pop(&R);Pop(&R);/删除栈顶的左括号 ch=s1+i;/对于四则运算符，使暂存栈顶不低于ch优先级的运算符依次出栈并写s2 else if(ch=+|ch=-|ch=*|ch=/)char w=Peek(&R);while(Precedence(w)=Precedence(ch)/Precedence(w)函数返回运算符形参的优先级 s2j+=w;Pop(&R);w=Peek(&R);Push(&R,ch);/把ch运算符写入栈中 ch=s1+i;/此处必然为数字或小数点字符，否则为中缀表达式错误 else /若ch不是数字或小数点字符则退出运行 if(ch9

30、)&ch!=.)printf(中缀表达式表示错误!n);exit(1);/把一个数值中的每一位依次写入到s2串中 while(ch=0&ch0)在这里n=0为递归终止条件，使函数返回1，n0实现递归调用，由n的值乘以f(n-1)的返回值求出f(n)的值。用C语言编写出求解n!的递归函数为：long f(int n)if(n=0)return 1;else return n*f(n-1);上述调用和返回过程可形象地用图4-5表示。图4-5 利用f(4)调用f(n)递归函数的执行流程 二、对有递归结构但没有直接递归定义的问题，可根据问题的二、对有递归结构但没有直接递归定义的问题，可根据问题的本身来

31、设计出递归程序本身来设计出递归程序例例4-5 求解迷宫问题 一个迷宫包含有m行n列个小方格，每个方格用0表示可通行，用1表示墙壁，即不可通行。迷宫中通常有一个入口和一个出口，设入口点的坐标为(1,1)，出口点的坐标为(m,n)，当然入口点和出口点的值应均为0，即均可通行。从迷宫中的某一个坐标位置向东、南、西、北任一方向移动一步（即一个方格）时，若前面的小方格为0，则可前进一步，否则通行受阻，不能前进，应按顺时针改变为下一个方向移动。求解迷宫问题是从入口点出发寻找一条通向出口点的路径，并打印出这条路径，即经过的每个小方格的坐标。如图4-7(a)是一个68的迷宫，入口点坐标为(1,1)，出口点坐标

32、为(6,8)，其中的一条路径为(1,1),(1,2),(2,2),(2,3),(3,3),(3,4),(3,5),(3,6),(4,6),(4,7),(5,7),(6,7),(6,8)。v为了判断从当从迷宫中的一个位置（称它为当前位置）前进到下一个位置时，下一个位置相对于当前位置的位移量（包括行位移量和列位移量），用一 个42的整型数组move来存储位移量数据，v在求解迷宫问题时，还需要使用一个与存储迷宫数据的maze数组同样大小的辅助数组mark，用它来标识迷宫中对应位置是否被访问过。该数组每个元素的初始值为0，表示迷宫中的所有位置均没有被访问过。每访问迷宫中一个可通行的位置时，都使mark

33、数组中对应元素置1，表示该位置已经被访问过，以后不会再访问到 行 列 东 南 西 北一步一试探，通则向前走，碰壁则回退另找通路一步一试探，通则向前走，碰壁则回退另找通路 回朔法回朔法 基本规律：依次按各方向寻找通路的下一个位置。基本规律：依次按各方向寻找通路的下一个位置。搜寻路径搜寻路径 ：若下个位置通且未试过，则前进一步，记录走过的位置与若下个位置通且未试过，则前进一步，记录走过的位置与 标志；标志；（归纳项）（归纳项）若下个试探位置不能走，对当前位置的下一个方向试若下个试探位置不能走，对当前位置的下一个方向试 探；探；若当前位置上各方向都无通路，退回到上一位置，继续若当前位置上各方向都无通

34、路，退回到上一位置，继续 试探。试探。终止搜寻：终止搜寻：试探位置到达出口，已走通，结束试探。试探位置到达出口，已走通，结束试探。（基本项）（基本项）已回退到入口处，未走通，结束试探已回退到入口处，未走通，结束试探 。由于每一个新的点的找路过程都重复上一个点的过程，因而形成了递由于每一个新的点的找路过程都重复上一个点的过程，因而形成了递归过程。归过程。int SeekPath(int x,int y)/*从迷宫中坐标点(x,y)的位置寻找通向终点(m,n)的路径，若找到则返回1，否则返回0，(x,y)的初始值通常为(1,1)*/*i作为循环变量，代表从当前位置移到下一个位置的方向*/int i

35、;/*g和h作为下一个位置的行坐标和列坐标*/int g,h;/*到达出口点返回1结束递归*/if(x=m)&(y=n)return 1;/*依次按每一个方向寻找通向终点的路径*/for(i=0;i 1 时：源柱时：源柱 中间柱中间柱 源柱源柱 目标柱目标柱 （归纳项）（归纳项）中间柱中间柱 目标柱目标柱 当当n=1 时时:直接搬移一个盘子（基本项）直接搬移一个盘子（基本项）当将中间柱的当将中间柱的n-1个盘子再移到目标柱时，又重复这个盘子再移到目标柱时，又重复这一过程，从而形成递归过程。一过程，从而形成递归过程。n-1个盘子个盘子第第n号盘子号盘子n-1个盘子个盘子移动盘子的基本规律（归纳）

36、：移动盘子的基本规律（归纳）：例如，当A柱上有3个圆盘，要求把它移动到C柱上，则需要以下3步完成：(1)把A柱上的2个圆盘移到过渡柱B上；(2)把A柱上剩下的1个圆盘直接移到目的柱C上；(3)把过渡柱B上的2个圆盘移到目的柱C上。对于第1步还需要递归完成，具体为以下3步：(1.1)把A柱上的1个圆盘直接移到此时的过渡柱C上；(1.2)把A柱上剩余的1个圆盘直接移到此时的目的柱B上；(1.3)把此时的过渡柱C上的1个圆盘直接移到此时的目的柱B上。对于第3步也需要递归完成，具体为以下3步：(3.1)把B柱上的1个圆盘直接移到此时的过渡柱A上；(3.2)把B柱上剩余的1个圆盘直接移到此时的目的柱C上

37、；(3.3)把此时的过渡柱A上的1个圆盘直接移到此时的目的柱C上。上述整个移动过程为7个直接步骤，依次为：AC;AB;CB;AC;BA;BC;AC 或用数字编号写为：13;12;32;13;21;23;13 根据以上分析，设把n个盘子由值参a所表示的柱子搬到由值参c所表示的柱子，用值参b所表示的柱子作为过渡，则编写出递归算法如下：void Hanoi(int n,int a,int b,int c)/*当只有一个盘子时，直接由a柱搬到c柱后结束一次调用*/if(n=1)printf(%d%d,a,c);/*当多于一个盘子时，向下递归*/else /*首先把n-1个盘子由值参a所表示的柱子搬到由

38、值参b所表示 的柱子上，用值参c所表示的柱子作为过渡*/Hanoi(n-1,a,c,b);/*把由值参a所表示的柱子上的最后一个盘子搬到由值参c所 表示的柱子上*/printf(%d%d,a,c);/*最后把n-1个盘子由值参b所表示的柱子搬到由值参c所表示 的柱子上，用值参a所表示的柱子作为过渡*/Hanoi(n-1,b,a,c);设调用函数返址为设调用函数返址为r r0 0 调用调用Hanoi(3,xHanoi(3,x0 0,y,y0 0,z,z0 0)时，递归栈中的状态变化：时，递归栈中的状态变化：进调用进调用(第一层第一层)进第二层调用进第二层调用 进第三层调用进第三层调用 返回第二层

39、返回第二层r0,3,x0,y0,z0r1,2,x0,z0,y0r0,3,x0,y0,z0r1,1,x0,y0,z0r1,2,x0,z0,y0r0,3,x0,y0,z0r1,2,x0,z0,y0r0,3,x0,y0,z0进入一层递归调用时进入一层递归调用时,该层参数入栈该层参数入栈(记录记录)；退出一层递归调用时退出一层递归调用时,栈顶参数出栈。栈顶参数出栈。归纳项归纳项重复调用的基本操作。重复调用的基本操作。递归算法递归算法 基本项基本项重复调用停止的条件。重复调用停止的条件。设计步骤：设计步骤：分析问题，归纳出解决问题的基本规律（基本操作）。分析问题，归纳出解决问题的基本规律（基本操作）。根

40、据问题性质和已知条件确定基本项。根据问题性质和已知条件确定基本项。分析重复调用在什么条件下终止分析重复调用在什么条件下终止确定递归边界，确定递归边界，确定递归调用参数，写出递归调用形式。确定递归调用参数，写出递归调用形式。递归调用的已知条件能传递给下层，得到的结果传递归调用的已知条件能传递给下层，得到的结果传 递给上一层；使每一层递归都向终止条件前进。递给上一层；使每一层递归都向终止条件前进。4.7 队列4.7.1 队列的定义v队列队列（queue）简称队队，它也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。v我们把进行插入的一端称作队尾队尾(rear)，进

41、行删除的一端称作队首队首(front)。向队列中插入新元素称为进进队队或入队入队，新元素进队后就成为新的队尾元素；从队列中删除元素称为离队离队或出队出队，元素离队后，其后继元素就成为队首元素。v由于队列的插入和删除操作分别是在各自的一端进行的，每个元素必然按照进入的次序离队，所以又把队列称为先进先出表先进先出表（first in first out,简称FIFO）。队列所针对问题：按先后顺序处理队列所针对问题：按先后顺序处理(先到先服务先到先服务)队列的例子队列的例子：生活中的排队、打印队列、作业队列等。：生活中的排队、打印队列、作业队列等。假定有假定有a,b,c,d四个元素依次进队，则得到的

42、队列为四个元素依次进队，则得到的队列为(a,b,c,d)，其中字符，其中字符a为队首元素，字符为队首元素，字符d为队尾元素。若从此为队尾元素。若从此队中删除一个元素，此队列变为队中删除一个元素，此队列变为(b,c,d)；若接着向该队列插入；若接着向该队列插入一个字符一个字符e，则，则e成为新的队尾元素，此队列变为成为新的队尾元素，此队列变为(b,c,d,e)；若；若接着做三次删除操作，则队列变为接着做三次删除操作，则队列变为(e)，此时只有一个元素，此时只有一个元素e，它既是队首元素又是队尾元素，当它被删除后队列变为空。它既是队首元素又是队尾元素，当它被删除后队列变为空。4.7.2 队列的运算

43、概述队列的运算概述 (1)初始化队列初始化队列Q，即置，即置Q为空为空 void InitQueue(Q);(2)将新元素将新元素x的值插入到队尾的值插入到队尾 void EnQueue(Q,ElemType x);(3)从队列中删除队首元素并返回之从队列中删除队首元素并返回之 ElemType OutQueue(Q);(4)返回队首元素，但不改变队列状态返回队首元素，但不改变队列状态 ElemType PeekQueue(Q);(5)判断队列是否为空，若是则返回判断队列是否为空，若是则返回1，否则返回，否则返回0 int EmptyQueue(Q);(6)清除队列清除队列Q中的所有元素，使之

44、成为一个空队中的所有元素，使之成为一个空队 void ClearQueue(Q);4.7.3 队列的顺序存储结构和操作实现 v采用顺序存储结构的队列是指其队列的主体依照其逻辑上的顺序依次存储在地址上连续的存储区域内。v队列的顺序存储结构可由一个数组和两至三个整形变量来实现。即 存储队列主体的数组、队首指针变量、队尾指针变量和队列的长度变量（如果使用的话）v队首指针：指向队首元素前一个位置的变量称为队首指针，由它加1就得到队首元素的坐标v队尾指针：指向队尾元素位置的变量称为队尾指针。a0a2a3anfront rear设定设定:队首指针队首指针 front 指向队头元素的前一个位置；指向队头元素

45、的前一个位置；元素退队，元素退队，front后移。后移。队尾指针队尾指针 rear 指向队尾元素位置；指向队尾元素位置；元素入队元素入队 rear 后移。后移。顺序队列顺序队列队列的顺序存储结构：队列的顺序存储结构：例例:0 1 2 n一般顺序队列存在的问题：假溢出。一般顺序队列存在的问题：假溢出。假溢出假溢出入队运算时，其队尾指针已达到所申请的存储区的入队运算时，其队尾指针已达到所申请的存储区的 末端末端,但队列中有空闲单元但队列中有空闲单元,即即:rear=Maxsize:rear=Maxsize 但但 rear-frontMaxsize-1rear-frontMaxSize=10;/*动

46、态存储空间分配*/Q-queue=malloc(10*sizeof(ElemType);/*置队列为空*/Q-front=Q-rear=0;第二种情况是分配由参数指定大小的动态存储空间。实用中使用任一种初始化算法均可。void InitQueue(struct QueueSq*Q,int ms)/*检查ms是否有效，若无效则退出运行*/if(msMaxSize=ms;/*动态存储空间分配，若分配失败则退出运行*/Q-queue=malloc(ms*sizeof(ElemType);if(!Q-queue)printf(内存空间用完!n);exit(1);/*初始置队列为空*/Q-front=Q

47、-rear=0;2.向队列插入元素向队列插入元素 void EnQueue(struct QueueSq*Q,ElemType x)/*当队列满时进行动态重分配*/if(Q-rear+1)%Q-MaxSize=Q-front)againMalloc(Q);/*求出队尾的下一个位置*/Q-rear=(Q-rear+1)%Q-MaxSize;/*把item的值赋给新的队尾位置*/Q-queueQ-rear=x;againMalloc()算法的具体定义如下：void againMalloc(struct QueueSq*Q)/*空间扩展为原来的2倍，并由p所指向，原内容被自动拷贝到p所指向的存储空间

48、中*/ElemType*p;p=realloc(Q-queue,2*Q-MaxSize*sizeof(ElemType);if(!p)/*分配失败退出运行*/printf(存储空间用完!n);exit(1);/*使queue指向新的队列空间*/Q-queue=p;/*把原队列的尾部内容向后移动MaxSize个位置*/if(Q-rear!=Q-MaxSize-1)int i;for(i=0;irear;i+)Q-queuei+Q-MaxSize=Q-queuei;Q-rear+=Q-MaxSize;/*队尾指针后移MaxSize个位置*/*把队列空间大小修改为新的长度*/Q-MaxSize=2*

49、Q-MaxSize;3.从队列中删除元素并返回从队列中删除元素并返回 ElemType OutQueue(struct QueueSq*Q)/*若队列为空则终止运行*/if(Q-front=Q-rear)printf(队列已空，无法删除!n);exit(1);/*使队首指针指向下一个位置*/Q-front=(Q-front+1)%Q-MaxSize;/*返回队首元素*/return Q-queueQ-front;4.7.3 队列的链接存储结构和操作实现队列的链接存储结构和操作实现 v队列的链接存储结构也是通过由结点构成的单链表实现的，此时只允许在单链表的表头进行删除和在单链表的表尾进行插入，因

50、此它需要使用两个指针：队首指针front和队尾指针rear。vfront指向队首结点的存储位置，rear指向队尾结点的存储位置。v用于存储队列的单链表简称链接队列链接队列或链队链队。采用链接存储结构的队列中数据节点的定义：struct QueueLk sNode*front;/队首指针 sNode*rear;/队尾指针 ;其中sNode结点类型重写如下：struct sNode ElemType data;/*值域*/struct sNode*next;/*链接指针域*/;v 一个链接存储的队列如下图所示。.frontreara1a2an在类型为QueueLk的链队HQ上进行队列的各种操作的算