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

1 0 〃最大队列长度
〃初始化动态分配存储空间
//头指针，假设队列不空，只想对列头元
//尾指针，假设队列不空，指向队列尾元素
/ /下一个位置
//构造一个空队列Q
〃销毁队列Q,Q不再存
〃将Q清为空队列
//假设队列Q为空队列，
//返回true,否则返回
〃返回Q得元素个数,
&e)//假设队列不空，则用
&Q)
&Q)
Q)
Status GetHea d (SqQueue Q, QElemType
e返回Q得对
//头元素，并返回OK,否则返回
e)//插入元素e为Q得
&e)//假设队列不空，则
〃元素，用e返回其值,

数据结构实验报告
—---试验三 循环队列得基本操作及应用
一、问题描述：
熟悉并掌握循环队列得相关操作,自己设计程序,实现循环队列
得构造、清空、销毁及队列元素得插入与删除等相关操作、
二、数据结构设计：
#def i n e MAXQS I ZE
st ruct SqQueue
{
o QElemType 大 base;
oInt f ront;
素
oint rear;
得
}；
三、功能设计：
程序中所涉及到得函数如下：
Status In it Que u e(SqQueue &Q)
Status DestroyQueue(SqQueu e
在
Status Cl ea rQue u e(SqQue ue
S ta tus Qu e u e Empt y (SqQueue Q)则
FALSE
i nt Q ue u eL e n gt h(Sq Q u eue
即队列长度
ERROR
S tatus EnQueue(S qQueue &Q,QElemTy p e新得队尾元素
Status DeQu eu e( S qQu eue &Q,QE 1 emType删除Q得队头
并返回
//OK,否则返回ERR
OR
Status Que ueTr a vers e (SqQueue Q,vo i d(* v i)(QElemT yp e))// 从队头到队尾依次
/ /对队列Q中每个元素调用函数
//vi()、一旦 vi 失败，
则操作失败
四、源程序：
// cl。h (程序名)
#include<string、h>
#i n c ludeVc t ype.h〉
#i n c 1 ude〈malloc。h> / / malloc()等
# i nclude〈limits.h〉// INT_M AX 等
# i nclude<s t dio.h〉 // EOF(=人 Z 或 F6),NULL
# inc lud e< s tdli b . h> // at o i()
# i ncl u d e <io、h〉/ / eof()
# inclu d e<m a t h . h> / / floor(), c eil(),abs()
#in cl ude <pr ocess、h> / / exit()
# i n clude<io s tr ea m、h > / / cout, ci n
//函数结果状态代码
# define TRUE 1
#d e f in e FALSE 0
# define OK 1
#define ERROR 0
#def i ne INFEASI BLE -1
//#define OVERFLOW -2 因为在 math.h 中已定义 OVERFLOW 得值为
3,故去掉此
〃行
typ ed e f int St at us; // St a tus就是函数得类型，其值就是函数结果状态代码,如OK等
typedef int Boolean; // Bool e an 就是布尔类型，其值就是 TRUE 或FALSE
// c 3 —3. h
#d e fine MAXQSIZE 1 0
s t ru ct S qQu eue
{
o QElemType * b ase;
in t fron t ;
。int rear;
}；
# in cl ude "c 1、h〞
typ e def i nt QE 1 emTy pe ;
#i n cl u de〞c 3 —3、h"
Status Init Qu e u e(SqQueue &Q)
{//构造一个空队列Q
Q. b a s e = (QE l e mTyp e 大)m a lloc(MAX Q SIZ E* s iz e o f (QE lemTyp
e))；
if(!Q。ba s e)//储存分配失败
。exit(OVERFLOW);
o Q。front=Q、r e ar=0;
re tu rn OK;
}
Status De s troyQueue(SqQ u eu e &Q)
{//销毁队列Q,Q不再存在
。if(Q、base)
。"ree(Q。b a se);
Q、base=NULL;
Q、fr o nt= Q、re a r=0;
r e turn OK;
}
5 tat us C learQueue(SqQue u e &Q)
{//将Q清为空队列
Q、fr o n t=Q、r ea r =0;
6 return OK;
}
S t a tus Queu eE mpty( S qQue u e Q)
(//假设队列Q为空队列,则返回TRE U,否则返回FALS E
i f(Q。f r ont = =Q.r ear )//队列空得标志
o o re t urn TRUE;
else
retu rn FAL S E;
}
int QueueL e ngth(S qQ ueue Q)
{//Q
ueturn(Q、rear—Q、f r ont+MAXQSIZE)%M AXQS IZE;
}
Status G e tHea d(SqQu eue Q,QElem Type &e)
{//
。if(Q、front==Q、rear)// 队列空
o return ERROR;
。e=*(Q、base+Q、fro nt);
ue turn OK;
}
Status E n Queue(SqQueue &Q,QElemType e)
{
。if((Q. rea r+1)%MAXQSIZE==Q、front)//队列满
。 re turn ERROR;
Q°b ase[Q、rear]=e;
Q、r ea r=(Q.rear+1)%MAXQSIZE;
o retu r n OK;
}
Status DeQue ue (S q Qu eue &Q,QE lemType & e )
{
if(Q、front==Q。rear)//队列空
a ue turn ERROR;
e =Q.ba s e [Q.fro n t];
Q。fro n t=(Q.fron t + 1 )%MAXQSIZE;
re turn OK;
}
Sta tu s Queu eT rav e r s e(SqQ u e u e Q,void(大 v i)( Q El e mTy pe ))
{
int i;
。i=Q、fr ont ;
o whi 1 e(i! = Q、r ea r )
{
。。v i (*(Q、b as e +i));
i=(i+1)%MAXQSIZE;
。}
printf(〃\n〃)；
r e tu r n O K;
}
void v isit(QE lem Type i)
{
o cout〈〈〞\t〞<<i;
}
void mai n ()
{
。i nt i= 0 ,a;
QElemType d ;
a S q Qu eue Q;
In i tQu e ue(Q);
。coutVV 〞初始化队列后，队列空否？(1 :空0：否)〞 V<Queue Empty(Q)V< 〞\n 〞；
。coutVV〞请输入整型队列元素,-1为提前结束符:\n〞 ；
d o
° {
o o cin>〉d;
o o o if( d ==-1)
o o o o br eak;
o i++;
o o EnQu e ue(Q,d);
}
while(i 〈MAXQS I ZE-1 );
cout〈〈〞队列长度为："V〈QueueLeng th (Q)V〈"\n〞;
oocout<<〞现在队列空否？(1：空 0:否)"〈VQueueEm p ty(Q)VV"\n";
"or(i=1;i〈=Que ueLeng t h(Q);i + + )
0 6 {
DeQueue(d);
。。。cout〈V〞删除得元素为:〞〈<d〈〈"请输入待插入得元素:"；
oo ci n〉>a;
E nQueue(Q,a);
。}
。cout<〈"现在队列中得元素为:\n〞；
o Queue T raverse(Q,v i sit);
ocout<<〃\n〞;
GetHead(Q, a);
。。cout<V〞现在对头元素为:"〈〈a<〈〞 \ n〞;
Cl e arQue u e();
cou t <<〞清空队列后，对列空否？(1：空0:否)〞〈〈QueueEmpty( Q);
o cout〈< " \n";
De s tr o yQue u e(Q);
}
五、程序调试结果:
SS '-i-\xh\De bug\x h, e^e"

・D：\学习 \C-f -F\Dch\Debug\xh.exe-

・D：\学习，C++\xh\Debug\xhexe・

画学习\C 4- 4-\xh\De bug\x h. e xe"
青输入颦型队列元素,T为捍前结束符=
1 2 3 4 5 6-1
快列长度为花
觑在队列空否？〞：空财否冲
ffi!除的元素为汀请输入待插A的元畚4ffi!除的元素为沌请输入待插A的元素泅ffi!除的元素为：3请输入待插A的元素泅ffi!除的元素为：4请输入待插A的元素沱ffi!除的元素为：5清输乳待插人的元素沱ffil除的元素为新清输火待插人的元素泅
瓯在队列由的元素为:啊，在对头元素为祯
清空队列后-对列空否?⑴空职否＞!
[Fipegs any key to c(int:Lrme
六、试验后得思考:
通过试验,对循环队列得功能有了更深得了解，同时也基本掌握
了循环队列得构造、清空、销毁及队列元素得插入与删除等相关操作,也为以后得学习奠定了一定得基础。