第十三课：队列

时间：2010-09-23 来源：雨雨

第十三课本课主题：队列教学目的：掌握队列的类型定义,掌握链队列的表示与实现方法教学重点：链队列的表示与实现教学难点：链队列的表示与实现授课内容：一、队列的定义: 队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。象日常生活中的排队，最早入队的最早离开。在队列中，允许插入的的一端叫队尾，允许删除的一端则称为队头。抽象数据类型队列: 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;} 三、总结链队列的存储表示链队列的操作及实现