数据结构实验报告队列的表示与实现.doc

数据结构实验报告
姓名

学号
号

实验地点
数学楼
指导教师

实验
名称
队列的表示与实现
1、实验目的
了解和掌握队列的数据类型描述及其特点；
完成链队列的初始化、入队、出队、取对头元素、显示操作的实现;
掌握队列的链式存储表示与基本操作算法实现;
掌握队列在实际问题中的应用和基本编程技巧。
2、实验方法
队列的抽象数据类型定义:
ADT Queue{
//数据对象：D={a[i］|a[i］∈ElemSet，i=1,2，..。，n，n〉=0｝
//数据关系：R1=｛〈a[i—1]，a［i]〉|a［i—1］,a［i］∈D,i=2,.。。,n｝
//约定其中a［1]端为队列头，a[n］端为队列尾
//基本操作:
InitQueue(＆Q）//操作结果:构造一个空队列Q。
DestoryQueue（＆Q）//初始条件：队列Q已存在
//操作结果：队列Q被销毁，不再存在
ClearQueue（＆Q)//初始条件：队列Q已存在
//操作结果：将Q清为空队列
QueueEmpty(Q）//初始条件：队列Q已存在
//操作结果：若队列Q为空队列，则返回TRUE，否则FALSE
QueueLength(Q)//初始条件:队列Q已存在
//操作结果:返回Q的元素个数，即队列的长度
GetHead(Q，＆e）//初始条件：Q为非空队列
//操作结果:用e返回Q的队头元素
EnQueue（＆Q，e)//初始条件:队列Q已存在
//操作结果:插入元素e为Q的新的队尾元素
DeQueue（&Q，&e）//初始条件：Q为非空队列
//操作结果：删除Q的队头元素，并用e返回其值
QueueTraverse（Q,visit（））//初始条件：Q已存在且非空
//操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit(）.
一旦visit（）失败，则操作失败。
｝ADT Queue
与线性表类似，队列有两种存储表示链队列和循环队列。
//--—--基本操作的函数原型说明-——-—
status INitQueue（LinkQueue ＆Q）//构造一个空队列Q
Status DestoryQueue（LinkQueue ＆Q）//销毁队列Q，Q不再存在
Status ClearQueue（LinkQueue &Q）//将Q清为空队列
Status QueueEmpty(LinkQueue Q)
//若队列Q为空队列，则返回TRUE，否则返回FALSE
int QueueLength(LinkQueue Q）//返回Q的元素个数，即为队列的长度
Status GetHead(LinkQueue Q，QElemType &e）
//若队列不空，则用e返回Q的队头元素，并返回OK;否则返回ERROR
Status ENQueue（LinkQueue ＆Q,QElemType e)//插入元素e为Q的新的队尾元素
Status DeQueue（LinkQueue ＆Q，QElemType ＆e)
//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR
status QueueTraverse（linkQueue Q，visit（)）
//从队头到队尾依次对队列Q中的每个元素调用函数visit()。
一旦visit失败，则操作失败。
链队列:
//单链队列——队列的链式存储结构
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 DestoryQueue（LinkQueue &Q）｛//销毁队列Q，Q不再存在
while（Q.front）｛
Q。rear=Q.front —>next;
free（Q。front ）；
Q.front =Q。rear ；}
return OK；｝
Status ClearQueue(LinkQueue ＆Q）
//将Q清为空队列
Status QueueEmpty(LinkQueue Q）
//若队列Q为空队列,则返回TRUE，否则返回FALSE
int QueueLength（LinkQueue Q)
//返回Q的元素个数，即为队列的长度
Status GetHead（LinkQueue Q，QElemType ＆e)
//若队列不空,则用e返回Q的队头元素，并返回OK；否则返回ERROR
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；}
status QueueTraverse(linkQueue Q,visit(））
//从队头到队尾依次对队列Q中的每个元素调用函数visit()。
//一旦visit失败，则操作失败。
循环队列：
//循环队列——队列的顺序存储结构
#define MAXQSIZE 100 //最大队列长度
typedef struct｛
QElemType ＊base；//初始化的动态分配存储空间
int front； //头指针，若队列不空，指向队列头元素
int rear； //尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue；
//—-———循环队列的基本操作的算法描述——-———
Status InitQueue（SqQueue &Q）｛
//构造一个空队列Q
Q.base=（QElemType ＊）malloc（MAXQSIZE *sizeof（QElemType)）；
if(！Q。base） exit (OVERFLOW）；//存储分配失败
Q.front=Q。rear=0；
return OK；
}
int QueueLength(SqQueue Q）｛//返回Q的元素个数,即队列的长度
return（Q。rear—Q。front+MAXQSIZE）％MAXQSIZE；｝
status EnQueue（SqQueue &Q，QElemType）{//插入元素e为Q的新的队尾元素
if((Q.rear+1)%MAXQSIZE==Q.front） return ERROR；//队列满
Q。base［Q。rear]=e;
Q。rear=（Q。rear+1）%MAXQSIZE;
return OK；}
Status DeQueue（Squeue ＆Q，QElemType ＆e）｛
//若队列不空，则删除Q的队头元素，用e返回其值,并返回OK；
//否则返回ERROR
if（Q。front==Q。rear） return ERROR;
e=Q。base［Q。front]；
Q.front=(Q.front+1）%MAXQSIZE；
return OK；
}
3、事先定义的常量和类型
/*＊**＊＊*＊*＊＊＊**＊＊*＊＊＊＊＊＊C函数库定义*＊＊＊＊＊*＊**＊*＊＊＊＊/
#include 〈stdio.h〉 //EOF NULL
#include <string。h>
＃include 〈malloc。h> //malloc()；
＃include <limits.h> //ENT MAX
＃include 〈stdlib。h>
＃include <math。h〉 //floor（），fabs（），abs(），ceil(），
#include <io。h〉 //eof(）
＃include <process。h> //exit（)
＃include <iostream.h〉 //cout,cin
/**＊＊＊＊***＊＊*＊*＊＊*＊函数结果状态代码＊＊＊*＊＊＊＊＊*＊*＊＊＊＊/
#define TRUE 1
#define FALSE 0
＃define OK 1
＃define ERROR 0
＃define INFEASIBLE —1
//#define OVERFLOW —2 // 因为math。h中已经定义OVERFLOW为3
typedef int QElemType;//ElemType是变量的类型定义
typedef int Status；//Status是函数的类型，其值是函数结果状态代码,如OK，TRUE。
4、实验过程
链队列
#include〈stdio.h〉
＃include〈stdlib。h>
＃include<process.h>
#define OK 1
＃define ERROR 0
＃define OVERFLOW 0
typedef struct QNode
{
int data;
struct QNode *next；
}QNode，＊QueuePtr;
typedef struct
｛
QueuePtr front；
QueuePtr rear；
｝LinkQueue；
int InitQueue（LinkQueue &Q）
｛
Q。rear=Q。front=（QueuePtr)malloc（sizeof（QNode)）;
if（!Q.rear)
exit（OVERFLOW）；
Q.front—>next=NULL;
return OK;
｝
void QueueEmpty（LinkQueue Q）
｛
if（Q。front==Q.rear）
printf("该链队为空："）；
else
printf（”该链队不为空:”）;
}
void EnQueue（LinkQueue &Q,int e）
｛
QueuePtr p;
p=（QueuePtr）malloc(sizeof(QNode）)；
if（！p)
printf(”error”)；
p—>data=e;
Q。rear—〉next=p；
Q.rear=p；
printf（"元素%d入队成功"，e)；
｝
int EnnQueue（LinkQueue ＆Q，int e）
｛
QueuePtr p；
p=（QueuePtr）malloc（sizeof（QNode））;
if（！p）
return ERROR;
p—〉data=e；
Q。rear->next=p；
Q。rear=p；
return OK;
｝
void DeQueue(LinkQueue &Q）
｛
QueuePtr p；
if(Q。front==Q。rear)
printf（"该链队为空”）;
p=Q。front—>next；
Q。front—〉next=p-〉next;
if（Q.rear==p）
Q.rear=Q.front;
free（p）;
printf（”队首元素删除成功”）;
}
void GetHead(LinkQueue ＆Q)
{
QueuePtr p；
if(Q.front==Q.rear)
printf（”该链队为空")；
p=Q.front—>next;
printf（"队首元素为：％d”，p—〉data);
}
void OutQueue(LinkQueue ＆Q）
｛
QueuePtr p；
if(Q。front==Q.rear）
printf("该链队为空")；
p=Q.front—〉next;
while（p!=Q.rear—>next）
｛
printf（”％d",p—>data）;
p=p—>next；
｝
｝
void LengthQueue（LinkQueue ＆Q）
｛
int f=0；
QueuePtr p;
if（Q。front==Q.rear）
printf（"该队列的长度是：%d"，f）；
else
｛
p=Q。front—>next;
while（p！=Q.rear—〉next）
｛
p=p—>next;
f++;
}
printf("该队列的长度是：％d",f）;
}
｝
void main（）
｛
system(”cls”）;
int flag=1,i；
LinkQueue Q;
InitQueue（Q)；
printf(”＊＊＊*＊＊＊＊*＊＊*＊*＊***＊***＊*链队列功能菜单*＊＊＊＊**＊＊＊＊＊*＊＊＊＊*＊*＊*＊\n”）;
printf（”1：初始化链队列, 2：判断链队列是否为空， 3：进入队列， 4：取出队首元素\n”）;
printf（”5：输出该队列的所有元素， 6：输出该队列的长度， 7：结束程序, 8:清屏\n"）；
while(flag）
{
printf（"\n请输入操作符："）;
scanf("％d”，＆i)；
switch（i)
｛
case 1:
int e,n，k；
printf（”请输入队列的长度：”)；
scanf（”％d”，&n);
printf("请输入队列的元素:")；
for(e=1；e<=n;e++)
{
scanf(”％d"，&k）；
EnnQueue（Q,k）;
｝
printf（"初始化链队成功”）;
break；
case 2:
QueueEmpty（Q）;
break;
case 3:
int j；
printf（"请输入要进入队列的元素"）；
scanf（”％d”，＆j)；
EnQueue（Q，j）；
break；
case 4:
GetHead(Q）；
break;
case 5：
printf（”该队列的元素是:"）；
OutQueue（Q);
break;
case 6：
LengthQueue（Q）；
break；
case 7：
flag=0；
break;
case 8：
system（”cls”）；
break；
｝
｝
printf(”程序结束”）;
｝
循环队列
＃include〈stdio.h>
＃include〈stdlib。h>
＃include<process。h>
#define MAXSIZE 10;
＃define OK 1；
＃define ERROR 0；
＃define OVERFLOW 0；
typedef struct
｛
int *data;
int front ；
int rear;
｝SqQueue；
int InitQueue_Sq（SqQueue &Q）
｛
Q。data=(int＊)malloc(10＊sizeof(int）)；
if（！Q。data）
exit（0）;
Q.front=Q。rear=0;
return OK；
}
int EnQueue_Sq（SqQueue ＆Q，int e）
｛
if（(Q.rear+1）%10==Q。front）
return ERROR;
Q。data［Q。rear］=e;
Q.rear=(Q.rear+1）%10；
return OK;
｝
void IfEmpty（SqQueue Q)
｛
if(Q。rear=Q.front)
printf（"该循环队列是空队列\n”）；
else
printf（”该循环队列不是空队列\n")；
｝
void IfFull(SqQueue Q)
｛
if（（Q。rear+1）%10==Q。front）
printf（”该循环队列已满\n"）；
else
printf(”该循环队列未满\n”）；
｝
void InQueue_Sq（SqQueue ＆Q,int e）
｛
if（（Q。rear+1）％10==Q.front）
printf（”循环队列已满\n"）；
else
｛
Q。data［Q.rear］=e；
Q.rear=（Q。rear+1）％10;
printf（"元素%d成功进入循环队列\n”，e)；
}
}
void DeQueue_Sq（SqQueue ＆Q)
｛
int e；
if（Q。front==Q。rear)
printf（”循环队列为空\n");
e=Q.data［Q.front］；
printf（"循环队列队首元素是：％d\n”，e）;
}
void DE_Sq(SqQueue ＆Q)
｛
int ＊w;
w=&Q。data［Q。front］；
Q。front=Q.front+1;
printf（"队首元数%d删除成功\n”，＊w）;
｝
int Length_Sq(SqQueue &Q)
｛
int s；
s=（Q.rear-Q.front+10）;
return s％10;
}
int OutQueue_Sq（SqQueue Q）
｛
SqQueue p；
p=Q；
int i,n；
n=Length_Sq（p)；
for（i=0；i〈n;i++)
{
printf（"％d"，p。data［p.front]）;
p。front++；
｝
return OK；
}
void Delet(SqQueue &Q）
｛
free(Q.data）;
printf("释放成功”）；
｝
void main(）
{
system(”cls")；
printf(”*＊＊*＊＊＊＊＊*＊*＊＊＊＊**＊＊*＊循环队列功能菜单**＊*＊＊＊＊＊*＊＊＊＊＊＊＊＊＊*＊*＊\n”）；
printf（”1。初始化队列输入的数不超过10个, 2。判断队列是否空， 3。判断队列是否满, \n")；
printf（”4.将元素入队， 5.取队列首元素， 6。队列的长度, 7。遍历循环队列，\n”）；
printf（”8。删除队首元素， 9。释放队列, 10。清屏， 0。结束程序，\n"）；
int flag=1,i;
SqQueue Q；
InitQueue_Sq(Q)；
while (flag）
{
printf(”请输入操作符:”)；
scanf（"%d”，＆i）;
switch（i）
｛
case 1:
int n，j，m；
printf(”请输入初始化元素的个数:"）;
scanf("％d”，＆n);
printf（”请输入元素:"）;
for（j=0;j<n；j++)
{
scanf(”％d”,&m)；
EnQueue_Sq（Q,m);
}
break；
case 2：
IfEmpty（Q);
break;
case 3：
IfFull（Q）;
break；
case 4：
int k;
printf(”请输入要进入循环队列的元素:")；
scanf（”％d",&k）；
InQueue_Sq(Q,k）；
break；
case 5：
DeQueue_Sq（Q）；
break;
case 6：
int f;
f=Length_Sq（Q)；
printf（”该循环队列的长度为：%d\n”，f）；
break;
case 7：
printf("该循环队列为："）；
OutQueue_Sq（Q）;
printf(”\n"）;
break;
case 8：
DE_Sq(Q)；
break；
case 9：
Delet(Q）；
break;
case 10：
system（”cls”)；
break;
case 0:
flag=0；
break;
｝
}
printf（”程序结束"）;
｝
4、实验总结
队列是一种先进先出的线性表,它只允许在表的一端进行插入，而在另一端删除元素，在C语言中不能用动态分配的一维数组来实现循环队列,如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用队列的最大长度，则宜采用链队列.
本次实验通过对队列的链式表示与实现、队列的顺序表示与实现，加深了对链队列和循环队列的特点的理解，并且熟悉了VC6。0集成环境，虽然在调试过程中遇到了一些问题，但经分析后达到了预期的结果.