数据结构课件：第3章队列.ppt

1、数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖 队列的应用队列的应用数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖3.4 3.4 队列队列3.4.1 3.4.1 抽象数据类型队列的定义抽象数据类型队列的定义 也是一种运算受限的线性表。它只允许在也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的表的一端进行插入，而在另一端进行删除。允许删除的一端称为一端称为，允许插入的一端称为，允许插入的一端称为。例如：排队购物。操作系统中的作业排队。先进入队例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作

2、先进先出列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)(First In First Out)的线性表，简称的线性表，简称FIFOFIFO表。表。当队列中没有元素时称为当队列中没有元素时称为。在空队列中依次加。在空队列中依次加入元素入元素a a1 1,a,a2 2, ,a an n之后，之后，a a1 1是是，a an n是是。显然退出队列的次序也只能是。显然退出队列的次序也只能是a a1 1,a,a2 2, ,a an n ，也就是说，也就是说队列的修改是依队列的修改是依先进先出先进先出的原则进行的。的原则进行的。数数 据据 结结 构构 武汉大学测绘学

3、院虞晖武汉大学测绘学院虞晖下图是队列的示意图：下图是队列的示意图： 队列的抽象数据定义见书队列的抽象数据定义见书59数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖队列的基本运算队列的基本运算 队列可定义如下五种基本运算：队列可定义如下五种基本运算：1初始化队列初始化队列 InitQueue(&Q) 将队列将队列Q设置成一个空队列。设置成一个空队列。2入队列入队列 EnQueue(&Q,X) 将元素将元素X插入到队尾中，也称插入到队尾中，也称“进队进队” ，“插入插入”。 3出队列出队列 DeQueue(&Q,&e) 将队列将队列Q的队头元素删除，并用的队头元素删除，并用e返回

4、其值，也称返回其值，也称“退队退队”、“删除删除”。4取队头元素取队头元素 GetHead(Q,&e) 得到队列得到队列Q的队头元素之值，并用的队头元素之值，并用e返回其值。返回其值。5判队空判队空 QueueEmpty(Q) 判断队列判断队列Q是否为空，若为空返回是否为空，若为空返回1，否则返回，否则返回0。数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖3.4.2 非循环队列和循环队列非循环队列和循环队列队列的顺序存储结构称为顺序队列，顺序队列实队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列际上是运算受限的顺序表，和顺序表一样，顺序

5、队列也是必须用一个向量空间来存放当前队列中的元素。也是必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设由于队列的队头和队尾的位置是变化的，因而要设两两个指针和分别指示队头和队尾元素在队列中的位置，个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值在队列初始化时均应置为。入队时将它们的初始值在队列初始化时均应置为。入队时将新元素插入所指的位置，然后尾指针加。出队时，新元素插入所指的位置，然后尾指针加。出队时，删去所指的元素，然后头指针加并返回被删元素。删去所指的元素，然后头指针加并返回被删元素。由此可见，由此可见，当头尾指针相等时队列为空当头尾指针相

6、等时队列为空。在非空队列在非空队列里，头指针始终指向队头元素，而尾指针始终指向队里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。尾元素的下一位置。数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖队列的顺序存储结构定义：队列的顺序存储结构定义：#define MAXQSIZE 100typedef struct ElemType dataMAXQSIZE; int front; int rear;SqQueue;数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖 0 1 2 3FrontrearabcFront rear (a)(a)队列初始为空（队

7、列初始为空（b b）A,B,CA,B,C入队入队 b c front rear front rear（c) a出队出队 (d) b,c出队，队为空出队，队为空 数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖n队空：队空：Q.front=Q.rearn队满：队满：Q.rear=maxsize（假溢出）（假溢出）求队长：求队长： Q.rear-Q.frontn 入队：新元素按入队：新元素按 rear 指示位置加入，指示位置加入，再将队尾指针加一再将队尾指针加一 ，即，即 rear = rear + 1n 出队：将出队：将front指示的元素取出，再将队指示的元素取出，再将队头指针

8、加一，即头指针加一，即front = front + 1，非循环队列非循环队列数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖 为充分利用向量空间，克服上述假上为充分利用向量空间，克服上述假上溢现象，可以将向量空间想象为一个首溢现象

9、，可以将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为量，存储在其中的队列称为循环队列（循环队列（Circular Queue)。在循环队列中进行出。在循环队列中进行出队、入队操作时，头尾指针仍要加队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量朝前移动。只不过当头尾指针指向向量上界（上界（QueueSize-1）时，其加）时，其加1操作的操作的结果是指向向量的下界结果是指向向量的下界0。数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖 显然，因为循环队列元素的空间可显然，因为循环队列元素的空

10、间可以被利用，除非向量空间真的被队列以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的，除一些简单的应用外，真正实用的顺序队列是顺序队列是循环队列。循环队列。 数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4J5J6012345rearfront初始状态初始状态J4,J5,J6出队出队J7,J8,J9入队入队队空：队空：front=rear队满：队满：front=rear解决方案：解决方案：1.另外另外设一个标志设

11、一个标志以区别队空、队满以区别队空、队满2.少用一个元素空间少用一个元素空间： 队空：队空：front=rear 队满：队满：(rear+1)%M=front数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖 由于入队时尾指针向前追赶头指针，出由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过时头尾指针均相等。因此，我们无法通过Q.front=Q.rear来判断队列来判断队列“空空”还是还是“满满”。 解决此问题的方法至少有两种：解决此问题的方法至少有两种： 其一是另设一个布尔变量以区

12、别队列的空其一是另设一个布尔变量以区别队列的空和满；其二是少用一个元素的空间，约定入和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加队前，测试尾指针在循环意义下加1后是否后是否等于头指针，若相等则认为队满（注意：等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）所指的单元始终为空）数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖队空：队空：Q.front =Q. rear队满：队满： Q.front =(Q.rear + 1) % maxSize入队入队: Q.rear = (Q.rear + 1) % maxSize出队出队: Q.front

13、 = (front + 1) % maxSize;求队长求队长:(Q.rear-Q.front+maxSize)%maxSize循环队列循环队列数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖 2) 进队列实现程序进队列实现程序Status EnQueue (SqQueue &Q, ElemType e) if (Q.rear+1)%MAXQSIZE = Q.front) return(ERROR); Q.dataQ.rear=e; Q.rear=(Q.rear+1)%MAXQSIZE; return(OK); 循环队列的基本运算实现循环队列的基本运算实现 1、进队列、进队列

14、1）进队列算法）进队列算法（1）检查队列是否已满，若队满，则进行溢出错误处理）检查队列是否已满，若队满，则进行溢出错误处理（2）将新元素赋给队尾指针所指单元；）将新元素赋给队尾指针所指单元；（3）将队尾指针后移一个位置（即加）将队尾指针后移一个位置（即加1），指向下一单元。），指向下一单元。数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖2) 出队列实现程序出队列实现程序Status DeQueue (SqQueue &Q, ElemType &e) if (Q.rear= Q.front) return(ERROR); e=Q.dataQ.front; Q.front=(Q.

15、front+1)%MAXQSIZE; return(OK); 2. 出队列出队列1)出队列算法出队列算法（1）检查队列是否为空，若队空，则进行下溢错误处理；）检查队列是否为空，若队空，则进行下溢错误处理；（2）取队首元素的值。）取队首元素的值。（3）将队首指针后移一个位置（即加）将队首指针后移一个位置（即加1）；）；数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖(4) 取队头元素取队头元素ElemType GetHead(SqQueue Q ) if (Q.front= =Q.rear) return(ERROR); return (Q.dataQ.front);(5) 判队

16、列空否判队列空否 int QueueEmpty(SqQueue Q ) if (Q.front= =Q.rear) reurn (1);else return (0); (3) 队列初始化队列初始化 Q.front=Q.rear=0;数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖3.4.3 3.4.3 链队列链队列 队列的链式存储结构简称为链队列，它是限队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指

17、向链表的最后一个结点。再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定。于是，一个链队列由头指针和尾指针唯一确定。数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖null*qq.frontq.rear非空队列非空队列q.frontq.rearnull空队列空队列*q 链队列示意图链队列示意图数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖 和顺序队列类似，我们也是将这两个指针封和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型装在一起，将链队列的类型LinkQueueLinkQueue定义为一定义为一个结构类型：个结

18、构类型： typedef struct queuenode ElemType data; struct queuenode *next; QueueNode;typedef struct QueueNode *front; QueueNode *rear; LinkQueue; 数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖q.frontq.rearnull置队空*q数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖下面给出链队列上实现的基本运算：下面给出链队列上实现的基本运算：构造一个空队列：构造一个空队列： void InitQueue(LinkQueue

19、&Q) Q.front=Q.rear=(queuenode *)malloc(sizeof(queuenode ); Q.front-next=Q.rear-next=NULL; 数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖队列的判空：队列的判空：int QueueEmpty(LinkQueue Q) return (Q.front-next= =NULL & Q.rear-next= =NULL); 数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖void EnQueue(LinkQueue &Q,ElemType e)QueueNode *p; p=(Q

20、ueueNode * )malloc(sizeof(QueueNode); pdata=e; pnext=NULL; Q.rearnext=p; Q.rear=p;入入队队操操作作数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖null*qq.frontq.rear入队xnullp数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖出队操作：Status DeQueue(LinkQueue &Q,ElenType &e) QueueNode *p; if(QueueEmpty(Q) return ERROR; p=Q.front-next; e=pdata; Q.f

21、ront-next=pnext; if(Q.rear = =p) Q.rear=Q.front; free(p); return OK; 数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖null*qq.rearxnullq.frontp存储池出队数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖队列的应用队列的应用 队列在日常生活中和计算机程序设计中，有着队列在日常生活中和计算机程序设计中，有着非常重要的作用，非常重要的作用， 如如CPU资源的竞争问题。在具有多个终端的计资源的竞争问题。在具有多个终端的计算机系统中，有多个用户需要使用算机系统中，有多个用户需要使用

22、CPU各自运行自各自运行自己的程序，它们分别通过各自终端向操作系统提出己的程序，它们分别通过各自终端向操作系统提出使用使用CPU的请求，操作系统按照每个请求在时间上的请求，操作系统按照每个请求在时间上的先后顺序，将其排成一个队列，每次把的先后顺序，将其排成一个队列，每次把CPU分配分配给队头用户使用，当相应的程序运行结束，则令其给队头用户使用，当相应的程序运行结束，则令其出队，再把出队，再把CPU分配给新的队头用户，直到所有用分配给新的队头用户，直到所有用户任务处理完毕。户任务处理完毕。数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖 第二个例子就是主机与外部设备之间速度不匹第

23、二个例子就是主机与外部设备之间速度不匹配的问题。以主机和打印机为例来说明，主机输出配的问题。以主机和打印机为例来说明，主机输出数据给打印机打印，主机输出数据的速度比打印机数据给打印机打印，主机输出数据的速度比打印机打印的速度要快得多，若直接把输出的数据送给打打印的速度要快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。所以印机打印，由于速度不匹配，显然是不行的。所以解决的方法是设置一个打印数据缓冲区，主机把要解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依此写如到这个缓冲区中，写满后打印输出的数据依此写如到这个缓冲区中，写满后就暂停输出，继而去做其它的事情，打

24、印机就从缓就暂停输出，继而去做其它的事情，打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样利用队列既保证了打印缓冲区写入打印数据，这样利用队列既保证了打印数据的正确，又使主机提高了效率。数据的正确，又使主机提高了效率。数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖线性表、栈与队的异同点线性表、栈与队的异同点相同点相同点：逻辑结构相同，都是线性的；都可以用顺序存逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈

25、和队列是两种特殊的线性表，即储或链表存储；栈和队列是两种特殊的线性表，即受受限的线性表限的线性表（只是对插入、删除运算加以限制）。（只是对插入、删除运算加以限制）。不同点：不同点： 运算规则不同，线性表为随机存取，而栈是只允许运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表在一端进行插入和删除运算，因而是后进先出表LIFOLIFO；队列是只允许在一端进行插入、另一端进行删除运；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表算，因而是先进先出表FIFOFIFO。 用途不同，线性表比较通用；堆栈用于函数调用、用途不同，线性表比较通用；堆栈用于

26、函数调用、递归和简化设计等；队列用于离散事件模拟、多道作递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。业处理和简化设计等。数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖一、一、填空题填空题1.1. 线性表、栈和队列都是线性表、栈和队列都是 结结构，可以在线性表的构，可以在线性表的 位置插入和删除元素；对于栈只能在位置插入和删除元素；对于栈只能在 插入和删除元插入和删除元素；对于队列只能在素；对于队列只能在 插入和插入和 删除元素。删除元素。2. 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈是一种特殊的线性表，允许插入和删除运算的一端称为 。不

27、允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为 。3. 3. 是被限定为只能在表的一端进行插入运算，在表的是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。另一端进行删除运算的线性表。4. 4. 在一个循环队列中，队首指针指向队首元素的在一个循环队列中，队首指针指向队首元素的 位置位置。5. 5. 在具有在具有n n个单元的循环队列中，队满时共有个单元的循环队列中，队满时共有 个元素个元素。6. 6. 向栈中压入元素的操作是先向栈中压入元素的操作是先 ，后，后 。7 . 7 . 从 循 环 队 列 中 删 除 一 个 元 素 时 ， 其 操 作 是从 循 环

28、 队 列 中 删 除 一 个 元 素 时 ， 其 操 作 是 先先 ，后，后 。数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖判断正误判断正误 1. 1.线性表的每个结点只能是一个简单类型，而链表的每个结点可线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。以是一个复杂类型。 2. 2. 在表结构中最常用的是线性表，栈和队列不太常用。在表结构中最常用的是线性表，栈和队列不太常用。 3. 3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。，是一种后进先出型结构。 4.

29、4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。也可以是线性表。 5. 5. 栈和链表是两种不同的数据结构。栈和链表是两种不同的数据结构。 6. 6. 栈和队列是一种非线性数据结构。栈和队列是一种非线性数据结构。 7. 7. 栈和队列的存储方式既可是顺序方式，也可是链接方式栈和队列的存储方式既可是顺序方式，也可是链接方式 8. 8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。出机会，应把两个栈的栈

30、底分别设在这片内存空间的两端。 9. 9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。种先进后出型结构。 10. 10. 一个栈的输入序列是一个栈的输入序列是1234512345，则栈的输出序列不可能是，则栈的输出序列不可能是1234512345。 数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖三、单项选择题（每小题三、单项选择题（每小题1分，共分，共20分）分）（ ）1. 栈中元素的进出原则是栈中元素的进出原则是 先进先出先进先出 后进先出后进先出 栈空则进栈空则进 栈满则出栈满则出 ( ）

31、2. 若已知一个栈的入栈序列是若已知一个栈的入栈序列是1，2，3，n，其输出序，其输出序列为列为p1，p2，p3，pn，若，若p1=n，则，则pi为为 i n=i n-i+1 不确定不确定 （ ）3. 判定一个栈判定一个栈ST（最多元素为（最多元素为m0）为空的条件是）为空的条件是 ST-top0 ST-top=0 ST-topm0 ST-top=m0（ ）4. 判定一个队列判定一个队列QU（最多元素为（最多元素为m0）为满队列的条件）为满队列的条件是是 QU-rear QU-front = = m0 QU-rear QU-front 1= = m0 QU-front = = QU-rear

32、QU-front = = QU-rear+1数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖（ ）5数组用来表示一个循环队列，为当前队数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为的个数小于，计算队列中元素的公式为（）（）rf; （）（）（nfr）% n; （）（）nrf; （）（）（nrf）% n6. 设有设有4个数据元素个数据元素a1、a2、a3和和a4，对他们分别进行栈操作或，对他们分别进行栈操作或队操作。在进栈或进队操作时，按队操作。在进栈或进队

33、操作时，按a1、a2、a3、a4次序每次进入次序每次进入一个元素。假设栈或队的初始状态都是空。一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是一次；这时，第一次出栈得到的元素是 A ，第二次出栈得到，第二次出栈得到的元素是的元素是 B ；类似地，考虑对这四个数据元素进行的队操作；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是次出队得到的元素是 C

34、 ，第二次出队得到的元素是，第二次出队得到的元素是 D 。经。经操作后，最后在栈中或队中的元素还有操作后，最后在栈中或队中的元素还有 E 个。个。供选择的答案：供选择的答案： AD：a1 a2 a3 a4 E： 1 2 3 0数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖作业作业: :1.1.说明线性表、栈与队的异同点。说明线性表、栈与队的异同点。2.2.顺序队的顺序队的“假溢出假溢出”是怎样产生的？如何知道循环是怎样产生的？如何知道循环队列是空还是满？队列是空还是满？3 .3 .按照四则运算加、减、乘、除和幂运算（按照四则运算加、减、乘、除和幂运算（）优先）优先关系的惯例，并仿照教材例关系的惯例，并仿照教材例3-23-2的格式，画出对下列算的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：术表达式求值时操作数栈和运算符栈的变化过程： A AB BC/D+EC/D+EF F数数 据据 结结 构构 武汉大学测绘学院虞晖武汉大学测绘学院虞晖1.实现栈的基本操作（顺序链式都可）实现栈的基本操作（顺序链式都可）2.在在main()中调用栈的函数实现数制转换中调用栈的函数实现数制转换.(可选做可选做)3.实现实现Hanoi塔的递归函数塔的递归函数.上机时间：上机时间：9月月30日日1,2节节地点：测绘学院一楼机房地点：测绘学院一楼机房