第4章栈和队列.ppt

分析：若一个柱子上只有一个圆盘，则不需要使用过渡台柱，直接把它放到目的柱上即可。若一个柱子上有两个圆盘，则先把一个（只能是上面一个）放到过渡柱子上，再把另一个放到目的柱上，最后把过渡柱上的一个圆盘放到目的柱上，到此完成搬动过程。若一个柱子上有三个、四个、…，又如何解决呢？必须找出适应于任意多个（即大于等于2个）情况的通用方法或规则才行。由此可能想到递归，即先把原柱子上的n-1个圆盘设法搬到过渡柱上，再把原柱子上剩下的最后一个圆盘直接搬到目的柱上，最后设法把过渡柱上的n-1个圆盘搬到目的柱上，从而完成全部搬动过程；当把n-1个圆盘从一个柱子搬动到另一个柱子时，若它多于一个，又需要使用第三个柱子作为过渡。此递归就是把n的问题化解为两个n-1的问题，当n等于1时不需要再递归，只需要直接移动即可。 例如，当A柱上有3个圆盘，要求把它移动到C柱上，则需要以下3步完成： (1) 把A柱上的2个圆盘移到过渡柱B上； (2) 把A柱上剩下的1个圆盘直接移到目的柱C上； (3) 把过渡柱B上的2个圆盘移到目的柱C上。 对于第1步还需要递归完成，具体为以下3步： (1.1) 把A柱上的1个圆盘直接移到此时的过渡柱C上； (1.2) 把A柱上剩余的1个圆盘直接移到此时的目的柱B上； (1.3) 把此时的过渡柱C上的1个圆盘直接移到此时的目的柱B上。 对于第3步也需要递归完成，具体为以下3步： (3.1) 把B柱上的1个圆盘直接移到此时的过渡柱A上； (3.2) 把B柱上剩余的1个圆盘直接移到此时的目的柱C上； (3.3) 把此时的过渡柱A上的1个圆盘直接移到此时的目的柱C上。 上述整个移动过程为7个直接步骤，依次为： A→C; A→B; C→B; A→C; B→A; B→C; A→C 或用数字编号写为： 1→3; 1→2; 3→2; 1→3; 2→1; 2→3; 1→3 根据以上分析，设把n个盘子由值参a所表示的柱子搬到由值参c所表示的柱子，用值参b所表示的柱子作为过渡，则编写出递归算法如下： void Hanoi(int n, int a, int b, int c ) { /*当只有一个盘子时，直接由a柱搬到c柱后结束一次调用*/ if(n==1) printf(%d→%d ,a,c); /*当多于一个盘子时，向下递归*/ else { /*首先把n-1个盘子由值参a所表示的柱子搬到由值参b所表示 的柱子上，用值参c所表示的柱子作为过渡*/ Hanoi(n-1,a,c,b); /*把由值参a所表示的柱子上的最后一个盘子搬到由值参c所 表示的柱子上*/ printf(%d→%d ,a,c); /*最后把n-1个盘子由值参b所表示的柱子搬到由值参c所表示 的柱子上，用值参a所表示的柱子作为过渡*/ Hanoi(n-1,b,a,c); } } 4.7 队列 4.7.1 队列的定义 队列（queue）简称队，它也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。我们把进行插入的一端称作队尾(rear)，进行删除的一端称作队首(front)。向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除元素称为离队或出队，元素离队后，其后继元素就成为队首元素。由于队列的插入和删除操作分别是在各自的一端进行的，每个元素必然按照进入的次序离队，所以又把队列称为先进先出表（first in first out, 简称FIFO）。 4.7.2 队列的运算概述 (1) 初始化队列Q，即置Q为空 void InitQueue(Q); (2) 将新元素x的值插入到队尾 void EnQueue(Q, ElemType x); (3) 从队列中删除队首元素并返回之 ElemType OutQueue(Q); (4) 返回队首元素，但不改变队列状态 ElemType PeekQueue(Q); (5) 判断队列是否为空，若是则返回1，否则返回0 int EmptyQueu