6队列的特点及其表示实现探析.ppt

队列的特点及其表示实现;3.4 队列 *3.4.1 抽象数据类型队列的定义 *3.4.2 链队列-队列的链式表示和实现 3.4.3 循环队列-队列的顺序表示和实现;内容回顾;3.4 队列;队列：队列是一种只允许在表的一端插入，在另一端删除的存取受限的线性表。 概念： 队尾rear： 插入端，线性表的表尾。 队头front：删除端，线性表的表头。;队列(Queue)图示; ADT Queue { 数据对象： D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0} 数据关系： R1＝{ a i-1,ai | ai-1, ai ∈D, i=2,...,n} 约定其中a1 端为队列头， an 端为队列尾;队列的基本操作：;用链表表示的队列简称为链队列。 ;(a)非空队; typedef struct QNode { // 结点类型 QElemType data; struct QNode *next; } QNode, *QueuePtr;;typedef struct { // 链队列类型 QueuePtr front; // 队头指针 QueuePtr rear; // 队尾指针 } LinkQueue;; Status InitQueue (LinkQueue Q) { // 构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit (OVERFLOW); //存储分配失败 Q.front-next = NULL; return OK; }; Status EnQueue (LinkQueue Q, QElemType e) { // 插入元素e为Q的新的队尾元素 p = (QueuePtr) malloc (sizeof (QNode)); if (!p) exit (OVERFLOW); //存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK; }; Status DeQueue (LinkQueue Q, QElemType e) { // 若队列不空，则删除Q的队头元素， //用 e 返回其值，并返回OK；否则返回ERROR if (Q.front == Q.rear) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear == p) Q.rear = Q.front; //注意：如果队 列中 只有一个元素，则队头也同时是队尾，删除队头元素后也需要修改队尾指针。 free (p); return OK; };3.4.3 循环队列-队列的顺序表示和实现; 例如：; 当Q.rear= =MAXSIZE时，表示队满，但队列中还有空闲单元，称为“假溢出” ;0;J7;6;如何判断循环队列的满与空： 1、设一标志位 2、空出一个元素的空间 3、使用计数器; 2、类型定义（实际实现） const int MAXSIZE=20; typedef struct { QElemType *base; // QElemType base[MAXSIZE]; int front; //队头指针 int rear; //队尾指针 }SqQueue; 其中队头指针始终指向队头元素，队尾指针始终指向队尾元素的下一个位置。;1）初始化 Status InitQueue (SqQueue Q) { // 构造一个空队列Q Q.base = (QElemType *) malloc