Microsoft PowerPoint - Slides04_第三章（1） 栈.ppt [兼容模式]

Transcription

1 第三章栈 队列 数组 栈 (Stack) 基本概念 顺序存储结构 链式存储结构 应用 队列 (Queue) 基本概念 顺序存储结构 链式存储结构 应用 特殊矩阵 (Matrix) 的压缩存储

2 栈 ( Stack ) 只允许在一端插入和删除的线性表 允许插入和删除的一端称为栈顶 (top), 另一端称为栈底 (bottom) 退栈 (pop) 进栈 (push) 特点后进先出 (LIFO) bottom top a n-1 a n-2 a 0

3 栈的抽象数据类型 template <class E> class Stack { // 栈的类定义 public: Stack(){ }; // 构造函数 virtual void Push(E x) = 0; // 进栈 virtual bool Pop(E& x) = 0; // 出栈 virtual bool gettop(e& x) = 0; // 取栈顶 virtual bool IsEmpty() = 0; // 判栈空 virtual bool IsFull() = 0; // 判栈满 };

4 栈的数组存储表示 顺序栈 elements maxsize-1 top ( 栈空 )

5 #include <assert.h> #include <iostream.h> #include stack.h 顺序栈类的定义 template <class E> class SeqStack : public Stack<E> { // 顺序栈类定义 private: E *elements; // 栈元素存放数组 int top; // 栈顶指针 int maxsize; // 栈最大容量 void overflowprocess(); // 栈的溢出处理

6 public: SeqStack(int sz =50); // 构造函数 ~SeqStack() { delete []elements; } // 析构函数 }; void Push(E x); // 进栈 bool Pop(E& x); // 出栈 bool gettop(e& x); // 取栈顶内容 bool IsEmpty() const { return top == -1; } bool IsFull() const { return top == maxsize-1; }

7 top 空栈 top a a 进栈 top a b b 进栈 top e d c b a top e d c b a top e d c b a e 进栈 f 进栈溢出 e 退栈

8 top d c b a d 退栈 top c b a c 退栈 top b a b 退栈 top a a 退栈 top 空栈

9 顺序栈的操作 template <class E> void SeqStack<E>::overflowProcess() { // 私有函数 : 当栈满则执行扩充栈存储空间处理 E *newarray = new E[2*maxSize]; // 创建更大的存储数组 for (int i = 0; i <= top; i++) newarray[i] = elements[i]; maxsize += maxsize; delete [ ]elements; elements = newarray; // 改变 elements 指针 };

10 template <class E> void SeqStack<E>::Push(E x) { // 若栈不满, 则将元素 x 插入该栈栈顶, 否则溢出处理 if (IsFull( ) == true) overflowprocess( ); // 栈满 elements[++top] = x; // 栈顶指针先加 1, 再进栈 }; template <class E> bool SeqStack<E>::Pop(E& x) { // 函数退出栈顶元素并返回栈顶元素的值 if (IsEmpty() == true) return false; x = elements[top--]; // 栈顶指针退 1 return true; // 退栈成功 };

11 template <class E> bool Seqstack<E>::getTop(E& x) { // 若栈不空则函数返回该栈栈顶元素的值 if (IsEmpty() == true) return false; x = elements[top]; return true; };

12 双栈共享一个栈空间 V 0 maxsize-1 b[0] t[0] t[1] b[1] 两个栈共享一个数组空间 V[maxSize] 设立栈顶指针数组 t[2] 和栈底指针数组 b[2] t[i] 和 b[i] 分别指示第 i 个栈的栈顶 (top) 与栈底 (bottom) 初始 t[0] = b[0] = -1, t[1] = b[1] = maxsize 栈满条件 :t[0]+1 == t[1] // 栈顶指针相遇 栈空条件 :t[0] = b[0] 或 t[1] = b[1] // 退到栈底

13 bool push(dualstack& DS, Type x, int i) { if (DS.t[0]+1 == DS.t[1]) return false; if (i == 0) DS.t[0]++; else DS.t[1]--; DS.V[DS.t[i]] = x; return true; } bool Pop(DualStack& DS, Type& x, int i) { if (DS.t[i] == DS.b[i]) return false; x = DS.V[DS.t[i]]; if (i == 0) DS.t[0]--; else DS.t[1]++; return true; }

14 栈的链接存储表示 链式栈 top 链式栈无栈满问题, 空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 适合于多栈操作

15 链式栈 (LinkedStack) 类的定义 #include <iostream.h> #include stack.h template <class E> struct StackNode { // 栈结点类定义 private: E data; // 栈结点数据 StackNode<E> *link; // 结点链指针 public: StackNode(E d = 0, StackNode<E> *next = NULL) : data(d), link(next) { } };

16 template <class E> class LinkedStack : public Stack<E> { // 链式栈类定义 private: StackNode<E> *top; // 栈顶指针 void output(ostream& os, StackNode <E> *ptr, int& i); // 递归输出栈的所有元素 public: LinkedStack() : top(null) {} // 构造函数 ~LinkedStack() { makeempty();} // 析构函数 void Push(E x); // 进栈 bool Pop(E& x); // 退栈

17 }; bool gettop(e& x) const; // 取栈顶 bool IsEmpty() const { return top == NULL; } void makeempty(); // 清空栈的内容 friend ostream& operator << (ostream& os, LinkedStack<E>& s) { output(os, s.top, 1); } // 输出栈元素的重载操作 <<

18 链式栈类操作的实现 template <class E> LinkedStack<E>::makeEmpty() { // 逐次删去链式栈中的元素直至栈顶指针为空 StackNode<E> *p; while (top!= NULL) // 逐个结点释放 { p = top; top = top->link; delete p; } };

19 template <class E> void LinkedStack<E>::Push(E x) { // 将元素值 x 插入到链式栈的栈顶, 即链头 top = new StackNode<E> (x, top);// 创建新结点 assert (top!= NULL); // 创建失败退出 }; template <class E> bool LinkedStack<E>::Pop(E& x) { // 删除栈顶结点, 返回被删栈顶元素的值 if (IsEmpty() == true) return false; // 栈空返回 StackNode<E> *p = top; // 暂存栈顶元素 top = top->link; // 退栈顶指针 x = p->data; delete p; // 释放结点 return true; };

20 template <class E> bool LinkedStack<E>::getTop(E& x) const { if (IsEmpty() == true) return false; // 栈空返回 x = top->data; // 返回栈顶元素的值 return true; }; template <class E> void LinkedStack<E>::output(ostream& os, StackNode<E> *ptr, int& i) { // 递归输出栈中所有元素 if (ptr!= NULL) { os << i << : << p->data << endl; // 逐个输出栈中元素的值 if (ptr->link!= NULL) output(os, ptr->link, i++); } };

21 问题是 : 当进栈元素的编号为 1, 2,, n 时, 可能的出栈序列有多少种? 关于栈的进一步讨论

22 设进栈元素数为 n, 可能出栈序列数为 m n : n = 0,m 0 = 1: 出栈序列 {} n = 1,m 1 = 1: 出栈序列 {1} n = 2,m 2 = 2 = m 0 *m 1 +m 1 *m 0 a) 出栈序列中 1 在第 1 位 1 进 1 出 2 进 2 出, 出栈序列为 {1, 2} = m 0 *m 1 = 1 b) 出栈序列中 1 在第 2 位 1 进 2 进 2 出 1 出, 出栈序列为 {2, 1} = m 1 *m 0 = 1

23 n = 3,m 3 = 5 = m 0 *m 2 +m 1 *m 1 +m 2 *m 0 a) 出栈序列中 1 在第 1 位 后面 2 个元素有 m 2 = 2 个出栈序列 :{1, 2, 3}, {1, 3, 2} = m 0 *m 2 = 2 b) 出栈序列中 1 在第 2 位 1 前有 2 后有 3, 出栈序列为 {2, 1, 3} = m 1 *m 1 = 1 c) 出栈序列中 1 在第 3 位 前面 2 个元素有 m 2 = 2 个出栈序列 :{2, 3, 1}, {3, 2, 1} = m 2 *m 0 = 2

24 n = 4,m 4 = 14 = m 0 *m 3 +m 1 *m 2 +m 2 *m 1 +m 3 *m 0 a) 出栈序列中 1 在第 1 位 后面 3 个元素有 m 3 = 5 个出栈序列 : {1, 2, 3, 4}, {1, 2, 4, 3}, {1, 3, 2, 4}, {1, 3, 4, 2}, {1, 4, 3, 2} = m 0 *m 3 = 5 b) 出栈序列中 1 在第 2 位 前面有 2, 后面 3 4 有 m 2 = 2 个出栈序列 : {2, 1, 3, 4}, {2, 1, 4, 3} = m 1 *m 2 = 2 b) 出栈序列中 1 在第 3 位 前面 2 3 有 m 2 = 2 个出栈序列, 后面有 4: {2, 3, 1, 4}, {3, 2, 1, 4} = m 2 *m 1 = 2 d) 出栈序列中 1 在第 4 位 前面 3 个元素有 m 3 = 5 个出栈序列 :{2, 3, 4, 1}, {2, 4, 3, 1}, {3, 2, 4, 1}, {3, 4, 2, 1}, {4, 3, 2, 1} = m 3 *m 0 = 5

25 一般地, 设有 n 个元素按序号 1, 2,, n 进栈, 轮流让 1 在出栈序列的第 1, 第 2, 第 n 位, 则可能的出栈序列数为 : 推导结果为 : n-1 0 i 0 1 n 2 n 1 1 n 0 1 i n i m * m m *m m *m *m m C n 2n 1 n 0 i 1 i n i 1 n 1 * m m

26 栈的应用 : 表达式求值 Evaluation of Expressions

27 一个表达式由操作数 ( 亦称运算对象 ) 操作符 ( 亦称运算符 ) 和分界符组成 算术表达式有三种表示 : 中缀 (infix) 表示 < 操作数 >< 操作符 >< 操作数 >, 如 A+B; 前缀 (prefix) 表示 < 操作符 >< 操作数 >< 操作数 >, 如 +AB; 后缀 (postfix) 表示 < 操作数 > < 操作数 > < 操作符 >, 如 AB+; 例如 : 中缀表达式 a+b*(c-d)- e/f 后缀表达式 abcd- *+ef/- 前缀表达式 - +a*b cd/ef

28 表达式中相邻两个操作符的计算次序为 : 优先级高的先计算 ; 优先级相同的自左向右计算 ; 当使用括号时从最内层括号开始计算

29 一般表达式的操作符有 4 种类型 : 1 算术操作符如双目操作符 (+ - * / 和 %) 以及单目操作符 (-) 2 关系操作符包括 < <= ==!= >= > 这些操作符主要用于比较 3 逻辑操作符如与 (&&) 或 ( ) 非 (!) 4 括号 ( 和 ) 它们的作用是改变运算顺序

30 中缀表示 转后缀表示 1) 对中缀表达式按运算优先次序加上括号, 2) 以就近移动为原则, 把操作符后移到右括号的后面, 3) 将所有括号消去 如中缀表示 (A+B)*D-E/(F+A*D)+C, 其转换为后缀表达式的过程如下 : ( ( ( ( A + B ) * D ) ( E / ( F + ( A * D ) ) ) ) + C ) 后缀表示 A B + D * E F A D * + / - C +

31 中缀表示 转前缀表示 1) 对中缀表达式按运算优先次序通统加上括号, 2) 以就近移动为原则, 把操作符前移到左括号前, 3) 将所有括号消去 如中缀表示 (A+B)*D-E/(F+A*D)+C, 其转换为前缀表达式的过程如下 : ( ( ( ( A + B ) * D ) ( E / ( F + ( A * D ) ) ) ) + C ) 前缀表示 + - * + A B D / E + F * A D C

32 使用栈可将表达式的中缀表示转换成它的前缀表示和后缀表示 为了实现这种转换, 需要考虑各操作符的优先级 优先级操作符 1 单目 -! 2 * / % < <= > >= 5 ==!= 6 && 7

33 中缀表示 转后缀表示 如 : 中缀表示 : A + B * (C - D ) - E / F 后缀表示 : ABCD-*+EF/-

34 各个算术操作符的优先级 操作符 ch # ( *,/,% +, - ) isp ( 栈内 ) icp ( 栈外 ) isp 叫做栈内 (in stack priority) 优先数 icp 叫做栈外 (in coming priority) 优先数 操作符优先数相等的情况 : 只出现在括号配对或栈底的 # 号与输入流最后的 # 号配对时

35 利用栈将中缀表达式转换为后缀表达式的算法 1) 操作符栈初始化 ; 2) 将结束符 # 进栈 ; 3) 读入中缀表达式字符流的首字符 ch; 4) 重复执行以下步骤, 直到 ch = #, 同时栈顶的操作符也是 #, 停止循环

36 若 ch 是操作数直接输出, 读入下一个字符 ch 若 ch 是操作符, 判断 ch 的优先级 icp 和位于栈顶的操作符 op 的优先级 isp 若 icp(ch) > isp(op), 令 ch 进栈, 读入下一个字符 ch 若 icp(ch) < isp(op), 退栈并输出 若 icp(ch) == isp(op), 退栈但不输出, 若退出的是 ( 号读入下一个字符 ch 5) 算法结束, 输出序列即为所需的后缀表达式

37 步输入栈内容语义输出 动作 1 # 栈初始化 2 A # A 操作数 A 输出, 读字符 3 + # + > # 操作符 + 进栈, 读字符 4 B #+ B 操作数 B 输出, 读字符 5 * #+ * > + 操作符 * 进栈, 读字符 6 ( #+* ( > * 操作符 ( 进栈, 读字符 7 C # +*( C 操作数 C 输出, 读字符 8 - # +*( - > ( 操作符 - 进栈, 读字符 9 D # +*(- D 操作数 D 输出, 读字符 10 ) # +*(- ) < - - 操作符 - 退栈输出 11 # +*( ) = ( ( 退栈, 消括号, 读字符

38 步输入栈内容语义输出动作 12 - #+* - < * * 操作符 * 退栈输出 13 #+ - < + + 操作符 + 退栈输出 14 # - > # 操作符 - 进栈, 读字符 15 E #- E 操作数 E 输出, 读字符 16 / #- / > - 操作符 / 进栈, 读字符 17 F #-/ F 操作数 F 输出, 读字符 18 # #-/ # < / / 操作符 / 退栈输出 19 #- # < - - 操作符 - 退栈输出 20 # # = # # 配对, 转换结束

39 void postfix(expression e) { stack<char> s; char ch= #, ch1, op; // 栈底放一个 # s.push(ch); cin.get(ch); while (s.isempty()==false && ch!= # ) if (isdigit(ch)) {cout<<ch; cin.get(ch)}; // 操作数直接输出 else{ s.gettop(ch1); if (isp(ch1)<icp(ch)) // 新输入操作符优先级高 {s.push(ch); cin.get(ch);} else if (isp(ch1)>icp(ch)) // 新输入操作符优先级低 {s.pop(op); cout<<op;}

40 }; } else { // 新输入操作符优先级相等 s.pop(op); if (op== ( ) cin.get(ch) }

41 思考题 : 利用栈将中缀表达式转换为前缀表达式的算法

42 中缀表示计算表达式的值 a + b * (c - d ) - e / f rst1 rst2 rst3 rst5 rst4 使用两个栈 : 操作符栈 OPTR (operator) 操作数栈 OPND(operand) 为了实现这种计算, 需要考虑各操作符的优先级

43 各个算术操作符的优先级 操作符 ch # ( *, /, % +, - ) isp ( 栈内 ) icp ( 栈外 ) isp 叫做栈内 (in stack priority) 优先数 icp 叫做栈外 (in coming priority) 优先数 操作符优先数相等的情况 : 只出现在括号配对或栈底的 # 号与输入流最后的 # 号配对时

44 中缀算术表达式求值 对中缀表达式求值的一般规则 : 1. 建立并初始化 OPTR 栈和 OPND 栈, 然后在 OPTR 栈中压入一个 # 2. 扫描中缀表达式, 取一字符送入 ch 3. 当 ch!= # 或 OPTR 栈的栈顶!= # 时, 执行以下工作, 否则结束算法 在 OPND 栈的栈顶得到运算结果 1 若 ch 是操作数, 进 OPND 栈, 从中缀表达式取下一字符送入 ch;

45 2 若 ch 是操作符, 比较 icp(ch) 的优先级和 isp(optr) 的优先级 : 若 icp(ch) > isp(optr), 则 ch 进 OPTR 栈, 从中缀表达式取下一字符送入 ch; 若 icp(ch) < isp(optr), 则从 OPND 栈退出 a2 和 a1, 从 OPTR 栈退出 θ, 形成运算指令 (a1)θ(a2), 结果进 OPND 栈 ; 若 icp(ch) == isp(optr) 且 ch == ')', 则从 OPTR 栈退出 '(', 对消括号, 然后从中缀表达式取下一字符送入 ch;

46 步输入 OPND OPTR 语义 动作 1 # 栈初始化 2 A 操作数 A 进栈, 读字符 3 + A # + > # 操作符 + 进栈, 读字符 4 B A #+ 操作数 B 进栈, 读字符 5 * AB #+ * > + 操作符 * 进栈, 读字符 6 ( AB #+* ( > * 操作符 ( 进栈, 读字符 7 C AB #+*( 操作数 C 进栈, 读字符 8 - ABC #+*( - > ( 操作符 - 进栈, 读字符 9 D ABC #+*(- 操作数 D 进栈, 读字符 10 ) ABCD #+*(- ) < - D C - 退栈, 计算 C-D, 结果 r1 进栈

47 步输入 OPND OPTR 语义 动作 11 ABr1 #+*( ) = ( ( 退栈, 消括号, 读字符 12 - ABr1 #+* - < * r1 B * 退栈, 计算 B*r1, 结果 r2 进栈 13 Ar2 #+ - < + r2 A + 退栈, 计算 A+r2, 结果 r3 进栈 14 r3 # - > # 操作符 - 进栈, 读字符 15 E r3 #- 操作数 E 进栈, 读字符 16 / r3e #- / > - 操作符 / 进栈, 读字符 17 F r3e #-/ 操作数 F 进栈, 读字符 18 # r3ef #-/ # < / F E / 退栈, 计算 E/F, 结果 r4 进栈

48 步输入 OPND OPTR 语义动作 19 r3r4 #- # < - r4 r3 - 退栈, 计算 r3-r4, 结果 r5 进栈 20 r5 # 算法结束, 结果 r5

49 void InFixRun() { stack<char> OPTR, OPND; char ch, op; OPTR.makeEmpty(); OPND.makeEmpty(); OPTR.Push( # ); // 两个栈初始化 getchar(ch); // 读入一个字符 op = '#' ; while (ch!= '#' op!= '#') { if (isdigit(ch)) // 是操作数, 进栈 { OPND.Push(ch); getchar(ch); } else { // 是操作符, 比较优先级 OPTR.GetTop(op); // 读一个操作符

50 } if (icp(ch) > isp(op)) // 栈顶优先级低 { OPTR.Push (ch); getchar(ch); } else if (icp(ch) < isp(op)) { OPTR.Pop(op); // 栈顶优先级高 OPND.DoOperator(op); } else if (ch == ) ) // 优先级相等 { OPTR.Pop(op); getchar(ch); } } OPTR.GetTop(op); } /*end of while*/

51 思考题 : 应用后缀表示计算表达式的值

52 思考题 : 应用后缀表示计算表达式的值 从左向右顺序地扫描表达式, 并用一个栈暂存扫描到的操作数或计算结果 在后缀表达式的计算顺序中已隐含了加括号的优先次序, 括号在后缀表达式中不出现 计算例 abcd- *+ef /- rst1 rst4 rst2 rst3 rst5

53 栈的应用 : 递归

54 递归 (Recursion) 的定义若, 一个对象部分地包含它自己, 或, 用它自己给自己定义, 则称这个对象是递归的 ; 若, 一个过程直接地或间接地调用自己, 则称这个过程是递归的过程 以下三种情况常常用到递归方法 定义是递归的 数据结构是递归的 问题的解法是递归的

55 1 定义是递归的 例如, 阶乘函数 1, n! n ( n 1)!, 当 n 当 n 0时 1时 求解阶乘函数的递归算法 long Factorial(long n) { if (n == 0) return 1; else return n*factorial(n-1); }

56 求解阶乘 n! 的过程 主程序 main : fact(4) 递归调用 参数传递 参数 4 计算 4*fact(3) 返回 24 参数 3 计算 3*fact(2) 返回 6 参数 2 计算 2*fact(1) 返回 2 结果返回 回归求值 参数 1 计算 1*fact(0) 返回 1 参数 0 直接定值 = 1 返回 1

57 2 数据结构是递归的 例如, 单链表结构 f f 一个结点, 它的指针域为 NULL, 是一个单链表 ; 一个结点, 它的指针域指向单链表, 仍是一个单链表

58 搜索链表最后一个结点并打印其数值 template <class E> void Print(ListNode<E> *f) { if (f ->link == NULL) cout << f ->data << endl; else Print(f ->link); } 递归找链尾 f a 0 a 1 a 2 a 3 a 4 f f f f

59 在链表中寻找等于给定值的结点并打印其数值 template <class E> void Print(ListNode<E> *f, E value) { if (f!= NULL) if (f -> data == value) cout << f -> data << endl; else Print(f -> link, value); } 递归找含 x 值的结点 f f f f x

60 3 问题的解法是递归的 例, 汉诺塔 (Tower of Hanoi) 问题的解法 : 如果 n = 1, 则将这一个盘子直接从 A 柱移到 C 柱上 否则, 执行以下三步 : 1 用 C 柱做过渡, 将 A 柱上的 (n-1) 个盘子移到 B 柱上 : 2 将 A 柱上最后一个盘子直接移到 C 柱上 ; 3 用 A 柱做过渡, 将 B 柱上的 (n-1) 个盘子移到 C 柱上

61

62 #include <iostream.h> void Hanoi (int n, chara, charb, charc) { // 解决汉诺塔问题的算法 if (n == 1) cout << " move " << A << " to " << C << endl; else { Hanoi(n-1, A, C, B); cout << " move " << A << " to " << C << endl; Hanoi(n-1, B, A, C); } }

63 自顶向下 逐步分解的策略 子问题应与原问题做同样的事情, 且更为简单 ; 解决递归问题的策略是把一个规模比较大的问题分解为一个或若干规模比较小的问题, 分别对这些比较小的问题求解, 再综合它们的结果, 从而得到原问题的解 分而治之策略 ( 分治法 ) 这些比较小的问题的求解方法与原来问题的求解方法一样

64 构成递归的条件 不能无限制地调用本身, 必须有一个出口, 化简为非递归状况直接处理 Procedure <name> ( <parameter list> ) { if ( < initial condition> ) // 递归结束条件 return ( initial value ); else // 递归 return (<name> ( parameter exchange )); }

65 递归过程与递归工作栈 递归过程在实现时, 需要自己调用自己 层层向下递归, 退出时的次序正好相反 : 递归调用 n! (n-1)! (n-2)! 1! 0!=1 返回次序 主程序第一次调用递归过程为外部调用 ; 递归过程每次递归调用自己为内部调用 它们返回调用它的过程的地址不同

66 RetLoc2 RetLoc1 long Factorial(long n) { int temp; if (n == 0) return 1; else temp = n * Factorial(n-1); } return temp; void main() { int n; n = Factorial(4); }

67 递归工作栈 每一次递归调用时, 需要为过程中使用的参数 局部变量等另外分配存储空间 每层递归调用需分配的空间形成递归工作记录, 按后进先出的栈组织 活动记录框架 局部变量返回地址参数 递归工作记录

68 函数递归时的活动记录 调用块 函数块. < 下一条指令 > Function(< 参数表 >). <return> 返回地址 ( 下一条指令 ) 局部变量参数

69 计算 Fact 时活动记录的内容 递归调用序列 参数返回值返回地址 4 24 RetLoc1 3 6 RetLoc2 2 2 RetLoc2 1 1 RetLoc2 0 1 RetLoc2 返回时的指令 return 4*6 // 返回 24 return 3*2 // 返回 6 return 2*1 // 返回 2 return 1*1 // 返回 1 return 1 // 返回 1

70 递归过程改为非递归过程 递归过程简洁 易编 易懂 递归过程效率低, 重复计算多 改为非递归过程的目的是提高效率 单向递归和尾递归可直接用迭代实现其非递归过程 其他情形必须借助栈实现非递归过程

71 单向递归

72 计算斐波那契数列的函数 Fib(n) 的定义 Fib(n) Fib(n 1) n, 求解斐波那契数列的递归算法 long Fib(long n) { if (n <= 1) return n; else return Fib(n-1)+Fib(n-2); } Fib(n 2), n n 0,1 1 如 F 0 = 0, F 1 = 1, F 2 = 1, F 3 = 2, F 4 = 3, F 5 = 5

73 斐波那契数列的递归调用树 Fib(5) Fib(4) Fib(3) Fib(3) Fib(2) Fib(2) Fib(1) Fib(2) Fib(1) Fib(1) Fib(0) Fib(1) Fib(0) Fib(1) Fib(0) 调用次数 NumCall(k) = 2*Fib(k+1)-1

74 单向递归用迭代法实现 long FibIter(long n) { if (n <= 1) return n; long twoback = 0, oneback = 1, Current; for (int i=2; i <= n; i++) { Current = twoback + oneback; twoback = oneback; oneback = Current; } return Current; }

75 尾递归 逆向输出

76 void recfunc(int A[ ], intn) { if (n >= 0) { cout << A[n] << ; n--; recfunc(a, n); } } void sterfunc(int A[ ], int n) { // 消除了尾递归的非递归函数 while (n >= 0) { cout << A[n] << ; n--; } } 尾递归用迭代法实现

77 递归与回溯 对一个包含有许多结点, 且每个结点有多个分支的问题, 可以先选择一个分支进行搜索 当搜索到某一结点, 发现无法再继续搜索下去时, 可以沿搜索路径回退到前一结点, 沿另一分支继续搜索 如果回退之后没有其他选择, 再沿搜索路径回退到更前结点, 依次执行, 直到搜索到问题的解, 或搜索完全部可搜索的分支没有解存在为止 回溯法与分治法本质相同, 可用递归求解

78 栈的应用 : 递归 -> 迷宫问题

79 迷宫问题 小型迷宫 路口动作结果 1 ( 入口 ) 正向走进到 2 2 左拐弯进到 3 3 右拐弯进到 4 4 ( 堵死 ) 回溯退到 3 3 ( 堵死 ) 回溯退到 2 2 正向走进到 5 5 ( 堵死 ) 回溯退到 2 2 右拐弯进到 6 6 左拐弯进到 7 ( 出口 ) 型迷宫的数据 小6 左 0 直 2 右 0 行 3 行 5 行

80 迷宫的类定义 交通路口结构定义 #include <iostream.h> struct Intersection { #include <fstream.h> int left; #include <stdlib.h> int forward; class Maze { int right; private: } int MazeSize; int EXIT; Intersection *intsec; public: Maze(char *filename); int TraverseMaze(int CurrentPos); };

81 Maze :: Maze(char *filename) { // 构造函数 : 从文件 filename 中读取各路口 // 和出口的数据 ifstream fin; fin.open(filename, ios::in ios::nocreate); // 为输入打开文件, 文件不存在则打开失败 if (!fin) { cerr << 迷宫数据文件 << filename << 打不开 << endl; exit(1); } fin >> MazeSize; // 输入迷宫路口数

82 } intsec = new Intersection[MazeSize+1]; // 创建迷宫路口数组 for (int i = 1; i <= MazeSize; i++) fin >> intsec[i].left >> intsec[i].forward >> intsec[i].right; fin >> EXIT; // 输入迷宫出口 fin.close();

83 迷宫漫游与求解算法 int Maze::TraverseMaze(int CurrentPos) { if (CurrentPos > 0) { // 路口从 1 开始 if (CurrentPos == EXIT) { // 出口处理 cout << CurrentPos << " "; return1; } else // 递归向左搜寻可行 if (TraverseMaze(intsec[CurrentPos].left)) { cout << CurrentPos << ; return1; } else // 递归向前搜寻可行 if (TraverseMaze(intsec[CurrentPos].forward)) { cout << CurrentPos << ; return1; } else // 递归向右搜寻可行 if (TraverseMaze(intsec[CurrentPos].right)) { cout << CurrentPos << " "; return1; } } return 0; }

84 利用栈实现 TraverseMaze 的非递归算法