数据结构实验报告--4.docx

长春理工大学数据结构与算法实验报告实验题目：实验时间：实验地点：班 级：学 号：姓 名：实验目的及要求1、掌握队列的类型定义方法。2、理解和掌握循环队列解决假溢出的方法。实验意义及原理1、利用循环队列模拟舞伴配对问题：在舞会上，男、女各自排成一队。舞会开始时。依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不等，则较长的那一队中未配对者等待下一轮舞曲。 2、假设初始男、女人数及性别已经固定，舞会的轮数从键盘输入。试模拟解决上述舞伴配对问题。 3、要求：从屏幕输出每一轮舞伴配对名单，如果在该轮有未配对的，能够从屏幕显示下一轮第一个出场的未配对者的姓名。算法分析（1）构造队列void Creat(LinkQueuep,LinkQueueq,Node s[]){p.base=new Node[n];q.base=new Node[n];if(!p.base!q.base){cout操作失败endl;exit(1);}p.Front=p.Rear=0;q.Front=q.Rear=0;for(int i=0;in;i++){if(s[i].Sex==0){p.base[p.Rear].Name=s[i].Name;p.base[p.Rear].Sex=s[i].Sex;p.Rear++;}else{q.base[q.Rear].Name=s[i].Name;q.base[q.Rear].Sex=s[i].Sex;q.Rear++;}}}（2）配对跳舞方法LinkQueue*Dance(LinkQueuep,LinkQueueq){while(p.Front!=p.Rearq.Front!=q.Rear){coutp.base[p.Front].Name和q.base[q.Front].Name会一起跳舞endl;p.Front++;q.Front++;}if(p.Front!=p.Rear)return p;else if(q.Front!=q.Rear)return q;elsereturn NULL;}源代码#includeiostream#includestringusing namespace std;static int n=0;struct Node{string Name;int Sex;};typedef struct{Node*base;int Front;int Rear;}LinkQueue;//构造队列void Creat(LinkQueuep,LinkQueueq,Node s[]){p.base=new Node[n];q.base=new Node[n];if(!p.base!q.base){cout操作失败endl;exit(1);}p.Front=p.Rear=0;q.Front=q.Rear=0;for(int i=0;in;i++){if(s[i].Sex==0){p.base[p.Rear].Name=s[i].Name;p.base[p.Rear].Sex=s[i].Sex;p.Rear++;}else{q.base[q.Rear].Name=s[i].Name;q.base[q.Rear].Sex=s[i].Sex;q.Rear++;}}}LinkQueue*Dance(LinkQueuep,LinkQueueq){while(p.Front!=p.Rearq.Front!=q.Rear){coutp.base[p.Front].Name和q.base[q.Front].Name会一起跳舞endl;p.Front++;q.Front++;}if(p.Front!=p.Rear)return p;else if(q.Front!=q.Rear)return q;elsereturn NULL;}int main(){Node s[100];cout输入性别：0表示男生，1表示女生endl;cout输入男女生总人数：n=;cinn;for(int i=0;in;i++){coutNoi+1的名字;cins[i].Name;coutNoi+1的性别;cins[i].Sex;}LinkQueue p,q;Creat(p,q,s);LinkQueue*t=Dance(p,q);if(t!=NULL)cout下一轮开始人员的名字是：t-base[t-Front].Nameendl;elsecout男女搭配刚好完成!endl;return 0;}运行结果心得体会1、了解了队列的类型定义方法。2、理解和掌握了循环队列解决假溢出的方法。