第3章栈和队列-2013数据结构电子教案c语言版本.ppt

* a3 a2 a1 0 1 2 3 N-1 rear front 循环队列（臆造） 顺序队列 a3 a2 a1 front rear 0 1 2 3 . . N-1 rear front 4 5 0 1 2 3 (a)队列初始情况 4 5 0 1 2 3 rear front (b)A进队 A front 4 5 0 1 2 3 rear (c) B、C、D进队 A B C D 4 5 0 1 2 3 rear (d) ABCD出队 front 队空 front 4 5 0 1 2 3 rear (f) G H I J进队 E F g H I J front 4 5 0 1 2 3 (e) E、F进队 E F rear 队满 如图所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front==rear来判断队列“空”还是“满”。 * 新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！ 解决方案有三： ① 加设标志位，让删除动作使其为1,插入动作使其为0,则可识别当前 front=rear ② 使用一个计数器记录队列中元素个数（即队列长度）； ③ 人为浪费一个单元，令队满特征为front=(rear+1)%N； front 4 5 0 1 2 3 rear (f) G H I J进队 E F g H I J 4 5 0 1 2 3 (a)队列初始情况 * 队空条件 : front = rear (初始化时：front = rear ) 队满条件： front = (rear+1) % N (N=maxsize) 队列长度：L=（N＋rear－front）% N J2 J3 J1 J4 J5 front rear 选用空闲单元法：即front和rear之一指向实元素，另一指向空闲元素。 问2： 在具有n个单元的循环队列中，队满时共有多少个元素？ n-1个 5 问1：左图中队列长度L=？ * J6 J5 J7 J8 J9 例1： 一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置? J2 J3 J1 J4 J5 front rear 解：由图可知，队头和队尾指针的初态分别为front=1和rear=6。 front rear 删除4个元素后front=5；再插入4个元素后，r=(6+4)%6=4 front front front front front * 问：为什么要设计队列？它有什么独特用途？ 离散事件的模拟（模拟事件发生的先后顺序）； 操作系统中多道作业的处理（一个CPU执行多个作业）； 3. 简化程序设计。 答： 循环队列的操作实现见教材P64 * 循环队列的操作实现 1）初始化一空队列 算法要求：生成一空队列 算法操作：为队列分配基本容量空间 设置队列为空队列， 即 front=rear=0（也可为任意单元，如 2，或 4）; * 算法： Status InitQueue ( SqQueue q ) {//初始化空循环队列 q q . base=(QElemType *)malloc(sizeof(QElemType） * QUEUE_MAXSIZE); //分配空间 if (!q.base) exit(OVERFLOW);//失败，退出程序 q.front =q.rear=0;//置空队列 return OK; }//InitQueue; 新开单元的地址为0则表示内存不足 * 算法说明：向循环队列的队尾插入一个元素 分 析： (1) 插入前应当先判断队列是否满 if (( q . rear + 1 ) % QUEUE_MAXSIZE )==q.front) return ERROR; (2）插入动作 q.base [q.rear] = e; q.rear = ( q . rear + 1 ) % QUEUE_MAXSIZE; 2） 入队操作 * Status EnQueue(SqQueue q,