《数据结构基础实验8》由会员分享，可在线阅读，更多相关《数据结构基础实验8（6页珍藏版）》请在金锄头文库上搜索。
1、浙江大学城市学院实验报告课程名称 数据结构基础 实验项目名称 实验八 队列（循环队列）的表示和实现 学生姓名 专业班级 学号 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1、掌握队列的存储结构及基本操作。2、掌握循环队列的设置及循环队列的各种基本操作的实现。3、通过具体的应用实例，进一步熟悉和掌握队列的实际应用。二. 实验内容1、建立头文件test8.h，定义顺序存储的循环队列存储结构，并编写循环队列的各种基本操作实现函数。同时建立一个验证操作实现的主函数文件test8.cpp，编译并调试程序，直到正确运行。 说明：队列的基本操作可包括： void InitQueue (Queue
2、 &Q); /构造一个空队列 Q int EmptyQueue (Queue Q); /判断队列Q是否为空，若空返回1，否则返回0 void EnQueue (Queue &Q, ElemType item); /元素 item 进队列Q ElemType OutQueue (Queue &Q); /队头元素出队列Q，并返回其值 ElemType PeekQueue (Queue Q); /返回队头元素值 void ClearQueue (Queue &Q); /清空队列2、应用（选做部分）：编写程序，实现舞伴问题：假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队，跳舞开始时，依次从男
3、队和女队的队头上各出一人配成舞伴，若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求设计一个函数void partner()，模拟上述舞伴配对问题。基本要求:1) 由键盘输入数据，每对数据包括姓名和性别；2) 输出结果包括配成舞伴的女士和男士的姓名，以及未配对者的队伍名称和队头者的姓名； 3) 要求利用test8.h中已实现的顺序循环队列的基本操作函数来实现。函数void partner() 添加到文件test8.cpp中，在主函数中进行调用测试。 测试数据如下：请输入跳舞者的姓名和性别（以“# #”结束）：aa Fbb Mcc Fdd Mee Fff Mgg Mhh Fii
4、 Mjj M # #配对的舞伴是：aa bbcc ddee ffhh gg男队还有人等待下一轮舞曲。ii 将是下一轮得到舞伴的第一人。3、填写实验报告，实验报告文件取名为report8.doc。4、上传实验报告文件report8.doc 、源程序文件test8.cpp及test8.h到Ftp服务器上（ ftp:/10.61.14.240:5000 ）自己的文件夹下。三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路）1、void InitQueue (Queue &Q) /构造一个空队列 Q Q.MaxSize=10;Q.queue=new ElemType
5、Q.MaxSize;Q.front=Q.rear=0;2、int EmptyQueue (Queue Q)/判断队列Q是否为空，若空返回1，否则返回0return Q.front =Q.rear ;3、void EnQueue (Queue &Q, ElemType item) /元素 item 进队列Q if(Q.rear +1)%Q.MaxSize =Q.front )int k=sizeof(ElemType);Q.queue =(ElemType*)realloc(Q.queue ,2*Q.MaxSize *k);if(Q.rear !=Q.MaxSize -1)for(int i=0
6、;i=Q.rear ;i+)Q.queue i+Q.MaxSize =Q.queue i;Q.rear +=Q.MaxSize ;Q.MaxSize =2*Q.MaxSize ;Q.rear =(Q.rear +1)%Q.MaxSize ;Q.queue Q.rear =item;4、ElemType OutQueue (Queue &Q) /队头元素出队列Q，并返回其值 if(Q.front =Q.rear )cerr列队已空，无法删除！endl;exit(1);Q.front =(Q.front +1)%Q.MaxSize ;return Q.queue Q.front ; 5、ElemT
7、ype PeekQueue (Queue Q) /返回队头元素值if(Q.front =Q.rear )cerr列队已空，无法读取！endl;exit(1);return Q.queue (Q.front +1)%Q.MaxSize ; 6、void ClearQueue (Queue &Q) /清空队列if(Q.queue !=NULL) delete Q.queue ;Q.front =Q.rear =0;Q.queue =NULL;Q.MaxSize =0;四. 实验结果与分析（包括运行结果截图、结果分析等）1、五. 心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意
8、见和建议等。）【附录-源程序】Test8.htypedef struct QueueElemType *queue;int front,rear,len;int MaxSize;void InitQueue (Queue &Q) /构造一个空队列 Q Q.MaxSize=10;Q.queue=new ElemTypeQ.MaxSize;Q.front=Q.rear=0;int EmptyQueue (Queue Q)/判断队列Q是否为空，若空返回1，否则返回0return Q.front =Q.rear ;void EnQueue (Queue &Q, ElemType item) /元素 i
9、tem 进队列Q if(Q.rear +1)%Q.MaxSize =Q.front )int k=sizeof(ElemType);Q.queue =(ElemType*)realloc(Q.queue ,2*Q.MaxSize *k);if(Q.rear !=Q.MaxSize -1)for(int i=0;i=Q.rear ;i+)Q.queue i+Q.MaxSize =Q.queue i;Q.rear +=Q.MaxSize ;Q.MaxSize =2*Q.MaxSize ;Q.rear =(Q.rear +1)%Q.MaxSize ;Q.queue Q.rear =item;Elem
10、Type OutQueue (Queue &Q) /队头元素出队列Q，并返回其值 if(Q.front =Q.rear )cerr列队已空，无法删除！endl;exit(1);Q.front =(Q.front +1)%Q.MaxSize ;return Q.queue Q.front ; ElemType PeekQueue (Queue Q) /返回队头元素值if(Q.front =Q.rear )cerr列队已空，无法读取！endl;exit(1);return Q.queue (Q.front +1)%Q.MaxSize ; void ClearQueue (Queue &Q) /清空
11、队列if(Q.queue !=NULL) delete Q.queue ;Q.front =Q.rear =0;Q.queue =NULL;Q.MaxSize =0;Test8.cpp#include#includetypedef int ElemType;#includetest8.hvoid main()Queue q; InitQueue (q);int a10=0,1,2,3,4,5,6,7,8,9;int i;for(i=0;i10;i+) EnQueue (q, ai);coutOutQueue (q) ;coutOutQueue (q) ;coutOutQueue (q)endl;EnQueue (q, 68);for(i=0;i9;i+=2) EnQueue (q, ai);coutPeekQueue (q) ;coutOutQueue (q)endl;while(!EmptyQueue (q) coutOutQueue (q) ;coutendl;ClearQueue (q);
