试验 --循环队列的基本操作及应用.doc

数据结构实验报告
－---试验三　循环队列得基本操作及应用
一、 问题描述:
熟悉并掌握循环队列得相关操作,自己设计程序,实现循环队列得构造、清空、销毁及队列元素得插入与删除等相关操作、
二、 数据结构设计:
　 　 ＃ｄｅfｉnｅ ＭAＸQSＩZE １0 　 //最大队列长度
　 ｓｔruct SqQueue
｛
ﻩ QＥlemＴyｐｅ 　＊base; //初始化动态分配存储空间
ﻩ 　 Int ｆront; 　　 　　　 //　头指针,若队列不空,只想对列头元素
ﻩ 　 　 int　 rear;　　　 /／尾指针,若队列不空,指向队列尾元素得
　 　 　 　 　 　 ／/下一个位置
　 　};
三、功能设计:
　 程序中所涉及到得函数如下:
　 　Status InｉｔQueｕe(SqQueue &Ｑ) 　 　 　 ／/构造一个空队列Q
Ｓtａｔｕs DestroyQueue(SqQueuｅ　＆Q) 　 //销毁队列Q,Q不再存在
　 　 Statｕs　ClｅａrQueｕe(SqQｕｅue　＆Q) 　 //将Q清为空队列
　 Sｔａtus QuｅuｅEmptｙ(SqQueue Q) 　 ／/若队列Q为空队列,则
　 　 　 　 　 　 　 //返回TRUE,否则返回FALSE
　 ｉnt ＱueｕeLｅnｇｔh(SqＱｕeue　Q) //返回Ｑ得元素个数,即队列长度
Status　GetHeaｄ(SｑＱｕeｕe Ｑ,ＱElemTｙpe　&ｅ)/／若队列不空,则用e返回Q得对 　　 　　 　 　　 　 　　 　 　 　 　 　　 　 　　 　　 　 　 　 　 　 　 　 　 　 　 　 　 　　 　 　 　 　 　 　 　 　 　 　 　 　　 　 　 　　 　
　 　 　 　　 /／头元素,并返回OK,否则返回ＥRRＯR
Ｓtatus EｎＱuｅｕe(ＳqQueue ＆Q,QEleｍＴｙpｅ　e)//插入元素e为Q得新得队尾元素
Stａtｕｓ DeQuｅｕe(ＳqQｕeue　&Q,QEｌemType　&e)//若队列不空,则删除Q得队头
　 　 　　 　 　 　 　　 　 //元素,用e返回其值,并返回
　 　　 　 　　 　 　 　 /／OＫ,否则返回ＥRRＯR
Sｔａtｕs QｕｅueTrａversｅ(SqQueue Q,voｉd(*ｖi)(QElemTｙｐe))//从队头到队尾依次　
　 　　 　 　 　 　　 　 /／对队列Q中每个元素调用函数
　 　 　　 　 　 　 　／/ｖi()、一旦vi失败,则操作失败
四、源程序:
// c1。h　(程序名)
＃iｎclｕde<string、ｈ>
＃ｉnｃlude＜cｔype.h＞
#iｎcｌude〈malloｃ。h> /／ malloc()等
　#ｉnclude〈limits.h＞　// INT_MＡX等
#ｉncluｄｅ<sｔdiｏ.h〉 /／ EOF(=＾Z或F6),NＵＬL
＃incｌｕｄe<ｓtdliｂ.ｈ＞　//　atｏi()
#ｉnclｕdｅ<io、ｈ〉　/／ eof()
＃incluｄe<mａtｈ.ｈ＞　/／ floor(),ｃeil(),abs()
　#inｃｌude〈ｐｒocess、h>　/／ exit()
＃iｎclude<ioｓtrｅａm、ｈ>　／/ cout,ｃｉn
　// 函数结果状态代码
＃define TRUE １
#dｅfｉｎe FALSE 0
＃defiｎe OK 1
#define　EＲROR 0
　#dｅfｉne IＮＦＥAＳＩBLE —1
／/ ＃ｄeｆinｅ OVＥRＦLOW -2　因为在ｍath.h中已定义OVERＦLOW得值为3,故去掉此
//行
typｅｄeｆ int Stａｔus; // Stａtus就是函数得类型,其值就是函数结果状态代码,如OＫ等
　typedef int　Bｏoｌeａn; // Boolｅan就是布尔类型,其值就是TRＵＥ或ＦALSE
// c３—3.ｈ
#dｅfine MＡXＱＳIＺE 1０
ｓtｒｕct ＳqQｕeue
{
ﻩQＥlemTypｅ *ｂase;
inｔ　fronｔ;
ﻩinｔ　ｒｅaｒ;
｝;
＃inｃｌude＂ｃ1、h”
typｅdef ｉnt QEｌemTyｐｅ;
#iｎclｕde”c３—3、h"
Status　InitＱｕeｕe(SqQueue &Q)
{ ／/构造一个空队列Q
Q.ｂaｓe＝(QＥlｅmTypｅ ＊)mａlloc(MAXＱSIZＥ＊ｓizｅoｆ(QＥlemTypｅ));
if(!Q。baｓe)//储存分配失败
ﻩｅｘit(OVＥRFＬOW);
ﻩＱ。front=Q、rｅar＝0;
reｔｕrｎ OK;
｝
Status DeｓtroyQueue(SqQｕeuｅ &Q)
{//销毁队列Q,Ｑ不再存在
ﻩif(Q、bａｓe)
ﻩﻩfree(Q。bａse);
Q、ｂase=NＵLL;
Q、frｏnt=Ｑ、reａr=0;
rｅturｎ　OK;
｝
Sｔａｔus ＣlearQueue(SqQueｕe &Q)
｛／／将Q清为空队列
Q、ｆｒoｎt=Q、ｒeaｒ=0;
ﻩｒeｔｕｒｎ OK;
}
Ｓtａtus QueuｅＥmpty(ＳqQueｕe Q)
｛/／若队列Q为空队列,则返回ＴRＥU,否则返回FALSＥ
ｉf(Q。fｒont＝=Ｑ.rｅａｒ)//队列空得标志
ﻩﻩreｔurn TRUE;
eｌsｅ
retuｒｎ FALＳE;
}
int QueueLｅngth(SｑＱueue Q)
{／／Q
ﻩreturn(Q、rear—Ｑ、fｒont＋ＭAXQSIZE)％MＡXＱＳIZE;
｝
Status GｅtＨｅａd(SqQｕeue Q,QElemＴype　＆e)
｛//
ﻩif(Q、froｎt＝=Q、ｒeａr)//队列空
ﻩreturｎ ＥRＲOR;
ﻩｅ=*(Ｑ、base+Q、fｒｏnt);
ﻩrｅturn　OＫ;
｝
Sｔaｔｕs EｎQueue(SqQueue ＆Ｑ,QＥleｍＴｙpｅ e)
｛
ﻩif((Q.ｒｅａr+1)％MAXQSIZE==Q、front)//队列满
ﻩ ｒｅturn　ERROR;
Q。ｂase[Q、rear]=e;
Ｑ、rｅａr＝(Ｑ.rear+1)％ＭＡXＱSIZE;
ﻩretuｒn OＫ;
｝
Status DeQueｕｅ(SｑQｕeue ＆Q,QＥleｍType &ｅ)
｛
iｆ(Ｑ、fｒont==Q。rear)//队列空
ﻩﻩrｅturn ERROR;
ｅ=Q.baｓe［Q.froｎt］;
Q。froｎt=(Q.fronｔ+１)％ＭAＸＱSIZE;
ｒｅturｎ OK;
｝
Staｔｕs QueuｅＴravｅrｓe(SqQｕeｕe Q,void(＊ｖi)(ＱElｅmTyｐｅ))
{
int i;
ﻩi=Q、frｏｎｔ;
ﻩwhiｌe(i!＝Q、ｒeaｒ)
{
ﻩﻩvｉ(＊(Q、ｂasｅ+i));
i=(i+1)%ＭＡXQSIＺE;
ﻩ｝
printf(”\ｎ”);
rｅtuｒn ＯK;
}
void ｖisit(QＥlemＴｙpｅ i)
｛
ﻩcout〈〈”＼t”<<i;
｝
void maiｎ()
{
ﻩｉnt　i=０,a;
　　 QElemType ｄ;
ﻩSｑQｕeue Q;
InｉtQuｅue(Q);
ﻩcout＜＜”初始化队列后,队列空否？(1:空 ０:否)”＜<QuｅuｅＥmpty(Ｑ)＜<＂＼n＂;
ﻩ cout＜＜”请输入整型队列元素,-1为提前结束符:\n”;
dｏ
ﻩ｛
ﻩﻩ cin>〉d;
ﻩﻩﻩif(ｄ==-1)
ﻩﻩﻩﻩ ｂｒeak;
ﻩ i++;
ﻩ ﻩEnQuｅue(Q,d);
｝
while(i〈MAＸＱSＩZE-１);
cｏｕｔ〈〈”队列长度为:＂＜〈QueueLengｔｈ(Ｑ)＜〈"\n";
ﻩﻩcout<<”现在队列空否?(1:空 0:否)＂〈＜QueueEmｐty(Q)＜＜＂\ｎ＂;
ﻩfor(i=1;i〈=QueｕｅＬengｔh(Q);i＋＋)
ﻩﻩ｛
DeQueue(d);
ﻩﻩﻩcout〈＜”删除得元素为:”〈<ｄ〈〈"请输入待插入得元素:";
ﻩﻩ cｉn＞>a;
ＥnQueue(Q,a);
ﻩ｝
ﻩcｏut<〈"现在队列中得元素为:\ｎ＂;
ﻩQueueＴraverse(Q,vｉｓiｔ);
ﻩ cout<<”\n";
　 GetＨｅａd(Q,ａ);
ﻩ ﻩcout<＜＂现在对头元素为:"〈〈a<〈”\ｎ";
　 　　 　　ClｅarQueｕe();
　　　　　 　couｔ<<＂清空队列后,对列空否？(1:空 0:否)”〈〈ＱueueEmpty(Ｑ);
ﻩ cout〈<＂\n";
　 　 　 　 ＤeｓtrｏyQueｕe(Q);
｝
五、程序调试结果:

六、试验后得思考:
　 通过试验,对循环队列得功能有了更深得了解,同时也基本掌握了循环队列得构造、清空、销毁及队列元素得插入与删除等相关操作,也为以后得学习奠定了一定得基础。