第3章栈与队列PPT课件

1、第第3章章 栈与队列栈与队列 目录目录 1.栈栈 2. 栈的栈的应用举例应用举例 3. 栈与递归栈与递归 4. 队列队列 5. 应用实例应用实例 3.1 栈栈 3.1.1 栈的定义及其运栈的定义及其运算算 栈栈（Stack）是限定插入和删除运算只能在表尾是限定插入和删除运算只能在表尾进行的线性表。进行的线性表。 通常称允许插入、删除的这一端为栈顶，另一端通常称允许插入、删除的这一端为栈顶，另一端称为栈底。称为栈底。 当表中没有元素时称为空栈。当表中没有元素时称为空栈。 其中数据元素的个数其中数据元素的个数n n定义为表的长度。定义为表的长度。图图3.13.1是一个栈的示意图，通常用指针是一个栈

2、的示意图，通常用指针toptop指示栈顶的位指示栈顶的位置，用指针置，用指针bottombottom指向栈底。栈顶指针指向栈底。栈顶指针toptop动态反映栈动态反映栈的当前位置。的当前位置。图3.1 栈进栈出栈a1a2an栈顶栈底 图图3.13.1所示的栈中，元素是以所示的栈中，元素是以a a1 1，a a2 2，a an n的顺序进栈，而出栈的顺序进栈，而出栈的次序却是的次序却是a an n，a an-1n-1，a a1 1。 也就是说，栈的修改是按后进先也就是说，栈的修改是按后进先出的原则进行的。出的原则进行的。因此，栈又称为因此，栈又称为后进先出（后进先出（Last In First

3、OutLast In First Out）的线性表，简称为）的线性表，简称为LIFOLIFO表。表。ADT Stack Typedef struct Stack S; InitStack(S,maxSize); 说明：构造空栈说明：构造空栈S，即栈的初始化，即栈的初始化 StackSize(S); 说明：求栈中元素的数目说明：求栈中元素的数目 isEmpty(S); 说明：判栈说明：判栈S是否为空栈是否为空栈 isFull(S); 说明：判栈说明：判栈S是否已是否已“满满”栈的栈的ADTADT声明如下声明如下： GetTop(S,e); 说明：取栈顶元素说明：取栈顶元素 Push (S,e);

4、 说明：值为说明：值为e的数据元素进栈（插入、压栈）的数据元素进栈（插入、压栈）Pop(S); 说明：栈顶元素出栈（删除、退栈）说明：栈顶元素出栈（删除、退栈）; 栈的顺序存储结构称为顺序栈，是用一组地址连续的栈的顺序存储结构称为顺序栈，是用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。存储单元依次存放自栈底到栈顶的数据元素。3.1.2 栈的顺序存储结构栈的顺序存储结构因为栈底位置是固定不变的，栈顶位置是随着进栈和退栈因为栈底位置是固定不变的，栈顶位置是随着进栈和退栈操作而变化的，故需用一个变量操作而变化的，故需用一个变量toptop来指示当前栈顶位置，来指示当前栈顶位置，通常称通常称

5、toptop为栈顶指针，参看图为栈顶指针，参看图3.23.2。Typedef struct int *elem; / elem是数据元素数组是数据元素数组 int top; / 栈顶指针栈顶指针 int maxSize; / 栈容量栈容量sqStack; 我们先以整数元素为例，给出顺序栈的基本我们先以整数元素为例，给出顺序栈的基本算法，在下一节，将给出顺序栈的模板类接口算法，在下一节，将给出顺序栈的模板类接口定义以及基本运算的实现代码和应用实例。定义以及基本运算的实现代码和应用实例。 void InitStack(S,maxSize) / 栈栈初始化初始化 S.top=-1; S.elem=n

6、ew intmaxSize; bool isEmpty(S) / 判栈空否？判栈空否？ return S.top=-1; bool isFull (S) / 判栈满否？判栈满否？ return top=S.maxSize-1; bool Push (sqStack S, int e) / 值为值为e的的数据元素数据元素进栈进栈(插入插入 、 压栈压栈) if(isFull(S) / 栈满（栈满（溢出溢出）无法无法进栈进栈, 返回返回false cout ERROR: overflow !n; return false; S.elem+S.top = e ; return true ; /栈顶栈

7、顶指针指针增增1元素元素进栈进栈, 返回返回truebool Pop(sqStack S) / 栈顶元素出栈栈顶元素出栈(删除删除) if(isEmpty(S) / 栈空无法删除栈空无法删除, 返回返回false cout “ ERROR: underflow !n”; return false ; S.top-; return true; / 元素出栈元素出栈bool GetTop(sqStack S, int &e) / 取栈取栈S的栈顶元的栈顶元/素素 if(isEmpty(S) / 栈空（下溢）栈空（下溢） cout “ ERROR: underflow !n”; return

8、 false ; e=S.elemS.top ; return true ; / 元素存元素存e, 栈顶指针不变栈顶指针不变(元素没出栈元素没出栈) 栈的使用非常广泛，常常会出现在一个程序中需要栈的使用非常广泛，常常会出现在一个程序中需要同时使用多个栈的情形。为了不因栈上溢而产生错同时使用多个栈的情形。为了不因栈上溢而产生错误中断，要给每个栈预分较大空间，但各个栈实际误中断，要给每个栈预分较大空间，但各个栈实际所用最大空间很难估计。而且各个栈的实际容量在所用最大空间很难估计。而且各个栈的实际容量在使用期间是变化的，往往会出现某个栈发生上溢，使用期间是变化的，往往会出现某个栈发生上溢，而另一个栈

9、还是空的。而另一个栈还是空的。试试设想设想，若令多个栈共享空间，则将提高空间的使，若令多个栈共享空间，则将提高空间的使用效率，并减少发生栈上溢的可能性。用效率，并减少发生栈上溢的可能性。假设在程序中需设两个栈，并共享一维数组空间假设在程序中需设两个栈，并共享一维数组空间vmvm。则利用则利用“栈底位置不变栈底位置不变”的特性，可将两个栈的栈底分的特性，可将两个栈的栈底分别设在数组空间的两端，然后各自向中间伸展（如图别设在数组空间的两端，然后各自向中间伸展（如图3.33.3所示），仅当两个栈的栈顶相遇时才可能发生上溢。由所示），仅当两个栈的栈顶相遇时才可能发生上溢。由于两个栈之间可以做到互补余缺

10、，使得每个栈实际可利于两个栈之间可以做到互补余缺，使得每个栈实际可利用的最大空间大于用的最大空间大于m/2m/2。显然，两个栈顶的初值分别为。显然，两个栈顶的初值分别为-1-1和和m m。栈的链式存储结构称为链栈，它是运算受限的单链表，栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行。其插入和删除操作仅限制在表头位置上进行。3.1.3 栈的链式存储结构栈的链式存储结构由于只能在链表头部进行操作，由于只能在链表头部进行操作，故链栈没有必要象单链表那样故链栈没有必要象单链表那样附加上头结点。栈顶指针就是附加上头结点。栈顶指针就是链表的头指针，如图链表的头指针，

11、如图3.43.4所示，所示，链栈就是无头结点的单链表链栈就是无头结点的单链表（头指针改称栈顶指针），因（头指针改称栈顶指针），因此不再重新讨论。此不再重新讨论。3.2 栈的应用举例栈的应用举例栈的应用非常广泛，只要问题满足栈的应用非常广泛，只要问题满足LIFOLIFO原则，均可使原则，均可使用栈做数据结构。用栈做数据结构。 /顺序顺序栈的栈的模板模板类类接口定义以及基本运算接口定义以及基本运算的的实现代码实现代码template class sqStack protected: int *elem ; / 指向存放数据元素指向存放数据元素的的数组指针数组指针 int top ; / 栈顶栈顶指

12、针指针 int maxSize; / 栈栈容量容量 public: sqStack(int ms=10); / 构造函数构造函数 sqStack (const sqStack&); / 复制构造函数复制构造函数 sqStack() delete elem; / 析构函数析构函数 sqStack& operator=(const sqStack&); / “=”运算符重载运算符重载 bool isEmpty() return top = = -1 ; / 判栈判栈“空空”否？否？ bool isFull() / 判栈判栈“满满” 否？否？ return top = max

13、Size-1; bool Push(T); / 进栈进栈 (插入、压栈插入、压栈) bool Pop(); / 出栈出栈 (删除、退栈删除、退栈) bool GetTop(T &); / 取栈顶元素取栈顶元素;template sqStack:sqStack(int ms) / 构造构造“空空” 栈栈 if(ms=0) coutERROR:invalid MaxSize!n; return; elem=new Tms; MaxSize=ms; top=-1;template bool sqStack:Push(T e) / 元素元素e压栈压栈 if(isFull() / 栈满（溢出）栈

14、满（溢出） cout “ ERROR: overflow !n”; return false; elem+top=e; / 栈顶指针增栈顶指针增1, 元素进栈元素进栈 return true; template bool sqStack:Pop() /栈顶元素出栈栈顶元素出栈, 被删元素存被删元素存e if(isEmpty() / 栈空（下溢）栈空（下溢） cout “ ERROR: underflow !n”; return false; top-; /栈顶指针减栈顶指针减1(元素出栈元素出栈) return true; template bool sqStack:GetTop(T &

15、;e) / 取栈顶元素取栈顶元素 if(isEmpty(S) / 栈空（下溢）栈空（下溢） cout “ ERROR: underflow !n”; return false; e=elem top; / 元素存元素存e, 栈顶不变栈顶不变(元素没出栈元素没出栈) return true; template sqStack:sqStack(const sqStack& obj)/由顺序栈由顺序栈obj复制构造新栈复制构造新栈 MaxSize=obj.MaxSize; /被构造栈与被构造栈与obj容量应相同容量应相同 elem=new T MaxSize; top = obj.top;

16、/申请空间申请空间, 栈顶指针赋值栈顶指针赋值 for(int j=0; j=top; j+) elemj= obj.elemj; / 复制数据元素复制数据元素 templatesqStack&sqStack:operator=(const sqStack&origin) /=运算符重载运算符重载 if(MaxSize!=origin.MaxSize) / 栈容量不等栈容量不等 / 需释放原来的存放数据元素空间，重新为当前栈申请空间需释放原来的存放数据元素空间，重新为当前栈申请空间 delete elem; MaxSize=origin.MaxSize; elem=new T

17、MaxSize; top=origin.top; /栈顶指针赋值栈顶指针赋值 for(int j=0; j=top; j+) elemj=origin.elemj; /复制数据元素复制数据元素【例例3.13.1】用栈实现程序设计语言中的子程序调用用栈实现程序设计语言中的子程序调用 和返回。和返回。假设有一个主程序假设有一个主程序mainmain和三个子程序和三个子程序A1A1，A2A2和和A3A3，其调用关系如图其调用关系如图3.53.5所示。所示。图3.5 子程序调用示意图void main() void A1() void A2() void A3() A1(); A2(); A3();

18、r: s: t: 从图从图3.53.5可知，主程序可知，主程序mainmain调用子程序调用子程序A1A1，子程序，子程序A1A1完成之后，完成之后，返回到主程序的返回到主程序的r r处继续执行。但是，因为子程序处继续执行。但是，因为子程序A1A1又调用了又调用了子程序子程序A2A2，所以在，所以在A2A2执行完毕并返回之前，执行完毕并返回之前，A1A1是不可能结束是不可能结束的。类似地，的。类似地，A2A2也必须在也必须在A3A3执行完毕并返回之后才能从执行完毕并返回之后才能从t t处继处继续进行。其调用与返回的过程如图续进行。其调用与返回的过程如图3.63.6所示。所示。图3.6 子程序调

19、用与返回main() A1() A2() A3()rst显然，调用次序和返回次序是显然，调用次序和返回次序是相反的，最后调用到的子程序相反的，最后调用到的子程序最先返回。为了保证各个被调最先返回。为了保证各个被调用子程序能正确地返回，可以用子程序能正确地返回，可以在程序运行期间设置一个工作在程序运行期间设置一个工作栈来保存返回地址栈来保存返回地址。当调用某一个子程序时，将该子程序的返回地址进栈；当当调用某一个子程序时，将该子程序的返回地址进栈；当某一子程序执行完毕时将当前栈顶的返回地址出栈，并按某一子程序执行完毕时将当前栈顶的返回地址出栈，并按该地址返回。注意，某一子程序该地址返回。注意，某一

20、子程序P执行完毕，当前栈顶内执行完毕，当前栈顶内容一定是容一定是P的返回地址。因为只有当执行的返回地址。因为只有当执行P时所调用的其它时所调用的其它子程序都已返回，子程序都已返回，P才能结束，这就保证了当才能结束，这就保证了当P返回时，其返回时，其相应的返回地址正好是在当前栈顶，参看图相应的返回地址正好是在当前栈顶，参看图3.7。【例例3.23.2】 表达式转换（中缀表达式改写成后缀表表达式转换（中缀表达式改写成后缀表 示法）示法）算术表达式有算术表达式有三种表示方法三种表示方法： ，如，如A+BA+B，称为中缀，称为中缀(infix)(infix)表示；表示； ，如，如+AB+AB称为前缀称

21、为前缀(prefix)(prefix)表示；表示； ，如，如AB+AB+，称为后缀，称为后缀(postfix)(postfix)表示。表示。在后缀表达式中，没有括号，也不存在优先级的差别，计算在后缀表达式中，没有括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后次序进行，整个计算过程仅过程完全按照运算符出现的先后次序进行，整个计算过程仅需一遍扫描便可完成，显然比中缀表达式的计算要简单得多。需一遍扫描便可完成，显然比中缀表达式的计算要简单得多。因此，程序设计语言的编译系统要将通常的中缀表达式转换因此，程序设计语言的编译系统要将通常的中缀表达式转换成后缀表达式成后缀表达式例如，例如，A*

22、(B+C)的后缀表达式是的后缀表达式是ABC+*, 因因+运算符运算符在前，在前，* 运算符在后，所以应先做加法，后做乘法。运算符在后，所以应先做加法，后做乘法。再如，表达式再如，表达式A/B*C+D*(E-A)+C/(D*B) 的后缀形式是的后缀形式是AB/C*DEA-*+CDB*/+ .怎样设计算法把运算符放在两个运算对象中间的中缀表达怎样设计算法把运算符放在两个运算对象中间的中缀表达式转换为后缀形式呢？式转换为后缀形式呢？观察一下两种形式的表达式，我们注意到操作数在两种形观察一下两种形式的表达式，我们注意到操作数在两种形式中出现的次序是相同的。所以在扫描表达式时，凡遇到式中出现的次序是相

23、同的。所以在扫描表达式时，凡遇到操作数就马上输出，剩下的事情就是处理所遇到的运算符。操作数就马上输出，剩下的事情就是处理所遇到的运算符。解决的办法是把遇到的运算符存放到栈中，直到某个适当解决的办法是把遇到的运算符存放到栈中，直到某个适当时刻再将运算符退栈并输出。时刻再将运算符退栈并输出。 我们来看两个例子：我们来看两个例子：（1）要由表达式）要由表达式A+B*C产生出后缀表达式产生出后缀表达式ABC*+，必，必须按照如表须按照如表3.1所示的操作顺序执行（栈向右增长）。所示的操作顺序执行（栈向右增长）。到达第到达第4步时必须确定是步时必须确定是*进入栈顶，还是进入栈顶，还是+退栈；由于退栈；由

24、于*的优先级更高，应该是的优先级更高，应该是*进栈，进栈，从而产生第从而产生第5步；现在已从表达式中取完所有的符号，步；现在已从表达式中取完所有的符号，于是我们输出运算符栈中所有剩余的运算符得到：于是我们输出运算符栈中所有剩余的运算符得到： ABC*+（2）表达式）表达式A*(B+C)/D 的后缀形式为的后缀形式为ABC+* D/，当遇到左括号时必须入栈，遇到右括号时，必须依次当遇到左括号时必须入栈，遇到右括号时，必须依次把栈中元素退栈。直到相应的左括号为止，然后去掉把栈中元素退栈。直到相应的左括号为止，然后去掉左右括号。如表左右括号。如表3.2所示。所示。这些例子启发我们，算术运算符和括号可

25、用如表这些例子启发我们，算术运算符和括号可用如表3.3所示分级方案实现。其规则是：所示分级方案实现。其规则是：只要运算符在栈中的优先级只要运算符在栈中的优先级ispisp(in-stack priori(in-stack priorityty) )大于或等于新运算符进来时的优先级大于或等于新运算符进来时的优先级icpicp(in-c(in-comingoming priority) priority)，则运算符就从栈中取出。，则运算符就从栈中取出。isp(x)isp(x)和和icpicp(x)(x)是函数，它们返回运算符按上述是函数，它们返回运算符按上述给定的优先级值。给定的优先级值。/将表达

26、式的中缀形式转换为后缀形式将表达式的中缀形式转换为后缀形式#include #include SQStack.hofstream ofile; / 创建输出流文件创建输出流文件void postfix(char*e); / 将中缀表达式将中缀表达式e转换为后缀形式输出的原型声明转换为后缀形式输出的原型声明void InitStack(S,maxSize) / 栈初始化栈初始化 S.top=-1; S.elem=new intmaxSize; bool isEmpty(S) /判栈空否？判栈空否？ return S.top=-1; 具体算法如下：具体算法如下： bool isFull (S) /

27、 判栈满否？判栈满否？ return top=S.maxSize-1; bool Push (sqStack S, int e) / 值为值为e的数据元素进栈的数据元素进栈(插入、压栈插入、压栈) if(isFull(S) / 栈满栈满 cout n; / 从文件读入要翻译的表达式数从文件读入要翻译的表达式数 for(i=0; i s; ofile “ n infix: ”s npostfix: ; postfix(s); / 转换中输出对应的转换中输出对应的/后缀表达式后缀表达式 ofile endl; infile.close(); ofile.close(); int isp(char

28、x) / 返回栈中运算符的优先级返回栈中运算符的优先级(in- stack priority) if(x=*|x=/) return 2; else if(x=+|x=-) return 1; else if(x=()return 0; else return -1; int icp(char x) / 返回读入运算符的优先级返回读入运算符的优先级(in-coming priority) if(x=*|x=/)return 2; else if(x=+|x=-) return 1; else return 3;void postfix(char *e) / 将中缀式将中缀式e转换为后缀式输出转

29、换为后缀式输出 char y, x= *e; sqStack stack ; stack.Push(#); / 栈底予置一栈底予置一“#” while(x!=0) / x不是不是“空白符空白符”(结束符结束符) if(x=) / 判断判断x是右括号吗？是右括号吗？ 是则执行退栈是则执行退栈, 直到直到 ( do stack.GetTop(y); stack.Pop(); if(y!=() ofile.put(y); while(y!=(); else / x不是右括号不是右括号, 判是其它运算符？不是判是其它运算符？不是,则输出则输出(操作数操作数) i f ( x ! = ( & &

30、amp; x ! = + & & x ! = -&x!=*&x!=/) ofile.put(x); else / x是运算符是运算符 do / 栈顶算符优先级栈顶算符优先级=读入算符优先读入算符优先级级, 则弹则弹 /出算符出算符/栈的运算符并输出栈的运算符并输出 stack.GetTop(y); / 取栈顶算符取栈顶算符 if(isp(y)=icp(x) / 弹出算符弹出算符 ofile.put(y); Stack.Pop(); else break; while(true); stack.Push(x); / 刚刚读入运算符进栈刚刚读入运算符进栈 /end_

31、if(x!=( e+; x=*e; / 取表达式取表达式e的下一符号的下一符号 / 结束结束while(x!=0)循环循环 while(stack.GetTop(x), stack.Pop(),x!=#) ofile.put(x); / 输出栈中其余运算符输出栈中其余运算符 (#不输出不输出)3.3 栈与递归栈与递归 3.3.1 栈的定义及其运栈的定义及其运算算若一个对象部分地包含它自己若一个对象部分地包含它自己, , 或用它自己给自己定或用它自己给自己定义义, , 则称这个对象是递归的；若一个过程直接地或间则称这个对象是递归的；若一个过程直接地或间接地调用自己接地调用自己, , 则称这个过程

32、是递归的过程。则称这个过程是递归的过程。 递归（递归（recursionrecursion）是最常用的算法设计思想，采用递归）是最常用的算法设计思想，采用递归的方法来编写求解程序，使程序非常简洁而清晰，本节重点的方法来编写求解程序，使程序非常简洁而清晰，本节重点讨论递归在计算机内的实现，以及怎样把一个递归的子程序讨论递归在计算机内的实现，以及怎样把一个递归的子程序变换成一个等价的非递归的子程序，读者将会看到，在这里变换成一个等价的非递归的子程序，读者将会看到，在这里起关键作用的是栈。起关键作用的是栈。 定义是递归的；定义是递归的；如，我们熟悉的如，我们熟悉的FactorialFactorial

33、函函数数,Ackerman,Ackerman函数，函数，FibnocciFibnocci函数等。函数等。在以下三种情况下，常常用到递归方法。在以下三种情况下，常常用到递归方法。 数据结构是递归的；数据结构是递归的；例如，单链表结构，每个结点例如，单链表结构，每个结点的的nextnext域指向的仍然是单链表的结点。我们后面将要域指向的仍然是单链表的结点。我们后面将要学习的二叉树、广义表等数据结构，它们的定义就是学习的二叉树、广义表等数据结构，它们的定义就是递归的（具有固有的递归特性）因此自然采用递归方递归的（具有固有的递归特性）因此自然采用递归方法进行处理。法进行处理。 问题的解法是递归的。问题

34、的解法是递归的。例如，汉诺塔例如，汉诺塔(Tower of Hanoi)(Tower of Hanoi)问题传说婆罗门庙问题传说婆罗门庙里有一个塔台，台上有三根标号为里有一个塔台，台上有三根标号为A,B,CA,B,C的用钻石的用钻石做成的柱子，在做成的柱子，在A A柱上放着柱上放着6464个金盘，每一个都比个金盘，每一个都比下面的略小一些。把下面的略小一些。把A A柱上的金盘全部移到柱上的金盘全部移到C C柱上的柱上的那一天就是世界末日。移动的条件是：一次只能移那一天就是世界末日。移动的条件是：一次只能移动一个金盘，移动过程中大金盘不能放在小金盘上动一个金盘，移动过程中大金盘不能放在小金盘上面

35、。庙里的僧人一直在移个不停。因为全部的移动面。庙里的僧人一直在移个不停。因为全部的移动是是2 26464 -1 -1次，如果移动一次需要一秒的话，需要次，如果移动一次需要一秒的话，需要500500亿年。亿年。 用递归方法求解问题是将一个较复杂的（规用递归方法求解问题是将一个较复杂的（规 模较大）的问题转换成一个与原问题同类型模较大）的问题转换成一个与原问题同类型 的稍简单（规模稍小）的问题来解决，使之的稍简单（规模稍小）的问题来解决，使之 比原问题进了一步（更靠近边界条件一步），比原问题进了一步（更靠近边界条件一步）， 直至到达边界条件（直接求解，不再递归）。直至到达边界条件（直接求解，不再递

36、归）。要理解递归算法，就必须了解计算机内递归是如何实要理解递归算法，就必须了解计算机内递归是如何实现的？我们通过例子说明之。现的？我们通过例子说明之。3.3.2 递归子程序的实现递归子程序的实现【例例3.33.3】汉诺塔问题：设需移动的金盘数为汉诺塔问题：设需移动的金盘数为n n（问题的规模），当（问题的规模），当n=1n=1时，只要将编号为时，只要将编号为1 1的金盘从柱的金盘从柱A A直接移至柱直接移至柱C C即可；当即可；当n1n1时，需时，需利用柱利用柱B B作辅助柱子。作辅助柱子。算法思路算法思路：若能设法将压在编号为：若能设法将压在编号为n n的金盘之的金盘之上的上的n-1n-1个

37、金盘从柱个金盘从柱A A依照上述法则移至柱依照上述法则移至柱B B；则可先将编号为则可先将编号为n n的金盘从柱的金盘从柱A A移至柱移至柱C C，然后，然后再将柱再将柱B B上的上的n-1n-1个金盘依照上述法则移至柱个金盘依照上述法则移至柱C C。而如何将而如何将n-1n-1个金盘从一个柱移至另一个柱的个金盘从一个柱移至另一个柱的问题是一个和原问题具有相同特征属性的问问题是一个和原问题具有相同特征属性的问题，只是问题的规模小了题，只是问题的规模小了1 1；因此可以用同样；因此可以用同样的方法求解。的方法求解。void Hanoi(int n, char A, char B, char C)

38、 if(n= =1) cout”move disk 1: “A”C; / 将将1号盘从号盘从A移到移到C else Hanoi(n-1,A,C,B); / 将将A上编号为上编号为1n-1的盘移至的盘移至B上上, C 用作过渡用作过渡 c o u t ” m o v e d i s k “ n “ : “A“C; / 将将n号盘从号盘从A移到移到C Hanoi (n-1,B,A,C); / 将将B上编号为上编号为1n-1的盘移至的盘移至C上上, A 用作过渡用作过渡 图图 3.83.8显示了问题规模显示了问题规模n=4n=4时时HanoiHanoi塔问题的调用过程塔问题的调用过程 (a) 初始状

39、态(b) 执行完语句（递归调用）的状态图3.8 n=4 的汉诺塔问题的求解过程示意(c) 执行完语句的状态(d) 执行完语句的状态显然，递归算法显然，递归算法HanoiHanoi在执行过程中，需多次调在执行过程中，需多次调用它本身。那末，递归子程序是如何执行的呢？用它本身。那末，递归子程序是如何执行的呢？和汇编程序设计中主程序和子程序之间的链和汇编程序设计中主程序和子程序之间的链接和信息交换相类似，在高级语言编制的程接和信息交换相类似，在高级语言编制的程序中，主调程序和被调子程序之间的链接和序中，主调程序和被调子程序之间的链接和信息交换也须通过信息交换也须通过栈栈来进行。来进行。 通常，当程序

40、在运行期间调用另一个程序时，在运行通常，当程序在运行期间调用另一个程序时，在运行被调程序之前，系统必须完成被调程序之前，系统必须完成3 3件工作：件工作： 将所有的实在参数、返回地址等信息传递将所有的实在参数、返回地址等信息传递给被调子程序保存；给被调子程序保存； 为被调子程序的局部变量分配存储区；为被调子程序的局部变量分配存储区； 将控制转移到被调子程序的入口。将控制转移到被调子程序的入口。而从被调子程序返回主调程序之前，系统也应完成而从被调子程序返回主调程序之前，系统也应完成3 3件工作：件工作： 保存被调子程序的计算结果：保存被调子程序的计算结果： 释放被调子程序的数据区；释放被调子程序

41、的数据区； 恢复被调子程序保存的返回地址将控制转恢复被调子程序保存的返回地址将控制转回到主调程序。回到主调程序。当有多个程序间构成嵌套调用时，按照当有多个程序间构成嵌套调用时，按照“后调用先返后调用先返回回”的原则。的原则。 上述程序之间的信息传递和控制转移必须通过上述程序之间的信息传递和控制转移必须通过“栈栈”来实现；来实现；即系统将整个程序运行时所需的数据空间安排在一即系统将整个程序运行时所需的数据空间安排在一个栈中。每当调用一个程序时，就为它在栈顶分配个栈中。每当调用一个程序时，就为它在栈顶分配一个存储区；每当退出一个程序时，就释放它的存一个存储区；每当退出一个程序时，就释放它的存储区；

42、则当前正运行程序的数据区必然在栈顶。储区；则当前正运行程序的数据区必然在栈顶。递归程序的运行子程序类似于例递归程序的运行子程序类似于例3.13.1中多个程序的嵌中多个程序的嵌套调用；只是套调用；只是主调程序和被调子程序是同一个程序主调程序和被调子程序是同一个程序而而已。已。 递归与分治法递归与分治法3.3.3 递归技术相关问题递归技术相关问题 任何一个可用计算机求解的问题所需的计算时间都与其任何一个可用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于计算时间也越少。例如，对于n

43、 n个元素的排序问题，当个元素的排序问题，当n=1n=1时，时，不需任何计算。不需任何计算。n=2n=2时，只要作一次比较即可排好序。时，只要作一次比较即可排好序。n=3n=3时时只要作只要作3 3次比较即可，次比较即可，。而当。而当n n较大时，问题就不那么容易较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困处理了。要想直接解决一个规模较大的问题，有时是相当困难的。难的。 分治法的思想：分治法的思想：将一个难以直接解决的大问题，分割成将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。一些规模较小的相同问题，以便各个击破，分而治之。如

44、果原问题可分割成如果原问题可分割成k k个子问题个子问题(1kn)(1kn)，且这些子，且这些子问题都可解，并可利用这些子问题的解求出原问题问题都可解，并可利用这些子问题的解求出原问题的解，那么分治法就是可行的。的解，那么分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接其规模却不断缩小，最终使子问题缩小到很容易

45、直接求出其解。这自然导致递归过程的产生。求出其解。这自然导致递归过程的产生。分治与递归分治与递归像一对孪生兄弟像一对孪生兄弟，经常同时应用在算法设计之中，并，经常同时应用在算法设计之中，并由此产生许多高效算法。由此产生许多高效算法。 递归与迭代递归与迭代递归与迭代都是基于程序设计语言的控制结构，迭代用重复递归与迭代都是基于程序设计语言的控制结构，迭代用重复结构，递归用选择结构。结构，递归用选择结构。例如，求解阶乘函数的递归算法如下：例如，求解阶乘函数的递归算法如下：long Factorial (long n) if(n=0) return 1; else return n*Factorial

46、(n-1); 迭代算法如下：迭代算法如下：long Factorial (long n) long i , p = 1; for (i=2; i=n; i +) p*=i; return p ;任何能用递归解决的问题也能用迭代方法解决。任何能用递归解决的问题也能用迭代方法解决。 究竟应当如何选择递归和迭代呢？我们将两种方法做个比较。究竟应当如何选择递归和迭代呢？我们将两种方法做个比较。一般对于象斐波那契数列和阶乘阶乘这样一些一般对于象斐波那契数列和阶乘阶乘这样一些方法，而没有明显迭代方案的如阿克曼函数，汉诺方法，而没有明显迭代方案的如阿克曼函数，汉诺塔问题还是应当采用递归方法，如果一定要转换为

47、非递归算法，塔问题还是应当采用递归方法，如果一定要转换为非递归算法，则必须借助于栈实现，有兴趣的读者可参看参看文献则必须借助于栈实现，有兴趣的读者可参看参看文献11。 递归方法能更自然地描述问题，使算法容易理解和调试递归方法能更自然地描述问题，使算法容易理解和调试（可读性好）（可读性好）；但是递归方法要耗费更多的时间与空间；但是递归方法要耗费更多的时间与空间（效率低）（效率低）；迭代方法发生在函数；迭代方法发生在函数( (子程序子程序) )内部，不需内部，不需进行进行“转子、返回转子、返回”及及“参数压栈参数压栈”等操作，因此等操作，因此时空时空效率高效率高。 【例【例3.43.4】 在在8

48、8* *8 8的国际象棋上摆放八个皇后，使的国际象棋上摆放八个皇后，使其不能互相攻击其不能互相攻击, ,即任意两个皇后不能处于同一行、即任意两个皇后不能处于同一行、同一列或同一斜线上，问有多少种摆法。同一列或同一斜线上，问有多少种摆法。 下面，我们就十九世纪著名的数学家高斯下面，我们就十九世纪著名的数学家高斯18501850年提出的年提出的“八皇八皇 后问题后问题” ” 分别用递归与迭代方法给出源程序，做为本小节的分别用递归与迭代方法给出源程序，做为本小节的 应用例。应用例。 / 递归回溯算法递归回溯算法 #include int sum=0, x9; / x1 x8存放当前解存放当前解, /

49、 xi = j表示第表示第i行的皇后放在第行的皇后放在第j列列 。ofstream out(QueenOUT.dat); / out声明输出流声明输出流 /(文件文件) out并打开之并打开之 void Backtrack(int); / 递归回溯法原型声明递归回溯法原型声明void main(void) Backtrack(1) ; / 主调函数从主调函数从Backtrack(1)开始开始/回溯法回溯法 out“nThe number of solution Queen is ”sumendl; /输出可行解的总数输出可行解的总数 out.close();bool Place(int k)

50、/ 检测检测k皇后能否放在皇后能否放在xk列列 (是是/否与以前的皇后不能相互攻击否与以前的皇后不能相互攻击) for(int j=1; j8) /找到一组解，输出找到一组解，输出 for(j=1; j=8; j+)out xj ; outendl ; sum+; for(j=1; j=8; j+) / 在在循环循环中中递归调用递归调用, 对每一对每一皇后皇后都都测试测试了了所有位置所有位置, 因此因此 / 可可得到所有得到所有解解 x i = j ; if(Place(i)Backtrack(i+1); /确定当前皇后确定当前皇后的的位置位置, 找下一找下一皇后位置皇后位置 /迭代迭代回溯算

51、法回溯算法#include #include void Backtrack(); / 找出所有找出所有解并解并输出输出之的之的函数函数, 原原 / 型型声明声明int x9; void main() / 主主函数仅仅调用函数仅仅调用Backtrack() , 注意注意 / Backtrack() 没有参数没有参数 Backtrack(); bool Place(int k) / 检测检测k皇后能否皇后能否放在放在xk列列(是否是否 / 与与以前以前的的皇后不能相互攻击皇后不能相互攻击) for(int j=1; j 0) / 若若k=0，则已，则已搜索搜索完完所有所有的解的解, / 结束回溯结

52、束回溯 xk+; / 列号增列号增1, 为为k皇后测试皇后测试下一下一位置位置 while(xk=8) & !(Place(k) xk+; if(xk=8) / 确定确定了了皇后皇后的的位置位置 if(k=8) /找到找到一组解，一组解，输出输出 sum+; for(int i=1; i=8; i+)out“ xi; outendl; else x +k=0; / k增增1, 为下一为下一皇后皇后找安找安 / 全的全的位置位置, 注意注意x k=0, 为什么为什么? else k-; / 回溯回溯 outnThe number of solution Queen is sumendl;

53、 out.close(); 该算法得到了该算法得到了9292组可行解，但实际上只有组可行解，但实际上只有1212组不同构的解（随书组不同构的解（随书光盘给出了光盘给出了1212组解图，由于篇幅关系，这儿不再画出），其余的组解图，由于篇幅关系，这儿不再画出），其余的解可以从这解可以从这1212组解经旋转或左右对称变换得到。组解经旋转或左右对称变换得到。 3.4 队列队列3.4.1 队列的定义及其运算队列的定义及其运算 队列队列(Queue)(Queue)是限定只能在表尾插入元素，而在表是限定只能在表尾插入元素，而在表头删除元素的线性表。头删除元素的线性表。这和我们日常生活中的排队是一致的，最早进

54、入队列的元素最这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。因此也称其为：早离开。因此也称其为：先进先出（先进先出（First In First OutFirst In First Out，缩，缩写为写为FIFOFIFO）表。）表。 允许插入的一端叫做允许插入的一端叫做队尾队尾，允许删除的一端则称为允许删除的一端则称为队头队头。 假设队列为假设队列为:Q = (a1:Q = (a1，a2a2，an)an)，那么，那么，a1a1就是队头就是队头元素，元素，anan则是队尾元素。队列中的元素是按照则是队尾元素。队列中的元素是按照a1a1，a2a2，anan的顺序进入的，退出队列也只

55、能按照这个次序依的顺序进入的，退出队列也只能按照这个次序依次退出，也就是说，只有在次退出，也就是说，只有在a1a1，a2a2，an-1an-1都离开队都离开队列之后，列之后，anan才能退出队列。才能退出队列。图图3.93.9是队列的示意图。是队列的示意图。 图3.9 队列示意图队尾队头a1a2an进队出队队列在程序设计中也经常出现。队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业排队。在允一个最典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业运许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就要按行。如

56、果运行的结果都需要通过通道输出，那就要按请求输出的先后次序排队。每当通道传输完毕可以接请求输出的先后次序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从作业队列中退出受新的输出任务时，队头的作业先从作业队列中退出做输出操作。凡是申请输出的作业都从队尾进入队列。做输出操作。凡是申请输出的作业都从队尾进入队列。队列的队列的ADTADT声明如下：声明如下：ADT Queue Typedef struct Stack Q; InitStack(Q,maxSize); 说明：构造空队列Q，即队列的初始化 QueueSize(Q); 说明：队列中元素的数目 isEmpty(Q); 说明：判队列

57、Q是否为空 isFull(Q); 说明：判队列Q是否已“满” GetFront(Q,e); 说明：取队头元素 EnQueue(Q,e); 说明：值为e的数据元素进入队列 Del Queue(Q); 说明：队头元素出队（删除）;3.4.2 顺序队列队列的顺序存储结构顺序队列队列的顺序存储结构队列的顺序存储结构称为队列的顺序存储结构称为顺序队列顺序队列。与顺序栈相同顺。与顺序栈相同顺序队列也是用一个向量空间来存放当前队列中的元素。序队列也是用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置均是变化的，因而要设由于队列的队头和队尾的位置均是变化的，因而要设置两个指针，分别指示当前队头元

58、素和队尾元素的位置两个指针，分别指示当前队头元素和队尾元素的位置。置。规定：队头指针总是指向当前队头元素的前一个位置规定：队头指针总是指向当前队头元素的前一个位置 队尾指针指向当前队尾元素的位置队尾指针指向当前队尾元素的位置初始，队头和队尾指针均指向向量空间的前一个置初始，队头和队尾指针均指向向量空间的前一个置。图图3.103.10说明了顺序队列中出队和入队运算时队列中说明了顺序队列中出队和入队运算时队列中的元素及其头尾指针的变化状况。的元素及其头尾指针的变化状况。(a)空队 (b)a1a2a3相继进队 (c)a1a2a3相继出队 (d)a4a5相继进队图3.10 顺序队列中头、尾指针变化情况

59、Typedef struct int *elem; / elem是数据元素数组，初始化操作是数据元素数组，初始化操作InitStack(Q)中分配存储空间中分配存储空间 int front, rear; / 队头，队尾指针队头，队尾指针 int maxSize; / 初始化操作初始化操作InitStack (S)中为栈中为栈分配单元数分配单元数/ （栈容量）（栈容量）sqStack;void InitStack(Q, maxSize) / 队列初始化队列初始化 Q.front=Q.rear=-1; Q.elem=new intmaxSize; 我们先以整数元素为例，给出顺序队列的基本运算的我们

60、先以整数元素为例，给出顺序队列的基本运算的实现代码。实现代码。bool isEmpty(Q) / 判队列空否？判队列空否？ return Q.front=Q.rear; bool isFull(Q) / 判队列满否？判队列满否？ return Q.rear=Q.maxSize-1; Bool EnQueue(sqStack Q, int x) / 值为值为x的数据的数据/元素进队列元素进队列(插入插入) if(isFull(Q) / 队列满（溢出）无法进队列队列满（溢出）无法进队列, 返回返回/ false cout ERROR: overflow !n; return false ; Q.elem+Q.rear=x; return true; / 队尾指队尾指/针增针增1元素进队列元素进队列, 返回返回trueb