数据结构课设学生搭配问题

1、数 据 结 构课程设计报告书班级 学号 专业 姓名 课题描述：一、 需求分析：1. 设计内容一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴.请设计一系统模拟动态地显示出上述过程,要求如下:1) 输出每曲配对情况2) 计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的 情况.至少求出K的两个值.3) 尽量设计出多种算法及程序,可视情况适当加分 2.需求 本课题要对数目不等的男生女生跳舞进行搭配，设计需要解决每一首曲子 男生女生的搭配情况，

2、要采用循环队列的模式来解决，男生和女生各在两个循环 的队列中，每首曲子开始，便在两个队首各取一人成功配对跳舞，并进入队尾， 等待下一次配对。 例如：（3男5女情况） 第一首：男1和女1 第二首：男2和女2. 第四首：男1和女4二、 总体结构设计： 为实现上述功能和目的，要用到循环队列的相关知识，同时，要定义一定的抽的数据类型，主函数调用各个函数模块 1.各模块函数介绍：1)class cirularQueue 作用：定义一个一个循环队列2)cirularQueue() 作用：定义析构函数，使对象在撤销时释放3)bool IsFull() 作用：判断队列是否已满4）bool IsEmpty()

3、作用：判断队列是否为空，用于出队列前使用5）void push(T info) 作用：入队。每对舞伴跳完舞之后，做入队处理，到达队尾，等待下次跳舞。6）void Pop(T &info) 作用：出队。每取曲子响起时男生队列和女生队列作出队处理，两人跳舞。7）void GetHead(T &info) 作用：取队首元素，对出队的男女进行识别。8）void Initqueue(cirularQueue<int>&,int);作用：初始化队列9）void display(int,int);作用：根据男生和女生的人数和曲目的数目，来判断每曲歌的男女配对情况 10）v

4、oid charge(int,int); 作用：判断指定组合能否配对成功 2. 本程序包含三个模块：1)主程序模块： void main()      初始化； do     接受命令；     处理命令；while(“命令”=”退出”) 2)、集合单元模块实现集合的各个函数模块3)、结点结构单元模块定义集合的结点结构三、 各子模块设计：1主函数调用关系图cirularQueue()void GetHead(T &info)class cirularQueu

5、e主函数k曲配对每曲配对数据输入输出编号void Pop(T &info)void push(T info)IsEmpty()bool IsFull()图main() i<Maxsize-1Push(i)endbegan 2初始化示意 否 图void Initqueue(cirularQueue<int> &Q,int m)3每曲配对函数调用关系图void display(int,int)初始化男女循环队列k<=songnummman.pop(x)woman.pop(y)否 是 输出k首男x女y跳舞 man.push(x)woman.push(y)end

6、k+图void display(int,int)4第k曲配对函数调用图void charge(int,int)输出他们不会一起跳breakendcount<=songnummman.pop(x)woman.pop(y)count+初始化男女循环队列(x=a)&&(y=b)man.push(x)woman.push(y)男a女b第count跳图void charge(int,int)4队满判断bool IsFull()首尾顺序相邻队列为满5对空判断原则bool IsEmpty()首尾指针相等队列为空6入队流程void push(T info)不能入队队满队尾进入尾指针移到

7、7出队流程void Pop(T &info)不能出队队空队头出列头指针移到8.取队首元素代码void GetHead(T &info)四、 编程实现：#include<iostream>template <class T>class cirularQueue /定义一个一个循环队列 private: int MaxSize; int front; /头指针 int rear; /尾指针 T *data; public: cirularQueue(int MaxLength) MaxSize=MaxLength; front=rear=0; data=ne

8、w TMaxLength; cirularQueue() /定义析构函数，使对象在撤销时释放 front=rear=0; delete data; void Initqueue() /队列的申明 for(int i=0;i<maxSize-1;i+) push(i);bool IsFull() /判断队列是否已满 if(rear+1)%MaxSize=front) return true; else return false; bool IsEmpty() /判断队列是否为空 if(front=rear) return true; else return false;void push(

9、T info) /入队 if(IsFull() cout<<"错误！队列已满！"<<endl; exit(-1); else datarear=info; rear=(rear+1)%MaxSize; void Pop(T &info) /出队 if(IsEmpty() cout<<"错误！队列为空！"<<endl; exit(-1); else info=datafront; front=(front+1)%MaxSize; void GetHead(T &info) /取队首元素 if(

10、IsEmpty() cout<<"错误！队列为空！"<<endl; exit (-1); else info=datafront; ;void Initqueue(cirularQueue<int>&,int);void display(int,int);void charge(int,int);using namespace std;static int songnum=0; /定义歌曲的数量并初始化为0static int m=0,n=0; /男生和女生的人数 int main() /主函数 cout<<"

11、;请分别输入男生和女生的人数:" cin>>m>>n; display(m,n); int a=0,b=0; /男生和女生的编号，以判断他们在第几首歌时能在一起跳舞 char quit='y' /判断是否继续输入,如果继续输入，则输入'y'；否则输入'n' while(quit!='n') cout<<"请输入男生和女生的编号:" cin>>a>>b; while(a>m)|(b>n) /如果输入错误 cout<<&q

12、uot;输入的编号过大，请重新输入:" cin>>a>>b; charge(a,b); cout<<"是否继续(是请输入'y',否则请输入'n'):" cin>>quit; return 0;void Initqueue(cirularQueue<int> &Q,int m) /初始化队列 for(int i=1;i<=m;i+) Q.push(i);void display(int m,int n) cirularQueue<int> man(m

13、+1); cirularQueue<int> woman(n+1); Initqueue(man,m); Initqueue(woman,n); cout<<"请输入曲目数:" cin>>songnum; cout<<"每曲的配对情况为:"<<endl; for(int k=1;k<=songnum;k+) int x=0,y=0; /男生和女生的编号 man.Pop(x); /男生按顺序出对跳舞 woman.Pop(y); /女生按顺序出对跳舞 cout<<"第&q

14、uot;<<k<<"曲:t"<<x<<"号男生<->"<<y<<"号女生"<<endl; /他们在一起跳舞 man.push(x); /跳完舞后男生再次进入队列等在下一次跳舞 woman.push(y); /跳完舞后男生再次进入队列等在下一次跳舞 void charge(int a,int b) int count=0; /定义舞曲计数以记录他们能在第几曲时在一起跳舞 cirularQueue<int> man1(m+1); c

15、irularQueue<int> woman1(n+1); Initqueue(man1,m); Initqueue(woman1,n); while(count<=songnum) int x, y; count+; man1.Pop(x); woman1.Pop(y); man1.push(x); woman1.push(y); if(x=a)&&(y=b) cout<<"第"<<count<<"首曲:t"<<a<<"号男生<->&qu

16、ot;<<b<<"号女生"<<endl; break; /如果他们在这个舞会上不能在一起跳舞，则输出 if(count=songnum+1) cout<<"他们在这个舞会上不可能在一起跳舞"<<endl;五、 测试结果：六、 总结： 本设计采用的是循环队列的基本操作顺利的解决学生舞曲搭配问题，主要利用用循环队列的环状结构，循环地执行出列入列操作并在出队列时进行配对并输出配对情况，而整个过程不需要不需要移动元素使程序在空间复杂度上降到最小，采用指针的移动大大加快了程序的执行效率。并且对输入进行了改

17、进，以防止用户随意输入时出现的各种意想不到的错误。 本次程序设计中所用语言为C+，程序开始定义了类cirular，其中有头指针，尾指针及数据域等。随之定义了析构函数，释放对象，然后进行了队列的基本操作，有队列的申明，判断队空及队满，出队，入队，其核心是display()函数和charge()函数，其中display()用于对各位同学编号和每队的输出情况，charge()用于计算已编号的同学在第几曲中进行配对。循环队列是一种环状的队列并且对头元素指向队尾元素，学生搭配问题是典型的只有采用循环队列才能解决的问题，实验表明该算法的空间复杂度优于其他算法。通过这次实验，我发现自己在数据结构这方面真是知之甚少，以前学习的知识也多有遗忘。与其说这是