[理学]栈.ppt

递归函数的执行过程 张乃孝精讲“数据结构”——第四讲 栈 * 递归函数的执行过程 张乃孝精讲“数据结构”——第四讲 栈 * 递归函数的执行过程 张乃孝精讲“数据结构”——第四讲 栈 * 递归函数的执行过程 张乃孝精讲“数据结构”——第四讲 栈 * 递归函数的执行过程 张乃孝精讲“数据结构”——第四讲 栈 * 递归函数的执行过程 张乃孝精讲“数据结构”——第四讲 栈 * 递归函数的执行过程 张乃孝精讲“数据结构”——第四讲 栈 * 递归函数的执行过程 张乃孝精讲“数据结构”——第四讲 栈 * 递归函数的执行过程 张乃孝精讲“数据结构”——第四讲 栈 * 递归函数的执行过程 张乃孝精讲“数据结构”——第四讲 栈 * 递归函数的执行过程 张乃孝精讲“数据结构”——第四讲 栈 * 张乃孝精讲“数据结构”——第四讲 栈 * 递归函数到非递归函数的转换 一般来说，函数调用的实现可以分解成下列三步来进行：?(1)??? 传送调用信息。(2)??? 分配被调函数需要的数据区，并接收传送来的调用信息。(3)??? 把控制转移到被调函数的入口。 当被调函数运行结束，需要返回到调用函数时，一般的返回处理也可以分解成下列三步：(1)??? 传送返回信息。(2)??? 释放被调函数的数据区。(3)??? 把控制按返回地址转移到调用函数中去。 张乃孝精讲“数据结构”——第四讲 栈 *  在非递归调用的情况下，数据区的分配可以在程序运行前进行，一直到整个程序运行结束才释放，这种分配称为静态分配。 在递归调用的情况下，被调函数的局部量不能分配给固定的某些单元，而必须每调用一次就分配一份，当前程序使用的所有的量（包括形参、局部变量和中间工作单元等），都必须是最近一次递归调用时所分配的数据区中的量。即所谓的动态分配。 递归函数到非递归函数的转换（续） 张乃孝精讲“数据结构”——第四讲 栈 * 动态分配通常的处理方法是：在内存中开辟一个存储区域称为运行栈（或简称栈）. 每次调用时，将动态区指针下推，分配被调函数所需的数据区； 在每次返回时，将内存指针上托，释放本次调用所分配的数据区，恢复到上次调用所分配的数据区中； 被调函数中变量地址全部采用相对于动态区指针的位移量来表示（称为相对地址）。 递归函数到非递归函数的转换（续） 张乃孝精讲“数据结构”——第四讲 栈 * 根据上述思想，不难给出算法4.9阶乘计算的非递归算法。 因为只有一处递归调用，返回地址（locate）和返回值(fact)都容易控制，而且局部量(res)与参数(n)关系十分清楚，所以栈中只要保存一个参数n的值就可以了。 阶乘计算的非递归算法 张乃孝精讲“数据结构”——第四讲 栈 * int nfact( int n ) {  int res; PSeqStack st; /* 使用顺序存储结构实现的栈 */  st = createEmptyStack_seq( );  while (n0) { push_seq(st,n); n = n – 1; } res = 1; while (! isEmptyStack_seq(st)) {res = res * top_seq(st); pop_seq(st); }  free(st); return ( res );} fact( int n )非递归函数(示意) 张乃孝精讲“数据结构”——第四讲 栈 * 迷宫问题 迷宫可用下页的左图所示的方块来表示，其中每个元素或为通道（以空白方块表示），或为墙（以带阴影的方块表示）。 迷宫问题要求的就是：从入口到出口的一个以空白方块构成的(无环)路径。 张乃孝精讲“数据结构”——第四讲 栈 * 张乃孝精讲“数据结构”——第四讲 栈 *  求解迷宫问题的思路： 从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行探索，直到所有可能的通路都探索到为止。 这类方法统称回溯法 张乃孝精讲“数据结构”——第四讲 栈 * 回溯法 从入口出发，采用试探方法，有哪些信誉好的足球投注网站到目标点(出口)的路径 遇到出口则成功结束 遇到分支点时选一个方向向前探索。这时需记录当时的分支点和在这里已试探过的分支(和尚未试探过的分支) 若遇到死路(所有方向都不能走或已试探过)，就退回前一分支点，换一方向再探索。直到找到目标，或者所有可能通路都探索到为止 张乃孝精讲“数据结构”——第四讲 栈 * 算法4.11 回溯法求迷宫问题一个解的框架： mazeFrame( void ) { 创建一个（保存探索过程的）空栈； 把入口位置压入栈中; while 栈不空时{ 取栈顶位置并设置为的当前位置;