零基础学数据结构第4章栈.ppt

《零基础学数据结构第4章栈.ppt》由会员分享，可在线阅读，更多相关《零基础学数据结构第4章栈.ppt（68页珍藏版）》请在三一文库上搜索。

1、第4章 栈,栈是一种操作受限的线性表。栈具有线性表的结构特点，即每一个元素只有一个前驱元素和后继元素（除了第一个元素和最后一个元素外），但它只允许在表的一端进行插入和删除操作。 本章重点和难点： 1、栈的顺序表示与算法实现 2、栈的链式表示与算法实现 3、求算术表达式的值 4、迷宫求解问题 5、递归的消除,4.1 栈的定义与抽象数据类型,4.1.1 什么是栈 栈（stack），也称为堆栈，它是限定仅在表尾进行插入和删除操作的线性表。对栈来说，表尾（允许操作的一端）称为栈顶（top），另一端称为栈底（bottom）。栈顶是动态变化的，它由一个称为栈顶指针（top）的变量指示。当表中没有元素时，称

2、为空栈。 栈的插入操作称为入栈或进栈，删除操作称为出栈或退栈。,4.1 栈的定义与抽象数据类型,在栈S=(a1,a2,an)中，a1称为栈底元素，an称为栈顶元素，由栈顶指针top指示。栈中的元素按照a1，a2，an的顺序进栈，当前的栈顶元素为an。如图4.1所示。最先进栈的元素一定是栈底元素，最后进栈的元素一定是栈顶元素。每次删除的元素是栈顶元素，也就是最后进栈的元素。因此，栈是一种后进先出（last in first out，简称LIFO）的线性表。,4.1 栈的定义与抽象数据类型,若将元素a、b、c和d依次入栈，最后将栈顶元素出栈，栈顶指针top的变化情况如图4.2所示。,4.1 栈的定

3、义与抽象数据类型,4.1.2 栈的抽象数据类型 1数据对象集合 栈的数据对象集合为a1，a2，an，每个元素都有相同的类型DataType。 栈中数据元素之间是一对一的关系。栈具有线性表的特点：除了第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。,4.1 栈的定义与抽象数据类型,2基本操作集合 （1）InitStack(&S)：初始化操作，建立一个空栈S。 （2）StackEmpty(S)：若栈S为空，返回1，否则返回0。 （3）GetTop(S,&e)：返回栈S的栈顶元素给e。 （4）PushStack(&S,e)：在栈S中插

4、入元素e，使其成为新的栈顶元素。 （5）PopStack(&S,&e)：删除栈S的栈顶元素，并用e返回其值。 （6）StackLength(S)：返回栈S的元素个数。 （7）ClearStack(S)：清空栈S。,4.2 栈的顺序表示与实现,4.2.1 栈的顺序存储结构 采用顺序存储结构的栈称为顺序栈。顺序栈是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，可利用C语言中的数组作为顺序栈的存储结构，同时附设一个栈顶指针top，用于指向顺序栈的栈顶元素。当top=0时表示空栈。 栈的顺序存储结构类型描述如下： #define StackSize 100 typedef struct D

5、ataType stackStackSize; int top; SeqStack;,4.2 栈的顺序表示与实现,当栈中元素已经有StackSize个时，称为栈满。如果继续进栈操作则会产生溢出，称为上溢。对空栈进行删除操作，称为下溢。 顺序栈的结构如图4.3所示。元素a、b、c、d、e、f、g、h依次进栈后，a为栈底元素，h为栈顶元素。在实际操作中，栈顶指针指向栈顶元素的下一个位置。 顺序栈涉及的一些基本操作如下： （1）在初始化栈时，将栈顶指针置为0，即令S.top=0。 （2）判断栈空条件为S.top=0，栈满条件为S.top=StackSize-1。 （3）栈的长度（即栈中元素个数）为S

6、.top。 （4）进栈操作时，先判断栈是否已满，若未满，将元素压入栈中，即S.stackS.top=e，然后使栈顶指针加1，即S.top+。出栈操作时，先判断栈是否为空，若为空，使栈顶指针减1，即S.top-，然后元素出栈，即e=S.stackS.top。,4.2 栈的顺序表示与实现,4.2.2 顺序栈的基本运算 （1）初始化栈。 void InitStack(SeqStack *S) /*初始化栈*/ S-top=0; /*把栈顶指针置为0*/ （2）判断栈是否为空。 int StackEmpty(SeqStack S) /*判断栈是否为空，栈为空返回1，否则返回0*/ if(S.top=0

7、) /*如果栈顶指针top为0*/ return 1; /*返回1*/ else /*否则*/ return 0; /*返回0*/ ,4.2 栈的顺序表示与实现,（3）取栈顶元素。 int GetTop(SeqStack S, DataType *e) if(S.top=0) /*如果栈为空*/ printf(“栈已经空!n”); return 0; else /*否则*/ *e=S.stackS.top-1; /*在取栈顶元素*/ return 1; ,4.2 栈的顺序表示与实现,（4）将元素e入栈。 int PushStack(SeqStack *S,DataType e) /*将元素e进

8、栈，元素进栈成功返回1，否则返回0.*/ if(S-top=StackSize) /*如果栈已满*/ printf(“栈已满，不能将元素进栈！n”); return 0; else /*否则*/ S-stackS-top=e; /*元素e进栈*/ S-top+; /*修改栈顶指针*/ return 1; ,4.2 栈的顺序表示与实现,（5）将栈顶元素出栈。 int PopStack(SeqStack *S,DataType *e) if(S-top=0) /*如果栈为空*/ printf(“栈中已经没有元素，不能进行出栈操作!n”); return 0; else /*否则*/ S-top-;

9、 /*先修改栈顶指针，即出栈*/ *e=S-stackS-top; /*将出栈元素赋给e*/ return 1; ,4.2 栈的顺序表示与实现,（6）求栈的长度。 int StackLength(SeqStack S) /*求栈的长度*/ return S.top; （7）清空栈。 void ClearStack(SeqStack *S) /*清空栈*/ S-top=0; /*将栈顶指针置为0*/ ,4.2 栈的顺序表示与实现,4.2.3 顺序栈应用举例 【例4_1】利用顺序栈的基本操作，将元素A、B、C、D、E、F依次进栈，然后将F和E出栈，再将G和H进栈，最后将元素全部出栈，并依次输出出栈

10、元素。,4.2 栈的顺序表示与实现,【例4_2】有两个栈S1和S2都采用顺序结构存储，并且共享一个存储区。为了尽可能利用存储空间，减少溢出的可能，采用栈顶相向，迎面增长的方式，试设计S1和S2有关入栈和出栈算法。 【分析】该题是哈尔滨工业大学的考研试题，主要考察共享栈的算法设计。 1什么是栈的共享 在使用顺序栈时，因为栈空间的大小难以准确估计，可能会出现有的栈还有空闲空间。为了能充分利用栈的空间，可以让多个栈共享一个足够大的连续存储空间，通过利用栈顶指针能灵活移动的特性，使多个栈存储空间互相补充，存储空间得到有效利用，这就是栈的共享。,4.2 栈的顺序表示与实现,共享栈的数据结构类型描述如下。

11、 typedef struct DataType stackStackSize; int top2; SSeqStack; 其中，top0和top1分别是两个栈的栈顶指针。 用一维数组表示的共享栈如图4.5所示。,4.2 栈的顺序表示与实现,2共享栈的基本运算 （1）初始化栈。 void InitStack(SSeqStack *S) /*共享栈的初始化*/ S-top0=0; S-top1=StackSize-1; ,4.2 栈的顺序表示与实现,（2）取栈顶元素。 int GetTop(SSeqStack S, DataType *e,int flag) /*取栈顶元素。将栈顶元素值返回给e

12、，并返回1表示成功；否则返回0表示失败。*/ switch(flag) case 1: /*为1，表示要取左端栈的栈顶元素*/ if(S.top0=0) return 0; *e=S.stackS.top0-1; break; case 2: /*为2，表示要取右端栈的栈顶元素*/ if(S.top1=StackSize-1) return 0; *e=S.stackS.top1+1; break; default: return 0; return 1; ,4.2 栈的顺序表示与实现,（3）将元素e入栈。 int PushStack(SSeqStack *S,DataType e,int f

13、lag) /*将元素e入共享栈。进栈成功返回1，否则返回0*/ if(S-top0=S-top1) /*如果共享栈已满*/ return 0; /*返回0，进栈失败*/ switch(flag) case 1: /*当flag为1，表示将元素进左端的栈*/ S-stackS-top0=e; /*元素进栈*/ S-top0+; /*修改栈顶指针*/ break; case 2: /*当flag为2，表示将元素要进右端的栈*/ S-stackS-top1=e; /*元素进栈*/ S-top1-; /*修改栈顶指针*/ break; default: return 0; return 1; /*返回

14、1，进栈成功*/ ,4.2 栈的顺序表示与实现,（4）将栈顶元素出栈。 int PopStack(SSeqStack *S,DataType *e,int flag) switch(flag) /*在出栈操作之前，判断哪个栈要进行出栈操作*/ case 1: /*为1，表示左端的栈需要出栈操作*/ if(S-top0=0) /*左端的栈为空*/ return 0; /*返回0，出栈操作失败*/ S-top0-; /*修改栈顶指针，元素出栈操作*/ *e=S-stackS-top0; /*将出栈的元素赋给e*/ break; case 2: /*为2，表示右端的栈需要出栈操作*/ if(S-to

15、p1=StackSize-1) /*右端的栈为空*/ return 0; /*返回0，出栈操作失败*/ S-top1+; /*修改栈顶指针，元素出栈操作*/ *e=S-stackS-top1; /*将出栈的元素赋给e*/ break; default: return 0; return 1; /*返回1，出栈操作成功*/ ,4.2 栈的顺序表示与实现,（5）判断栈是否为空。 int StackEmpty(SSeqStack S,int flag) switch(flag) case 1: /*为1，表示判断左端的栈是否为空*/ if(S.top0=0) return 1; break; cas

16、e 2: /*为2，表示判断右端的栈是否为空*/ if(S.top1=StackSize-1) return 1; break; default: printf(“输入的flag参数错误!”); return -1; return 0; ,4.3 栈的链式表示与实现,在顺序栈中，由于顺序存储结构需要事先静态分配，而存储规模往往又难以确定，如果栈空间分配过小，可能会造成溢出；如果栈空间分配过大，又造成存储空间浪费。 4.3.1 栈的存储结构 栈的链式存储结构是用一组不一定连续的存储单元来存放栈中的数据元素的。一般来说，当栈中数据元素的数目变化较大或不确定时，使用链式存储结构作为栈的存储结构是比较

17、合适的。人们将用链式存储结构表示的栈称为链栈或链式栈。,4.3 栈的链式表示与实现,链栈通常用单链表表示。插入和删除操作都在栈顶指针的位置进行，这一端称为栈顶，通常由栈顶指针top指示。为了操作上的方便，通常在链栈中设置一个头结点，用栈顶指针top指向头结点，头结点的指针指向链栈的第一个结点。例如，元素a、b、c、d依次入栈的链栈如图4.7所示。,4.3 栈的链式表示与实现,栈顶指针top始终指向头结点，最先入栈的元素在链栈的栈底，最后入栈的元素成为栈顶元素。由于链栈的操作都是在链表的表头位置进行，因而链栈的基本操作的时间复杂度均为O(1)。 链栈的结点类型描述如下： typedef stru

18、ct node DataType data; struct node *next; LStackNode,*LinkStack;,4.3 栈的链式表示与实现,4.3.2 链栈的基本运算 （1）初始化链栈。 void InitStack(LinkStack *top) /*链栈的初始化*/ if(*top=(LinkStack)malloc(sizeof(LStackNode)=NULL) exit(-1); (*top)-next=NULL;/*将链栈的头结点指针域置为空*/ ,4.3 栈的链式表示与实现,（2）判断链栈是否为空。 int StackEmpty(LinkStack top) /

19、*判断链栈是否为空*/ if(top-next=NULL) /*如果头结点的指针域为空*/ return 1; /*返回1*/ else /*否则*/ return 0; /*返回0*/ ,4.3 栈的链式表示与实现,（3）将元素e入栈。先动态生成一个结点，用p指向该结点，将元素e值赋给*p结点的数据域，然后将新结点插入到链表的第一个结点之前。把新结点插入到链表中分为两个步骤：p-next=top-next；top-next=p。进栈操作如图4.8所示。,4.3 栈的链式表示与实现,将元素e入栈的算法实现如下。 int PushStack(LinkStack top, DataType e)

20、LStackNode *p; /*定义指针p，指向新生成的结点*/ if(p=(LStackNode*)malloc(sizeof(LStackNode)=NULL) printf(“内存分配失败!”); exit(-1); p-data=e; /*将e赋给p指向的结点数据域*/ p-next=top-next; /*指针p指向头结点*/ top-next=p; /*栈顶结点的指针域指向新插入的结点*/ return 1; ,4.3 栈的链式表示与实现,（4）将栈顶元素出栈。先判断栈是否为空，如果栈为空，返回0表示出栈操作失败；否则，将栈顶元素出栈，并将栈顶元素值赋给e，最后释放结点空间，返回

21、1表示出栈操作成功。出栈操作如图4.9所示。,4.3 栈的链式表示与实现,将栈顶元素出栈的算法实现如下。 int PopStack(LinkStack top,DataType *e) LStackNode *p; p=top-next; if(!p) /*判断链栈是否为空*/ printf(“栈已空”); return 0; top-next=p-next; /*将栈顶结点与链表断开，即出栈*/ *e=p-data; /*将出栈元素赋值给e*/ free(p); /*释放p指向的结点*/ return 1; ,（5）取栈顶元素。 int GetTop(LinkStack top,DataTy

22、pe *e) /*取栈顶元素。取栈顶元素成功返回1，否则返回0*/ LStackNode *p; p=top-next; /*指针p指向栈顶结点*/ if(!p) /*如果栈为空*/ printf(“栈已空”); return 0; *e=p-data; /*将p指向的结点元素赋值给e*/ return 1; ,4.3 栈的链式表示与实现,4.3 栈的链式表示与实现,6）求栈的长度。 int StackLength(LinkStack top) LStackNode *p; int count=0; /*定义一个计数器，并初始化为0*/ p=top; /*p指向栈顶指针*/ while(p-n

23、ext!=NULL) /*如果栈中还有结点*/ p=p-next; /*依次访问栈中的结点*/ count+; /*每次找到一个结点，计数器累加1*/ return count; /*返回栈的长度*/ ,4.3 栈的链式表示与实现,（7）销毁链栈。 void DestroyStack(LinkStack top) LStackNode *p,*q; p=top; while(!p) /*如果栈还有结点*/ q=p; /*q就是要释放的结点*/ p=p-next; /*p指向下一个结点，即下一次要释放的结点*/ free(q); /*释放q指向的结点空间*/ ,4.3.3 链栈应用举例 【例4_

24、3】利用链表模拟栈实现将十进制数5678转换为对应的八进制数。 【分析】进制转换是计算机实现计算的基本问题。根据我们掌握的C语言知识，我们可以采用辗转相除法实现将十进制数转换为八进制数。将5678转换为八进制数的过程如图4.10所示。,4.3 栈的链式表示与实现,转换后的八进制数为(13056)8。通过观察图4.10的转换过程不难看出，每次不断利用被除数除以8得到商数后，记下余数，又将商数作为新的被除数继续除以8，直到商数为0为止，把得到的余数排列起来就是转换后的八进制数。依据此原理，得到十进制数N转换为八进制的算法如下： （1）将N除以8，记下其余数； （2）判断商是否为零，如果为零，结束程

25、序；否则，将商送N，转到（1）继续执行。 得到的位序正好与八进制数的位序相反，这恰好可利用栈的“后进先出”特性，先把得到的余数序列放入栈保存，最后依次出栈得到八进制数。,4.3 栈的链式表示与实现,4.4.1 括号匹配 在计算机中，常见的括号有3种：花括号、方括号和圆括号。和、和、(和)分别是匹配的括号，括号的嵌套顺序是任意的，即()和()等为正确的格式，、()和()等为不正确的格式。例如，有括号序列如图4.12所示。 不难看出，括号匹配的处理过程符合栈的后进先出的特点。因此，解决括号匹配问题可以利用栈来实现，设置一个栈，依次读入括号序列。如果读入的是左括号，则进栈；若是右括号，则与栈顶的括号

26、进行比较，是否匹配，如果匹配，则栈顶的括号出栈。如果栈不空，并且此时的括号不匹配，则说明整个括号序列不匹配。当括号序列读入完毕，且栈为空时，说明整个括号序列是匹配的。,4.4 栈的典型应用,【例4_4】任意给定一个数学表达式如5*(9-2)-15-(8-3)/2+3*(6-4)，试设计一个算法判断表达式的括号是否匹配。 【分析】检验括号是否匹配可以设置一个栈，每读入一个括号，如果是左括号，则直接进栈。 （1）如果读入的是右括号且与当前栈顶的左括号是同类型的，说明这一对括号是匹配的，则将栈顶的左括号出栈，否则是不匹配。 且栈已经为空，说明缺少左括号，该括号序列不匹配。 （2）如果输入序列已经读完

27、，而栈中仍然有等待匹配的左括号，说明缺少右括号，该括号序列不匹配。 （3）如果读入是数字字符，则不进行处理，直接读入下一个字符。,4.4 栈的典型应用,4.4.2 求算术表达式的值 表达式求值是程序设计编译中的基本问题，它的实现是栈应用的一个典型例子。本节给大家介绍一种简单并广为使用的算法，被称之为算符优先法。计算机编译系统利用栈的“后进先出”特性把人们便于理解的表达式翻译成计算机能够正确理解的表示序列。 一个算术表达式是由操作数、运算符和分界符组成。为了简化问题，我们假设算术运算符仅由加、减、乘、除四种运算符和左、右圆括号组成。,4.4 栈的典型应用,例如，一个算术表达式为 6+(7-1)*

28、3+10/2 这种算术表达式中的运算符总是出现在两个操作数之间，这种算术表达式被称为中缀表达式。计算机编译系统在计算一个算术表达式之前，要将中缀表达式转换为后缀表达式，然后对后缀表达式进行计算。后缀表达式就是算术运算符出现在操作数之后，并且不含括号。 计算机在求算术表达式的值时分为两个步骤： （1）将中缀表达式转换为后缀表达式； （2）依据后缀表达式计算表达式的值。,4.4 栈的典型应用,1将中缀表达式转换为后缀表达式 要将一个算术表达式的中缀形式转化为相应的后缀形式，首先了解下算术四则运算的规则。算术四则运算的规则是： （1）先乘除，后加减； （3）同级别的运算从左到右进行计算； （2）先括

29、号内，后括号外。 上面的算术表达式转换为后缀表达式为： 6 7 1 3 * + 10 2 / +,4.4 栈的典型应用,转换后的后缀表达式具有以下两个特点： （1）后缀表达式与中缀表达式的操作数出现顺序相同，只是运算符先后顺序改变了； （2）后缀表达式不出现括号。 正因为后缀表达式的以上特点，所以编译系统不必考虑运算符的优先关系。仅需要从左到右依次扫描后缀表达式的各个字符，遇到运算符时，直接对运算符前面的两个操作数进行运算即可。,4.4 栈的典型应用,如何将中缀表达式转换为后缀表达式呢？ 我们约定#作为后缀表达式的结束标志，假设1为栈顶运算符，2为当前扫描的运算符。则中缀表达式转换为后缀表达式

30、的算法描述如下： （1）初始化栈，并将#入栈； （2）若当前读入的字符是操作数，则将该操作数输出，并读入下一字符； （3）若当前字符是运算符，记作2，则将2与栈顶的运算符1比较。若1优先级低于2，则将2进栈；若1优先级高于2，则将1出栈并将其作为后缀表达式输出。然后继续比较新的栈顶运算符1与当前运算符2的优先级，若1的优先级与2相等，且1为(，2为)，则将1出栈，继续读入下一个字符； （4）如果2的优先级与1相等，且1和2都为#，将1出栈，栈为空。则完成中缀表达式转换为后缀表达式，算法结束。,4.4 栈的典型应用,运算符的优先关系如表4.1所示。 表4.1 运算符的优先关系,4.4 栈的典型应

31、用,初始化一个空栈，用来对运算符进行出栈和入栈操作。中缀表达式6+(7-1)*3+10/2#转换为后缀表达式的具体过程如图4.14所示（为了便于描述，在要转换表达式的末尾加一个#作为结束标记）。,4.4 栈的典型应用,4.4 栈的典型应用,2求后缀表达式的值 将中缀表达式转换为后缀表达式后，就可以计算利用后缀表达式的值了。计算后缀表达式的值的规则如下：依次读入后缀表达式中的每个字符，如果是操作数，则将操作数进入栈；如果是运算符，则将处于栈顶的两个操作数出栈，然后利用当前运算符进行运算，将运行结果入栈，直到整个表达式处理完毕。 利用上述规则，后缀表达式的6 7 1 3 * + 10 / +的值的

32、运算过程如图4.15所示。,4.4 栈的典型应用,4.4 栈的典型应用,4.4 栈的典型应用,3算法实现 【例4_5】通过键盘输入一个表达式，如6+(7-1)*3+10/2，要求将其转换为后缀表达式，并计算该表达式的值。 中缀表达式6+(7-1)*3+10/2#转换为后缀表达式的处理流程如图4.16所示。,4.4 栈的典型应用,4.4.3 迷宫求解 通常采用穷举法即从入口出发，顺某一个方向向前探索，若能走通，则继续往前走；否则沿原路返回，换另一个方向继续探索，直到探索到出口为止。为了保证在任何位置都能原路返回，显然需要用一个后进先出的栈来保存从入口到当前位置的路径。 图中的空白方块为通道，带阴

33、影的方块为墙。,4.4 栈的典型应用,所谓下一位置指的是当前位置四周（东、南、西、北）4个方向上相邻的方块。假设入口位置为(1,1)，出口位置为(8,8)，根据以上算法搜索出来的一条路径如图4.18所示。,4.4 栈的典型应用,【例4_6】在图4.17所示的迷宫中，编写算法求一条从入口到出口的路径。 在程序的实现中，定义墙元素值为0，可通过路径为1，不能通过路径为-1。完整的求解迷宫程序如下。,4.5 栈与递归,4.5.1 递归 我们先来看一个经典的递归例子：斐波那契数列，对于学过C语言的同学来说，这个数列应该不陌生。 1。斐波那契数列 如果兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生

34、出一对兔子，假设所有兔子都不死，那么一年以后可以繁殖多少对兔子呢？,4.5 栈与递归,我们不妨拿新出生的一对小兔子来分析下。第一、二个月小兔子没有繁殖能力，所以还是一对；两个月后，生下一对小兔子，小兔子数共有2对兔子；三个月后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是3对兔子；依次类推，可以得出下表（表4.1所示）。 表4.1 每个月兔子的对数,4.5 栈与递归,从表4.1中不难看出，数字1、1、2、3、5、8构成了一个数列，这个数列有个十分明显的特征：前面相邻两项之和构成后一项。可用数学函数表示为：,4.5 栈与递归,如果要打印出斐波那契数列的前40项，用常规的迭代方法怎样实现

35、呢？代码如下： void main( ) int i,a40; a0=0; a1=1; printf(“%4d”,a0); printf(“%4d”,a1); for(i=2;i40;i+) ai=ai-1+ai-2; printf(“%4d”,ai); ,4.5 栈与递归,以上代码比较简单，不用过多解释，如果用递归实现，代码会更加简洁。 int Fib (int n) if(n=0) return 0; else if(n=1) return 1; else return Fib(n-1)+Fib(n-2); void main() int i; for(i=0;i40;i+) printf

36、(“%4d”,Fib(i); ,4.5 栈与递归,例如，当n=4时，代码执行过程如图4.20所示。,4.5 栈与递归,2。什么是递归函数 如果一个函数在函数体中直接调用自己，称为直接递归函数。如果 经过一系列的中间调用，间接调用自己的函数称为间接递归函数。 例如，n的阶乘的递归定义如下： n的阶乘递归函数C语言实现如下： int fact(int n) if(n=1) return 1; else n*fact(n-1); ,4.5 栈与递归,Ackermann函数定义如下： Ackerman递归函数C语言实现如下： int Ack(int m,int n) if(m=0) return n+

37、1; else if(n=0) return Ack(m-1,1); else return Ack(m-1,Ack(m,n-1); ,4.5 栈与递归,3。分析递归调用过程 递归问题可以被分解成规模小、性质相同的问题加以解决。在今后将要学习的广义表、二叉树等都具有递归的性质，它们的操作可以用递归实现。 n阶汉诺塔问题。假设有3个塔座A、B、C，在塔座A上放置有n个直径大小各不相同、从小到大编号为1，2，n的圆盘，如图4.21所示。要求将A轴上的n个圆盘移动到塔座C上并要求按照同样的叠放顺序排列，圆盘移动时必须遵循以下规则： （1）每次只能移动一个圆盘； （2）圆盘可以放置在A、B和C中的任何

38、一个塔座； （3）任何时候都不能将一个较大的圆盘放在较小的圆盘上。,4.5 栈与递归,如何实现将放在A上的圆盘按照规则移动到C上呢？当n=1时，直接将编号为1的圆盘从塔座A移动到C上即可。当n1时，需利用塔座B作为辅助塔座，先将放置在编号为n之上的n-1个圆盘从塔座A上移动到B上，然后将编号为n的圆盘从塔座A移动到C上，最后将塔座B上的n-1个圆盘移动到塔座C上。那现在将n-1个圆盘从一个塔座移动到另一个塔座又成为与原问题类似的问题，只是规模减小了1，故可用同样的方法解决。,4.5 栈与递归,void Hanoi(int n,char a,char b,char c) /*将塔座A上按照从小到

39、大自上而下编号为1到n的那个圆盘按照规则搬到塔座C上，B可以作为辅助塔座*/ if(n=1) Move(a,1,c); /*将编号为1的圆盘从A移动到C*/ else Hanoi(n-1,a,c,b); /*将编号为1到n-1的圆盘从A移动到B，C作为辅助塔座*/ Move(a,n,c); /*将编号为n的圆盘从A移动到C*/ Hanoi(n-1,b,a,c); /*将编号为1到n-1的圆盘从B移动到C，A作为辅助塔座*/ ,4.5 栈与递归,下面以n=3，观察一下汉诺塔递归调用的具体过程。,4.5 栈与递归,递归的实现本质上就是把嵌套调用变成栈实现。在递归调用过程中，被调用函数在执行前系统要

40、完成3件事情： （1）将所有参数和返回地址传递给被调用函数保存； （2）为被调用函数的局部变量分配存储空间； （3）将控制转到被调用函数的入口。 当被调用函数执行完毕，返回给调用函数前，系统同样需要完成3个任务： （1）保存被调用函数的执行结果； （2）释放被调用函数的数据存储区； （3）将控制转到调用函数的返回地址处。,4.5 栈与递归,4.5.2 消除递归 用递归编写的程序结构清晰，算法也容易实现，读算法的人也容易理解，但递归算法的执行效率比较低，这是因为递归需要反复入栈，时间和空间都比较开销大。 为了避免这种开销，我们需要消除递归，消除递归方法通常有两种，一种是对于简单的递归可以直接用迭

41、代，通过循环结构就可以消除；另一种方法是利用栈的方式实现。,4.5 栈与递归,【例4_7】编写求n的阶乘的递归算法与利用栈实现的非递归算法。 【分析】通过利用栈模拟在n的阶乘递归实现中，递归过程中的工作记录的进栈过程与出栈过程，实现非递归算法的实现。定义一个二维数组，数组的第一维用于存放本层参数n，第二维用于存放本层要返回的结果。 当n=3时，递归调用过程如图4.27所示。,4.5 栈与递归,在递归函数调用的过程中，各参数入栈情况如图4.28所示。为便于描述，我们用f代替fact表示函数。 当n=1时，递归调用开始逐层返回，参数开始出栈，如图4.29所示。,4.6 小结,栈是一种只允许在线性表的一端进行插入和删除操作的线性表。 与线性表类似，栈也有两种存储方式：顺序存储和链式存储。采用顺序存储结构的栈称为顺序栈，采用链式存储结构的栈称为链栈。 递归的调用过程也是系统借助栈的特性实现的。因此，可利用栈模拟递归调用过程，可以设置一个栈，用于存储每一层递归调用的信息，包括实际参数、局部变量及上一层的返回地址等。每进入一层，将工作记录压入栈顶。每退出一层，将栈顶的工作记录弹出。这样就可以将递归转化为非递归，从而消除了递归。,