数据结构第三章栈和队列ppt课件.ppt

《数据结构第三章栈和队列ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构第三章栈和队列ppt课件.ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章栈和队列栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能n教学目的教学目的n通过本章的学习，要求掌握栈和队列的定义，通过本章的学习，要求掌握栈和队列的定义，熟练掌握顺序和链接存储的栈和队列的算法设熟练掌握顺序和链接存储的栈和队列的算法设计及其程序实现，了解栈和队的各种应用。计及其程序实现，了解栈和队的各种应用。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能n本章主要介绍以下内容：本章主要介绍以下内容：l栈的概念、存储结构及其基本操作栈的概念、存储结构

2、及其基本操作l队列的概念、存储结构及其基本操作队列的概念、存储结构及其基本操作l栈与队列的应用举例栈与队列的应用举例为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能n重点：栈和队列的定义、特征；顺序栈、链栈重点：栈和队列的定义、特征；顺序栈、链栈的描述及基本操作实现算法；循环队列和链队的描述及基本操作实现算法；循环队列和链队列的基本操作实现算法。列的基本操作实现算法。n难点：栈满、栈空的条件及描述方法；队满和难点：栈满、栈空的条件及描述方法；队满和队空的描述方法；循环队列上的插入、删除操队空的描述方法；循环队列上的插入、删除操作。作

3、。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能栈（stack）n栈的定义n栈的类型定义n栈的存储方式为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能栈的定义n栈是一种特殊的线性表。其特殊性在于限定插栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在入和删除数据元素的操作只能在线性表的一端线性表的一端进行。进行。a1ana2栈的示意图栈顶栈底进栈出栈进行插入和删除的进行插入和删除的一端是浮动端，被一端是浮动端，被称为栈顶称为栈顶固定端一端被固定端一端被

4、称为栈底称为栈底为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能假设栈假设栈S=(a1，a2，a3，an)，则，则a1称为栈底称为栈底元素，元素，an为栈顶元素。栈中元素按为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈的次序进栈，退栈的第一个元素应为栈顶元素。顶元素。换句话说，栈的修改是按后进先出的原则进行换句话说，栈的修改是按后进先出的原则进行的。的。因此，栈称为后进先出表（因此，栈称为后进先出表（LIFO）LastInFirstOut。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯

5、彻全国教育大会精神,充分发挥中小学图书室育人功能栈的类型定义ADTStack 数据对象数据对象：D=ai|ai ElemSeti=1,2,.,nn0数据关系数据关系：R1=|ai,ai+1 ElemSet,i=1,2,.,n-10约定约定an端为栈顶，端为栈顶，a1端为栈底端为栈底为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能基本操作基本操作：结构初始化结构初始化InitStack(&S)操作结果：构造一个空栈操作结果：构造一个空栈S销毁结构销毁结构DetroyStack(&S)初始条件：栈初始条件：栈S已经存在已经存在操作结果：

6、销毁栈操作结果：销毁栈S为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能引用型操作引用型操作StackEmpty(S)/判断判断S是否为空栈，若为空返回是否为空栈，若为空返回True，否则返回，否则返回FalseStackLength(S)/得到栈得到栈S的元素个数，即栈的长度的元素个数，即栈的长度GetTop(S，&e)/得到得到S的栈顶元素，并将之放入变量的栈顶元素，并将之放入变量e中中StackTraverse(S,visit()/从栈底到栈顶遍历栈从栈底到栈顶遍历栈S，对每个元素调用，对每个元素调用visit()为深入学习习

7、近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能加工型操作加工型操作ClearStack(&S)/清空栈清空栈SPush(&S,e)/向栈中插入元素向栈中插入元素e为新的栈顶元素为新的栈顶元素Pop(&S,&e)/删除栈删除栈S的栈顶元素，并用的栈顶元素，并用e返回值返回值为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能栈的存储方法栈的存储方法n栈有两种存储表示方法栈有两种存储表示方法:顺序存储和链式存储顺序存储和链式存储 由于栈是运算受限的线性表，因此线性表由于栈是运算受限的线性表

8、，因此线性表的存储结构对栈也适应。的存储结构对栈也适应。栈的顺序存储结构简称为栈的顺序存储结构简称为顺序栈顺序栈，它是运，它是运算受限的线性表。因此，可用数组来实现顺序算受限的线性表。因此，可用数组来实现顺序栈。栈。通常由一个一维数组和一个记录栈顶元素通常由一个一维数组和一个记录栈顶元素位置的变量组成。位置的变量组成。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能当当栈栈中中没没有有数数据据元元素素时时，表表示示为为栈栈空空。栈栈顶顶元元素素所所对对应应的的下下标标值值top=-1。在刚才基础上执行在刚才基础上执行Push(S,A

9、)后得到这种状态后得到这种状态又又有有三三个个元元素素B、C、D先先后后入入栈栈，此此时时栈栈顶顶元元素素的的下下标标值值top=3。栈已满。栈已满。在刚才状态下，执行两次在刚才状态下，执行两次Pop(S,x)运算后得到运算后得到Top-1D01230123Top-A0123Top-ABC0123Top-AB为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能顺序存储结构n n顺序栈的顺序栈的顺序栈的顺序栈的C#C#语言描述如下：语言描述如下：语言描述如下：语言描述如下：publicclassSeqStackpublicclassSeq

10、StackprivateintmaxSize;/privateintmaxSize;/顺序栈的容量顺序栈的容量顺序栈的容量顺序栈的容量privatechardata;/privatechardata;/数组，用于存储顺序栈的数据元素，这里存数组，用于存储顺序栈的数据元素，这里存数组，用于存储顺序栈的数据元素，这里存数组，用于存储顺序栈的数据元素，这里存储的只有字符型储的只有字符型储的只有字符型储的只有字符型privateinttop;/privateinttop;/指示顺序栈的栈顶指示顺序栈的栈顶指示顺序栈的栈顶指示顺序栈的栈顶n nmaxSizemaxSize为栈中元素的最大容量。为栈中元素

11、的最大容量。为栈中元素的最大容量。为栈中元素的最大容量。n ndatadata域域域域:为一个一维数组，用于存储栈中元素。为一个一维数组，用于存储栈中元素。为一个一维数组，用于存储栈中元素。为一个一维数组，用于存储栈中元素。n ntoptop域域域域:栈顶指针。取值范围为栈顶指针。取值范围为栈顶指针。取值范围为栈顶指针。取值范围为0 0MaxSize-1MaxSize-1。n ntop=-1top=-1表示栈空，表示栈空，表示栈空，表示栈空，top=MaxSize-1top=MaxSize-1表示栈满。表示栈满。表示栈满。表示栈满。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯

12、彻全国教育大会精神,充分发挥中小学图书室育人功能类的实现类的实现publicclassSeqStackprivateintmaxSize;/顺序栈的容量顺序栈的容量privatechardata;/数组，用于存储顺序栈的数据元素，这数组，用于存储顺序栈的数据元素，这里存储的只有字符型里存储的只有字符型privateinttop;/指示顺序栈的栈顶指示顺序栈的栈顶publicintMaxSize/最大容量属性最大容量属性getreturnmaxSize;setmaxSize=value;publicintTop/栈顶属性栈顶属性getreturntop;为深入学习习近平新时代中国特色社会主义思想

13、和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 使用使用SeqList s=new SeqList()SeqList s=new SeqList()生成一个生成一个SeqListSeqList类的对象实例类的对象实例n栈底元素为栈底元素为n栈顶指针为栈顶指针为n进栈时需将进栈时需将s.tops.top加加1 1，退栈时需将，退栈时需将s.top s.top 减减1 1ns.top0s.top0表示空栈，表示空栈，s.top=MaxSize-1 s.top=MaxSize-1表示栈表示栈满满s.data0s.top为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,

14、贯彻全国教育大会精神,充分发挥中小学图书室育人功能基本操作1.初始化栈初始化栈S/构造函数构造函数publicSeqStack(intsize)data=newcharsize;maxSize=size;top=-1;2.求栈的长度求栈的长度publicintGetLength()returntop+1;3.清空顺序栈清空顺序栈publicvoidClear()top=-1;为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能4、判栈空、判栈空publicboolIsEmpty()if(top=-1)returntrue;elseret

15、urnfalse;5、入栈、入栈publicvoidPush(charitem)if(top=maxSize-1)/若栈已满，则不能再做入栈操作若栈已满，则不能再做入栈操作Console.WriteLine(TheStackisfull!);return;top+;datatop=item;为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能6、出栈出栈publiccharPop()if(IsEmpty()/若栈为空栈，无法做出栈操作若栈为空栈，无法做出栈操作Console.WriteLine(TheStackisempty!);ret

16、urn;charitem=datatop;top-;returnitem;为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能7、取栈顶元素、取栈顶元素publiccharGetTop()if(IsEmpty()Console.WriteLine(TheStackisemptye!);return;returndatatop;为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能链式存储结构链式存储结构n栈的链式存储结构称为栈的链式存储结构称为链栈链栈，它是运算是受限的单链，它是运

17、算是受限的单链表，可插入和删除操作仅限制在表头位置上进行表，可插入和删除操作仅限制在表头位置上进行.链栈的类型说明如下：链栈的类型说明如下：publicclasspublicclassStackNodeStackNodeprivateintdata;/privateintdata;/数据域数据域数据域数据域privateprivateStackNodeStackNodenext;/next;/指针域指针域指针域指针域为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能链栈的几种状态链栈的几种状态为深入学习习近平新时代中国特色社会主义思想

18、和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能栈的应用举例栈的应用举例n由于栈结构具有的后进先出的固有特性，致使由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。栈成为程序设计中常用的工具。n数值转换数值转换n括号匹配检验括号匹配检验为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能数值转换数值转换n十进制数值转换成二进制 使用展转相除法将一个十进制数值转换成二进使用展转相除法将一个十进制数值转换成二进制数值。制数值。即用该十进制数值除以即用该十进制数值除以2，并保留其余数；重，并保留其余数；重

19、复此操作，直到该十进制数值为复此操作，直到该十进制数值为0为止。为止。最后将所有的余数反向输出就是所对应的二进最后将所有的余数反向输出就是所对应的二进制数值。制数值。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5822920214170231212101十进制十进制58的二进制表示为：的二进制表示为：111010为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能publicvoidDToB(intdecVal)SeqStacks=newSeqStack(50);whil

20、e(decVal!=0)s.Push(decVal%2);decVal/=2;while(!s.IsEmpty()Console.Write(s.Pop().ToString();Console.WriteLine();Console.ReadLine();为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能检验表达式中的括号匹配情况n 假设在一个算术表达式中，可以包含三种括号：圆括假设在一个算术表达式中，可以包含三种括号：圆括号号“（”和和“）”，方括号，方括号“”和和“”和花括号和花括号“”和和“”，并且这三种括号可以按任意的次序嵌

21、套，并且这三种括号可以按任意的次序嵌套使用。比如，使用。比如，.(.).。现。现在需要设计一个算法，用来检验在输入的算术表达式在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。中所使用括号的合法性。n算术表达式中各种括号的使用规则为：算术表达式中各种括号的使用规则为：出现左括号，出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况嵌套，但不能出现交叉情况。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能n检验括号是否匹配的方法可以用检验括号

22、是否匹配的方法可以用“期待的急迫程度期待的急迫程度”这个这个概念来描述。概念来描述。n()(),()()是正确的格式，而是正确的格式，而(),()是错是错误的格式误的格式()12345678()()()为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能检验出错的情况n（1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；于左括号；n（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；了

23、括号交叉情况；n（3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。括号多于右括号。我们可以利用一个栈结构保存每个出现的左括号，当遇我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。不匹配的结论。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能算法基本思

24、想算法基本思想n凡出现左括号，进栈凡出现左括号，进栈n凡出现右括号，首先检查栈是否是空凡出现右括号，首先检查栈是否是空若栈空，表明右括号多了若栈空，表明右括号多了否则和栈顶元素比较，否则和栈顶元素比较，若相等，则左括号出栈若相等，则左括号出栈否则不匹配否则不匹配n表达式检查结束时，表达式检查结束时，若栈空，则匹配正确若栈空，则匹配正确否则表明左括号多了否则表明左括号多了为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能迷宫求解.为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功

25、能算法思想算法思想n若当前位置若当前位置“可通可通”，则纳入，则纳入“路径路径”，继续，继续前进前进n若当前位置若当前位置“不可通不可通”，则后退，换向探索，则后退，换向探索n若四周皆若四周皆“不可通不可通”，则从路径中删除，则从路径中删除为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能汉诺塔问题：汉诺塔问题：n有三根柱子分别叫有三根柱子分别叫A柱、柱、B柱、柱、C柱。现假设有柱。现假设有N个圆盘（都是按从大到小依次放入柱中的）个圆盘（都是按从大到小依次放入柱中的）已经放在了已经放在了A柱上，我们的任务就是把这柱上，我们的任务就是把

26、这N个个圆盘移动到圆盘移动到C柱。但移动的过程，必须遵守大柱。但移动的过程，必须遵守大盘永远在小盘的下面这一个原则。盘永远在小盘的下面这一个原则。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能栈与递归栈与递归n n递归是一种非常重要的数学概念和解决问题的递归是一种非常重要的数学概念和解决问题的方法，在计算机科学和数学等领域有着广泛的方法，在计算机科学和数学等领域有着广泛的应用。在计算机科学中，许多数据结构，如广应用。在计算机科学中，许多数据结构，如广义表、树和二叉树等，由于其自身固有的递归义表、树和二叉树等，由于其自身固有的递归性

27、质，都可通过递归方式加以定义并实现许多性质，都可通过递归方式加以定义并实现许多问题的算法设计。问题的算法设计。n n在计算机内部，在计算机内部，通过栈来实现递归算法通过栈来实现递归算法。所以。所以递归是栈的一个实际应用。递归是栈的一个实际应用。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能当在一个函数的运行期间当在一个函数的运行期间调用另一个函数调用另一个函数时，时，在运行该被调用函数在运行该被调用函数之前之前，需要完成三件，需要完成三件事：事：n将所有的实在参数、返回地址等将所有的实在参数、返回地址等信息信息传递给被传递给被调用

28、函数保存调用函数保存n为被调用函数的局部变量为被调用函数的局部变量分配存储存储区分配存储存储区n将将控制转移控制转移到被调用函数的入口到被调用函数的入口为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能从被调用函数返回调用函数从被调用函数返回调用函数之前之前，应完成：，应完成：n保存保存被调用函数的被调用函数的计算结果计算结果n释放释放被调用函数的被调用函数的数据区数据区n依照被调用函数保存的依照被调用函数保存的返回地址返回地址将将控制转移控制转移到到调用函数调用函数为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国

29、教育大会精神,充分发挥中小学图书室育人功能多个函数嵌套调用的规则是：多个函数嵌套调用的规则是：后调用先返回后调用先返回内存管理实行内存管理实行“栈式管理栈式管理”为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能递归函数递归函数n斐波纳茨函数：斐波纳茨函数：1，1，2，3，5，8，13n求求n的阶乘的递归函数算法的阶乘的递归函数算法:longfact(intn)longfact(intn)longf;longf;if(n=0)f=1;if(n=0)f=1;elsef=n*fact(n-1);elsef=n*fact(n-1);retu

30、rnf;returnf;为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能if(n=0)f=1;if(n=0)f=1;elseelsef=n*fact(n-f=n*fact(n-1);1);returnf;returnf;函数函数fact(4)if(n=0)f=1;if(n=0)f=1;elseelsef=n*fact(n-f=n*fact(n-1);1);returnf;returnf;调用调用fact(3)if(n=0)f=1;if(n=0)f=1;elseelsef=n*fact(n-f=n*fact(n-1);1);retur

31、nf;returnf;调用调用fact(2)if(n=0)f=1;if(n=0)f=1;elseelsef=n*fact(n-f=n*fact(n-1);1);returnf;returnf;调用调用fact(1)if(n=0)f=1;if(n=0)f=1;elseelsef=n*fact(n-f=n*fact(n-1);1);returnf;returnf;调用调用fact(0)函数函数fact(3)函数函数fact(2)函数函数fact(1)函数函数fact(0)函数fact(0)的调用返回一个1值返回1函数fact(1)中f=1*1返回值1返回1函数fact(2)中f=2*1返回值2返回

32、2函数fact(3)中f=3*2返回值6返回6为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能n递归函数：直接调用自身或通过一系列的调用递归函数：直接调用自身或通过一系列的调用语句间接地调用自己的函数语句间接地调用自己的函数为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能调用调用fact(3)调用调用fact(4)longfact(intn)longfact(intn)longf;longf;if(n=0)f=1;if(n=0)f=1;elsef=n*fact(n-1);

33、elsef=n*fact(n-1);returnf;returnf;调用调用调用调用fact(4)fact(4)fact(4)fact(4)调用调用调用调用fact(3)fact(3)fact(3)fact(3)调用调用调用调用fact(2)fact(2)fact(2)fact(2)调用调用调用调用fact(1)fact(1)fact(1)fact(1)调用调用调用调用fact(0)fact(0)调用调用fact(2)调用调用fact(1)调用调用fact(0)4r13r22r31r40r5为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育

34、人功能汉诺塔问题汉诺塔问题n如果汉诺塔问题中盘子的个数为如果汉诺塔问题中盘子的个数为64，而，而64个盘个盘的移动次数是：的移动次数是：18，446，744，073，709，551，615这是一个天文数字，若每一微秒可能计算这是一个天文数字，若每一微秒可能计算(并不输出并不输出)一次移动，那么也需要几乎一百万一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决值时的汉诺塔，但很难用计算机解决64层的层的汉诺塔。汉诺塔。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分

35、发挥中小学图书室育人功能汉诺塔问题分析汉诺塔问题分析n首先考虑首先考虑a杆下面的盘子而非杆上最上面的盘杆下面的盘子而非杆上最上面的盘子，于是任务变成了：子，于是任务变成了：*将上面的将上面的63个盘子移到个盘子移到b杆上；杆上；*将将a杆上剩下的盘子移到杆上剩下的盘子移到c杆上；杆上；*将将b杆上的全部盘子移到杆上的全部盘子移到c杆上。杆上。将这个过程继续下去，就是要先完成移动将这个过程继续下去，就是要先完成移动63个盘子、个盘子、62个盘子、个盘子、61个盘子个盘子.的工作的工作为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能n为

36、了更清楚地描述算法，可以定义一个函数为了更清楚地描述算法，可以定义一个函数hanoi(n,a,b,c)。该函数的功能是：将。该函数的功能是：将N个盘子从个盘子从A杆杆上借助上借助B杆移动到杆移动到C杆上。这样移动第杆上。这样移动第N个盘子的工作个盘子的工作就可以按照以下过程进行：就可以按照以下过程进行：1)hanoi(n-1,a,c,b);功能：将功能：将N-1个盘子从个盘子从A杆上借助杆上借助C杆移动到杆移动到B杆上杆上2)将一个盘子从将一个盘子从A杆杆移动到移动到C杆杆上；上；3)hanoi(n-1,b,a,c)；功能：将功能：将N-1个盘子从个盘子从B杆上借助杆上借助A杆移到杆移到C杆上

37、杆上这样就完成了工作，接着我们要做的就是看怎样完成这样就完成了工作，接着我们要做的就是看怎样完成hanoi(n-1,a,c,b);和和hanoi(n-1,b,a,c)；为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能Voidhanoi(intn,charx,chary,charz)/从柱从柱x上按规则移动编号从上按规则移动编号从1到到n的的n个圆盘到柱个圆盘到柱z上，上，柱柱y辅助移动辅助移动if(n=1)move(1,x,z);/将编号为将编号为1的圆盘从柱的圆盘从柱x移到柱移到柱zelsehanoi(n-1,x,z,y);/将编

38、号从将编号从1到到n-1的圆盘从柱的圆盘从柱x移移到柱到柱y，柱，柱z辅助移动辅助移动move(n,x,z);/将编号为将编号为n的圆盘从柱的圆盘从柱x移到柱移到柱zhanoi(n-1,y,x,z);将编号从将编号从1到到n-1的圆盘从柱的圆盘从柱y移移到柱到柱z，柱，柱x辅助移动辅助移动为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能Addr n x y zVoidhanoi(intn,charx,chary,charz)12if(n=1)3move(1,x,z);4else56hanoi(n-1,x,z,y);7move(n,x

39、,z);8hanoi(n-1,y,x,z);910 0 3 a b c 6 2 a c b调用调用hanoi(3,a,b,c);执行语句执行语句1，2，4，5调用调用hanoi(2,a,c,b);执行语句执行语句1，2，4，5调用调用hanoi(1,a,b,c);执行语句执行语句1，2，3，9hanoi(1,a,b,c)执行完毕执行完毕返回返回hanoi(2,a,c,b);中的第中的第6个语句个语句执行语句执行语句7，8调用调用hanoi(1,c,a,b);执行语句执行语句1，2，3，9hanoi(1,c,a,b)执行完毕执行完毕 6 1 a b c321abc12 8 1 c a b1为深入

40、学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能递归习题n小猴子第一天摘下若干桃子小猴子第一天摘下若干桃子,当即吃掉一半当即吃掉一半,又又多吃一个多吃一个.第二天早上又将剩下的桃子吃一半第二天早上又将剩下的桃子吃一半,又多吃一个又多吃一个.以后每天早上吃前一天剩下的一以后每天早上吃前一天剩下的一半另一个半另一个.到第到第10天早上猴子想再吃时发现天早上猴子想再吃时发现,只只剩下一个桃子了剩下一个桃子了.问第一天猴子共摘多少个桃问第一天猴子共摘多少个桃子？子？n有雌雄一对兔子，假定从两个月开始便可每月有雌雄一对兔子，假定从两个月开始便可每月

41、繁殖雌雄各一的一对小兔子。问过繁殖雌雄各一的一对小兔子。问过n个月后共个月后共有多少对兔子？有多少对兔子？为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能队列n n队列也是一种运算受限的线性表。在这种线性表上，队列也是一种运算受限的线性表。在这种线性表上，队列也是一种运算受限的线性表。在这种线性表上，队列也是一种运算受限的线性表。在这种线性表上，插入限定在表的某一端进行，删除限定在表的另一端插入限定在表的某一端进行，删除限定在表的另一端插入限定在表的某一端进行，删除限定在表的另一端插入限定在表的某一端进行，删除限定在表的另一端进行。

42、进行。进行。进行。n n允许插入的一端称为允许插入的一端称为允许插入的一端称为允许插入的一端称为队尾队尾队尾队尾，允许删除的一端称为，允许删除的一端称为，允许删除的一端称为，允许删除的一端称为队头队头队头队头。n n队列中数据元素的入队和出队过程是按照队列中数据元素的入队和出队过程是按照队列中数据元素的入队和出队过程是按照队列中数据元素的入队和出队过程是按照“先进先出先进先出先进先出先进先出”的原则进行的。因此，队列又称为的原则进行的。因此，队列又称为的原则进行的。因此，队列又称为的原则进行的。因此，队列又称为“先进先出先进先出先进先出先进先出”的的的的线性表，简称线性表，简称线性表，简称线性

43、表，简称(FirstInFirstOut)FIFO(FirstInFirstOut)FIFO表。表。表。表。an-1a1a2aian只允许插入只允许插入只允许插入只允许插入只允许删除只允许删除只允许删除只允许删除为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能n举例举例1：到医院看病，首先需要到挂号处挂号，：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。然后，按号码顺序救诊。n举例举例2：乘坐公共汽车，应该在车站排队，车：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。来后，按顺序上车。n举例举例3：在：在Windows

44、这类多任务的操作系统环这类多任务的操作系统环境中，每个应用程序响应一系列的境中，每个应用程序响应一系列的“消息消息”，像用户点击鼠标；拖动窗口这些操作都会导致像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。断地从队列中读取消息，并依次给予响应。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分

45、发挥中小学图书室育人功能队列的类型定义ADTQueue 数据对象数据对象：D=ai|ai ElemSeti=1,2,.,nn0数据关系数据关系：R1=|ai,ai+1 ElemSet,i=1,2,.,n-10约定约定an端为队列尾，端为队列尾，a1端为队列头端为队列头为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能基本操作基本操作：结构初始化结构初始化InitQueue(&Q)操作结果：构造一个空队列操作结果：构造一个空队列Q销毁结构销毁结构DetroyQueue(&Q)初始条件：队列初始条件：队列Q已经存在已经存在操作结果：销毁队

46、列操作结果：销毁队列Q为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能引用型操作引用型操作QueueEmpty(Q)/判断判断Q是否为空队列，若为空返回是否为空队列，若为空返回True，否则返，否则返回回FalseQueueLength(Q)/得到队列得到队列Q的元素个数，即队列的长度的元素个数，即队列的长度GetHead(Q，&e)/得到得到Q的队列头元素，并将之放入变量的队列头元素，并将之放入变量e中中StackTraverse(Q,visit()/从栈底到栈顶遍历队列从栈底到栈顶遍历队列Q，对每个元素调用，对每个元素调用vis

47、it()为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能加工型操作加工型操作ClearQueue(&Q)/清空队列清空队列QEnQueue(&Q,e)/向队列中插入元素向队列中插入元素e为新的队尾元素为新的队尾元素DeQueue(&Q,&e)/删除删除Q的队头元素，并用的队头元素，并用e返回值返回值为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能队列的存储结构n n队列有两种存储表示方法队列有两种存储表示方法:顺序存储和链式存顺序存储和链式存储储队列的顺序存储结构队列的顺

48、序存储结构n n队列的顺序存储结构简称队列的顺序存储结构简称顺序队顺序队n n顺序队是用一维数组依次存放队列中的元素顺序队是用一维数组依次存放队列中的元素,还需要有两个变量分别指示队列的首端和队列还需要有两个变量分别指示队列的首端和队列的尾端。这两个变量分别称为的尾端。这两个变量分别称为“队头指针队头指针”和和“队尾指针队尾指针”an-1a1a2aian出队入队frontrear为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能队列初始为空时队列初始为空时n队头和队尾都为队头和队尾都为0入队时入队时n将新元素插入将新元素插入rear所

49、指的位置，然后将之加所指的位置，然后将之加出队时出队时n删去删去front所指的元素，然后将之减并返回所指的元素，然后将之减并返回被删元素被删元素abc 0 1 2 3 4 5 6 7frontrearrearrearrear由此可见，当头尾指针相等时由此可见，当头尾指针相等时队列为空。队列为空。在非空队列里，头指针始终指在非空队列里，头指针始终指向队头元素，而尾指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。向队尾元素的下一位置。front为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能abc 0 1 2 3 4 5 6

50、 7defghfrontrear和栈类似，队列中亦有上溢和下溢现象。和栈类似，队列中亦有上溢和下溢现象。0 1 2 3 4 5 6 7frontrearcfront?再继续插入再继续插入?再继续删除再继续删除为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能?什么情况下什么情况下上溢上溢abc 0 1 2 3 4 5 6 7defghfrontrear队尾指针大于数组的最大下标时队尾指针大于数组的最大下标时 0 1 2 3 4 5 6 7rearfront?什么情况下什么情况下下溢下溢队头指针等于队尾指针时队头指针等于队尾指针时为深入