栈-精选课件(设计).ppt

栈与递归的实现_C函数调用 调用前： 实参，返回地址等传递给被调用函数保存； 为被调用函数的局部变量分配存贮区； 将控制转移到被调用函数； 函数执行结束： 保存结果； 释放数据； 根据保存的地址，返回调用函数； 栈与递归的实现 递归？ 递归函数 直接或间接调用自己的函数。 例如阶乘 n! = n * ( n - 1 ) * … * 1; n! = n * ( n – 1 ) ! 栈与递归的实现 // 求n 的阶乘 unsigned long Fact( unsigned short n) { unsigned long l = 1; for( i = n; i 1; i-- ) { l *= i; } } unsigned long Fact( unsigned short n) { return n * Fact( n – 1 ); } 栈与递归的实现 // 求n 的阶乘 unsigned long Fact( unsigned short n) { if( n == 0 ) { return 1; } else { return n * Fact( n – 1 ); } } #define Fact( n ) ( (n) == 0 ) ? 1: (n) * Fact ( (n) - 1)) 栈与递归的实现_递归函数 递归函数执行的过程，实际就是函数嵌套调用，只是，在一系列函数调用过程中，被调用的函数始终是自己。 递归函数必须有出口，否则就是死循环 出口实际就是边界条件； 在C的函数调用中，最先被调用的函数，总是最后执行完，最后调用的函数，总是最先执行完。 若一个问题，可以使用递归，也可以不使用，则递归函数执行的效率通常情况下，比较低。 栈与递归的实现_Hanoi n阶Hanoi塔问题：假设有三个分别命名为X,Y,Z的塔座，在X塔座上插有n个直径大小各不相同，依小到大编号为1，2，。。。n的圆盘，要求：把X上的n个圆盘移到Z上，排列顺序相同，移动规则为： 每次只能移动一个园盘； 园盘可以在任一塔上做多次移动； 在任何时刻，大盘不能压小盘； X Y Z 栈与递归的实现_Hanoi 数学归纳法 n = 1, OK; 设n = k 时， 若可以以Y为辅助盘，把k个盘从X移动到Z; 当n = k + 1时，方法： 把X中k个盘，以Z为辅助盘，移动到Y; 把X中第k+1个盘，移动到X; 把Y中k个盘，以X为辅助盘，移动到Z; 栈与递归的实现_Hanoi // Hanoi, 把n个盘，从x移动到z，以y为辅助盘 void Hanoi( int n, char x, char y, char z ) { if( n == 1 ) { move( x, 1, z ); // 把1号盘，从x移到z } else { Hanoi( n – 1, x, z, y ); // 把n-1个盘，从x移到y，z为辅助塔 move( x, n, z ); // 把n号盘，从x移到z Hanoi( n – 1, y, x, z ); //把n-1个盘，从y移到z，x为辅助塔 } } 第三章 栈和队列 栈（Statck）概念和定义 定义：仅在表尾进行插入或删除操作的线性表； 栈就是操作受限制的线性表 概念： 栈顶：top， 表尾； 栈底：bottom，表头； 空栈；空表； 栈图示 a1 a2 a3 an … 栈顶top 栈底 bottom 表头 表尾 操作原则：后进先出（Last In First Out）, LIFO 先进后出 栈的ADT ADT Stack { 数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R={ai-1,ai|ai,ai-1∈D,i=2,…,n} 约定:an为栈顶，a1为栈底 基本操作： InitStack( S ); // 初始化栈; DestroyStack( S ); // 销毁栈； ClearStack( S ); // 清空栈; StackEmpty( S ); // 栈空？ StackLength( S ); // 栈长度； GetTop( S, e ); // 取栈顶元素； Push( S, e); // 把e插入到栈中，入栈； Pop( S, e ); // 删除栈元素，出栈； StackTraverse( S, visit( )); // 遍历 }// ADT Stack 栈的表示和实现 两种 顺序存贮结构__顺序栈； 链式存贮结构__链栈； 顺序栈概念 利用一组地址连续的存贮单元依次自栈底到栈顶存放栈的数据元