栈和队列课件

第三章栈和队列栈栈的存储结构及应用队列队列的存储结构及应用第三章栈和队列栈栈的基本概念定义数据元素之间是一对一的关系顺序存储或链式存储只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则存储结构运算规则逻辑结构只能在表的一端进行插入和删除的线性表基本操作建栈、判断栈满或栈空、入栈、出栈、取栈顶元素值栈的基本概念定义数据元素之间是一对一的关系顺序存储或链栈的示意图栈是仅在表尾进行插入、删除操作的线性表表尾(即an端)称为栈顶(top)

表头(即a1端)称为栈底(bottom)插入元素到栈顶的操作，称为入栈从栈顶删除元素的操作，称为出栈栈S=(a1,a2,a3,……….,an-1,an)栈顶元素栈底元素插入和删除都只在表的一端（栈顶）进行栈的示意图栈是仅在表尾进行插入、删除操作的线性表栈S=栈的基本操作INISTACK(S)：初始化操作。设置一个空栈S。EMPTY(S)：判栈空函数。若S为空栈，函数值为1，否则为0SIZE(S)：求栈深函数。函数值为栈中当前的元素个数。TOP(S)：读栈顶元函数。若栈S不空，函数值为栈顶元素，否则为空元素NULL。PUSH(S,x)：进栈操作。将元素x插入栈S中，使x成为栈S的栈顶元素。POP(S):出栈函数。若栈S不空，函数值为栈顶元素，且从栈中删除当前栈顶元素，否则函数值为空元素NULL。CLEAR(S):栈置空操作。不论栈S是否为空栈，将S置为空栈栈的基本操作INISTACK(S)：初始化操作。设置一个空35178421011001余数结果：10011十进制数转换成二进制数把所有的余数按出现的逆序排列起来（先出现的余数排在后面，后出现的余数排在前面）,十进制数35转换成二进制数

3517842101余数结果：10011十进制数转换成二进制将带头结点的单链表（a1,a2,…,an）逆置将带头结点的单链表（a1,a2,…,an）逆置

栈的顺序存储结构(顺序栈)顺序栈:利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素C语言中预设较大的数组空间栈底设为0栈顶随插入和删除元素而变化用一个整型变量top来指示栈顶的位置a1a2……an顺序栈Sai……0n栈底栈顶top压入(PUSH):

S[top++]=an+1弹出(POP):e=S[--top]栈的顺序存储结构(顺序栈)顺序栈:利用一组地址连续的存储顺序栈存储结构的描述#defineMAXSIZE100typedefintelemtype;typedefstructstack{elemtypeelem[MAXSIZE];inttop；//栈顶指针}sqstacktp；//顺序栈类型定义sqstacktp*s；//s为顺序栈类型变量的指针s=(sqstacktp*)malloc(sizeof(sqstacktp));顺序栈存储结构的描述#defineMAXSIZE100123450栈空栈顶指针top,可初始化为0，指向实际栈顶后的空位置.top123450进栈Atop出栈BCDEF设数组大小为MAXSIZEs->top=0,栈空，此时出栈则下溢s->top=MAXSIZE,栈满，此时入栈上溢toptoptoptoptop123450ABCDEFtoptoptoptoptoptoptop设MAXSIZE=6顺序栈的几种情况栈空栈满top123450栈空栈顶指针top,可初始化为0，指向实际栈顶后顺序栈上实现的操作初始化（栈置空）操作voidini_sqstack(sqstacktp*s)；判栈空函数intempty_sqstack(sqstacktp*s)；进栈操作voidpush_sqstack(sqstacktp*s，elemtypex)；出栈函数elemtypepop_sqstack(sqstacktp*s)；求栈深函数intsize_sqstack(sqstacktp*s)；读栈顶元函数elemtypetop_sqstack(sqstacktp*s)；顺序栈上实现的操作初始化（栈置空）操作栈的链式存储结构定义栈的链式存储结构，简称链栈组织形式与单链表类似，链表的尾部是栈底，链表的头部是栈顶栈的链式存储结构定义FtopdatanextEDANULL栈顶栈底栈的链式存储结构链栈的类型定义：typedefstructstacknode{elemtypedata；structstacknode*next；}stacknode;typedefstruct{stacknode*top;

//栈顶指针

}linkstack;linkstack*ls;ls=(linkstack*)malloc(sizeof(linkstack));ls->top=?FtopdatanextEDANULL栈顶栈底栈的链式存储结初始化操作voidinit_linkstack(linkstack*ls)；进栈操作voidpush_linkstack(linkstack*ls,elemtypex)；出栈操作elemtypepop_linkstack(linkstack*ls)；链栈上实现的操作初始化操作链栈上实现的操作对算术表达式求值：

1+2*4-9/3遵循先乘除后加减、先左后右及先括号内，后括号外的四则运算法则，其计算顺序应为：1+2*4-9/3└─┘└┘①②└─┘③└───┘④栈的应用实例—表达式求值采用“运算符优先数法”对每种运算符赋于一个优先数，如：运算符：*/+-#优先数：22110其中#是表达式结束符对表达式求值时，一般设立两个栈运算符栈（OPTR)操作数栈(OPND)分别存放表达式中的运算符和操作数对算术表达式求值：栈的应用实例—表达式求值采用“运算符优先数

步骤OPTR栈OPND栈输入字符主要操作

──────────────────────────1#1+2*4-9/3#PUSH(OPND,'1')2#1+2*4-9/3#PUSH(OPTR,'+')3#+12*4-9/3#PUSH(OPND,'2')4#+12*4-9/3#PUSH(OPTR,'*')5#+*124-9/3#PUSH(OPND,'4')6#+*124-9/3#operate('2','*','4')7#+18-9/3#operate('1','+','8')8#9-9/3#PUSH(OPTR,'-')9#-99/3#PUSH(OPND,'9')10#-99/3#PUSH(OPTR,'/')11#-/993#PUSH(OPND,'3')12#-/993#operate('9','/','3')13#-93#operate('9','-','3')14#6#RETURN(TOP(OPND))

利用算法对算术表达式求值的操作过程步骤OPTR栈OPND栈栈在回溯法中的应用在某些问题的求解过程中常常采用试探方法，当某一路径受阻时，需要逆序退回，重新选择新路径，这样必须用栈记录曾经到达的每一状态，栈顶状态即是回退的第一站。

栈在回溯法中的应用在某些问题的求解过程中常常采用试探方法，当地图四染色问题“四染色”定理可以用不多于四色对地图着色，使相邻的地区不重色算法思想：“回溯”法从第一号地区开始逐一染色，每一个地区逐次用色数1、2、3、4进行试探若当前所取的色数与周围已染色的地区不重色，则用栈记下该地区的色数，否则依次用下一色数进行试探若出现用1..4色均与相邻地区发生重色，则需退栈回溯，修改当前栈顶的色数。地图四染色问题“四染色”定理地图四染色问题算法实现“四染色”定理数据结构graph[n][n]n*n的关系矩阵grph[i][j]=0表示地区i与地区j不相邻graph[i][j]=1表示地区i与地区j相邻。color[n]颜色表：顺序存储color[i]表示i号地区的染色数。地图四染色问题算法实现“四染色”定理(1)(2)(4)(5)(6)(7)(3)r[7][7]12345671234567100001001111101010110101101011011001001100000000012345671223414334231#紫色2#黄色3#红色4#

绿色地图四染色算法(1)(2)(4)(5)(6)(7)(3)r[7][栈与函数调用由于程序设计都采用模块化程序设计方法，模块（函数、过程）是完成功能相对独立的一个程序段，在主函数（主程序）中调用模块来解决复杂的实际问题由于函数调用后，需返回调用处，所以，在调用时，需用栈记录断点的地址以及有关信息，以便返回。

栈与函数调用由于程序设计都采用模块化程序设计方法，模块（函数栈的应用-函数调用intfunc_B(intx,inty){intz;z=x+y;returnz;}intfunc_A(){intx=10,y=20,k;k=func_B(x,y);returnk;}voidmain(){printf(“%d”,func_A());}栈的应用-函数调用intfunc_B(intx,int函数调用函数调用栈与函数堆栈是存储器的一个区域编译器一般使用堆栈实现函数调用函数占用的区域被称作函数的栈帧函数调用时，为被调用的函数分配栈帧，存放函数的参数、局部变量等信息函数嵌套调用时，堆栈中会同时存在多个函数的栈帧，每个函数占用一个连续的区域栈与函数堆栈是存储器的一个区域函数独占自己的栈帧空间当前正在运行的函数的栈帧总是在栈顶两个特殊的寄存器ESP，EBP栈与函数栈帧中的信息局部变量栈帧状态值保存前一栈帧的顶部和底部函数返回地址保存函数调用前的指令位置函数独占自己的栈帧空间栈与函数栈帧中的信息栈与函数栈与函数r主程序srrrs子过程1rst子过程2rst子过程3栈与函数调用的图示r主程序srrrs子过程1rst子过程2rst子过程3栈与函递归的定义若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的二叉树是结点的有限集合，这个集合或者是空的，或者由一个根结点或两棵互不相交的称为左子树的和右子树的二叉树组成若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。递归的定义若一个对象部分地包含它自己,或用它自己给自己定义,直接递归fun_a(){

…

fun_a()

…}间接递归fun_a(){

…

fun_b()

…}fun_b(){

…

fun_a()

…}递归的定义直接递归间接递归fun_b()递归的定义递归条件解决问题时，可以把一个问题转化为一个新的问题，这个新问题的解决方法，与原问题的解法相同，只是所处理的对象有所不同。这些被处理的对象之间有规律的递增或递减要有一个明确的结束递归的条件，否则递归将会无止境地进行下去，直到耗尽系统资源.必须要有终止递归的条件递归条件解决问题时，可以把一个问题转化为一个新的问题，这个新适用递归技术的问题以下三种情况常常用到递归方法定义是递归的数据结构是递归的问题的解法是递归的适用递归技术的问题以下三种情况常常用到递归方法求解阶乘函数的递归算法longFactorial(longn){if(n==0)return1;elsereturnn*Factorial(n-1);}例如，阶乘函数定义是递归的求解阶乘函数的递归算法例如，阶乘函数定义是递归的例如，单链表结构ff数据结构是递归的一个结点，它的指针域为NULL，是一个单链表一个结点，它的指针域指向单链表，仍是一个单链表例如，单链表结构ff数据结构是递归的一个结点，它的打印单链表最后一个结点的值voidPrint(ListNode*f){if(f->link==NULL)

printf(“%d\n”,f->data);elsePrint(f->link);}ffffa0a1a2a3a4f递归找链尾数据结构是递归的打印单链表最后一个结点的值ffffa0a1a2a313

321312212313源中间目的123源中间目的64个abcmove(n,a,b,c)move(n-1,a,c,b)acmove(n-1,b,a,c)64个64个问题的解法是递归的13321312212313源第三章栈和队列课件hanoi(3,1,2,3)n=3a=1b=2c=3hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(2,1,3,2)n=2a=1b=3c=2hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(1,1,2,3)n=1a=1b=2c=3

move(a,c);1->31->21->3hanoi(1,3,1,2)n=1a=3b=1c=2move(a,c);3->2hanoi(2,2,1,3)n=2a=2b=1c=3hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(1,2,3,1)n=1a=2b=3c=1move(a,c);2->12->3hanoi(1,1,2,3)n=1a=1b=2c=3move(a,c);1->3voidhanoi(intn,inta,intb,intc){if(n==1) move(a,c);else{hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c); }}1->31->23->22->12->31->31->3hanoi(3,1,2,3)n=3a=1b=2c=3h递归模型递归是把一个不能或不好直接求解的“大问题”转化为一个或几个“小问题”再把这些“小问题”进一步分解成更小的“小问题”来解决直到递归出口为止递归模型反映一个递归问题的递归结构递归模型由递归出口和递归体两部分组成前者确定递归到何时为止后者确定递归的方式递归模型递归是把一个不能或不好直接求解的“大问题”转化为一递归模型递归出口的一般格式为f(s0)=m0这里的s0与m0均为常量，有的递归问题可能有几个递归出口。递归体的一般格式为f(s)=g(f(s1),f(s2),……,f(sn),c1,c2,……，cm)s是一个递归“大问题”s1,s2,……,sn是递归“小问题”c1,c2,……，cm是若干个可以直接（用非递归方法）解决的问题g是一个非递归函数，反映了递归问题的结构。递归模型递归出口的一般格式为递归模型例如，阶乘函数递归出口递归体递归模型例如，阶乘函数递归出口递归体主程序main:fact(4)参数4计算4*fact(3)

参数3计算3*fact(2)

参数2计算2*fact(1)

参数1计算1*fact(0)参数0直接定值=1

参数传递结果返回递归调用回归求值求解n!的过程返回1返回1返回2返回6返回24主程序main:fact(4)参数4计算4运行结果：1，2，2，3，3，3，递归过程与递归工作栈voidprint(intw){inti;if(w!=0){print(w-1);for(i=1;i<=w;++i)printf(“%3d,”,w);printf(“/n”);}}运行结果：递归过程与递归工作栈voidprint(i主程序(1)print(w)w=3;3print(2);（1）w=3top(2)输出：3,3,3w2print(1)（2）w=2（1）w=3top(3)输出：2,2w1print(0);（3）w=1（2）w=2（1）w=3top(4)输出：1w0（4）w=0（3）w=1（2）w=2（1）w=3topw(3)输出：2,2(2)2(1)3top(4)输出：1(3)1(2)2(1)3top(2)输出：3,3,3(1)3top返回(3)1(2)2(1)3top(4)0结束(1)递归调用执行情况如下主程序(1)print(w)w=3;3print(2);递归算法的非递归描述intfac(intn){if(n==1)return1;else returnn*fac(n-1);}voidmain(){ fac(4);}intfac(intn){ints=1;while(n>=1) push(stack,n--);while(!empty(stack))s*=pop(stack);returns;}voidmain(){ fac(4);}递归算法的非递归描述intfac(intn)intfa栈和队列栈和队列的概念栈和队列的存储结构及它们的应用栈和队列与线性表有着密切的联系栈和队列栈和队列的概念第三章栈和队列栈栈的存储结构及应用队列队列的存储结构及应用第三章栈和队列栈栈的基本概念定义数据元素之间是一对一的关系顺序存储或链式存储只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则存储结构运算规则逻辑结构只能在表的一端进行插入和删除的线性表基本操作建栈、判断栈满或栈空、入栈、出栈、取栈顶元素值栈的基本概念定义数据元素之间是一对一的关系顺序存储或链栈的示意图栈是仅在表尾进行插入、删除操作的线性表表尾(即an端)称为栈顶(top)

表头(即a1端)称为栈底(bottom)插入元素到栈顶的操作，称为入栈从栈顶删除元素的操作，称为出栈栈S=(a1,a2,a3,……….,an-1,an)栈顶元素栈底元素插入和删除都只在表的一端（栈顶）进行栈的示意图栈是仅在表尾进行插入、删除操作的线性表栈S=栈的基本操作INISTACK(S)：初始化操作。设置一个空栈S。EMPTY(S)：判栈空函数。若S为空栈，函数值为1，否则为0SIZE(S)：求栈深函数。函数值为栈中当前的元素个数。TOP(S)：读栈顶元函数。若栈S不空，函数值为栈顶元素，否则为空元素NULL。PUSH(S,x)：进栈操作。将元素x插入栈S中，使x成为栈S的栈顶元素。POP(S):出栈函数。若栈S不空，函数值为栈顶元素，且从栈中删除当前栈顶元素，否则函数值为空元素NULL。CLEAR(S):栈置空操作。不论栈S是否为空栈，将S置为空栈栈的基本操作INISTACK(S)：初始化操作。设置一个空35178421011001余数结果：10011十进制数转换成二进制数把所有的余数按出现的逆序排列起来（先出现的余数排在后面，后出现的余数排在前面）,十进制数35转换成二进制数

3517842101余数结果：10011十进制数转换成二进制将带头结点的单链表（a1,a2,…,an）逆置将带头结点的单链表（a1,a2,…,an）逆置

栈的顺序存储结构(顺序栈)顺序栈:利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素C语言中预设较大的数组空间栈底设为0栈顶随插入和删除元素而变化用一个整型变量top来指示栈顶的位置a1a2……an顺序栈Sai……0n栈底栈顶top压入(PUSH):

S[top++]=an+1弹出(POP):e=S[--top]栈的顺序存储结构(顺序栈)顺序栈:利用一组地址连续的存储顺序栈存储结构的描述#defineMAXSIZE100typedefintelemtype;typedefstructstack{elemtypeelem[MAXSIZE];inttop；//栈顶指针}sqstacktp；//顺序栈类型定义sqstacktp*s；//s为顺序栈类型变量的指针s=(sqstacktp*)malloc(sizeof(sqstacktp));顺序栈存储结构的描述#defineMAXSIZE100123450栈空栈顶指针top,可初始化为0，指向实际栈顶后的空位置.top123450进栈Atop出栈BCDEF设数组大小为MAXSIZEs->top=0,栈空，此时出栈则下溢s->top=MAXSIZE,栈满，此时入栈上溢toptoptoptoptop123450ABCDEFtoptoptoptoptoptoptop设MAXSIZE=6顺序栈的几种情况栈空栈满top123450栈空栈顶指针top,可初始化为0，指向实际栈顶后顺序栈上实现的操作初始化（栈置空）操作voidini_sqstack(sqstacktp*s)；判栈空函数intempty_sqstack(sqstacktp*s)；进栈操作voidpush_sqstack(sqstacktp*s，elemtypex)；出栈函数elemtypepop_sqstack(sqstacktp*s)；求栈深函数intsize_sqstack(sqstacktp*s)；读栈顶元函数elemtypetop_sqstack(sqstacktp*s)；顺序栈上实现的操作初始化（栈置空）操作栈的链式存储结构定义栈的链式存储结构，简称链栈组织形式与单链表类似，链表的尾部是栈底，链表的头部是栈顶栈的链式存储结构定义FtopdatanextEDANULL栈顶栈底栈的链式存储结构链栈的类型定义：typedefstructstacknode{elemtypedata；structstacknode*next；}stacknode;typedefstruct{stacknode*top;

//栈顶指针

}linkstack;linkstack*ls;ls=(linkstack*)malloc(sizeof(linkstack));ls->top=?FtopdatanextEDANULL栈顶栈底栈的链式存储结初始化操作voidinit_linkstack(linkstack*ls)；进栈操作voidpush_linkstack(linkstack*ls,elemtypex)；出栈操作elemtypepop_linkstack(linkstack*ls)；链栈上实现的操作初始化操作链栈上实现的操作对算术表达式求值：

1+2*4-9/3遵循先乘除后加减、先左后右及先括号内，后括号外的四则运算法则，其计算顺序应为：1+2*4-9/3└─┘└┘①②└─┘③└───┘④栈的应用实例—表达式求值采用“运算符优先数法”对每种运算符赋于一个优先数，如：运算符：*/+-#优先数：22110其中#是表达式结束符对表达式求值时，一般设立两个栈运算符栈（OPTR)操作数栈(OPND)分别存放表达式中的运算符和操作数对算术表达式求值：栈的应用实例—表达式求值采用“运算符优先数

步骤OPTR栈OPND栈输入字符主要操作

──────────────────────────1#1+2*4-9/3#PUSH(OPND,'1')2#1+2*4-9/3#PUSH(OPTR,'+')3#+12*4-9/3#PUSH(OPND,'2')4#+12*4-9/3#PUSH(OPTR,'*')5#+*124-9/3#PUSH(OPND,'4')6#+*124-9/3#operate('2','*','4')7#+18-9/3#operate('1','+','8')8#9-9/3#PUSH(OPTR,'-')9#-99/3#PUSH(OPND,'9')10#-99/3#PUSH(OPTR,'/')11#-/993#PUSH(OPND,'3')12#-/993#operate('9','/','3')13#-93#operate('9','-','3')14#6#RETURN(TOP(OPND))

利用算法对算术表达式求值的操作过程步骤OPTR栈OPND栈栈在回溯法中的应用在某些问题的求解过程中常常采用试探方法，当某一路径受阻时，需要逆序退回，重新选择新路径，这样必须用栈记录曾经到达的每一状态，栈顶状态即是回退的第一站。

栈在回溯法中的应用在某些问题的求解过程中常常采用试探方法，当地图四染色问题“四染色”定理可以用不多于四色对地图着色，使相邻的地区不重色算法思想：“回溯”法从第一号地区开始逐一染色，每一个地区逐次用色数1、2、3、4进行试探若当前所取的色数与周围已染色的地区不重色，则用栈记下该地区的色数，否则依次用下一色数进行试探若出现用1..4色均与相邻地区发生重色，则需退栈回溯，修改当前栈顶的色数。地图四染色问题“四染色”定理地图四染色问题算法实现“四染色”定理数据结构graph[n][n]n*n的关系矩阵grph[i][j]=0表示地区i与地区j不相邻graph[i][j]=1表示地区i与地区j相邻。color[n]颜色表：顺序存储color[i]表示i号地区的染色数。地图四染色问题算法实现“四染色”定理(1)(2)(4)(5)(6)(7)(3)r[7][7]12345671234567100001001111101010110101101011011001001100000000012345671223414334231#紫色2#黄色3#红色4#

绿色地图四染色算法(1)(2)(4)(5)(6)(7)(3)r[7][栈与函数调用由于程序设计都采用模块化程序设计方法，模块（函数、过程）是完成功能相对独立的一个程序段，在主函数（主程序）中调用模块来解决复杂的实际问题由于函数调用后，需返回调用处，所以，在调用时，需用栈记录断点的地址以及有关信息，以便返回。

栈与函数调用由于程序设计都采用模块化程序设计方法，模块（函数栈的应用-函数调用intfunc_B(intx,inty){intz;z=x+y;returnz;}intfunc_A(){intx=10,y=20,k;k=func_B(x,y);returnk;}voidmain(){printf(“%d”,func_A());}栈的应用-函数调用intfunc_B(intx,int函数调用函数调用栈与函数堆栈是存储器的一个区域编译器一般使用堆栈实现函数调用函数占用的区域被称作函数的栈帧函数调用时，为被调用的函数分配栈帧，存放函数的参数、局部变量等信息函数嵌套调用时，堆栈中会同时存在多个函数的栈帧，每个函数占用一个连续的区域栈与函数堆栈是存储器的一个区域函数独占自己的栈帧空间当前正在运行的函数的栈帧总是在栈顶两个特殊的寄存器ESP，EBP栈与函数栈帧中的信息局部变量栈帧状态值保存前一栈帧的顶部和底部函数返回地址保存函数调用前的指令位置函数独占自己的栈帧空间栈与函数栈帧中的信息栈与函数栈与函数r主程序srrrs子过程1rst子过程2rst子过程3栈与函数调用的图示r主程序srrrs子过程1rst子过程2rst子过程3栈与函递归的定义若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的二叉树是结点的有限集合，这个集合或者是空的，或者由一个根结点或两棵互不相交的称为左子树的和右子树的二叉树组成若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。递归的定义若一个对象部分地包含它自己,或用它自己给自己定义,直接递归fun_a(){

…

fun_a()

…}间接递归fun_a(){

…

fun_b()

…}fun_b(){

…

fun_a()

…}递归的定义直接递归间接递归fun_b()递归的定义递归条件解决问题时，可以把一个问题转化为一个新的问题，这个新问题的解决方法，与原问题的解法相同，只是所处理的对象有所不同。这些被处理的对象之间有规律的递增或递减要有一个明确的结束递归的条件，否则递归将会无止境地进行下去，直到耗尽系统资源.必须要有终止递归的条件递归条件解决问题时，可以把一个问题转化为一个新的问题，这个新适用递归技术的问题以下三种情况常常用到递归方法定义是递归的数据结构是递归的问题的解法是递归的适用递归技术的问题以下三种情况常常用到递归方法求解阶乘函数的递归算法longFactorial(longn){if(n==0)return1;elsereturnn*Factorial(n-1);}例如，阶乘函数定义是递归的求解阶乘函数的递归算法例如，阶乘函数定义是递归的例如，单链表结构ff数据结构是递归的一个结点，它的指针域为NULL，是一个单链表一个结点，它的指针域指向单链表，仍是一个单链表例如，单链表结构ff数据结构是递归的一个结点，它的打印单链表最后一个结点的值voidPrint(ListNode*f){if(f->link==NULL)

printf(“%d\n”,f->data);elsePrint(f->link);}ffffa0a1a2a3a4f递归找链尾数据结构是递归的打印单链表最后一个结点的值ffffa0a1a2a313

321312212313源中间目的123源中间目的64个abcmove(n,a,b,c)move(n-1,a,c,b)acmove(n-1,b,a,c)64个64个问题的解法是递归的13321312212313源第三章栈和队列课件hanoi(3,1,2,3)n=3a=1b=2c=3hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(2,1,3,2)n=2a=1b=3c=2hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(1,1,2,3)n=1a=1b=2c=3

move(a,c);1->31->21->3hanoi(1,3,1,2)n=1a=3b=1c=2move(a,c);3->2hanoi(2,2,1,3)n=2a=2b=1c=3hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(1,2,3,1)n=1a=2b=3c=1move(a,c);2->12->3hanoi(1,1,2,3)n=1a=1b=2c=3move(a,c);1->3voidha