Microsoft PowerPoint - DS_Ch4_EN [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - DS_Ch4_EN [兼容模式]"

佳含罕俞
6 years ago
Views:

1 Data Structure Ch.4 Recursion Dr. He Emil Huang School of Computer Science and Technology Soochow University 苏州大学计算机科学与技术学院网络工程系本章 ppt 与教材对应情况本章涉及所有内容涵盖了教材以下章节 Chapter 5 ( 递归,Recursion) Question: 递归与数据结构课程体系的关系? 递归在计算机科学中是一个很重要的工具, 在数据结构中可以用来解决树形结构定义以及树的遍历等问题递归用简练的语句描述一些复杂的算法, 代码紧凑, 简单明了, 易于编写和理解 huangh@suda.edu.cn What is Recursion 3 Relation of Function-call and Recursion What must be done when function-call happened? 函数被调用时, 系统应该做什么? Remember the place where the call was made ( 保存调用点 - 返回地址 ), so that it can return there after the function is complete; Remember all the local variables, processor registers and etc. ( 局部变量寄存器等 ), so that the information will not be lost while the function is working. 栈区 (stack): 由编译器自动分配和释放, 存放函数的参数值, 局部变量的值等操作方式类似于数据结构中的栈我们将函数的所有入栈信息看成一个数据结构, 这种结构可以被称为 Invocation record (activation record) ( 调用记录, 活动记录, 栈帧 stack frame) Relation of Function-call and Recursion Stack frame for function calls How Recursion Works Process illustration invocation record for Main Tree of function calls 1

$void foo(int x, int y, int z){ printf("x = %d at [%X]\n", x, &x); printf("y = %d at [%X]\n", y, &y); printf("z = %d at [%X]\n", z, &z); int main(int argc, char *argv[]){ foo(100, 200, 300); return 0;$

2 void foo(int x, int y, int z){ printf("x = %d at [%X]\n", x, &x); printf("y = %d at [%X]\n", y, &y); printf("z = %d at [%X]\n", z, &z); int main(int argc, char *argv[]){ foo(100, 200, 300); return 0; What is Recursion? 递归是一种强有力的数学工具, 可使问题的描述和求解变得简洁与清晰递归 : 若一函数过程或数据结构定义的内部又直接或间接使用了定义本身, 则称它们是递归的, 或递归定义的 7 8 What is Recursion? What is Recursion? 阶乘 n! 的定义如下 : 1 当 n=0 时 n!= n(n-1)! 当 n>0 时函数 n! 的定义中引用自身, 即 (n 1)! 9 Recursion is the name for the case when a function invokes itself ( 直接递归, 如果一个函数在其定义体内直接调用自己, 则称直接递归函数 ) invokes a sequence of other function, one of which eventually invokes the first function again( 间接递归, 如果一个函数经过一系列的中间调用语句, 通过其它函数间接调用自己, 则称间接递归函数 ) int fun(int n){ if (n<=1) return n; return n*fun(n-1); int fun1(int n){ if (n<=1) return n; return(fun2(n)); int fun2(int n){ return (n*fun1(n-1)); Some instances of the Recursion 2. Some instances of the Recursion 以下三种情况下, 常常需要用到递归的方法定义是递归的,e.g. 阶乘数据结构是递归的问题的解法是递归的,e.g. Hanoi 11 2

3 Some Instances of Recursion 1 例 1:Bakus-Naur Form (BNF) 巴科斯 - 诺尔范式早期定义 Algol 60 语法 1 直接递归 < 标识符 > ::= < 字母 > < 标识符 >< 字母 > < 标识符 >< 数字 > < 字母 > ::= a b y z < 数字 > ::= Some Instances of Recursion 2 递归算法设计 ( 分治法 ) 分解求解组合 step1: 将原问题分解为一个或多个规模更小, 但与问题特性类似的子问题 ( 递归步骤 ) // 解子问题为调用语句 step2: 确定一个或多个无须分解, 可直接求解的最小子问题 ( 终结条件 ) // 归纳基础非终结符终结符可选分隔符由此定义的标识符是由字母打头的字母数字串 2 间接递归 < 表达式 > ::= < 项 > + < 项 > < 项 > - < 项 > < 项 > < 项 > ::= < 因子 > * < 因子 > < 因子 > / < 因子 > < 因子 > < 因子 > ::= (< 表达式 >) < 字母 > < 数字 > 合法的表达式 :A+5,B*C+D,(A+B*C)/D 13 例 2:Factorials // 递归终结条件 // 递归步骤 (n-1)! 的规模比 n! 小 1 14 分治法分治法与软件设计的模块化方法类似为了解决一个大的问题, 将一个规模为 n 的问题分解为规模较小的子问题, 这些子问题互相独立并且和原问题相同分别解这些子问题, 最后将将各个子问题的解合并得到原问题的解子问题通常与原问题相似, 可以递归地使用分治策略来解决 Some Instances of Recursion 2 int F (int n) { // 设 n 为非负整数 if (n==0) return 1; else return n*f(n-1) ; 至少有一个直接求解的最小子问题, 保证递归终止, 否则无限循环分解为一个子问题, 若 F(n) 是解 n!, 则 F(n-1) 可解 (n-1)! 15/44 16 Factorials: A Recursive Definition 1 if ( n 0) n! n ( n 1)! if( n 0) 4!=4 3!=4 (3 2!)=4 (3 (2 1!)) =4 (3 (2 (1 0!))) =4 (3 (2 (1 1))) =4 (3 (2 1)) =4 (3 2) =4 6 =24 递归层次 : main() fac(5) 输出第一层 fac n=5 p=5*fac(4) fac(5)=120 第二层 fac n=4 p=4*fac(3) fac(4)=24 第三层 fac n=3 p=3*fac(2) fac(3)=6 第四层 fac n=2 p=2*fac(1) fac(2)=2 第五层 fac n=1 p=1 fac(1)=1 假设调用该递归函数的主函数为第 0 层, 则从主函数调用递归函数为进入第 1 层 ; 从第 i 层递归调用本身为进入下一层, 即第 i+1 层反之, 退出第 i 层递归应返回至上一层, 即第 i- 1 层 18/44 3

Factorials: A Recursive Definition Every recursive process consists of two parts: A smallest, base case that is processed without recursion; ( 非递归部分 ) A general method that reduces a particular case

( 递归部分 ) Programmers must look at the big picture and leave the detailed computations to the computer. 例 3:n 阶 Hanoi 塔问题将 X 上的圆盘移到 Z 上, 要求按同样次序排列, 且满足 : 1. 每次只能移动一片 2. 圆盘可插在 X,Y,Z 任一塔座上 3.

4 Factorials: A Recursive Definition Every recursive process consists of two parts: A smallest, base case that is processed without recursion; ( 非递归部分 ) A general method that reduces a particular case to one or more of the smaller cases, thereby making progress toward eventually reducing the problem all the way to the base case. ( 递归部分 ) Programmers must look at the big picture and leave the detailed computations to the computer. 例 3:n 阶 Hanoi 塔问题将 X 上的圆盘移到 Z 上, 要求按同样次序排列, 且满足 : 1. 每次只能移动一片 2. 圆盘可插在 X,Y,Z 任一塔座上 3. 任一时刻大盘不能压在小盘上 20 n 阶 Hanoi 塔问题 Hanoi(n, x, y, z), 当 n=0 时, 没盘子可供移动, 什么也不做 ; 当 n=1 时, 可直接将 1 号盘子从 x 轴移动到 z 轴上 ; 当 n=2 时, 可先将 1 号盘子移动到 y 轴, 再将 2 号盘子移动到 z 轴, 最后将 1 号盘子移动到 z 轴 ; 对于一般 n>0 的一般情况可采用如下分治策略进行移动 (1) 将 1 至 n-1 号盘从 x 轴移动至 y 轴, 可递归求解 Hanoi(n-1, x, z, y); (2) 将 n 号盘从 x 轴移动至 z 轴 ; (3) 将 1 至 n-1 号盘从 y 轴移动至 z 轴, 可递归求解 Hanoi(n-1, y, x, z) 21/44 1 分解设 n>1 原问题 : 将 n 片从 X 移到 Z,Y 为辅助塔, 可分解为 : I. 将上面 n-1 个盘从 X 移至 Y,Z 为辅助盘 II. 将 n th 片从 X 移至 Z III. 将 Y 上 n-1 个盘子移至 Z,X 为辅助盘 2 终结条件 n = 1 时, 直接将编号为 1 的盘子从 X 移到 Z void Hanoi (int n, char x, char y, char z ) { // n 个盘子从 X 移至 Z,Y 为辅助 if ( n==1 ) move(x,1,z); // 将 1 号盘子从 X 移至 Z, 打印 else { Hanoi (n-1,x,z,y); // 源 X, 辅 Z, 目 Y move (x,n,z); Hanoi (n-1,y,x,z); // 源 Y, 辅 X, 目 Z // 子问题特征属性与原 // 问题相同规模小 1, 参 // 数不同 22 分析 Hanoi 塔问题移动圆盘的次数设 T(n) 表示 n 个圆盘的 Hanoi 塔问题移动圆盘的次数, 显然 T(0)=0, 对于 n>0 的一般情况采用如下分治策略 : (1) 将 1 至 n-1 号盘从 X 轴移动至 Y 轴, 可递归求解 Hanoi(n-1, X, Z, Y); (2) 将 n 号盘从 X 轴移动至 Z 轴 ; (3) 将 1 至 n-1 号盘从 Y 轴移动至 Z 轴, 可递归求解 Hanoi(n-1, Y, X, Z) 在 (1) 与 (3) 中需要移动圆盘次数 T(n-1),(2) 需要移动一次圆盘可得如下的关系 : T(n)=2T(n-1)+1 展开上式可得 : T(n) =2T(n-1)+1 =2[2T(n-2)+1]+1 使用 O(2 n ) 限界 =2 2 T(n-2)+1+2 =2 n T(n-n) n-1 23/44 =2 n -1 The Problem move(64,1,3,2) move 64 disks from tower 1 to tower 3 using tower 2 as temporary storage. One disk can be moved at a time and no disk is ever allowed to be placed on top of a smaller disk. 4

5 The Solution Concentrate our attention not on the first step, but rather on the hardest step: moving the bottom disk. //***************************************************// move(63,1,2,3); //move 63 disks from tower 1 to 2 // using tower 3 as temporary storage cout<< Move disk 64 from tower 1 to tower 3. <<endl; move(63,2,3,1); //move 63 disks from tower 2 to 3 //using tower 1 as temporary storage //**************************************************// Divide and Conquer: To solve a problem, split the work into smaller and smaller parts, each of which is easier to solve than the original problem. const int disks=64; // 问题规模为 64 void move(int count, int start, int finish, int temp); main( ){ move(disks,1,3,2); // 将总数为 disks 数量的盘子由柱 1 移至柱 3, 借助柱 2 void move(int count, int start, int finish, int temp){ if (count>0){ move(count-1,start,temp,finish); cout<< Move disk <<count<< from <<start<< to <<finish <<. <<endl; move(count-1,temp,finish,start); Tracing move(int count, int start, int finish, int temp){ 1 if (count>0){ 2 move(count- 1,start,temp,finish); 3 cout<< Move disk <<count<< from <<start<< to <<finish<<. <<endl; 4 move(count- 1,temp,finish,start); Analysis 移动次数 :3 次圆盘移动次数 :1+2+4=7 次会画递归树 64 个圆盘所需搬动次数 : = =1.6*10 19 次如每秒移动一次, 所需时间 :5*10 11 years Astronomers estimate the age of the universe at less than (2*10 10 ) years 有些问题表面上不是递归定义的, 但可通过分析, 抽象出递归的定义例 4: 写一个就地生成 n 个元素 a 1,a 2,,a n 全排列 (n!) 的算法, 要求算法终止时保持 a 1,a 2,,a n 原状解 : 设 A[0..n-1] 基类型为 char, 就地不允许使用 A 以外的数组 1 生成 a 1, a 2,, a n 全排列 n 个子问题求 n-1 个元素的全排列 + n th 个元素 1 st 子问题 a 1, a 2,, a n-1 a n // 2 nd 子问题 a 1,, a n-2, a n a n-1 //A[n-2] A[n-1] 3 rd 子问题 a 1,, a n, a n-1 a n-2 //A[n-3] A[n-1] n th 子问题 a n,a 2, a n-1 a 1 //A[0] A[n-1] 2 递归终结分支当 n=1 时, 一个元素全排列只有一种, 即为本身实际上无须进一步递归, 可直接打印输出 A 30 5

6 3 算法 : 以 A[0..7] 为例 void permute (char A[ ], int n) { // 外部调用时令 n=7 if (n==0) print (A); // 打印 A[0 7] else { permute(a,n-1); // 求 A[0..n-1] 的全部排列 1 st 子问题不用交换 for (i=n-1; i>0; i--) { Swap(A[i], A[n]); // 交换 a i 和 a n 内容, 说明为引用 permute(a,n-1); // 求 A[0..n-1] 全排列 Swap(A[i],A[n]); // 交换, 恢复原状 //endfor //endif 时间 : 所以实验时,n 不能太大 31 递归函数的一般形式 : void Pname( 参数表 ){ if ( 条件 ) 递归出口简单操作 ; else { 简单操作 ; Pname ( 实参表 ); 可能有多次的调用递归出口是 n==0 简单操作 ; [Pname ( 实参表 ); 简单操作 ;] 函数也可以是其他类型 ; 调用方式自然也不同例如 : 在阶乘函数 int fact(int n){ if ( n == 0 ) return 1; else return n * fact( n 1 ); 32 递归的内部实现 3. How Recursion Works? C/C++ 语言内部实现机理 : 一段可执行的 C/C++ 程序代码在内存中分为 4 个区域组成 : 代码段 : 包含程序运行时执行的机器指令 ; 静态数据区 (Static): 程序生命期内一直存在的数据, 全局变量 ; 堆 (Heap): 程序运行时动态分配的存储空间,e.g. malloc 分配内存 ; 栈 (Stack): 函数调用的信息. 函数调用时会产生一个活跃记录 ( 或活动记录 ), 将一直存在栈中直至函数调用结束栈的应用 3. 递归的内部实现 1 调用调用一个函数时, 系统将为调用者构造一个活动记录, 并将其压入栈的顶, 然后将程序控制权转移到被调用函数若被调用函数有局部变量, 则在栈顶也要为其分配空间, 形成一个活动结构实际上所有的递归或非递归函数都是这样实现的活动结构 : 局部变量活动记录 : 参数表的内容为实参返址为函数调用语句的下一指令的位置递归的内部实现 2 返回当被调用函数执行完毕时, 系统将活动结构退栈, 并根据退栈返回地址将程序控制权转移给调用者继续执行例 : F(4) 为例 Ret L1 void main(void) { int n; Ret L1: 赋值语句的地址 Ret L2: 计算乘法的地址 n = F(4); // 调用引起压栈为简单起见, 假设局部变量不入栈改写 : int F (int n) { Ret L2 int temp; if (n==0) return 1; // 返回语句引起退栈 else { // 调用 F(n-1) 引起入栈 temp = n*f(n-1); return temp; // 退栈 36 6

7 3. 递归的内部实现 * 执行返回指令 Ret L2: temp=1*1; // 从 F(0) 返回 0! = 1 是递归终结条件, 故执行 F(0) 引起返回 (return 1) 退栈, 返回到 F(1) 的 Ret L2 处, 继续执行 temp = 1*1; 按着执行 return temp 又引起退栈, 返回到 F(2) 的 Ret L2 处, 执行 temp = 2*1, How Recursion Works Data Structures: Stacks and Trees The time requirement of the program is related to the number of functions are done, and therefore to the total number of vertices in the tree. ( 时间需求与调用树中结点数成正比 ) The space requirement is reflected in the height of the tree. ( 空间需求与树的高度成正比 ) Correctness of the Recursion 4. 递归算法的正确性初学者很难相信递归程序的正确性原因 : 一个函数尚未完成 ( 即对本函数的正确性还未确信 ) 时又调用了自身, 故对递归函数正确性缺乏信心例 : 非递归函数或过程假设 Q 正确的情况下, 证明了 P 正确, 则一旦证明了被调过程 Q 是正确的, 我们就对 P 的正确性深信不疑! 由于 P Q 各自独立, 独立于 P 来证明 Q 的正确性很容易, 这大概是对自己写非递归程序较有信心的缘故递归算法的正确性若 P 是递归过程, 则不可能独立于 P 来证明被调过程 ( 亦自身 ) 是否正确因此, 我们只能假设过程 P 内部所有递归的调用是正确的 ( 不考虑其内部实现细节 ), 才能由此证明 P 的正确性其理论依据是数学归纳法 : (1) 证明参数满足递归终结条件时函数或过程正确 ( 相当于归纳基础 ) (2) 假设过程函数内部的所有递归调用语句正确 ( 相当于归纳假设 ), 由此证明过程正确或函数是正确的 ( 相当于归纳步骤 ) Note: 函数内的递归调用语句的参数应比函数本身的参数更接近递归终结条件参数, 这样才能确保递归是可终止的递归程序的正确性证明证明下面的函数 fact(n) 所实现的是实现阶乘的功能, 即 fact(n) 函数如下 : int fact(int n){ if ( n == 0 ) return 1; else return n * fact( n 1 ); 证明 : (1) 当 n=0 时, 调用函数得到值为 1, 符合函数定义, 功能正确 (2) 假设 0 n<k 时, 函数正确, 即函数 fact(n) 的结果为 n(n-1)!, 则当 n = k > 0 时, 由程序可知 fact(n)=n*fact(n-1)=n* (n-1) (n-2)! = n* (n-1)!, 功能正确综上所述, 程序功能正确

8 5. Transition from Recursive Function to Non-recursive Function 递归程序到非递归程序的转换 Transition to the non-recursive function 选择递归还是非递归 : 采用递归方式实现问题的算法程序具有结构清晰读性好易于理解等优点, 但递归程序较之非递归程序无论是空间需求还是时间需求都更高, 因此在希望节省存储空间和追求执行效率的情况下, 人们更希望使用非递归方式实现问题的算法程序 43 44/44 递归程序到非递归程序的转换求解递归问题的两种方式背景 : 为何要将递归程序转换为等价的非递归程序? 递归程序虽然有良好的可读性, 但由于以下一些原因, 需要将递归程序转化为等价的非递归程序 : 时间花费空间开销一些编成环境的不支持, 或者编写起来复杂如何转换? 一种方式是重新设计 -- 没有利用已有的工作基础还有一种方式是对给定的递归程序, 用一组规则进行等价的转换 1. 在求解过程中直接求值, 无需回溯称这类递归问题为简单递归问题 ; 2. 另一类递归问题在求解过程中不能直接求值, 必须进行试探和回溯, 称这类递归问题为复杂递归问题转换方法不同 : 1. 简单递归问题可以采用递推方法直接求解 ; 2. 复杂递归问题由于要进行回溯, 在实现过程中必须借助栈来管理和记忆回溯点 3. 两种方法实现递归到非递归的转换 : 递推栈 45 46/44 (1) 简单递归问题非递归实现将原问题分解成若干结构与原问题相同, 但规模较小的子问题, 并建立原问题与子问题解之间的递推关系, 然后定义若干变量用于记录递推关系的每个子问题的解 ; 程序的执行便是根据递推关系, 不断修改这些变量的值, 使之成为更大子问题的解的过程 ; 当得到原问题解时, 递推过程便可结束了 factorial: recursive version int factorial (int n) /* Pre: n is a nonnegative integer. Post: Return the value of the factorial of n. */ { if (n == 0) return 1; else return n * factorial(n 1); 47/44 8

9 the recursive program will set up a stack and fill it with the n numbers n, n 1, n 2,, 2, 1 as it works its way out of the recursion, multiply these numbers in the same order as does the second program. The progress of execution for the recursive function applied with n = 5 is as follows: factorial(5) = 5 * factorial(4) = 5 * (4 * factorial(3)) = 5 * (4 * (3 * factorial(2))) = 5 * (4 * (3 * (2 * factorial(1)))) = 5 * (4 * (3 * (2 * (1 * factorial(0))))) = 5 * (4 * (3 * (2 * (1 * 1)))) = 5 * (4 * (3 * (2 * 1))) = 5 * (4 * (3 * 6)) = 5 * (4 * 6) = 5 * 24 = 120. Thus the recursive program keeps more storage than the iterative version, and it will take more time as well, since it must store and retrieve all the numbers as well as multiply them. iterative version: int factorial(int n) /*Pre: n is a nonnegative integer. Post: Return the value of the factorial of n. */ { int count, product = 1; // 将变量 product 初始化为 factorial(0) 的值 */ for (count = 1; count <= n; count++) product *= count; // 根据递推关系进行递推 return product; Recursive function int fibonacci (int n) /* fibonacci : recursive version Pre: The parametern is a nonnegative integer. Post: The function returns then th Fibonacci number. */ { if (n <= 0) return 0; else if (n == 1) return 1; else return fibonacci(n 1) + fibonacci(n 2); Non-recursive function P179 int fibonacci(int n) /* fibonacci : iterative version*/ { int last_but_one; // second previous Fibonacci number, F i 2 int last_value; // previous Fibonacci number, F i 1 int current; // current Fibonacci number F i if (n <= 0) return 0; else if (n == 1) return 1; else { last_ but_ one = 0; last_ value = 1; for (int i = 2; i <= n; i++) { current = last_but_one + last_value; last_but_ one = last_value; last_value = current; return current; (2) 复杂递归程序到非递归程序的转换复杂递归问题在求解的过程中无法保证求解动作一直向前, 往往需要设置一些回溯点, 当求解无法进行下去或当前处理的工作已经完成时, 必须退回到所设置的回溯点, 继续问题的求解因此, 在使用非递归方式实现一个复杂递归问题的算法时, 经常使用栈来记录和管理所设置的回溯点 6. Tail Recursion 53/

10 Tail Recursion Tail recursion A recursive call is the last-executed statement of the function, which is called tail recursion. 如果一个函数中所有递归形式的调用都出现在函数最末尾, 我们称这个递归为尾递归 (Q: 前面的 factorial 递归程序是尾递归吗??) 当递归调用是整个函数体中最后执行的语句, 且它的返回值不属于表达式的一部分尾递归 feature of tail recursion (P): Since each call by P to itself is its last action, there is no need to maintain the storage areas after returning from the call. (see Figure of the next-next page) the calls to P as repeated in iterative fashion on the same level of the diagram. Tail Recursion Tail Recursion 与普通递归相比具有的优势 : 尾递归效率更高, 当编译器检测到一个函数调用属于尾递归时, 覆盖当前活跃记录而不是在栈中创建新的活跃记录因为递归调用是当前活跃期内最后一条待执行语句, 当这个调用返回时, 栈帧中并没有其他事情可做, 因此没有必要保存栈帧 ; 栈空间大大缩减, 效率更高 ; 大多数编译器会利用这种特点自动生成优化的代码, GCC, 但是请注意 C++, python, C#, java 并不默认对尾递归进行优化 ; When a compiler detects a call that is tail recursive, it overwrites the current activation record instead of pushing a new one onto the stack. Tail Recursion Q: 将递归求解 n! 递归程序转化为尾递归 Tail Recursion Notes on tail recursion If space considerations are important, tail recursion should often be removed. ( 空间要求较高时, 可以消除尾递归 ) Instance: Hanoi Tower void move(int count, int start, int finish, int temp){ int swap; while (count>0){ move(count-1,start,temp,finish); // 非尾递归, 保留 cout<< Move disk <<count<< from <<start << to <<finish <<. << endl; count--; //change parameters to mimic the second recursive call. swap=start; start=temp; temp=swap; 机械地将任何一个递归程序转换为与其等价的非递归程序五条规则 : (1) 设置一个栈 ( 不妨用 S 表示 ), 并且开始时将其置为空 (2) 在子程序入口处设置一个标号 ( 不妨设为 L0) (3) 对子程序中的每一递归调用, 用以下几个等价操作来替换 : a) 保留现场 : 开辟栈顶存储空间, 用于保存返回地址 ( 不妨用 b) Li,i=1,2,3, ) 调用层中的形参和局部变量的值( 最外层调用不必考虑 ) c) 准备数据 : 为被调子程序准备数据, 即计算实在参数的值, 并赋给对应的形参 d) 转入 ( 子程序 ) 执行, 即执行 goto L0 e) 在返回处设一个标号 Li(i=1,2,3, ), 并根据需要设置以下语句 : 若函数需要返回值, 从回传变量中取出所保存的值并传送到相应的位置 60 10

11 (4) 对返回语句, 可用以下几个等价操作来替换 : 如果栈不空, 则依次执行如下操作, 否则结束本子程序, 返回 a) 回传数据 : 若函数需要返回值, 将其值保存到回传变量中 b) 恢复现场 : 从栈顶取出返回地址 ( 不妨保存到 X 中 ) 及各变量形参值, 并退栈 c) 返回 : 按返回地址返回 ( 即执行 goto X) (5) 对其中的非递归调用和返回操作可照搬 61 11

Microsoft PowerPoint - Ch3 [兼容模式]

Microsoft PowerPoint - Ch3 [兼容模式] Ch.3 栈和队列 1 3.1 栈定义和运算栈仅在表的一端插删的线性表插入进 ( 入 ) 栈删除出 ( 退 ) 栈栈顶插删的一端栈底另一端结构特征 -- 后进先出修改原则 : 退栈者总是最近入栈者服务原则 : 后来者先服务 (LIFO 表 ) 例 : 入栈出栈 a n a 2 a 1 2 3.1 栈 Note: 后入栈者先出栈, 但不排除后者未进栈, 先入栈者先出栈 an,,