数据结构第3章栈和队列栈ppt课件

1、武汉科技大学Wuhan University of Science and Technology张 凯计算机学院 软件工程系2021年3月12日;队列类型的定义和实现第第3 3章章 栈和队列栈和队列栈的类型定义栈的运用举例栈类型的实现;3.1 栈的类型定义栈的类型定义;3.1 栈的类型定义栈的类型定义;3.1 栈的类型定义栈的类型定义;v栈表示图栈表示图3.1 栈的类型定义栈的类型定义 a1 a2 a3 an栈顶栈底 ;v栈的相关概念栈的相关概念3.1 栈的类型定义栈的类型定义1.定义与同线性表一样，仍为一对一关系。用顺序栈或链栈存储均可，但以顺序栈更常见只能在栈顶运算，且访问结点时按照后进先

2、出LIFO的原那么。关键是编写入栈和出栈函数，详细实现依顺序栈或链栈的不同而不同。 3.存储构造4.运算规那么5.实现方式 2.逻辑构造限定只能在表的一端进展插入和删除运算的线性表只能在栈顶操作;v栈与普通线性表有什么不同栈与普通线性表有什么不同3.1 栈的类型定义栈的类型定义栈与普通线性表的区别：仅在于运算规那么不同。 普通线性表普通线性表 栈栈逻辑构造：一对一逻辑构造：一对一 逻辑构造：逻辑构造：一对一一对一存储构造：顺序表、链表存储构造：顺序表、链表 存储构造：顺序存储构造：顺序栈、链栈栈、链栈运算规那么：随机存取运算规那么：随机存取 运算规那运算规那么：后进先出么：后进先出(LIFO)

3、(LIFO)“进 压入=PUSHx)“出 弹出=POP ( y );v栈的相关概念栈的相关概念3.1 栈的类型定义栈的类型定义栈 是仅在表尾进展插入、删除操作的线性表。表尾(即an端)称为栈顶 Top；表头(即a1端)称为栈底Base例如： 栈 s = (a1, a2, a3, an-1, an) a1称为栈底元素 an称为栈顶元素插入元素到栈顶(即表尾)的操作，称为入栈。从栈顶(即表尾)删除最后一个元素的操作，称为出栈。;v思索题思索题v一个栈的入栈序列是一个栈的入栈序列是a, b, c, d, e，那么栈，那么栈的不能够的输出序列是的不能够的输出序列是 。3.1 栈的类型定义栈的类型定义A

4、 e d c b a B d e c b a C d c e a b D a b c d e;v栈的笼统数据类型定义栈的笼统数据类型定义3.1 栈的类型定义栈的类型定义ADT Stack 数据对象：数据对象：D=ai|aiElemSet,i=1,2,.,n) 数据关系数据关系: R=|ai-1,aiD,i=2,.,n) 商定商定an端为栈顶，端为栈顶，a1端为栈底端为栈底 根本操作：根本操作： InitStack( &S ) 操作结果：构造空栈操作结果：构造空栈S DestroyStack( &S ) 初始条件：栈初始条件：栈S已存在已存在 操作结果：销毁栈操作结果：销毁栈S

5、ClearStack( &S ) 初始条件：栈初始条件：栈S已存在已存在 操作结果：将操作结果：将S置为空栈置为空栈 StackEmpty( S ) 初始条件：栈初始条件：栈S已存在已存在 操作结果：判别栈操作结果：判别栈S能否为空栈能否为空栈 StackLength( S ) 初始条件：栈初始条件：栈S已存在已存在 操作结果：前往栈操作结果：前往栈S中元素个数中元素个数(栈长栈长) GetTop( S,&e ) 初始条件：栈初始条件：栈S已存在且非空已存在且非空 操作结果：用操作结果：用e前往前往S的栈顶元的栈顶元素素 Push( &S, e ) 初始条件：栈初始条件

6、：栈S已存在已存在 操作结果：插入元素操作结果：插入元素e为新的栈顶元素为新的栈顶元素 Pop( &S, &e ) 初始条件：栈初始条件：栈S已存在已存在 操作结果：删除操作结果：删除S的栈顶元素，用的栈顶元素，用e前往前往值值 ADT Stack;v栈的物理存储栈的物理存储v栈的物理存储可以用顺序存储构造，也可栈的物理存储可以用顺序存储构造，也可用链式存储构造。相应地，栈的存储方式用链式存储构造。相应地，栈的存储方式也分为两种，即顺序栈和链栈。也分为两种，即顺序栈和链栈。 3.2 栈的表示和实现栈的表示和实现;v顺序栈的定义顺序栈的定义3.2 栈的表示和实现栈的表示和实现#d

7、efine STACK_INIT_SIZE 100; / 存储空间初始分配量#define STACKINCREMENT 10; / 存储空间分配增量typedef struct SElemType *base; / base的初值为NULL，阐明栈构造不存在 SElemType *top; / 栈顶指针，初值指向栈底， / 即top=base作为栈空的标志 int stacksize; / 当前已分存储空间，即指示当前栈 / 可运用的最大容量，以元素为单位 SqStack; ;v栈顶指针和栈中元素之间的关系栈顶指针和栈中元素之间的关系3.2 栈的表示和实现栈的表示和实现1空栈中的栈顶指针的指

8、向和栈底指针一致2非空栈中的栈顶指针一直在栈顶元素的下一个位置AABCDABbasetopbasetopbasetopbasetop;v栈在笼统类型中的几种操作举例栈在笼统类型中的几种操作举例3.2 栈的表示和实现栈的表示和实现例1：构造一个空栈Status InitStack(SqStack &s) /构造一个空栈S s.base=(SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemtype); If (!s.base) exit (OVERFLOW); /存储分配失败 s.top=s.base; s.stacksize= STACK

9、_INIT_SIZE; return OK; / InitStack;v栈在笼统类型中的几种操作举例栈在笼统类型中的几种操作举例3.2 栈的表示和实现栈的表示和实现例2：取栈顶元素Status GetTop(SqStack s, SElemtype &e) /假设栈不空，用e前往S的栈顶元素 if (s.top = = s.base) return ERROR; e = * (s.top - 1); /操作后s.top不变，并将当前栈顶元素赋给e return OK; / GetTop;等同于删除栈顶元素出栈，区别在于： e = * - - s.top; /操作后stop减，并将当前出

10、栈的元素赋给etopbaseACBDbasetoptop-1e=D;v栈在笼统类型中的几种操作举例栈在笼统类型中的几种操作举例3.2 栈的表示和实现栈的表示和实现例3：插入新栈顶元素即入栈Status Push(SqsTack & s, SElemType e) /插入元素e为新的栈顶元素 if (s.top - s.base = s.stacksize) /栈满，追加存储空间 s.base=(SElemtype *)realloc(s.base, s.stacksize + STACKINCREMENT) * sizeof( Selemtype ); if (!s.base) exi

11、t (OVERFLOW); /存储分配失败 s.top = s.base + s.stacksize; s.stacksize += STACKINCREMENT; * s.top + = e; /*s.top =e; s.top+;栈顶指针一直在栈顶元素的下一个位置 return OK; / Push;acbdtope;v栈在笼统类型中的几种操作举例栈在笼统类型中的几种操作举例3.2 栈的表示和实现栈的表示和实现例4：删除栈顶元素即出栈Status Pop(SqStack & s, SElemType &e) / 假设栈不空，删除S的栈顶元素，用e前往其/ 值 ，并前往0K，

12、否那么前往ERROR if (s.top = = s.base) return (ERROR); e = * - - s.top; /-s.top; e=*stop;栈顶指针一直在栈顶元素的下一位置 return OK; / Pop;topbaseERRORACBDbasetope=D;v栈的链式存储构造栈的链式存储构造v栈的链式存储构造称为链栈，它是运算是栈的链式存储构造称为链栈，它是运算是受限的单链表，插入和删除操作仅限制在受限的单链表，插入和删除操作仅限制在表头位置上进展。由于只能在表头进展操表头位置上进展。由于只能在表头进展操作，故没必要附加头结点，栈顶指针就是作，故没必要附加头结点，

13、栈顶指针就是链表的头指针。链表的头指针。 3.2 栈的表示和实现栈的表示和实现;v栈的链式存储构造栈的链式存储构造3.2 栈的表示和实现栈的表示和实现链栈表示图 an an-1 a1 / Top栈顶栈底;v链栈的类型阐明如下链栈的类型阐明如下3.2 栈的表示和实现栈的表示和实现typedef struct StackNode ElemType data struct StackNode *next StackNode; typedef struct StackNode *top LinkStack;Data next an an-1 a1 / Top;v链栈的根本操作链栈的根本操作3.2 栈的

14、表示和实现栈的表示和实现Void InitStack(LinkStack *s) /初始化链栈 stop=null; Int StackEmpty(LinkStack *s) /判别能否空栈 return stop=null; ElemType Gettop(LinkStack *s) /前往栈顶元素 if(StackEmpty(s) return (ERROR); return stopdata; ;v链栈插入新栈顶元素即入栈链栈插入新栈顶元素即入栈3.2 栈的表示和实现栈的表示和实现Status Push(LinkStack *s, ElemType e) /插入元素e为新的栈顶元素 q=

15、(StackNode*)malloc(sizeof(StackNode); qdata=e; qnext=stop; stop=q; ;v链栈删除栈顶元素即出栈链栈删除栈顶元素即出栈3.2 栈的表示和实现栈的表示和实现Status Pop( LinkStack *s, ElemType &e) /假设栈不空，那么删除链栈栈顶元素，用e前往其值 if (StackEmpty(s) return (Error); q=stop; e=qdata; stop=qnext; free(q); return OK; ;v1.数制转换数制转换v2.括号匹配的检验括号匹配的检验v3.行编辑程序行编辑

16、程序v4.迷宫求解迷宫求解v5.表达式求值表达式求值3.3 栈的运用举例栈的运用举例;v数制转换数制转换3.3 栈的运用举例栈的运用举例十进制数 N 和其它 D 进制数的转换 N = ( N div d )d + N mod d (其中：div 为整除运算，mod 为求余运算;v数制转换数制转换3.3 栈的运用举例栈的运用举例例如：(1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 对应的8进制数 1348 168 4 4 168 21 0 0 21 2 5 5 2 0 2 2;v数制转换数制转换3.3 栈的运用举例栈的运用举例void Convers

17、ion ( ) / 对于输入的恣意一个非负十进制整数，输出等值的八进制数 InitStack(&S); / 构造空栈 scanf (%d,N); while (N) Push(&S, N % 8); N = N/8; while (!StackEmpty(S) Pop(&S,&e); printf ( %d, e ); / conversion;v括号匹配的检验括号匹配的检验3.3 栈的运用举例栈的运用举例 假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即： 1.或 为正确格式； 2. 为错误格式； 3. 或 ( ) )为错误格式。;v括号匹配

18、的检验括号匹配的检验3.3 栈的运用举例栈的运用举例思索以下括号序列： ( ) 1 2 3 4 5 6 7 8 ( ( ) 分析能够出现的不匹配的情况以“(为例：到来的右括弧不是所“等待的,如“；直到终了，也没有到来右括弧“；;v算法思想算法思想3.3 栈的运用举例栈的运用举例1)凡出现左括弧，那么进栈2)凡出现右括弧，首先检查栈能否空 是：该“右括弧多余； 否：和栈顶元素比较，假设相匹配，那么“左括弧 出栈，否那么阐明不匹配；3)表达式检验终了时， 假设栈空，匹配正确； 否那么阐明“左括弧有余。;v括号匹配的检验括号匹配的检验3.3 栈的运用举例栈的运用举例status matching(s

19、tring &exp) / 检验表达式中所含括弧能否正确嵌套， int state = 1; while ( i -*/(#=21;v表达式求值表达式求值3.3 栈的运用举例栈的运用举例 +、-、*、/为1时的优先性均低于“(但高于“) 当1=2时，“#是表达式的终了符。为了算法简约，在表达式的最左边也虚设一个“#构成整个表达式的一对括号 “(=“)表示括号内的运算曾经完成 “#=“#表示整个表达式求值终了 “)与“(、“#与“)以及“(与“#之间无优先关系，可以为出了现语法错误;3.3 栈的运用举例栈的运用举例步骤OPTR栈OPND栈输入字符主要操作1#3*(7-2)#PUSH(OP

20、ND,3)2#3 *(7-2)#PUSH(OPTR,*)3#*3 (7-2)#PUSH(OPTR,()4#*(3 7-2)#PUSH(OPND,7)5#*(3 7 -2)#PUSH(OPTR,-)6#*(-3 7 2)#PUSH(OPND,2)7#*(-3 7 2 )#operate(7,-,2)8#*(3 5 )#POP(OPTR)消去一对括号9#*3 5 #operate(3,*,5)10#15 #RETURN(GETTOP(OPND);3.3 栈的运用举例栈的运用举例OperandType EvaluateExpression() /设OPTR和OPND分别为运算符栈和运算数栈，OP为运

21、算符集合 InitStack(OPTR); Push(OPTR,#); InitStack(OPND); c=getchar(); while(c!=#|GetTop(OPTR)!=#) if(!In(c,OP) Push(OPND,c); c=getchar(); else switch(Precede(GetTop(OPTR),c) case : /退栈并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; /switch /while return Get

22、Top(OPND);/ EvaluateExpression;v表达式的三种标识方法表达式的三种标识方法3.3 栈的运用举例栈的运用举例设 Exp = S1 + OP + S2那么称 OP + S1 + S2 为前缀表示法 S1 + OP + S2 为中缀表示法 S1 + S2 + OP 为后缀表示法 ;例如例如: Exp = a b + (c d / e) f前缀式前缀式: + a b c / d e f中缀式中缀式: a b + c d / e f后缀式后缀式: a b c d e / f + 结论结论:1操作数之间的相对次序不变操作数之间的相对次序不变;2运算符的相对次序不同运算符的相对

23、次序不同;3中缀式丧失了括弧信息，中缀式丧失了括弧信息， 致使运算的次序不确定致使运算的次序不确定;4)前缀式的运算规那么为前缀式的运算规那么为:延续出现的两个操作数和在它们延续出现的两个操作数和在它们之前且紧靠它们的运算符构成一之前且紧靠它们的运算符构成一个最小表达式个最小表达式; 5)后缀式的运算规那么为后缀式的运算规那么为: 运算符在式中出现的顺序恰为运算符在式中出现的顺序恰为 表达式的运算顺序表达式的运算顺序; 每个运算符和在它之前出现每个运算符和在它之前出现 且且 紧靠它的两个操作数构成一个最小紧靠它的两个操作数构成一个最小 表达式。表达式。;v如何从后缀式求值如何从后缀式求值3.3

24、 栈的运用举例栈的运用举例先找运算符，再找操作数例如： a b c d e / f +abd/ec-d/e(c-d/e)f;v如何从原表达式求得后缀式如何从原表达式求得后缀式3.3 栈的运用举例栈的运用举例 每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。分析 “原表达式 和 “后缀式中的运算符:原表达式: a + b c d / e f 后缀式: a b c + d e / f ;v从原表达式求得后缀式的规律为从原表达式求得后缀式的规律为3.3 栈的运用举例栈的运用举例1) 设立操作数栈；2) 设表达式的终了符为“#，预设运算符栈的栈底为“

25、#3) 假设当前字符是操作数，那么直接发送给后缀式。4) 假设当前运算符的优先数高于栈顶运算符，那么进栈；5) 否那么，退出栈顶运算符发送给后缀式； 6) “( 对它之前后的运算符起隔离作用，“)可视为自相应左括弧开场的表达式的终了符。;v从原表达式求得后缀式的规律为从原表达式求得后缀式的规律为3.3 栈的运用举例栈的运用举例void transform(char suffix , char exp ) InitStack(S); Push(S, #); p = exp; ch = *p; while (!StackEmpty(S) if (!IN(ch, OP) Pass( Suffix,

26、ch); else if ( ch!= # ) p+; ch = *p; else Pop(S, ch); Pass(Suffix, ch); / while / CrtExptree;v从原表达式求得后缀式的规律为从原表达式求得后缀式的规律为3.3 栈的运用举例栈的运用举例switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) Pass( Suffix, c); Pop(S, c) break; defult : while(Gettop(S, c) & ( precede(c,ch) P

27、ass( Suffix, c); Pop(S, c); if ( ch!= # ) Push( S, ch); break; / switch;3.4 栈与递归的实现栈与递归的实现 当求解一个问题时，是经过求解与它同样解法的子问题而得到的，这就是递归。 或了解为子程序或函数反复的调用本人，并传入不同的变量来执行的一种程序设计技巧。 递归是程序设计及解题的一种有力的、重要的工具，协助程序设计者处理复杂问题，并精简程序构造。;v例：设计一个乘法器，可以计算出两个数例：设计一个乘法器，可以计算出两个数相乘的乘积。但是此时计算机不能提供乘相乘的乘积。但是此时计算机不能提供乘法运算仅知道任何数乘法运算仅

28、知道任何数乘 1，其值不变，其值不变，那么独一可以运用的运算方式就是加法运那么独一可以运用的运算方式就是加法运算。算。3.4 栈与递归的实现栈与递归的实现 11 3是 11 连加 3 次 (11 3) = 11 + 11 2 = 11 + 11 + 11 1) = 11 + 11 + 11 = 11 + 22 = 33;v运用递归的一个重要问题运用递归的一个重要问题v一个递归的求解问题必然包含有终止递归一个递归的求解问题必然包含有终止递归的条件，当满足一定条件时就终止向下递的条件，当满足一定条件时就终止向下递归，从而使问题得以处理。归，从而使问题得以处理。3.4 栈与递归的实现栈与递归的实现;

29、v运用递归的一个重要问题运用递归的一个重要问题v处理递归问题的算法称递归算法，在递归处理递归问题的算法称递归算法，在递归算法中需求根据递归条件直接或间接地调算法中需求根据递归条件直接或间接地调用算法本身，当满足某种条件时终了递归用算法本身，当满足某种条件时终了递归调用。当然对于一些简单的递归问题，很调用。当然对于一些简单的递归问题，很容易把它转换为循环问题处理，从而使编容易把它转换为循环问题处理，从而使编写出的算法更为有效。写出的算法更为有效。3.4 栈与递归的实现栈与递归的实现;v实现递归实现递归3.4 栈与递归的实现栈与递归的实现将一切的实参、前往地址等信息传送给被调用函数保管;为被调用函

30、数的部分变量分配存储区;将控制转移到被调用函数的入口。 当在一个函数的运转期间调用另一个函数时，在运转该被调用函数之前，需先完成三项义务：;v实现递归实现递归3.4 栈与递归的实现栈与递归的实现保管被调函数的计算结果;释放被调函数的数据区;按照被调函数保管的前往地址将控制转移到调用函数。 从被调用函数前往调用函数之前，应该完成以下三项义务：;v多个函数嵌套调用的规那么是多个函数嵌套调用的规那么是3.4 栈与递归的实现栈与递归的实现此时的内存管理实行“栈式管理后调用先前往 ！例如：void main( ) void a( ) void b( ) a( ); b( ); /main / a / b

31、Main的数据区函数a的数据区函数b的数据区;v实现递归实现递归3.4 栈与递归的实现栈与递归的实现递归任务栈：递归过程执行过程中占用的数据区。递归任务记录：每一层的递归参数合成一个记录。当前活动记录：栈顶记录指示当前层的执行情况。当前环境指针：递归任务栈的栈顶指针。 递归函数执行的过程可视为同一函数进展嵌套调用，例如：;v例：采用递归算法求解正整数例：采用递归算法求解正整数n的阶乘的阶乘(n!)3.4 栈与递归的实现栈与递归的实现用C言语编写出求解n!的递归函数为： long f (int n) if n = = 0 return 1; else return n * fn 1; ;v进展进

32、展f (4)调用的系统栈的变化形状调用的系统栈的变化形状3.4 栈与递归的实现栈与递归的实现4r13r24r12r33r24r10r41r42r33r24r11r42r33r24r1;v进展进展f (4)调用的系统栈的变化形状调用的系统栈的变化形状3.4 栈与递归的实现栈与递归的实现4r13r24r12r33r24r11r42r33r24r1;v例：最大公因子问题例：最大公因子问题v数学上利用辗转相除法处理。同时此种方数学上利用辗转相除法处理。同时此种方法也称为欧几理德定理，其定义为：法也称为欧几理德定理，其定义为：3.4 栈与递归的实现栈与递归的实现GCD(M，N) =GCDN，M % N

33、N0M N=0;v写出求解最大公因子的递归函数为写出求解最大公因子的递归函数为3.4 栈与递归的实现栈与递归的实现long GCD( int M，int N ) / 前提条件：MN if N = = 0 /递归终了条件 return M ； else return GCD( N，M % N )； ;v汉诺汉诺( hanoi )塔问题塔问题v汉诺塔问题是印度的一个古老的传说。开天汉诺塔问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着石的棒，第一根上面套着64个圆的金片，最个圆的金片，最大的一个在底下，其他一个比一个

34、小，依次大的一个在底下，其他一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间从这根棒搬到另一根棒上，规定可利用中间的一根棒作为协助，但每次只能搬一个，而的一根棒作为协助，但每次只能搬一个，而且大的不能放在小的上面。且大的不能放在小的上面。3.4 栈与递归的实现栈与递归的实现;v汉诺汉诺( hanoi )塔问题塔问题v假设有三个分别命名为假设有三个分别命名为X、Y、Z的塔座，在的塔座，在塔座塔座X上插有上插有n个直径大小各不一样、依小到个直径大小各不一样、依小到大编号为大编号为1、2、n的圆盘。现要求将的圆盘。现

35、要求将X轴上轴上的的n个圆盘移到塔座个圆盘移到塔座Z上并仍按同样的顺序叠上并仍按同样的顺序叠排，圆盘挪动时必需遵照以下规那么：排，圆盘挪动时必需遵照以下规那么：v 1每次只能挪动一个圆盘；每次只能挪动一个圆盘；v 2圆盘可以插在圆盘可以插在X、Y、Z的任一塔座上；的任一塔座上；v 3任何时辰都不能将一个较大的圆盘压任何时辰都不能将一个较大的圆盘压在较在较 小的圆盘上。小的圆盘上。3.4 栈与递归的实现栈与递归的实现;3.4 栈与递归的实现栈与递归的实现void hanoi (int n, char x, char y, char z)/ 将塔座x上按直径由小到大且至上而下编号为1至n/ 的n个

36、圆盘按规那么搬到塔座z上，y可用作辅助塔座。 if (n=1) move(x, 1, z); / 将编号为的圆盘从x移到z else hanoi(n-1, x, z, y); / 将x上编号为至n-1的 /圆盘移到y, z作辅助塔 move(x, n, z); / 将编号为n的圆盘从x移到z hanoi(n-1, y, x, z); / 将y上编号为至n-1的 /圆盘移到z, x作辅助塔 123456789;3.4 栈与递归的实现栈与递归的实现递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0, 3, a, b, cabc主函数： 执行调用语句hanoi (3,a,b,c) ，入栈

37、。层1： 执行1,2,4,5语句，产生向下调用，进层2。;3.4 栈与递归的实现栈与递归的实现层2 入栈，记录层1的前往地址6等信息； 执行2层的1,2,4,5语句，执行到语句再向下调用，进入层3递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0, 3, a, b, cabc6, 2, a, c, b;3.4 栈与递归的实现栈与递归的实现递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0, 3, a, b, cabc6, 2, a, c, b6, 1, a, b, c层3 入栈，记录层2的前往地址6等信息； 执行1,2,3,9语句，过程执行完。;3.4 栈与递归的实现栈

38、与递归的实现层2 第3层调用终了，出栈，前往第2层； 从第2层的断点语句6执行； 执行到语句7，又开场向下递归调用到第3层。递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0, 3, a, b, cabc6, 2, a, c, b6, 1, a, b, c;3.4 栈与递归的实现栈与递归的实现层3 入栈,记录层2的前往地址8等信息； 执行语句1,2,3,9,过程执行完。 出栈，前往第2层断点语句8。递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0, 3, a, b, cabc6, 2, a, c, b8, 1, c, a, b;3.4 栈与递归的实现栈与递归的实现层 从第3层前往后，从断点开场执行，执行语句