数据结构教程第十三课队列

数据结构教程第十三课队列2007-05-17教学目的：掌握队列的类型定义,掌握链队列的表示与实现方法

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

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

授课内容：

一、队列的定义:

队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。象日常生活中的排队，最早入队的最早离开。
在队列中，允许插入的的一端叫队尾，允许删除的一端则称为队头。
抽象数据类型队列:
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;}

三、总结

链队列的存储表示
链队列的操作及实现

首页 / 软件开发 / 数据结构与算法 / 数据结构教程 第十三课 队列

首页 / 软件开发 / 数据结构与算法 / 数据结构教程第十三课队列