实验八-队列(循环队列)表示及实现-舞伴问题.doc

浙江大学城市学院实验报告
课程名称 数据结构基础
实验项目名称 实验八 队列（循环队列）的表示和实现
学生姓名 *** 专业班级 信管1104 学号 3110****
实验成绩 指导老师（签名 ） 日期

一. 实验目的和要求
1、掌握队列的存储结构及基本操作。
2、掌握循环队列的设置及循环队列的各种基本操作的实现。
3、通过具体的应用实例，进一步熟悉和掌握队列的实际应用。

二. 实验内容
1、建立头文件SeqQueue.h，定义顺序存储的循环队列存储结构，并编写循环队列的各种基本操作实现函数。同时建立一个验证操作实现的主函数文件test3_2.cpp，编译并调试程序，直到正确运行。
2、选做：编写程序，实现舞伴问题。假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队，跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴，若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。要求设计一个函数void partner()，模拟上述舞伴配对问题。
基本要求:
1) 由键盘输入数据，每对数据包括姓名和性别；
2) 输出结果包括配成舞伴的女士和男士的姓名，以及未配对者的队伍名称和队头者的姓名；
3) 要求利用SeqQueue.h中已实现的顺序循环队列的基本操作函数来实现。函数void partner() 添加到文件test3_2.cpp中，在主函数中进行调用测试。
3、填写实验报告，实验报告文件取名为report8.doc。
4、上传实验报告文件report8.doc 、源程序文件test3_2.cpp及SeqQueue.h到Ftp服务器上自己的文件夹下。

三. 函数的功能说明及算法思路
（包括每个函数的功能说明，及一些重要函数的算法实现思路）
1）InitQueue(Queue &q)
实现初始化队列的功能
2）EnQueue(Queue &q,ElemType item)
向队列插入元素item
3）OutQueue(Queue &q)
队列头位元素出列，并返回该值
4）PeekQueue(Queue &q)
返回队头元素值
5）EmptyQueue(Queue &q)
判断队列Q是否为空，若空返回1，否则返回0
6）ClearQueue(Queue &q)
清空队列
7）partner()
实现舞伴的配对操作。定义Dancer结构，包含name与sex来储存舞者的名字与性别。操作过程中通过调用上面6个函数实现，由于上述6个函数中的变量均为int类型，因此在输出时，通过（char）将强制转换为char类型。
四. 实验结果与分析
（包括运行结果截图、结果分析等）

基本操作

输入

成功实现配对
五. 心得体会
在做选做题“舞伴问题”时，引用头文件中的各项函数过程中，由于头文件中的函数中的变量都是int类型，使得输出时，配对的舞伴名字都为ASCII码，无法正确输出名字。在反复调整函数后，我发现，在舞伴问题的输出操作时，直接使用强制转换类型来实现最为方便，同时不影响原函数的操作。

【附录----源程序】
源文件
#include<iostream.h>
#include<stdlib.h>
typedef int ElemType;
#include<stdio.h>
struct Queue{
ElemType *queue;
int front,rear,len;
int MaxSize;
};
#include"SeqQueue.h"

void partner()
{
struct Dancer{
char name;
char sex;
};
Queue F, M;
Dancer D;
InitQueue(F);
InitQueue(M);
cout<<endl<<"请输入跳舞者的姓名和性别（以“# #”结束）："<<endl;
cin>>D.name>>D.sex;
while(D.name!='#'&&D.sex!='#')
{
if(D.sex=='F')
EnQueue(F,D.name);
if(D.sex=='M')
EnQueue(M,D.name);
cin>>D.name>>D.sex;
}
cout<<"配对的舞伴是:"<<endl;
while(EmptyQueue(M)!=1)
{
if(EmptyQueue(F)==1)
{
cout<<(char)OutQueue(M)<<"将是下一轮得到舞伴的第一人"<<endl;
break;
}
else
{
cout<<(char)OutQueue(F)<<' '<<(char)OutQueue(M)<<endl;
}
}
if(EmptyQueue(F)!=1)
{
while(EmptyQueue(F)!=1)
{
cout<<(char)OutQueue(F)<<"将是下一轮得到舞伴的第一人"<<endl;
break;
}
}
}

void main()
{
Queue q;
InitQueue(q);
int a[9]={3,8,5,17,9,30,15,22,20};
int i;
for(i=0;i<9;i++)
EnQueue(q,a[i]);
cout<<OutQueue(q)<<" ";
cout<<OutQueue(q)<<" ";
cout<<OutQueue(q)<<endl;
EnQueue(q,68);
for(i=0;i<9;i+=2)
EnQueue(q,a[i]);
cout<<PeekQueue(q)<<" ";
cout<<OutQueue(q)<<endl;
while(!EmptyQueue(q))
cout<<OutQueue(q)<<' ';
cout<<endl;
ClearQueue(q);
partner();
}
头文件
void InitQueue(Queue &q)
{
q.MaxSize=50;
q.queue=new ElemType[q.MaxSize];
q.front=q.rear=0;
}

void EnQueue(Queue &q,ElemType item)
{
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;
}

ElemType OutQueue(Queue &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];
}

bool EmptyQueue(Queue &q)
{
return q.front==q.rear;
}

void ClearQueue(Queue &q)
{
if(q.queue!=NULL)
delete []q.queue;
q.front=q.rear=0;
q.queue=NULL;
q.MaxSize=0;
}