据结构 从被调用函数返回调用函数之前,系 统需先完成三件事: 保存被调函数的计算结果; >释放被调函数的数据区; 依照被调函数保存的返回地址将控制转 栈和队列 移到调用函数 嵌套调用时,按照“后调用先返回” 的原则 >栈的应用—递归和非递归 据 构 函数之间的信息传递和控制转移必须通过 “栈”来实现:系统将整个程序运行时所 需的数据空间安排在一个栈中,每当调用 一个函数时,就为它在栈顶分配一个存储 栈和队列 区;每当从一个函数退出时,就释放它的 存储区,则当前正运行的函数的数据区必 在栈顶。(Page56)
6 数 据 结 构 之 栈 和 队 列 11 ¾ 从被调用函数返回调用函数之前，系 统需先完成三件事： ¾保存被调函数的计算结果； ¾释放被调函数的数据区； ¾依照被调函数保存的返回地址将控制转 移到调用函数。 ¾ 嵌套调用时，按照“后调用先返回” 的原则 数 据 结 构 之 栈 和 队 列 12 ¾ 栈的应用——递归和非递归 ¾ 函数之间的信息传递和控制转移必须通过 “栈”来实现：系统将整个程序运行时所 需的数据空间安排在一个栈中，每当调用 一个函数时，就为它在栈顶分配一个存储 区；每当从一个函数退出时，就释放它的 存储区，则当前正运行的函数的数据区必 在栈顶。 ( Page 56 )
据结构 递归函数的运行过程类似于多个函数 的嵌套调用 递归函数的运行的“层次” 栈和队列 13 例1.已知f(m,n)函数(m,n均为自然数)的定义 数据结构 如下 m+n+1 (m*n=0) f(m, n)= f(m-1,f(m,n-1)(m*n≠0) (1)写出计算f(m,n)的递归算法。 和(2)利用堆栈改写出非递归算法。 队 列(3)根据非递归算法,画出计算f(2,1)时 值参、局部变量以及堆栈的变化情况 14
7 数 据 结 构 之 栈 和 队 列 13 ¾ 递归函数的运行过程类似于多个函数 的嵌套调用 ¾ 递归函数的运行的“层次” 数 据 结 构 之 栈 和 队 列 14 例1.已知f(m,n)函数(m,n均为自然数)的定义 如下： m+n+1 (m*n=0) f(m,n)= f(m-1,f(m,n-1)) (m*n≠0) ( 1)写出计算f(m,n)的递归算法。 ( 2)利用堆栈改写出非递归算法。 ( 3)根据非递归算法，画出计算f(2,1)时 值参、局部变量以及堆栈的变化情况