第三章栈与队列ppt课件

1、第三章 栈与队列赵建华第三章 栈与队列l只允许在一端插入和删除的线性表l允许插入和删除l的一端称为栈顶l(top)，另一端称l为栈底(bottom)l特点l后进先出 (LIFO)栈 ( Stack )退栈进栈a0an-1an-2topbottomtemplate class Stack /栈的类定义栈的类定义public: Stack() ;/构造函数构造函数 virtual void Push(T x) = 0; /进栈进栈 virtual bool Pop(T& x) = 0; /出栈出栈 virtual bool getTop(T& x) = 0; /取栈顶取栈顶 vir

2、tual bool IsEmpty() = 0; /判栈空判栈空 virtual bool IsFull() = 0; /判栈满判栈满；栈的笼统数据类型栈的笼统数据类型top空栈toptoptoptopa 进栈进栈b 进栈进栈aababcdec,d,e 进栈进栈abd退栈c退栈f退栈退栈aba退栈topab退栈ctopabftoptopbtemplate class SeqStack : public Stack /顺序栈类定义顺序栈类定义private: T *elements;/栈元素存放数组栈元素存放数组 int top;/栈顶指针栈顶指针 int maxSize; /栈最大容量栈最大容

3、量 void overflowProcess(); /栈的溢出处置栈的溢出处置public:;栈的数组存储表示 顺序栈0 1 2 3 4 5 6 7 8 9 maxSize-1top (栈空栈空)elementstemplate void SeqStack:Push(T& x) /假设栈不满假设栈不满, 那么将元素那么将元素x插入该栈栈顶插入该栈栈顶, 否那么溢否那么溢出处置出处置 if (IsFull( ) = true) overflowProcess; /栈满栈满 elements+top = x; /栈顶指针先加栈顶指针先加1, 再进栈再进栈; template bool Se

4、qStack:Pop(T& x) /函数退出栈顶元素并前往栈顶元素的值函数退出栈顶元素并前往栈顶元素的值 if (IsEmpty() = true) return false; x = elementstop-; /栈顶指针退栈顶指针退1 return true; /退栈胜利退栈胜利; template bool Seqstack:getTop(T& x) /假设栈不空那么函数前往该栈栈顶元素的地址假设栈不空那么函数前往该栈栈顶元素的地址 if (IsEmpty() = true) return false; x = elementstop; return true;templ

5、ate void SeqStack:overflowProcess() /私有函数：当栈满那么执行扩展栈存储空间处置私有函数：当栈满那么执行扩展栈存储空间处置 T *newArray = new T2*maxSize;/创建更大的存储数组创建更大的存储数组 for (int i = 0; i = top; i+) newArrayi = elementsi; maxSize += maxSize; delete elements; elements = newArray; /改动改动elements指针指针;思索直接运用SeqList实现class SeqStack : public Stac

6、k private: SeqListst;/栈元素存放数组栈元素存放数组public:push(T& x)st.Insert(st.getLength(), x);pop(T& x)st.Remove(st.getLength(),x);双栈共享一个栈空间b0 t0 t1 b10 maxSize-1Vl两个栈共享一个数组空间两个栈共享一个数组空间VmaxSize，两个栈的栈，两个栈的栈底分别位于数组的开头和结尾；分别向中间生长。底分别位于数组的开头和结尾；分别向中间生长。l主要目的是节约空间：主要目的是节约空间：l两个独立栈，预期的最大空间两个独立栈，预期的最大空间max(si

7、ze of stack1)+max(size of stack2)。l而双栈空间是而双栈空间是max(size of stack1 + size of stack2)。实现方法l设立栈顶指针数组设立栈顶指针数组 t2 和栈底指针数组和栈底指针数组 b2lti和和bi分别指示第分别指示第 i 个栈的栈顶与栈底个栈的栈顶与栈底l初始化初始化lt0 = b0 = -1, t1 = b1 = maxSize l栈满条件：栈满条件：t0+1 = t1 /栈顶指针相遇栈顶指针相遇l栈空条件：栈空条件：t0 = b0t1 = b1 /退到栈底退到栈底l对第一个栈压栈时对第一个栈压栈时:元素放入元素放入Vt0

8、+1;l对第二个栈压栈时对第二个栈压栈时:元素放入元素放入Vt1-1;bool push(DualStack& DS, Type x, int i) if (DS.t0+1 = DS.t1) return false; /栈满栈满 if (i = 0)DS.t0+; /压入第一个栈压入第一个栈 elseDS.t1-;/压入第二个栈压入第二个栈 DS.VDS.ti = x; return true;假设某次调用是假设某次调用是push(DS, x, 0)，上面的程序实践上相当于，上面的程序实践上相当于bool push(DualStack& DS, Type x, int i)

9、if (DS.t0+1 = DS.t1) return false; /栈满栈满 DS.t0+; /栈顶指针加栈顶指针加1 DS.VDS.t0 = x;/设置压栈数据设置压栈数据 return true;可以看到，这个程序实践上就是前面的普通压栈程序；可以看到，这个程序实践上就是前面的普通压栈程序；当当i=1时，相当于反向的压栈。时，相当于反向的压栈。bool Pop(DualStack& DS, Type& x, int i) if (DS.ti = DS.bi) return false; x = DS.VDS.ti; if (i = 0) DS.t0-;/弹出第一个栈弹出

10、第一个栈 else DS.t1+;/弹出第二个栈弹出第二个栈 return true; 栈的链接存储表示 链式栈l链式栈无栈满问题，空间可扩展链式栈无栈满问题，空间可扩展l插入与删除仅在栈顶处执行，效率为插入与删除仅在栈顶处执行，效率为O(1)l链式栈的栈顶在链头链式栈的栈顶在链头l适宜于多栈操作适宜于多栈操作top链式栈链式栈 (LinkedStack) (LinkedStack)类的定义类的定义 实践上是运用单链表来实现栈的操作实践上是运用单链表来实现栈的操作 #include #include “stack.h template struct StackNode /栈结点类定义栈结点类定

11、义 private: T data; /栈结点数据栈结点数据 StackNode *link; /结点链指针结点链指针 public: StackNode(T d = 0, StackNode *next = NULL) : data(d), link(next) ; template class LinkedStack : public Stack /链式栈类定义链式栈类定义 private: StackNode *top; /栈顶指针栈顶指针 void output(ostream& os, StackNode *ptr, int& i); /递归输出栈的一切元素递归输出栈

12、的一切元素public:void Push(T& x); /进栈进栈bool Pop(T& x); /退栈退栈bool getTop(T& x) const;/取栈顶取栈顶 bool IsEmpty() const return top = NULL; void makeEmpty();/清空栈的内容清空栈的内容;链式栈类操作的实现链式栈类操作的实现LinkedStack:makeEmpty() /逐次删去链式栈中的元素直至栈顶指针为空。 StackNode *p;while (top != NULL)/逐个结点释放 p = top; top = top-link; d

13、elete p; ;回想单链表中的makeempty操作void LinkedStack:Push(T x) /将元素值x插入到链式栈的栈顶,即链头。top = new StackNode (x, top); /创建新结点，并使得新结点的link执行原来的topassert (top != NULL);/创建失败退出;回想单链表中的Insert(0,x)操作bool LinkedStack:Pop(T& x) /删除栈顶结点删除栈顶结点, 前往被删栈顶元素的值。前往被删栈顶元素的值。 if (IsEmpty() = true) return false; /栈空前往栈空前往 Stack

14、Node *p = top;/暂存栈顶元素暂存栈顶元素 top = top-link;/退栈顶指针退栈顶指针 x = p-data; delete p;/释放结点释放结点 return true;回想单链表中的回想单链表中的delete(0);bool LinkedStack:getTop(T& x) const if (IsEmpty() = true) return false; /栈空前往栈空前往 x = top-data; /前往栈顶元素的值前往栈顶元素的值 return true; 回想单链表中的回想单链表中的getData(0, T& x)用LinkList实现栈t

15、emplate class LinkedStack : public Stack private:LinkList st; /栈中元素；栈中元素；public:void Push(T x)st.Insert(0, x); /进栈进栈bool Pop(T& x)return st.Remove(0,x); /退栈退栈bool getTop(T& x) const /取栈顶取栈顶 E*p=getData(x); if(!p)return false; else x=*p; return true;bool IsEmpty() const return st.IsEmpty(); v

16、oid makeEmpty() st.makeEmpty(); /清空栈的内容清空栈的内容;注：上面对注：上面对st的各个成员函数的调用都是的各个成员函数的调用都是O(1)时间的。时间的。队列 ( Queue )定义定义队列是只允许在一端删除，在另一端插入的队列是只允许在一端删除，在另一端插入的线性表线性表允许删除的一端叫做队头允许删除的一端叫做队头(front)，允许插入，允许插入的一端叫做队尾的一端叫做队尾(rear)。特性特性先进先出先进先出(FIFO, First In First Out)a0 a1 a2 an-1frontreartemplate class Queue publi

17、c: Queue() ; /构造函数构造函数 Queue() ; /析构函数析构函数 virtual bool EnQueue(E x) = 0; /进队列进队列 virtual bool DeQueue(E& x) = 0；/出队列出队列 virtual bool getFront(E& x) = 0; /取队头取队头 virtual bool IsEmpty() const = 0; /判队列空判队列空 virtual bool IsFull() const = 0; /判队列满判队列满;注：假设需求访问队列内部的元素，或者遍历，那么依然注：假设需求访问队列内部的元素，或者

18、遍历，那么依然建议实现建议实现Iterator接口接口队列的笼统数据类型 运用数组来存放队列中的元素；数组中的元素是循环存放的。 两个指针front和rear指示队列的首尾位置。 假设rear大于front，队列中就包括从front到rear不含的元素。 假设rear等于front，表示空表； 假设rear小于front，那么队列中包括从front到数组末尾，再从数组开头到达rear不含的数据。 队空：front=rear 队满：(rear+1)%maxSize=front队列的数组存储表示 顺序队列队列的进队和出队 front rear空队列空队列front rearA进队进队Afront

19、rearB进队进队A Bfront rearC, D进队进队A B C Dfront rearA退队退队B C Dfront rearB退队退队C Dfront rearE,F,G进队进队C D E F Gfront rearH进队进队C D E F GH队头、队尾指针加1时从maxSize-1直接进到0，可用言语的取模(余数)运算实现。队头指针进1: front = (front+1) % maxSize;队尾指针进1: rear = (rear+1) % maxSize;队列初始化：front = rear = 0;队空条件：front = rear;队满条件：(rear+1) % max

20、Size = front 循环队列 (Circular Queue)class SeqQueue : public Queue /队列类定义队列类定义protected: int rear, front; /队尾与队头指针队尾与队头指针 E *elements; /队列存放数组队列存放数组 int maxSize; /队列最大容量队列最大容量public: SeqQueue(int sz = 10); /构造函数：构造函数：/恳求空间，设置恳求空间，设置maxSize，front，rear。SeqQueue() delete elements; /析构函数析构函数 bool EnQueue(E

21、 x); /新元素进队列新元素进队列 bool DeQueue(E& x); /退出队头元素退出队头元素 bool getFront(E& x); /取队头元素值取队头元素值 void makeEmpty() front = rear = 0; bool IsEmpty() const return front = rear; bool IsFull() const return (rear+1)% maxSize = front); int getSize() const return (rear-front+maxSize) % maxSize; ;template boo

22、l SeqQueue:EnQueue(E x) /假设队列不满假设队列不满, 那么将那么将x插入到该队列队尾插入到该队列队尾, 否那么前往否那么前往 if (IsFull() = true) return false; elementsrear = x; /先存入先存入 rear = (rear+1) % maxSize; /尾指针加一尾指针加一 return true;template bool SeqQueue:DeQueue(E& x) /假设队列不空那么函数退队头元素并前往其值假设队列不空那么函数退队头元素并前往其值 if (IsEmpty() = true) return f

23、alse;x = elementsfront; /先取队头先取队头 front = (front+1) % maxSize; /再队头指针加一再队头指针加一 return true; template bool SeqQueue:getFront(E& x) const /假设队列不空那么函数前往该队列队头元素的值假设队列不空那么函数前往该队列队头元素的值 if (IsEmpty() = true) return false; /队列空队列空 x = elementsfront; /前往队头元素前往队头元素 return true; 思索题：假设运用顺序表中的思索题：假设运用顺序表中的

24、Remove(0,X)和和Insert(n,X)来来实现队列的实现队列的DeQueue和和EnQueue操作，效果如何？操作，效果如何？SeqQueue:SeqQueue(int sz):front(0),rear(0),maxSize(sz)elements = new TmaxSize;assert(elements != NULL); /在调试版本下，假设在调试版本下，假设elements = NULL会报会报告错误；告错误；队列的链接存储表示 链式队列队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为 front = NULL此时rear为空？frontrea

25、rtemplate struct QueueNode /队列结点类定义队列结点类定义private: E data; /队列结点数据队列结点数据 QueueNode *link; /结点链指针结点链指针public: QueueNode(E d = 0, QueueNode* next = NULL) : data(d), link(next) template class LinkedQueue private: QueueNode *front, *rear; /队头、队尾指针队头、队尾指针public: LinkedQueue() : rear(NULL), front(NULL) Li

26、nkedQueue();链式队列类的定义template LinkedQueue:LinkedQueue() /析构函数析构函数 QueueNode *p; while (front != NULL) /逐个结点释放逐个结点释放 p = front; front = front-link; delete p; ;template bool LinkedQueue:EnQueue(T x) /将新元素将新元素x插入到队列的队尾插入到队列的队尾 if (front = NULL) /创建第一个结点创建第一个结点 front = rear = new QueueNode (x);/保证保证rear总

27、是指向对尾总是指向对尾 if (front = NULL) return false; /分配失败分配失败 else /队列不空队列不空, 插入插入 rear-link = new QueueNode (x); if (rear-link = NULL) return false; rear = rear-link; return true;template /假设队列不空，将队头结点从链式队列中删去假设队列不空，将队头结点从链式队列中删去 bool LinkedQueue:DeQueue(T& x) if (IsEmpty() = true) return false; /判队空判队

28、空 QueueNode *p = front; x = front-data; front = front-link; delete p; return true;template bool LinkedQueue:GetFront(T& x) /假设队列不空，那么函数前往队头元素的值假设队列不空，那么函数前往队头元素的值 if (IsEmpty() = true) return false; x = front-data; return true;思索题添加附加的队列头结点能否简化实现？如运用单链表的Insert(n,X)和Remove(0,X)分别实现EnQueue和DeQueue

29、，效率如何？带有尾指针的单链表呢？栈的运用：表达式求值 栈的LIFO特性决议了它比较适宜用来处置具有嵌套构造/递归构造的问题: 括号匹配，表达式求值 由于LIFO特性，假设一个运用中总是把前面求出的某个值和后续求出的某个值进展运算得到一个新结果，并且从此之后前面求出的值就不再需求，就可以思索运用栈来完成计算。 在计算这些值的过程中，能够还需求计算一些中间结果，那么这些中间结果的计算也需求遵照这样的方式。 此时可以把运算分量入栈，然后在计算结果时在栈顶获得运算分量。结果能够还需求入栈。中缀表达式中缀表达式 a + b * ( c - d ) - e / f后缀表达式后缀表达式 a b c d -

30、 * + e f / -前缀表达式前缀表达式 - + a * b c d / e f中缀表达式中相邻两个操作符的计算次序为：中缀表达式中相邻两个操作符的计算次序为：优先级高的先计算优先级高的先计算优先级一样的自左向右计算优先级一样的自左向右计算当运用括号时从最内层括号开场计算当运用括号时从最内层括号开场计算但是括号左边的值的计算可以先期进展但是括号左边的值的计算可以先期进展表达式例如后缀表达式的计算l每个子表达式的计算结果，和下一个并列子每个子表达式的计算结果，和下一个并列子表达式的计算结果，根据后续的运算符进展表达式的计算结果，根据后续的运算符进展运算，得到较大的子表达式的结果。运算，得到较

31、大的子表达式的结果。l从左向右顺序地扫描表达式，并用一个栈暂从左向右顺序地扫描表达式，并用一个栈暂存扫描到的操作数或计算结果。存扫描到的操作数或计算结果。l计算计算rst1rst2rst3rst4rst5a b c d - * + e f / -计算方式 从左到右扫描后缀表达式： 假设是数字最小的子表达式，压栈 假设是运算符和前面的子表达式一同，组成一个较大的子表达式，从栈中弹出相应的分量，并计算结果。将结果压栈。 例如：3 5 + 2 * 首先3，5入栈 然后处置+，3、5出栈，得到结果83 5 +)，再入栈 2入栈 处置*，8，2出栈，得到结果(3 5 + 2 *)16，再入栈，完成。 思

32、索题 假设要把后缀表达式转成中缀表达式，怎样做？ 假设利用上面的算法的框架？中缀表示转后缀表示中缀表达式：用+、-衔接起来的项的序列；项：用*、/衔接起来的因子序列因子：整数变量或括号中的表达式转化规那么term1 + term2 - term3 term1 term2 + term3 -factor1 * factor2 / factor3 factor1 factor2 * factor3 /方法不思索效率 将中缀到后缀的转换看作是一种运算 普通的+运算是求和 分量的值是其后缀表示，+运算是把分量的后缀表示组合成为新的后缀表示 同样运用栈来存放结果和运算符 栈顶有+号 下一个运算符是+/-

33、/)/#，将两个运算分量相加； 下一个运算符是*，要先进展乘法运算，将*压栈； 当栈顶有*号时，方法不思索效率设置一个栈存放曾经扫描过的分量及其后缀表示方式和运算符。自左向右扫描中缀表达式。假设扫描到整数，直接作为operand入栈，相应的后缀方式就是这个整数。假设扫描到+，-号；假设之前扫描到了“operand1(+,-,*,/)operand1的方式，就可以把这两个项的归约成为一个项，然后计算其后缀方式。把前面的三个元素出栈，把这个项和它的后缀方式一同入栈。否那么不需求进展处置。当前扫描到的符号入栈。假设扫描到*，/号：处置方法和前面类似，但是只思索*，/。假设扫描到(，阐明要首先扫描到一

34、个表达式和一个)将(入栈。假设扫描到一个)，阐明要和前面的匹配，成为一个因子。假设栈顶型如operand * operand，那么计算operand * operand的后缀方式；将三个元素出栈，计算结果入栈。第一步之后，假设栈顶型如operand+operand，那么进展类似处置。前面两步之后，栈顶必然是型如(operand的方式：将两个元素出栈，然后operand入栈。扫描到终了时，按照)处置，但是不需求思索左括号。例子 输入：A+B*(C-D)-E/F分量D-分量C(*分量B+分量A分量CD-(*分量B+分量A分量CD-*分量B+分量A分量BCD-*+分量A分量F/分量E-分量ABCD-

35、*+计算C-D处置(C-D)计算B*(C-D)计算A+B*(C-D)，继续入栈这个方法的框架不仅可以计算后缀，也可以直接计算表达式的值，还可以计算一个程序中的表达式的类型。更加高效的实现方法 重要的现实 对于一切的表达式，其后缀表示中的各运算分量的顺序不变。 一个表达式的后缀表示是它的第一个子表达式的后缀表示，并联上第二个表达式的后缀表示，然后加上一个运算符。 term1 + term2 - term3 term1 term2 + term3 - factor1 * factor2 / factor3 factor1 factor2 * factor3 / 因此，我们可以思索在扫描到运算分量的

36、时候直接输出；而在原来计算新后缀的地方添加上相应的运算符号。 请本人看书上的转换方法栈的运用：递归栈的运用：递归递归的定义递归的定义 假设一个对象部分地包含它本人，或用假设一个对象部分地包含它本人，或用它本人给本人定义它本人给本人定义, 那么称这个对象是递归那么称这个对象是递归的；假设一个过程直接地或间接地调用本人的；假设一个过程直接地或间接地调用本人, 那么称这个过程是递归的过程。那么称这个过程是递归的过程。以下三种情况经常用到递归方法。以下三种情况经常用到递归方法。 定义是递归的定义是递归的 数据构造是递归的数据构造是递归的 问题的解法是递归的问题的解法是递归的定义是递归的定义是递归的求解

37、阶乘函数的递归算法求解阶乘函数的递归算法long Factorial(long n) if (n = 0) return 1; else return n*Factorial(n-1);例如，阶乘函数例如，阶乘函数时时当当时时当当 1 ,)!1( 0 , 1!nnnnn求解阶乘求解阶乘 n! 的过程的过程参数参数 4参数参数 3参数参数 2参数参数 1参数参数 0 直接定值直接定值 = 1 前往前往 1计算计算 4*fact(3) 前往前往 24计算计算 3*fact(2) 前往前往 6计算计算 2*fact(1) 前往前往 2计算计算 1*fact(0) 前往前往 1数据构造由更小的类似的数

38、据构造组成。数据构造由更小的类似的数据构造组成。对这个数据构造的处置，分解成对较小部分对这个数据构造的处置，分解成对较小部分的递归处置的递归处置例如，单链表构造例如，单链表构造一个指针域为一个指针域为NULL的节点组成一个单链表的节点组成一个单链表;一个其指针域指向单链表的结点，组成一个一个其指针域指向单链表的结点，组成一个单链表。单链表。f f 数据构造是递归的数据构造是递归的搜索链表最后一个结点并打印其数值搜索链表最后一个结点并打印其数值template template void PrintLastNode(ListNode void PrintLastNode(ListNode * *

39、f) f) if (f -link = NULL) if (f -link = NULL) cout data endl; cout data link); PrintLastNode(f -link); /f-link /f-link所指向的链表的最后结点就所指向的链表的最后结点就是是f f所指向链表的最后结点所指向链表的最后结点 f f f f f a0a1a2a3a4递归找链尾在链表中寻觅等于给定值的结点并打印其数值在链表中寻觅等于给定值的结点并打印其数值template void Print(ListNode *f, E value) if (f != NULL) if (f - da

40、ta = value) cout data link, value);f f f f 递归找含x值的结点x问题的解法是递归的问题的解法是递归的汉诺塔汉诺塔(Tower of Hanoi)问题的解法：问题的解法：假设假设 n = 1，那么将这一个盘子直接从，那么将这一个盘子直接从 A 柱移到柱移到 C 柱上。柱上。假设假设n1，必需先把，必需先把n-1个盘子挪动到个盘子挪动到B，然后再把盘子然后再把盘子n挪动到挪动到C。因此执行以下三。因此执行以下三步：步：用用 C 柱做过渡，将柱做过渡，将 A 柱上的柱上的 (n-1) 个盘子个盘子移到移到 B 柱上；柱上；将将 A 柱上最后一个盘子直接移到柱

41、上最后一个盘子直接移到 C 柱上；柱上；用用 A 柱做过渡，将柱做过渡，将 B 柱上的柱上的 (n-1) 个盘子个盘子移到移到 C 柱上。柱上。#include void Hanoi (int n, char A, char B, char C) /处理汉诺塔问题的算法处理汉诺塔问题的算法 if (n = 1) cout move A to C endl; else Hanoi(n-1, A, C, B); cout move A to C CA,B,C(1,A,C,B)A,B,CA-CA-C(1,B,A,C)A,B,CA-CA-BA-BA-CB-CC-BA-C(2,B,A,C)A,B,C(1

42、,A,C,B)A,B,CA-CA-C(1,B,A,C)A,B,CA-CB-CA-BB-AB-CA-C自顶向下、逐渐分解的战略自顶向下、逐渐分解的战略处理递归问题的战略是把一个规模比较大的处理递归问题的战略是把一个规模比较大的问题分解为一个或假设干规模比较小的问题，问题分解为一个或假设干规模比较小的问题，分别对这些比较小的问题求解，再综合它们分别对这些比较小的问题求解，再综合它们的结果，从而得到原问题的解。的结果，从而得到原问题的解。 分而治之战略分治法分而治之战略分治法这些比较小的问题的求解方法与原来问题的这些比较小的问题的求解方法与原来问题的求解方法一样；子问题应与原问题做同样的求解方法一样

43、；子问题应与原问题做同样的事情，且更为简单；那么适用递归事情，且更为简单；那么适用递归构成递归的条件构成递归的条件不能无限制地调用本身不能无限制地调用本身必需有一个出口，化简为非递归情况直接处置。必需有一个出口，化简为非递归情况直接处置。必需保证分解之后的子问题要必需保证分解之后的子问题要“小于原来的问题，并且保证小于原来的问题，并且保证总是可以把一个问题分解到一个可直接处置的根本问题。总是可以把一个问题分解到一个可直接处置的根本问题。 Procedure ( ) if ( ) /递归终了条件递归终了条件 直接处置并前往；直接处置并前往； else /递归递归递归调用递归调用过程，并且进展某些

44、综合处置，过程，并且进展某些综合处置，然后前往；然后前往； 递归过程在实现时，需求本人调用本人。递归过程在实现时，需求本人调用本人。层层向下递归，退出时的次序正好相反：层层向下递归，退出时的次序正好相反： 递归调用递归调用 n! (n-1)! (n-2)! 1! 0!=1 前往次序前往次序主程序第一次调用递归过程为外部调用；主程序第一次调用递归过程为外部调用；递归过程每次递归调用本人为内部调用。递归过程每次递归调用本人为内部调用。它们前往调用它的过程的地址不同。它们前往调用它的过程的地址不同。递归过程与递归任务栈递归过程与递归任务栈 long Factorial(long n) int tem

45、p; if (n = 0) return 1; else temp = n * Factorial(n-1); return temp; void main() int n; n = Factorial(4); RetLoc1RetLoc2递归任务栈递归任务栈每一次递归调用时，需求为过程中运用的每一次递归调用时，需求为过程中运用的参数、部分变量等另外分配存储空间。参数、部分变量等另外分配存储空间。每层递归调用需分配的空间构成递归任务每层递归调用需分配的空间构成递归任务记录，按后进先出的栈组织。记录，按后进先出的栈组织。 递归递归任务记录任务记录函数递归时的活动记录函数递归时的活动记录.Func

46、tion() .调用块调用块函数块函数块计算计算Fact时活动记录的内容时活动记录的内容递递归归调调用用序序列列0 1 RetLoc21 1 RetLoc22 2 RetLoc23 6 RetLoc24 24 RetLoc1参数参数 前往值前往值 前往地址前往地址 前往时的指令前往时的指令return 4*6 /前往前往 24 return 3*2 /前往前往 6 return 1 /前往前往 1 return 1*1 /前往前往 1 return 2*1 /前往前往 2 递归过程改为非递归过程递归过程改为非递归过程递归的优点递归的优点简约、易编、易懂简约、易编、易懂缺陷缺陷效率低，反复计算多

47、效率低，反复计算多改为非递归过程的目的是提高效率改为非递归过程的目的是提高效率单向递归和尾递归可直接用迭代实现其单向递归和尾递归可直接用迭代实现其非递归过程非递归过程其他情形能够必需借助栈来实现非递归其他情形能够必需借助栈来实现非递归过程过程单向递归问题单向递归问题 单向递归 一个递归函数递归地调用本身时，其参数按照特定的方向变化。 比如按照特定的步长变小； 该函数不向全局变量赋值； 对于一个特定的调用recurFun(p)，我们可以知道这个函数会以哪些参数调用recurFun。 可以思索设置一些变量来记录中间数据，并且从初始条件开场计算各个参数的recurFun值计算斐波那契数列的函数计算斐

48、波那契数列的函数Fib(n)Fib(n)的定义的定义求解斐波那契数列的递归算法求解斐波那契数列的递归算法 long Fib(long n) long Fib(long n) if (n = 1) return n; if (n = 1) return n; else return Fib(n-1)+Fib(n-2); else return Fib(n-1)+Fib(n-2); 1n2),Fib(n1)Fib(n0,1nn,)Fib(n如如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5 调用次数调用次数 NumCall(k) = 2*Fib(k+

49、1)-1斐波那契数列的递归调用树斐波那契数列的递归调用树Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)简单的迭代实现简单的迭代实现 Fib(n)的计算依赖于Fib(n-1)和Fib(n-2)的值。参数总是不断减小； 最简单的想法 一个足够大的数组A，Ai记录Fib(i)的值。 按照从小到大的方式计算，就可以得到Fib(n)。 然而需求大量的空间。ABIG_NUM;A0=0; A1 = 1;for(int i=2; i=n; i+)Ai=Ai-1+Ai-2;ret

50、urn An;单向递归用迭代法实现单向递归用迭代法实现计算计算Fib(i)的时候，我们只需求的时候，我们只需求Fib(i-1)和和Fib(i-2)的值。的值。用用oneback和和twoback来保管这两个值，然后计算完来保管这两个值，然后计算完Fib(i)之之后，就丢弃后，就丢弃Fib(i-2)。long FibIter(long n) if (n = 1) return n;/对应于初始条件；对应于初始条件； long twoback = 0, oneback = 1, Current; for (int i = 2; i = n; i+) Current = twoback + oneb

51、ack; twoback = oneback; oneback = Current; return Current;其他可迭代化的递归调用(1) 一个程序几乎在最后递归调用本人，然后对前往值进展运算后前往。 该运算的其他分量可以根据该函数的参数计算得到。 并且我们可以知道调用时的参数序列。 求解阶乘函数的递归算法long Factorial(long n) if (n = 0) return 1;else return n*Factorial(n-1);其他可迭代化的递归调用(2) 迭代化后的程序： result = 1；/初始条件下的前往值； for(i=1; i= 0) cout An = 0) cout value An endl; n-; 运用栈的迭代实现方法 模拟递归栈，栈中保管 部分变量 参数 前往值存放地址； 当前处置进度相当于前往时需将执行地址 运用入栈/出栈来模拟递归调用/前往 调用：设置栈顶的进度标志；设置参数、前往值地址入栈 前往：拷贝前往值，出栈 其他计算过程：根据当前进度标志执行；运用栈的Fib的迭代实现1