教学目的： 掌握队列的类型定义,掌握链队列的表示与实现方法

教学重点： 链队列的表示与实现

教学难点： 链队列的表示与实现

授课内容：

一、队列的定义:

队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。象日常生活中的排队，最早入队的最早离开。

在队列中，允许插入的的一端叫队尾，允许删除的一端则称为队头。

抽象数据类型队列:

ADT Queue{

数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}

数据关系: R1={<ai-1,ai> | ai-1,ai(- D,i=2,...,n}

基本操作：

InitQueue(&Q) 构造一个空队列Q

Destroyqueue(&Q) 队列Q存在则销毁Q

ClearQueue(&Q) 队列Q存在则将Q清为空队列

QueueEmpty(Q) 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE

QueueLenght(Q) 队列Q存在,返回Q的元素个数,即队列的长度

GetHead(Q,&e) Q为非空队列,用e返回Q的队头元素

EnQueue(&Q,e) 队列Q存在,插入元素e为Q的队尾元素

DeQueue(&Q,&e) Q为非空队列,删除Q的队头元素,并用e返回其值

QueueTraverse(Q,vivsit()) Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败

}ADT Queue

二、链队列－队列的链式表示和实现

用链表表示的队列简称为链队列。一个链队列显然需要两个分别指示队头和队尾的指针。

Q.front -> |     /|/     1 | 队头   /|/     2 |     /|/     3 |     /|/ /|/   Q.rear -> 9 // 队尾

Q.front -> |     /|/     1 | 队头   /|/     2 |     /|/     3 |     /|/ /|/   Q.rear -> 9 // 队尾

 

链队列表示和实现：

//存储表示

typedef struct QNode{

QElemType data;

struct QNode *next;

}QNode,*QueuePtr;

typedef struct{

QueuePtr front;

QueuePtr rear;

}LinkQueue;

//操作说明

Status InitQueue(LinkQueue &Q)

//构造一个空队列Q

Status Destroyqueue(LinkQueue &Q)

//队列Q存在则销毁Q

Status ClearQueue(LinkQueue &Q)

//队列Q存在则将Q清为空队列

Status QueueEmpty(LinkQueue Q)

// 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE

Status QueueLenght(LinkQueue Q)

// 队列Q存在,返回Q的元素个数,即队列的长度

Status GetHead(LinkQueue Q,QElemType &e)

//Q为非空队列,用e返回Q的队头元素

Status EnQueue(LinkQueue &Q,QElemType e)

//队列Q存在,插入元素e为Q的队尾元素

Status DeQueue(LinkQueue &Q,QElemType &e)

//Q为非空队列,删除Q的队头元素,并用e返回其值

Status QueueTraverse(LinkQueue Q,QElemType vivsit())

//Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败

//操作的实现

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 Destroyqueue(LinkQueue &Q) {

//队列Q存在则销毁Q

while(Q.front){

Q.rear=Q.front->next;

free(Q.front);

Q.front=Q.rear;

}

return OK;}

Status EnQueue(LinkQueue &Q,QElemType e) {

//队列Q存在,插入元素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为非空队列,删除Q的队头元素,并用e返回其值

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;}

三、总结

链队列的存储表示

链队列的操作及实现