数据结构基础第4章栈和队列幻灯片.ppt

void main() { HuiWen(“ABCDEDCBA” ); HuiWen(“123abcabc321”); } main ( ) { ? f=fac(3); ? } fac(3) { ? f=3.fac(2); return f; } fac(2) { ? f=2?fac(1); return f; } fac=3! n=4 n=3 fac=2! fac(1) { ? f=1?fac(0); return f; } fac(0) { ? return 1; ? } n=1 fac=1 n=2 fac=1! 堆栈变化: 3, addr1 2, addr2 3, addr1 2, addr2 1, addr2 3, addr1 2, addr2 1, addr2 0, addr2 3, addr1 2, addr2 1, addr2 ….. Main?fac(3) fac(3)?fac(2) fac(2)?fac(1) fac(1)?fac(0) fac(1) 3, addr1 递归算法的效率分析 若循环方式的算法和递归方式的算法均能求解某问题时，通常循环方式算法的时间与空间效率均比递归方式算法要高很多。 如：n阶乘递归算法的时间复杂度与空间复杂度均为O(n)，而非递归算法的空间复杂度为O(1)，时间复杂度虽仍为O(n)，但常数因子要小许多。 long fac( int n ) { // 求n阶乘的非递归算法，设n是大于等于0的正整数 int i; long f=1; for ( i=2; i=n; i++) f = f*i; return f; } 三、递归算法的设计方法 递归既是一种有效的分析问题的方法，也是一种有效的算法设计方法。 设计递归算法的方法： 把对原问题的求解设计成包含对子问题求解的形式； （即较复杂的问题转换为较简单的问题） 设计递归出口； （简单到一定程度，直接给出结果） 例：汉诺(hannoi)塔问题 问题描述： 设有三根标号为A,B,C的柱子，在A柱上放n个盘子，每个盘子都比下面的略小一点，要求把A柱上的盘子全部移到C柱上，移动规则是： 一次只能移动一个盘子； 移动过程中大盘子不能放在小盘子上面； 在移动过程中盘子可以放在A,B,C的任意一个柱子上。 算法描述: void Towers( int n, char a, char b, char c ) { // 把n个盘从a移到c， b为辅助 if (n == 1) printf(“%c ? %c\n”, a, c); else { Towers( n-1, a, c, b ); printf( “%c ? %c\n”, a, c ); Towers( n-1, b, a, c ); } } 算法复杂度分析： 令把n个盘按规则移动所需的时间为：T(n),则 1 若 n=1 T(n) = 2T(n-1) + 1 其他情形 解上面的递推方程可得： T(n) = O(2n) 一、队列的基本概念： 队列也是一种操作受限的线性表，只允许在表的一端进行插入（表尾），在表的另一端进行删除（表头）。 术语：队头、队尾、进（入）队列、出（离）队列、空队列。 a1 a2 an ??? 队头 队尾 出队列 进队列 先进先出(FIFO)的线性表 4.7 队列 二、队列的抽象数据类型的定义： ADT QUEUE is Data： n (n=0) 个相同类型数据元素a1, a2, …， an 构成的有限序列。用类型名 QueueType 表示。 Operation:： ： void InitQueue (QueueType Q); //构造一个空队列 Q int EmptyQueue (QueueType Q); //判断队列Q是否为空 vo