队列的基本操作及其应用.docx
《队列的基本操作及其应用.docx》由会员分享，可在线阅读，更多相关《队列的基本操作及其应用.docx（26页珍藏版）》请在冰点文库上搜索。
队列的基本操作及其应用
广西工学院计算机学院
《数据结构》课程实验报告书
实验四队列的基本操作及其应用
学生姓名：
李四
学号：
2012
班级：
计Y124
指导老师：
王日凤
专业：
计算机学院软件学院
提交日期：
2013年6月20日
1．实验目的
1）通过对队列特点的分析，掌握队列的存储结构及其基本操作，学会定义队列的顺序存储结构和链式存储结构，在实际问题中灵活运用。
2）掌握队列先进先出的特点，掌握队列的基本操作，如出队列、入队列、判队列空、判队列满等，熟悉各种操作的实现方法。
3）通过具体的应用实例，进一步熟悉和掌握队列的实际应用。
2.实验内容
（1）建立一个含n个数据的队列，实现队列的基本操作。
包括：
▪//1.初始化,构造一个空队列
voidinitQueue（Queue&Q）
▪//2.判断队列空,空则返回true
boolQueueEmpty（seqQueue&Q）
▪//3.判断队列满,满则返回true
boolQueueFull（seqQueue&Q）
▪//4.取队头元素,用x返回队头元素，返回true；空队列则返回false
BoolQueueHead（seqQueue&Q,elementType&x）
▪//5.入队列，在队尾插入新元素x（流程图）
boolpushQueue（seqQueue&Q,elementTypex）
▪//6.出队列，用x带回队头元素，并在队头删除，返回true，队列空则返回false（流程图）
boolpopQueue（seqQueue&Q,elementType&x）
▪//7.输出队列,从队头到队尾依次输出
voidprintQueue（seqQueueQ）
（2）队列应用：
利用队列操作打印杨辉三角形的前n行（如n=7）。
3．实验要求
（1）上机前交实验源程序（纸质版），由学习委员统一收好交老师（附上不交同学名单）。
（2）用一切你能想到的办法解决遇到的问题，培养解决问题的能力。
（3）实验课上进行答辩。
（4）实验报告当场交。
报告内容包括：
实验目的、实验内容、实验代码、实验输入输出结果以及实验体会供五部分。
3．主要算法
3.1顺序存储结构
（1）结构定义：
#include
#include
#include
#include//各个头文件
#defineOK1
#defineERROR0
#defineOVERFLOW-2//定义宏参
#defineMAXQSIZE100//最大队列长度
typedefintQElemType;//引用整型数据类型别名
//顺序表的储存结构
typedefstruct
{
QElemType*base;//初始化的动态分配内存空间
intfront;//头指针
intrear;//尾指针
}SqQueue;
intN;
//======================函数声明=========================//
intInitQueue（SqQueue&Q）;//初始化
voidcreatQueue（SqQueue&Q,intn）;//创建
intQueueLength（SqQueue&Q）;//求长度
voidEnQueue（SqQueue&Q,QElemTypee）;//入队
intDeQueue（SqQueue&Q）;//出队
intQueueTraverse（SqQueue&Q）;//显示队列
intGetHead（SqQueueQ）;//取头元素
intDestroyQueue（SqQueue&Q）;//销毁顺序表
intClearQueue（SqQueue&Q）;//清空顺序表
intyanghui（intn）;//杨辉三角
intElemptyQueue（SqQueue&Q）;//判空
//======================函数声明=========================//
//构造空队列
intInitQueue（SqQueue&Q）
{//操作结果：
构造一个空队列Q
printf（"输入分配空间大小:
"）;
scanf（"%d",&N）;
Q.base=（QElemType*）malloc（N*sizeof（QElemType））;//动态分配内存空间，以下同样
if（!
Q.base||N<0||N>MAXQSIZE）
{//若n值不合理，则返回ERROR，以下同样
printf（"构造失败!
"）;
printf（"\n\t\t按任意键返回主菜单!
"）;
getch（）;
returnERROR;
}
Q.front=Q.rear=0;//队列设置为空，以下同样
printf（"构造成功!
"）;
printf（"\n\t\t按任意键返回主菜单!
"）;
getch（）;
returnOK;
}
//初始化队列
intInitQue（SqQueue&Q,intn）
{//操作结果:
初始化一个空队列
Q.base=（QElemType*）malloc（n*sizeof（QElemType））;
if（!
Q.base||n<0||n>MAXQSIZE）
returnERROR;
Q.front=Q.rear=0;
returnOK;
}
//创建队列
voidcreatQueue（SqQueue&Q,intn）
{//初始条件：
Q已经存在
//操作结果：
向队列输入n个元素
intm;
if（!
Q.base||n<0||n>N）
{
printf（"初始化未完成或超出队列长度，无法创建!
"）;
printf（"\n\t\t按任意键返回主菜单!
"）;
getch（）;
return;
}
printf（"请输入入队元素!
\n"）;
for（inti=0;i{
printf（"请输入第%d个数据：
",i+1）;
scanf（"%d",&m）;
Q.rear=i;
Q.base[Q.rear]=m;
}
Q.rear=（Q.rear+1）%N;//尾指针后移一位
printf（"创建成功!
\n"）;
QueueTraverse（Q）;//调用显示函数
printf（"\n\t\t按任意键返回主菜单!
"）;
getch（）;
return;
}
//求队列的长度
intQueueLength（SqQueue&Q）
{//初始条件：
Q已经存在
//操作结果：
返回队列的长度
QueueTraverse（Q）;//调用显示函数
printf（"\nTheQueuelengthis:
%d",（Q.rear-Q.front+N）%N）;//打印表长
printf（"\n\n"）;
printf（"\n\t\t按任意键返回主菜单!
"）;
getch（）;
returnOK;
}
//入队列
voidEnQueue（SqQueue&Q,QElemTypee）
{//初始条件：
Q已经存在
//操作结果：
插入元素e为Q的新的队尾元素
if（（Q.rear+1）%N==Q.front）//队列为满的情况
{
printf（"队列已满,无法插入!
"）;
printf（"\n\t\t按任意键返回主菜单!
"）;
getch（）;
return;
}
Q.base[Q.rear]=e;
Q.rear=（Q.rear+1）%N;//尾指针后移一位
printf（"入队成功!
\n"）;
QueueTraverse（Q）;//调用显示函数
printf（"\n\t\t按任意键返回主菜单!
"）;
getch（）;
return;
}
//入队列
voidEnQueu（SqQueue&Q,QElemTypee）
{//初始条件：
Q已经存在
//操作结果：
插入元素e为Q的新的队尾元素
if（（Q.rear+1）%MAXQSIZE==Q.front）
return;
Q.base[Q.rear]=e;
Q.rear=（Q.rear+1）%MAXQSIZE;
}
//出队列
intDeQueue（SqQueue&Q）
{//初始条件：
Q已经存在
//操作结果：
若队列不空，删除Q的队头元素，
//用e返回其值，并返回，否则返回
inte;
if（Q.front==Q.rear）//队列为空的情况
{
printf（"队列为空，无法出队!
"）;
printf（"\n\t\t按任意键返回主菜单!
"）;
getch（）;
returnERROR;
}
e=Q.base[Q.front];
Q.front=（Q.front+1）%N;//头指针后移一位
printf（"队头元素出队成功!
\n"）;
printf（"这队头元素是：
%d",e）;
printf（"\n\t\t按任意键返回主菜单!
"）;
getch（）;
returnOK;
}
//出队列
intDeQueu（SqQueue&Q）
{//初始条件：
Q已经存在
//操作结果：
若队列不空，删除Q的队头元素，
//用e返回其值，并返回，否则返回
inte;
if（Q.front==Q.rear）//队列为空的情况
returnERROR;
e=Q.base[Q.front];//将头元素赋给e
Q.front=（Q.front+1）%MAXQSIZE;//头指针后移一位
returne;
}
//显示
intQueueTraverse（SqQueue&Q）
{//初始条件：
Q已经存在
//操作结果：
把队列中的元素输出到显示屏
inti;
i=Q.front;
if（Q.front==Q.rear）//队列为空的情况
{
printf（"TheQueueisEmpty!
"）;
printf（"\n\t\t按任意键返回主菜单!
"）;
getch（）;
returnERROR;
}
else
{
printf（"TheQueueis:
"）;
while（i!
=Q.rear）//当队列不为空时
{
printf（"%3d",Q.base[i]）;
i=（i+1）%N;
}
}
printf（"\n"）;
printf（"显示成功!
"）;
returnOK;
}
//取队头元素
intGetHead（SqQueueQ）
{//初始条件：
Q已经存在
//操作结果：
若队列不空，返回其值，否则返回
inte;
if（Q.front==Q.rear）//队列为空的情况
{
printf（"TheQueueisEmpty!
"）;
printf（"\n\t\t按任意键返回主菜单!
"）;
getch（）;
returnERROR;
}
e=*（Q.base+Q.front）;//将头元素赋给e
returne;
}
//判断顺序表是否为空
intElemptyQueue（SqQueue&Q）
{//初始条件：
Q已经存在
//操作结果：
若队列为空返回，否则返回
if（Q.front==Q.rear）//队列为空的情况
returnOK;
else
returnERROR;
}
//销毁链表
intDestroyQueue（SqQueue&Q）
{//初始条件:
顺序表已存在
//操作结果:
销毁顺序表
Q.front=Q.rear=0;
returnOK;
}
//清空队列
intClearQueue（SqQueue&Q）
{//初始条件:
顺序表已存在
//操作结果:
清空顺序表
Q.front=Q.rear=0;
returnOK;
}
//杨辉三角
intyanghui（intn）
{//打印输出杨辉三角的前n（n>0）行
if（n<0||n>MAXQSIZE）
{
printf（"行数不合理，无法显示!
"）;
printf（"\n\t\t按任意键返回主菜单!
"）;
getch（）;
returnERROR;
}
SqQueueQ;//定义新的循环队列
intk,e,p;
for（inti=1;i<=n;i++）
printf（""）;
printf（"1\n"）;//在中心位置输出杨辉三角最顶端的"1"
InitQue（Q,n+2）;//设置最大容量为n+2的空队列
EnQueu（Q,0）;//添加行界值
EnQueu（Q,1）;
EnQueu（Q,1）;//第一行的值入队列
k=1;
while（k{//通过循环队列输出前n-1行的值
for（inti=1;i<=n-k;i++）
printf（""）;//输出n-k个空格以保持三角型
EnQueu（Q,0）;//行界值"0"入队列
do//输出第k行，计算第k+1行
{
p=DeQueu（Q）;
e=GetHead（Q）;
if（e）
printf（"%d",e）;//若e为非行界值，则打印输出e
else
printf（"\n"）;//否则回车换行，为下一行输出做准备
EnQueu（Q,p+e）;
}while（e!
=0）;
k++;
}
e=DeQueu（Q）;//行界值"0"出队列
while（!
ElemptyQueue（Q））
{//单独处理第n行的值的输出
e=DeQueu（Q）;
printf（"%d",e）;
}
printf（"\n\t\t显示成功!
"）;
printf（"\n\t\t按任意键返回主菜单!
"）;
getch（）;
returnOK;
}
//主函数
voidmain（）
{
SqQueueQ;//定义队列变量
intb,c,f;//定义整型数据变量
intj,k;//设置选项变量
while
（1）
{
system（"cls"）;//清屏
printf（"\n\t***************************************************"）;
printf（"\n\t*队列的基本操作及其应用*"）;
printf（"\n\t***************************************************\n"）;
printf（"\t*1.初始化队列2.创建队列*\n"）;
printf（"\t*3.队列长度4.入队队列*\n"）;
printf（"\t*5.取头元素6.显示队列*\n"）;
printf（"\t*7.杨辉三角8.销毁队列*\n"）;
printf（"\t*9.清空队列0.退出*\n"）;
printf（"\t****************************************************\n"）;
printf（"请选择选项<1-9>:
"）;//打印选项功能提示
scanf（"%d",&k）;
if（k<0||k>9）
{
printf（"输入有误，请重新输入!
"）;
printf（"\n"）;
printf（"\n\t\t\t按任意键进行重新操作!
"）;
getch（）;
continue;
}
switch（k）//分支结构来调用各功能子函数
{
case1:
printf（"创建空的循环队列\n"）;
InitQueue（Q）;//调用初始化函数
printf（"\n"）;
break;//退出并重新进入主菜单
case2:
printf（"创建新的循环队列\n"）;
printf（"输入长度:
"）;
scanf（"%d",&f）;
creatQueue（Q,f）;//调用创建函数
break;
case3:
printf（"求表长!
\n"）;
QueueLength（Q）;//调用求表长函数
break;
case4:
printf（"入队!
\n"）;
printf（"输入入队元素:
"）;
scanf（"%d",&b）;
EnQueue（Q,b）;//调用入队函数
QueueTraverse（Q）;//调用显示函数
break;
case5:
printf（"出队!
\n"）;
DeQueue（Q）;//调用出队函数
break;
case6:
printf（"显示顺序表!
\n"）;
QueueTraverse（Q）;//调用显示函数
getch（）;
break;
case7:
system（"cls"）;//清屏
printf（"杨辉三角!
\n"）;
printf（"输入其行数:
"）;
scanf（"%d",&c）;//输入行数+1
printf（"杨辉三角显示为:
\n"）;
yanghui（c-1）;//调用杨辉三角函数
break;
case8:
printf（"你真确定要销毁队列!
1.YES2.NO\n"）;
printf（"请选择项<1-2>:
"）;
scanf（"%d",&j）;
if（j==1）
DestroyQueue（Q）;
printf（"队列销毁成功呦!
\n"）;
if（j==2）
printf（"\n"）;
printf（"\n\t\t\t按任意键进行重新操作!
"）;
getch（）;
break;
case9:
printf（"你真确定要清空队列!
1.YES2.NO\n"）;
printf（"请选择项<1-2>:
"）;
scanf（"%d",&j）;
if（j==1）
{
ClearQueue（Q）;
printf（"队列清空成功呦!
\n"）;
}
else
printf（"\n"）;
printf（"\n\t\t\t按任意键进行重新操作!
"）;
getch（）;
break;
case0:
printf（"你真确定要退出!
1.YES2.NO\n"）;
printf（"请选择项<1-2>:
"）;
scanf（"%d",&j）;
if（j==1）
{
printf（"\n\t\t\t再见，欢迎再次使用!
\n\n\t\t\t"）;
exit（OVERFLOW）;
}
else
printf（"\n"）;
printf（"\n\t\t\t按任意键进行重新操作!
"）;
getch（）;
break;
}
}
}
3.流程图如下
1.队尾插入元素
Q.front->
Q.rear->
1.队尾插入元素
If语句
队还不满，在队尾插入e，返回1.
队已满，返回0
返回主菜单
结束
2.删除队头元素
4．程序运行结果
（1）实验内容
（1）
运行结果如下：
运行结果如下：
运行结果如下：
5.心得体会。
WelcomeTo
Download!
!
!
欢迎您的下载，资料仅供参考！
升级会员 