第3单元线性数据结构二主讲：刘志强

第3单元线性数据结构二主讲：刘志强内容摘要：

= queue[front]； front = front +1； 显然，对于第 1个元素和其它元素的读操作，将出现不一致。 判别队列为空的条件也将复杂化。 下一页 上一页 停止放映 第 40/89 页 关于队列表示的约定 为解决这个问题，约定如下： 队头指针 front总是指向队头元素的前一个位置； 队尾指针 rear总是指向队尾元素的位置。 这样一来，无论对什么元素，出队操作都是一样的。 front = front +1 ； x = queue [front ]； front rear a1 a2 … a n 下一页 上一页 停止放映 第 41/89 页 举例：顺序队列的入队、出队操作 （ A）空队列 （ B） A、 B、 C、 D、 E入队 （ C） A、 B、 C出队 A B C D E front rear front rear D E front rear 入队时， rear在变 出队时， front在变 下一页 上一页 停止放映 第 42/89 页 举例 :顺序队列入队、出队操作 （ D） F、 G、 H入队 (E） D、 E、 F、 G、 H出队，出现假 ‚ 溢出 ‛ 注： 一方面队列中是空的，另一方面又出现溢出。 显然，这是逻辑设计上的问题。 front front rear D E F G H rear 下一页 上一页 停止放映 第 43/89 页 解决假溢出的方法 如果使当 rear = MAXSIZE+1 时，即超过队列末端时，令 rear = 1；从而使队列的首尾相连接。 用表达式描述 : if （ rear MAXSIZE ） rear = 1。 else rear = rear + 1。 这就是循环队列的处理思想。 下一页 上一页 停止放映 第 44/89 页 循环队列 设定 queue[1]接在 queue[MAXSIZE]之后 ,使得 if （ rear MAXSIZE ） rear = 1。 else rear＝ rear + 1。 这样构成循环队列。 下一页 上一页 停止放映 第 45/89 页 循环队列的指针移动 （ 1） 队头指针 front = front% MAXSIZE + 1； 等价于： if（ front MAXSIZE ） front = 1。 else front ＝ front + 1。 （ 2）队尾指针 rear = rear % MAXSIZE +1 ； 等价于： if （ rear MAXSIZE ） rear = 1。 else rear＝ rear + 1。 循环队列在指针移动处理时与一般队列不同： 下一页 上一页 停止放映 第 46/89 页 循环队列队空、队满条件 队空条件 front = rear ； 队满条件 front = rear % MAXSIZE +1 rear front 1 2 3 MAXSIZE ... 1 2 3 4 ... i rear i+1 front MAXSIZE a1 a2 a3 ai1 示例 … 下一页 上一页 停止放映 第 47/89 页 循环队列入队操作 算法 112描述 : step1 判别队列是否已满。 step2 队尾指针后移一个位置 ,将新结点元素值存入当前结点单元。 数据结构定义： define MAXSIZE n int queue[MAXSIZE]； int front， rear； 下一页 上一页 停止放映 第 48/89 页 循环队列入队操作程序 addqueue(int x) { if (front = = rear % MAXIZE +1 ) { printf(“循环队列已满 \n”)。 exit(1)。 } else { rear = rear % MAXSIZE +1。 queue[rear] = x。 } } 下一页 上一页 停止放映 第 49/89 页 循环队列出队操作 算法 113描述 : step1 判别队列是否为空。 若空 ,则显示队列 ‘ 下溢 ’。 step2 队头指针后移一个位置。 下一页 上一页 停止放映 第 50/89 页 循环队列出队操作程序 delqueue( ) { int y。 if ( front = = rear ) { printf( “ 循环队列已空 \n”)。 y = 1 ； } else { front = front % MAXSIZE +1 ； y = queue[front] ； } return y ； } 下一页 上一页 停止放映 第 51/89 页 队列的链式存储结构 用带头结点的单链表作为队列的存储结构，称为队列的链式存储结构。 存储结构的 C语言描述， struct qnode { int data ； struct qnode * next； } ； typedef struct qnode QNODE ； QNODE *front， *rear； data next 数据域 指针域 下一页 上一页 停止放映 第 52/89 页 链队列为空的表示 链队列为空 = 表示形式： front rear ^ front rear ^ ... an a2 a1 非空队列 下一页 上一页 停止放映 第 53/89 页 链队列为满的条件 链满的条件为 : T = NULL T 为新创建的结点 ,当没有存储空间时 ,T为 NULL,表示链队列已满。 下一页 上一页 停止放映 第 54/89 页 链队列的入队操作 算法 114描述 : step1 申请建立一个新结点 T。 step2 判别 T是否为空。 若空 ,表示 队列已满。 step3 非空 ,将 T插入链中 ,修改 rear指针。 下一页 上一页 停止放映 第 55/89 页 链队列的入队操作 addqueue(int x) { QNODE *t。 t = (QNODE*)malloc(sizeof(QNODE))。 if （ t = = NULL） { printf（ ‚ 内存无可用空间 \n”)。 exit(1)。 } else { rear next = t。 rear = t。 t data = x。 t next = NULL。 } } 下一页 上一页 停止放映 第 56/89 页 链队列的出队操作 当队列长度大于 1时 ,只修改队头指针即可。 an ^ front rear Queue Queue front rear ^ an ^ T ... Queue Queue front rear rear front a1 an ^ a1 a2 a2 ^ ... an ^ 出队操作要考虑两种情况。 当队列长度为 1时 ,除了修改队头指针外 ,还要修改队尾指针。 下一页 上一页 停止放映 第 57/89 页 链队列的出队操作 算法 115描述 : step1 判别队列是否为空。 若空 ,则显示 队列 ‘ 下溢 ’。 step2 非空 ,则判别队长度是否为 1。 不为 1,修改头指针。 为 1,则修改头、尾指针； step3 释放 T。 下一页 上一页 停止放映 第 58/89 页 链队列的出队操作的程序 delqueue( ) { int x。 QNODE *t。 if ( front = = rear) { printf(“链队列已空 \n”)。 exit(1)。 } else { t = frontnext。 x = t data。 frontnext = tnext。