PowerPoint Presentation

Transcription

1 数据结构与算法 ( 三 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社, ( 十一五 国家级规划教材 )

2 第 3 章栈与队列 栈 栈与表达式求值 队列 栈和队列的应用 队列的应用 递归到非递归的转换 ( 补充 ) 2

3 栈 (Stack) 操作受限的线性表 运算只在表的一端进行 队列 (Queue) 运算只在表的两端进行 3

4 3.1 栈 栈定义 后进先出 (Last In First Out) 一种限制访问端口的线性表 主要操作 进栈 (push) 出栈 (pop) 应用 表达式求值 消除递归 深度优先搜索 栈顶栈底 出栈 K i+1 K i... k 1 k 0 进栈 4

5 3.1 栈 栈的抽象数据类型 template <class T> class Stack { public: // 栈的运算集 void clear(); // 变为空栈 bool push(const T item); // item 入栈, 成功返回真, 否则假 bool pop(t& item); // 返回栈顶内容并弹出, 成功返回真, 否则假 bool top(t& item); // 返回栈顶但不弹出, 成功返回真, 否则假 bool isempty(); // 若栈已空返回真 bool isfull(); // 若栈已满返回真 ; 5

6 3.1 栈 火车进出栈问题 判断火车的出栈顺序是否合法 编号为 1,2,,n 的 n 辆火车依次进站, 给定一个 n 的排列, 判断是否是合法的出站顺序? 5, 4, 3, 2, 1 1, 2, 3, 4, 5 B A 6 车站

7 3.1 栈 利用合法的重构找冲突

8 3.1 栈 思考 若入栈的顺序为 1,2,3,4, 那么出栈的顺序可以有哪些? 从初始输入序列 1,2,,n, 希望利用一个栈得到输出序列 p 1,p 2,,p n ( 它们是 1, 2,,n 的一种排列 ) 若存在下标 i,j,k, 满足 i<j<k 同时 P j <P k <P i, 则输出序列是否合法? 8

9 3.1 栈 栈的实现方式 顺序栈 (Array-based Stack) 使用向量实现, 本质上是顺序表的简化版 栈的大小 关键是确定哪一端作为栈顶 上溢, 下溢问题 链式栈 (Linked Stack) 用单链表方式存储, 其中指针的方向是从栈顶向下链接 9

10 3.1.1 顺序栈 顺序栈的类定义 template <class T> class arrstack : public Stack <T> { private: // 栈的顺序存储 int msize; // 栈中最多可存放的元素个数 int top; // 栈顶位置, 应小于 msize T *st; // 存放栈元素的数组 public: // 栈的运算的顺序实现 arrstack(int size) { // 创建一个给定长度的顺序栈实例 msize = size; top = -1; st = new T[mSize]; arrstack() { // 创建一个顺序栈的实例 top = -1; ~arrstack() { delete [] st; void clear() { top = -1; // 清空栈 10

11 3.1.1 顺序栈 顺序栈 按压入先后次序, 最后压入的元素编号为 4, 然后依次为 3,2,1 栈顶栈底

12 3.1.1 顺序栈 上溢 (Overflow) 顺序栈的溢出 当栈中已经有 maxsize 个元素时, 如果再做进栈运算, 所产生的现象 下溢 (Underflow) 对空栈进行出栈运算时所产生的现象 12

13 3.1.1 顺序栈 压入栈顶 bool arrstack<t>::push(const T item) { if (top == msize-1) { // 栈已满 cout << " 栈满溢出 " << endl; return false; else { // 新元素入栈并修改栈顶指针 st[++top] = item; return true; 13

14 3.1.1 顺序栈 从栈顶弹出 bool arrstack<t>::pop(t & item) { // 出栈 if (top == -1) { // 栈为空 cout << " 栈为空, 不能执行出栈操作 "<< endl; return false; else { item = st[top--]; // 返回栈顶, 并缩减 1 return true; 14

15 3.1.2 链式栈 用单链表方式存储 链式栈的定义 指针的方向从栈顶向下链接 栈顶 K n-1 K n-2 K 1 K 0 15

16 3.1.2 链式栈 链式栈的创建 template <class T> class lnkstack : public Stack <T> { private: // 栈的链式存储 Link<T>* top; // 指向栈顶的指针 int size; // 存放元素的个数 public: // 栈运算的链式实现 lnkstack(int defsize) { // 构造函数 top = NULL; size = 0; ~lnkstack() { // 析构函数 clear(); 16

17 3.1.2 链式栈 压入栈顶 // 入栈操作的链式实现 bool lnksstack<t>:: push(const T item) { Link<T>* tmp = new Link<T>(item, top); top = tmp; size++; return true; Link(const T info, Link* nextvalue) {// 具有两个参数的 Link 构造函数 data = info; next = nextvalue; 17

18 3.1.2 链式栈 从单链栈弹出元素 // 出栈操作的链式实现 bool lnkstack<t>:: pop(t& item) { Link <T> *tmp; if (size == 0) { cout << " 栈为空, 不能执行出栈操作 "<< endl; return false; item = top->data; tmp = top->next; delete top; top = tmp; size--; return true; 18

19 3.1 栈 时间效率 顺序栈和链式栈的比较 所有操作都只需常数时间 顺序栈和链式栈在时间效率上难分伯仲 空间效率 顺序栈须说明一个固定的长度 链式栈的长度可变, 但增加结构性开销 19

20 3.1 栈 顺序栈和链式栈的比较 实际应用中, 顺序栈比链式栈用得更广泛 顺序栈容易根据栈顶位置, 进行相对位移, 快速定位并读取栈的内部元素 顺序栈读取内部元素的时间为 O(1), 而链式栈则需要沿着指针链游走, 显然慢些, 读取第 k 个元素需要时间为 O(k) 一般来说, 栈不允许 读取内部元素, 只能在栈顶操作 20

21 3.1 栈 思考 : STL 中关于栈的函数 top 函数表示取栈顶元素, 将结果返回给用户 pop 函数表示将栈顶元素弹出 ( 如果栈不空 ) pop 函数仅仅是一个操作, 并不将结果返回 pointer = astack.pop()? 错误! STL 为什么这两个操作分开? 为什么不提供 ptop? 21

22 3.1 栈 栈的特点 : 后进先出 栈的应用 体现了元素之间的透明性 常用来处理具有递归结构的数据 深度优先搜索 表达式求值 子程序 / 函数调用的管理 消除递归 22

23 3.1 栈 表达式的递归定义 计算表达式的值 基本符号集 :{0,1,,9,+,-,*,/,(,) 语法成分集 :{< 表达式 >, < 项 >, < 因子 >, < 常数 >, < 数字 > 中缀表达式 23+(34*45)/(5+6+7) 后缀表达式 * / + 23

24 3.1 栈 中缀表达式 中缀表达式 4 * x * (2 * x + a) c 运算符在中间 需要括号改变优先级 * - c * + * 4 x a 2 x 24

25 3.1 栈 中缀表达法的语法公式 < 表达式 > = < 项 > + < 项 > < 项 > - < 项 > < 项 > < 项 > = < 因子 > * < 因子 > < 因子 > / < 因子 > < 因子 > < 因子 > = < 常数 > ( < 表达式 > ) < 常数 > = < 数字 > < 数字 > < 常数 > < 数字 > =

26 3.1 栈 表达式的递归图示 表达式 项 因子 项 + - 因子 * / ( 表达式 ) 数字 26

27 3.1 栈 后缀表达式 后缀表达式 4 x * 2 x * a + * c 运算符在后面 完全不需要括号 * - c * + 4 x a * 2 x 27

28 3.1 栈 后缀表达式 < 表达式 > = < 项 > < 项 > + < 项 > < 项 > - < 项 > < 项 > = < 因子 > < 因子 > * < 因子 > < 因子 > / < 因子 > < 因子 > = < 常数 > < 常数 > = < 数字 > < 数字 > < 常数 > < 数字 > =

29 3.1 栈 后缀表达式的计算 * / + =? 计算特点? 中缀和后缀表达式的主要异同? * 45 / ( ) =? * / + =? 29

30 待处理后缀表达式 : * / + 栈状态的变化 计算结果

31 3.1 栈 后缀表达式求值 循环 : 依次顺序读入表达式的符号序列 ( 假设以 = 作为输入序列的结束 ), 并根据读入的元素符号逐一分析 1. 当遇到的是一个操作数, 则压入栈顶 2. 当遇到的是一个运算符, 就从栈中两次取出栈顶, 按照运算符对这两个操作数进行计算 然后将计算结果压入栈顶 如此继续, 直到遇到符号 =, 这时栈顶的值就是输入表达式的值 31

32 3.1 栈 后缀计算器的类定义 class Calculator { private: Stack<double> s; // 这个栈用于压入保存操作数 // 从栈顶弹出两个操作数 opd1 和 opd2 bool GetTwoOperands(double& opd1,double& opd2); // 取两个操作数, 并按 op 对两个操作数进行计算 void Compute(char op); public: Calculator(void){ ; // 创建计算器实例, 开辟一个空栈 void Run(void); // 读入后缀表达式, 遇 = 符号结束 void Clear(void); // 清除计算器, 为下一次计算做准备 ; 32

33 3.1 栈 后缀计算器的类定义 template <class ELEM> bool Calculator<ELEM>::GetTwoOperands(ELEM& opnd1, ELEM& opnd2) { if (S.IsEmpty()) { cerr << "Missing operand!" <<endl; return false; opnd1 = S.Pop(); // 右操作数 if (S.IsEmpty()) { cerr << "Missing operand!" <<endl; return false; opnd2 = S.Pop(); // 左操作数 return true; 33

34 3.1 栈 后缀计算器的类定义 template <class ELEM> void Calculator<ELEM>::Compute(char op) { bool result; ELEM operand1, operand2; result = GetTwoOperands(operand1, operand2); if (result == true) switch(op) { case '+' : S.Push(operand2 + operand1); break; case '-' : S.Push(operand2 - operand1); break; case '*' : S.Push(operand2 * operand1); break; case '/' : if (operand1 == 0.0) { cerr << "Divide by 0!" << endl; S.ClearStack(); else S.Push(operand2 / operand1); break; else S.ClearStack(); 34

35 3.1 栈 后缀计算器的类定义 template <class ELEM> void Calculator<ELEM>::Run(void) { char c; ELEM newoperand; while (cin >> c, c!= '=') { switch(c) { case '+': case '-': case '*': case '/': Compute(c); break; default: cin.putback(c); cin >> newoperand; Enter(newoperand); break; if (!S.IsEmpty()) cout << S.Pop() << endl; // 印出求值的最后结果 35

36 目录页 思考 1. 栈往往用单链表实现 可以用双链表吗? 哪个更好? 2. 请总结前缀表达式的性质, 以及求值过程 36

37 第 3 章栈与队列 栈 栈与表达式求值 队列 栈和队列的应用 队列的应用 递归到非递归的转换 ( 补充 ) 37

38 3.2 队列 队列的定义 先进先出 (First In First Out) 限制访问点的线性表 按照到达的顺序来释放元素 所有的插入在表的一端进行, 所有的删除都在表的另一端进行 主要元素 队头 (front) 队尾 (rear) 38

39 3.2 队列 队列的主要操作 入队列 (enqueue) 出队列 (dequeue) 取队首元素 (getfront) 判断队列是否为空 (isempty) 39

40 3.2 队列 队列的抽象数据类型 template <class T> class Queue { public: // 队列的运算集 void clear(); // 变为空队列 bool enqueue(const T item); // 将 item 插入队尾, 成功则返回真, 否则返回假 bool dequeue(t & item) ; // 返回队头元素并将其从队列中删除, 成功则返回真 bool getfront(t & item); // 返回队头元素, 但不删除, 成功则返回真 bool isempty(); // 返回真, 若队列已空 bool isfull(); // 返回真, 若队列已满 ; 40

41 3.2 队列 顺序队列 队列的实现方式 关键是如何防止假溢出 链式队列 用单链表方式存储, 队列中每个元素对于链表中的一个结点 41

42 3.2 队列 队列示意 : 环形 ( 实指 ) Q.front Q.rear Q.front Q.rear Q.rear k 1 k 0 k 2 k 3 k 6 Q.rear k 4 k 5 Q.rear 空队列 Q.rear Q.rear 42

43 3.2.1 顺序队列 顺序队列的类定义 class arrqueue: public Queue<T> { private: int msize; // 存放队列的数组的大小 int front; // 表示队头所在位置的下标 int rear; // 表示队尾所在位置的下标 T * qu; // 存放类型为 T 的队列元素的数组 public: // 队列的运算集 arrqueue(int size); // 创建队列的实例 ~arrqueue(); // 消除该实例, 并释放其空间 43

44 3.2.1 顺序队列 顺序队列的维护 rear 实指 front front rear rear A B C B D C D 插入删除 44

45 3.2.1 顺序队列 顺序队列的维护 front 和 rear 都实指 45

46 3.2.1 顺序队列 顺序队列代码实现 template <class Elem> class Aqueue : public Queue<Elem> { private: int size; // 队列的最大容量 int front; // 队首元素指针 int rear; // 队尾元素指针 Elem *listarray; // 存储元素的数组 public: AQueue(int sz=defaultlistsize) { // 让存储元素的数组多预留一个空位 size = sz+1; // size 数组长,sz 队列最大长度 rear = 0; front = 1; // 也可以 rear=-1; front=0 listarray = new Elem[size]; ~AQueue() { delete [] listarray; void clear() { front = rear+1; 46

47 3.2.1 顺序队列 顺序队列代码实现 bool enqueue(const Elem& it) { if (((rear+2) % size) == front) return false; // 还剩一个空位, 就要报满 rear = (rear+1) % size; // 因为实指, 需要先移动到下一个空位 listarray[rear] = it; return true; bool dequeue(elem& it) { if (length() == 0) return false; // 队列为空 it = listarray[front]; // 先出队, 再移动 front 下标 front = (front+1) % size; // 环形增加 return true; 47

48 3.2.1 顺序队列 顺序队列代码实现 bool frontvalue(elem& it) const { if (length() == 0) return false; // 队列为空 it = listarray[front]; return true; int length() const { return (size +(rear - front + 1)) % size; 48

49 3.2.1 顺序队列 思考 1. 只是用 front, rear 两个变量, 长度为 msize = n 的队列, 可以容纳的最大元素个数为多少? 请给出详细的推导过程 2. 如果不愿意浪费队列的存储单元, 还可以采用什么方法? 49

50 3.2.2 链式队列 链式队列的表示 单链表队列 链接指针的方向是从队列的前端向尾端链接 f r k 0 k 1 k 2. k n-1 50

51 3.2.2 链式队列 链式队列的类定义 template <class T> class lnkqueue: public Queue<T> { private: int size; // 队列中当前元素的个数 Link<T>* front; // 表示队头的指针 Link<T>* rear; // 表示队尾的指针 public: // 队列的运算集 lnkqueue(int size); // 创建队列的实例 ~lnkqueue(); // 消除该实例, 并释放其空间 51

52 3.2.2 链式队列 链式队列代码实现 bool enqueue(const T item) { // item 入队, 插入队尾 if (rear == NULL) { // 空队列 front = rear = new Link<T> (item, NULL); else { // 添加新的元素 rear-> next = new Link<T> (item, NULL); rear = rear ->next; size++; return true; 52

53 bool dequeue(t* item) { Link<T> *tmp; if (size == 0) { 第三章 链式队列代码实现 cout << " 队列为空 " << endl; return false; *item = front->data; tmp = front; front = front -> next; delete tmp; if (front == NULL) rear = NULL; size--; return true; 链式队列 // 返回队头元素并从队列中删除 // 队列为空, 没有元素可出队 53

54 3.2.2 链式队列 顺序队列与链式队列的比较 顺序队列 固定的存储空间 链式队列 可以满足大小无法估计的情况 都不允许访问队列内部元素 54

55 3.2 队列 队列的应用 只要满足先来先服务特性的应用均可采用队列作为其数据组织方式或中间数据结构 调度或缓冲 消息缓冲器 邮件缓冲器 计算机硬设备之间的通信也需要队列作为数据缓冲 操作系统的资源管理 宽度优先搜索 55

56 Q.front 思考 Q.rear 链式队列往往用单链表 为什么不用双链表来实现? k 1 k 0 若采用虚指方法实现队尾指针 (rear 指向队尾元素后一个元素, 和实指相比后移一位 ), 在具体实现上有何异同? 哪一种更好? 56

57 第 3 章栈与队列 栈 栈与表达式求值 队列 栈和队列的应用 队列的应用 递归到非递归的转换 ( 补充 ) 57

58 队列的应用 农夫过河问题 问题抽象 : 人狼羊菜 乘船过河 只有人能撑船, 船只有两个位置 ( 包括人 ) 狼羊 羊菜不能在没有人时共处 人羊狼菜人狼菜人羊狼人羊菜 人羊 狼菜狼菜羊空 ( 成功 ) 58

59 队列的应用 人羊 1111 人 人 人狼菜羊人羊 1101 人羊 人菜 1110 空 ( 成功 ) 人狼 59 人狼菜 0100 人羊 菜 羊 狼菜 人羊菜 ( 人狼菜羊 ) 狼菜 ( 人狼菜 ) 菜 ( 人菜羊 ) 羊 ( 人羊 ) 空 算法示意 人羊 人狼 人羊 人菜 人 人羊 人 人狼菜羊 ( 人菜羊 ) 羊 ( 人狼羊 ) 狼 ( 人狼菜 ) 狼菜 ( 人狼菜 ) 人狼菜羊

60 目录页队列的应用 问题分析 广度优先 :(m 种状态 ) A 1 A 2 A 3 A m A 11 A 12 A 1n A 21 A 22 A 3 A 211 A 21 深度优先 :(m 种状态 ) A 2 A 111 A 11 A 1 60

61 队列的应用 数据抽象 每个角色的位置进行描述 农夫 狼 菜和羊, 四个目标各用一位 ( 假定按照农夫 狼 白菜 羊次序 ), 目标在起始岸位置 :0, 目标岸 : 如 0101 表示农夫 白菜在起始岸, 而狼 羊在目标岸 ( 此状态为不安全状态 ) 61

62 队列的应用 数据的表示 用整数 status 表示上述四位二进制描述的状态 整数 0x08 表示的状态 整数 0x0F 表示的状态 如何从上述状态中得到每个角色所在位置? 函数返回值为真 (1), 表示所考察人或物在目标岸 否则, 表示所考察人或物在起始岸 62

63 队列的应用 确定每个角色位置的函数 bool farmer(int status) { return ((status & 0x08)!= 0); 人狼菜羊 1 x x x bool wolf(int status) { return ((status & 0x04)!= 0); x 1 x x bool cabbage(int status) { return ((status & 0x02)!= 0); x x 1 x bool goat(int status) { return ((status & 0x01)!= 0); x x x 1 63

64 队列的应用 安全状态的判断 人 狼 菜 羊 bool safe(int status) { if ((goat(status) == cabbage(status)) && (goat(status)!= farmer(status))) return(false); // 羊吃白菜 if ((goat(status) == wolf(status)) && (goat(status)!= farmer(status))) return(false); // 狼吃羊 return(true); // 返回 true: 安全,false: 不安全 // 其它状态为安全 64

65 队列的应用 算法抽象 问题变为从状态 0000( 整数 0) 出发, 寻找全部由安全状态构成的状态序列, 以状态 1111 ( 整数 15) 为最终目标 状态序列中每个状态都可以从前一状态通过农夫 ( 可以带一样东西 ) 划船过河的动作到达 序列中不能出现重复状态 65

66 队列的应用 算法设计 定义一个整数队列 moveto, 它的每个元素表示一个可以安全到达的中间状态 还需要定义一个数据结构记录已被访问过的各个状态, 以及已被发现的能够到达当前这个状态的路径 用顺序表 route 的第 i 个元素记录状态 i 是否已被访问过 若 route[i] 已被访问过, 则在这个顺序表元素中记入前驱状态值 ; -1 表示未被访问 route 的大小 ( 长度 ) 为 16 66

67 算法实现 void solve() { int movers, i, location, newlocation; vector<int> route(end+1, -1); // 记录已考虑的状态路径 queue<int> moveto; // 准备初值 moveto.push(0x00); route[0]=0; 67

68 算法实现 while (!moveto.empty() && route[15] == -1) { // 得到现在的状态 status = moveto.front(); moveto.pop(); for (movers = 1; movers <= 8; movers <<= 1) { // 农夫总是在移动, 随农夫移动的也只能是在农夫同侧的东西 if (farmer(status) == (bool)(status & movers)) { newstatus = status ^ (0x08 movers); // 安全的, 并且未考虑过的走法 if (safe(newstatus) && (route[newstatus] == -1)) { route[newstatus] = status; moveto.push(newstatus); 68 人狼菜羊

69 算法实现 // 反向打印出路径 if (route[15]!= -1) { cout << "The reverse path is : << endl; for (int status = 15; status >= 0; status = route[status]) { cout << "The status is : << status << endl; if (status == 0) break; else cout << "No solution. << endl; 69

70 队列的应用 人羊 1111 人 人 人狼菜羊人羊 1101 人羊 人菜 1110 空 ( 成功 ) 人狼 70 人狼菜 0100 人羊 菜 羊 狼菜 人羊菜 ( 人狼菜羊 ) 狼菜 ( 人狼菜 ) 菜 ( 人菜羊 ) 羊 ( 人羊 ) 空 算法示意 人羊 人狼 人羊 人菜 人 人羊 人 人狼菜羊 ( 人菜羊 ) 羊 ( 人狼羊 ) 狼 ( 人狼菜 ) 狼菜 ( 人狼菜 ) 人狼菜羊

71 例题讲解 思考 : 另一个小游戏 五人提灯过独木桥 : 有一盏灯能使用 30 秒, 要在灯熄灭前过这座桥 ; 一家五口人每个人过桥的速度不同 : 哥哥 1 秒, 弟弟 3 秒, 爸爸 6 秒, 妈妈 8 秒, 奶奶 12 秒 ; 每次只能过两个人 过去后, 对岸要有一个人再把灯送回来 71

72 第 3 章栈与队列 栈 队列 栈和队列的应用 队列的应用 递归到非递归的转换 ( 补充 ) 72

73 递归转非递归 递归函数调用原理 机械的递归转换 优化后的非递归函数 73

74 递归调用原理 递归的再研究 阶乘 f n = 递归出口 n f(n 1) n 1 1 n = 0 递归终止的条件, 即最小子问题的求解 可以允许多个出口 递归规则 ( 递归体 + 界函数 ) 将原问题划分成子问题 保证递归的规模向出口条件靠拢 74

75 递归算法的非递归实现 f n = 阶乘的非递归方式 - 建立迭代 递归调用原理 - 递归转换为非递归 n f(n 1) n 1 1 n = 0 以 Hanoi 塔为例呢? 75

76 递归调用原理 河内塔问题的递归求解程序 hanoi(n,x,y,z) 移动 n 个槃环 X 柱出发, 将槃环移动到 Z 柱 X Y Z 都可以暂存 大盘不能压小盘 例如, hanoi(2, B, C, A ) B 柱上部的 2 个环槃移动到 A 柱 76

77 3.1.3 递归转非递归 void hanoi(int n, char X, char Y, char Z) { if (n <= 1) move(x,z); else { // X 上最大的不动, 其他 n-1 个环槃移到 Y hanoi(n-1,x,z,y); move(x,z); // 移动最大环槃到 Z, 放好 hanoi(n-1,y,x,z); // 把 Y 上的 n-1 个环槃移到 Z void move(char X, char Y) // 把柱 X 的顶部环槃移到柱 Y { cout << "move" << X << "to" << Y << endl; 77

78 3.1.3 递归转非递归 Hanoi 递归子程序的运行示意图 出栈 进栈 执行 hanoi 程序的指令流 通过内部栈和子程序交换信息 栈顶 栈底 K i+1 K i... k 1 k 0 78

79 79 目录页第三章栈与队列 H A,B,C H A,C,B 递归调子程序 3 2 递归调子程序 H A,B,C 1 调子程序 move(a,c) 返回 move(a,b) H C,A,B 1 调子程序 move(c,b) 返回返回 move(a,c) H B,A,C 2 H B,C,A 1 调子程序 move(b,a) 返回 move(b,c) H A,B,C 1 调子程序 move(a,c) 返回返回完成 Hanoi (3,A,B,C) 递归转非递归

80 递归调 子程序 3 H A,B,C 返回 完成 Hanoi(3,A,B,C) 80 2 递归调子程序 H A,C,B 返回 move(a,c) 2 H B,A,C 返回 返回 返回 返回 1 H A,B,C 1 move(a,b) H C,A,B 1 H B,C,A 1 move(b,c) H A,B,C 调子程序 调子程序 调子程序 调子程序 move(a,c) move(c,b) move(b,a) move(a,c)

81 3.1.3 递归转非递归 递归运行时, 堆栈的进退以及通过堆栈传递参数 hanoi(1,a,b,c) hanoi(1,b,c,a) hanoi(2,b,a,c) hanoi(1,c,a,b) hanoi(1,a,b,c) hanoi(2,a,c,b) hanoi(3,a,b,c) 1,C,A,B 1,B,C,A 1,A,B,C 2,A,C,B 2,B,A,C 3,A,B,C 执行 move(a,c) move(a,b) move(b,a) move(c,b) move(b,c) 81

82 fu( n ) 递归转非递归 一个递归数学公式 n 1 fu( n / 2 )* fu( 当 n 2 时 n / 4 ) n 2 时 82

83 3.1.3 递归转非递归 int f(int n) { 递归函数示例 fu( n if (n<2) return n+1; else return f(n/2) * f(n/4); ) n 1 当 n 2 时 fu( n / 2 )* fu( n / 4 ) n 2 时 83

84 3.1.3 递归转非递归 递归函数示例 ( 转换一下 ) void exmp(int n, int& f) { int u1, u2; if (n<2) f = n+1; else { exmp((int)(n/2), u1); exmp((int)(n/4), u2); f = u1*u2; fu( n ) n 1 当 n 2 时 fu( n / 2 )* fu( n / 4 ) n 2 时 84

85 3.1.3 递归转非递归 函数运行时的动态存储分配 栈 (stack) 用于分配后进先出 LIFO 的数据 如函数调用 堆 (heap) 用于不符合 LIFO 的 如指针所指向空间的分配 代码区域 代码区域 全程静态区域 / 栈 自由空间 堆 85

86 3.1.3 递归转非递归 函数调用及返回的步骤 调用 保存调用信息 ( 参数, 返回地址 ) 分配数据区 ( 局部变量 ) 控制转移给被调函数的入口 返回 保存返回信息 释放数据区 控制转移到上级函数 ( 主调用函数 ) 主流程 函数函数 函数 86

87 3.1.3 递归转非递归 函数执行过程图解 u1=f=2 fu ( Exmp(7,&f) n ) f=u1*u2=4 u2=f=2 n 1 fu( 当 n 2 时 n / 2 )* fu( n / 4 ) n 2 时 f=u1*u2=2 u1=f=2 Exmp(3,&f) u2=f=1 Exmp(1,&f) f=2 f=2 Exmp(1,&f) Exmp(0,&f) f=1 87

88 3.1.3 递归转非递归 用栈模拟递归调用过程 后调用, 先返回 (LIFO), 所以用栈 void exmp(int n, int& f) { int u1, u2; if (n<2) f = n+1; else { exmp((int)(n/2), u1); exmp((int)(n/4), u2); f = u1*u2; rd=1: rd=2: n=1 n=0 f=2 f=? f=1 u1=? u2=? rd=1: rd=2: n=3 n=1 f=? f=2 u1=2 u1=? u2=? u2=1 rd=3: n=7 f=? u1=? u1=2 u2=? u2=2 88

89 思考 对以下函数, 请画出 n=4 情况下的递归树, 并用栈模拟递归的调用过程 阶乘函数 2 阶斐波那契函数 f 0 =0, f 1 =1, f n = f n-1 + f n-2 89

90 第 3 章栈与队列 栈 栈的应用 递归到非递归的转换 队列 90

91 递归转非递归 递归函数调用原理 机械的递归转换 优化后的非递归函数 91

92 递归转换为非递归的方法 机械方法 (2) 机械的递归转换 fu( n) 1. 设置一工作栈当前工作记录 2. 设置 t+2 个语句标号 3. 增加非递归入口 4. 替换第 i (i = 1,, t) 个递归规则 5. 所有递归出口处增加语句 :goto label t+1; 6. 标号为 t+1 的语句的格式 7. 改写循环和嵌套中的递归 8. 优化处理 n 1 fu( 当 n 2 时 n / 2 )* fu( n / 4 rd=2: n=0 f=? u1=? u2=? rd=1: n=3 f=? u1=? u1=2 u2=? rd=3: n=7 f=? u1=? u2=? ) n 2 时 92

93 (2) 机械的递归转换 1. 设置一工作栈记录当前工作记录 在函数中出现的所有参数和局部变量都必须用栈中相应的数据成员代替 返回语句标号域 (t+2 个数值 ) 函数参数 ( 值参 引用型 ) 局部变量 typedef struct elem { // 栈数据元素类型 int rd; Datatypeofp1 p1; Datatypeofpm pm; Datatypeofq1 q1; ELEM; Datatypeofqn qn; // 返回语句的标号 // 函数参数 // 局部变量 93

94 (2) 机械的递归转换 2. 设置 t+2 个语句标号 label 0 : 第一个可执行语句 label t+1 : 设在函数体结束处 label i (1<=i<=t): 第 i 个递归返回处 94

95 (2) 机械的递归转换 // 入栈 3. 增加非递归入口 S.push(t+1,p1,,pm,q1, qn); 95

96 (2) 机械的递归转换 4. 替换第 i (i=1,,t) 个递归规则 假设函数体中第 i (i=1,, t) 个递归调用语句为 : recf(a1, a2,,am); 则用以下语句替换 : S.push(i, a1,, am); // 实参进栈 goto label 0;.. label i: x = S.top();S.pop(); /* 退栈, 然后根据需要, 将 x 中某些值赋给栈顶的工作记录 S.top () 相当于把引用型参数的值回传给局部变量 */ 主流程 函数 函数 函数 96

97 (2) 机械的递归转换 5. 所有递归出口处增加语句 goto label t+1; 97

98 (2) 机械的递归转换 6. 标号为 t+1 的语句 switch ((x=s.top ()).rd) { case 0 : goto label 0; break; case 1 : goto label 1; break;. case t+1 : item = S.top(); S.pop(); // 返回 break; default : break; 98

99 (2) 机械的递归转换 7. 改写循环和嵌套中的递归 对于循环中的递归, 改写成等价的 goto 型循环 对于嵌套递归调用 例如,recf ( recf()) 改为 : exmp 1 = recf ( ); exmp 2 = recf (exmp 1 ); exmp k = recf (exmp k-1 ) 然后应用规则 4 解决 99

100 (2) 机械的递归转换 进一步优化 8. 优化处理 去掉冗余进栈 / 出栈 根据流程图找出相应的循环结构, 从而消去 goto 语句 100

101 (2) 机械的递归转换 数据结构定义 fu( n) n 1 当 n 2 时 fu( n / 2 )* fu( n / 4 ) n 2 时 typedef struct elem { int rd, pn, pf, q1, q2; ELEM; class nonrec { ; private: stack <ELEM> S; public: nonrec(void) { // constuctor void replace1(int n, int& f); rd=2: n=0 f=? u1=? u2=? rd=1: n=3 f=? u1=? u1=2 u2=? rd=3: n=7 f=? u1=? u2=? 101

102 (2) 机械的递归转换 递归入口 void nonrec::replace1(int n, int& f) { ELEM x, tmp x.rd = 3; x.pn = n; S.push(x); // 压在栈底作 监视哨 label0: if ((x = S.top()).pn < 2) { S.pop( ); x.pf = x.pn + 1; S.push(x); goto label3; 102

103 (2) 机械的递归转换 第一个递归语句 fu( n) x.rd = 1; // 第一处递归 x.pn = (int)(x.pn/2); S.push(x); goto label0; label1: tmp = S.top(); S.pop(); x = S.top(); S.pop(); x.q1 = tmp.pf; // 修改 u1=pf S.push(x); n 1 当 n 2 时 fu( 主流程 n / 2 )* fu( n / 4 函数函数 函数 ) n 2 时 103

104 (2) 机械的递归转换 第二个递归语句 x.pn = (int)(x.pn/4); x.rd = 2; S.push(x); goto label0; label2: tmp = S.top(); S.pop(); x = S.top(); S.pop(); x.q2 = tmp.pf; x.pf = x.q1 * x.q2; S.push(x); 104

105 (2) 机械的递归转换 label3: x = S.top(); switch(x.rd) { case 1 : goto label1; break; case 2 : goto label2; break; case 3 : tmp = S.top(); S.pop(); f = tmp.pf; // 计算结束 break; default : cerr << "error label number in stack"; break; 105

106 (3) 优化后的非递归函数 优化后的非递归算法 void nonrec::replace2(int n, int& f) { ELEM x, tmp; // 入口信息 x.rd = 3; x.pn = n; S.push(x); do { // 沿左边入栈 while ((x=s.top()).pn >= 2){ x.rd = 1; x.pn = (int)(x.pn/2); S.push(x); 106

107 (3) 优化后的非递归函数 x = S.top(); S.pop(); // 原出口,n <= 2 x.pf = x.pn + 1; S.push(x); // 如果是从第二个递归返回, 则上升 while ((x = S.top()).rd==2) { tmp = S.top(); S.pop(); x = S.top(); S.pop(); x.pf = x.q * tmp.pf; S.push(x); 107

108 (3) 优化后的非递归函数 if ((x = S.topValue()).rd == 1) { tmp = S.top(); S.pop(); x = S.top(); S.pop(); x.q = tmp.pf; S.push(x); tmp.rd = 2; // 进入第二个递归 tmp.pn = (int)(x.pn/4); S.push(tmp); while ((x = S.top()).rd!= 3); x = S.top(); S.pop(); f = x.pf; 108

109 递归转非递归的性能实验 快排的时间对照 ( 单位 ms) 方法 数据量 递归快排 机械方法的非递归快排 非机械方法的非递归快排 STL 中的 sort 注 : 测试环境 Intel Core Duo CPU T2350 内存 512MB 操作系统 Windows XP SP2 编程环境 Visual C

110 递归转非递归的性能实验 递归与非递归处理问题的规模 递归求 f(x): int f(int x) { if (x==0) return 0; return f(x-1)+1; 在默认设置下, 当 x 超过 11,772 时会出现堆栈溢出 非递归求 f(x), 栈中元素记录当前 x 值和返回值 在默认设置下, 当 x 超过 32,375,567 时会出现错误 110

111 用机械的转换方法 阶乘函数 2 阶斐波那契函数 思考 f 0 =0, f 1 =1, f n = f n-1 + f n-2 Hanoi 塔算法 111

112 数据结构与算法 谢谢聆听 国家精品课 数据结构与算法 张铭, 王腾蛟, 赵海燕高等教育出版社, 十一五 国家级规划教材