数据结构实训-学生分配问题

1、淮阴工学院算法设计技能训练实习报告题目： 学生搭配问题 系 （院）: 计算机工程学院 专 业： 微软 班 级： 计1137 学 号： 1131317726 姓 名： 陆炎炜 指导教师： 周海岩 学年学期: 2014 2015 学年 第 1 学期2015年 1月 1 日算法设计技能训练任务书课题名称 学生搭配问题设计目的1、 通过算法设计技能训练，深入理解算法设计的意义和重要性，更好地掌握 算法设计的知识。2、 能够针对某一具体问题，设计算法进行解决。3、 锻炼实践动手能力，提高解决问题的能力。实验环境硬件：1、PC机，奔腾以上CPU， 512MB以上内存，80G以上硬盘； 软件：Visual

2、C+编程工具任务要求1、 应用数据结构基础知识进行实际问题求解与分析2、 作为一个完整的系统，应具有友好的界面和较强的容错能力3、 上机能正常运行代码4、 分析算法的运行效率5、 按要求撰写课程设计报告和设计总结工作进度计划序号起止日期工 作 内 容12014.12.29任务下达，查阅文献资料22014.12.292014.12.31总体设计、素材搜集、课题详细设计、调试32014.12.312015.1.3完善设计、撰写报告42015.1.4答辩指导教师（签章）： 年 月 日 摘要 针对学生搭配问题，循环队列是一种重要的链式结构，其特殊性在于需附设 两个指针front和rear分别指示对头元

3、素及队尾元素的位置且对头和队尾相邻接。在程序的设计过程中，运用了各种基本的算法，有判断队空及队满，出队，入队等.循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。学生搭配问题是典型的只有采用循环队列才能解决的问题，实验表明该算法的空间复杂度优于其他算法。 本文用循环队列会很好的把这个程序设计出来，会有很好的效果。得出的程序运行结果能够很形象的把结果表示出来。关键词： 学生搭配 数据结构 循环队列 目录一、设计目的.二、课程设计. 1、设计内容. 2、设计思想. 3、关键算法.

4、 4、测试结果.三、实验程序.四、结论.5、 致谢.六、参考文献.17一、设计目的1、通过算法设计技能训练，深入理解算法设计的意义和重要性，更好地掌握 算法设计的知识。2、能够针对某一具体问题，设计算法进行解决。3、锻炼实践动手能力，提高解决问题的能力。2、 课程设计1.设计内容一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴.请设计一系统模拟动态地显示出上述过程,要求如下:1) 输出每曲配对情况2) 计算出任何一个男生(编号为X)和任意女生(编号为Y),在第

5、K曲配对跳舞的 情况.至少求出K的两个值.3) 尽量设计出多种算法及程序,可视情况适当加分2、设计思想队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。 循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。循环队列的入队，出队，判队满，判队空。 （1） 要模拟动态地显示出现题目中所要求的循环，我们要先建立两个循环队列SqQueue和SqQueue2。 （2） 将男生、女生两组人分别存

6、入这两个队列。以实现他们的循环配对输出，这是循环队列固有的特性。 （3） 利用循环队列的特性，将男女生分别进行入队列和出队列操作，且实现搭配输出。 （4） 循环队列的长度分别设为男女生的个数即可。（5） 在计算机终端输出的结果是：根据要求输出男生女生搭配情况。3、关键算法建立两个链式循环队列来分别存储男生和女生，然后调用入队出队函数实现循环队列的配对输出。为充分利用向量空间，克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，存储在其中成为循环队列。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界时、其加1操作是指向向量的下界。这样就可以通过

7、出队再入队来实现男生女生的循环搭配。课程设计过程中的关键算法如下：1)关键算法之一：初始化队列void InitQ(LinkQueue &Q)    QueuePtr p;   p=(QueuePtr)malloc(sizeof(QNode);  Q.front=p;  Q.rear=p;  Q.front->next=NULL; (2)关键算法之二：入队函数 void EnQueue(Lin

8、kQueue &Q,int num)/入队函数   QueuePtr p;   p=(QueuePtr)malloc(sizeof(QNode);  p->num=num;  p->next=NULL;  Q.rear->next=p;  Q.rear=p; (3)关键算法之三：出队函数 void DeQueue(LinkQueue &Q, i

9、nt &num)/出队函数   QueuePtr p,q;   if(Q.front=Q.rear)   printf("队列为空");  p=Q.front->next;  num=p->num;  Q.front->next=p->next;  q=p->next;  if(Q.rear=q)   

10、;Q.rear=Q.front;  free(p); (4)关键算法之四：输出第i首曲子时女队的情况 void printF(LinkQueue &F,int i) /输出第i首曲子时女队的情况   QueuePtr p;   int n=1;  while(n<i)     printf("_ ");  

11、; n+;     p=F.front->next;  while(F.rear!=p)      printf("%d ",p->num);   p=p->next;  printf("%d n",p->num); 4、测试结果：三、实验程序#include<iostream>template <

12、;class T>class cirularQueue /定义一个一个循环队列 private: int MaxSize; int front; /头指针 int rear; /尾指针 T *data; public: cirularQueue(int MaxLength) MaxSize=MaxLength; front=rear=0; data=new TMaxLength; cirularQueue() /定义析构函数，使对象在撤销时释放 front=rear=0; delete data; void Initqueue() /队列的申明 for(int i=0;i<maxS

13、ize-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(T info) /入队 if(IsFull() cout<<"错误！队列已满！"<<endl; exit(-1); else datarear=info; rear=(rear+1)%MaxSi

14、ze; void Pop(T &info) /出队 if(IsEmpty() cout<<"错误！队列为空！"<<endl; exit(-1); else info=datafront; front=(front+1)%MaxSize; void GetHead(T &info) /取队首元素 if(IsEmpty() cout<<"错误！队列为空！"<<endl; exit (-1); else info=datafront; ;void Initqueue(cirularQueue<

15、;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<<"请分别输入男生和女生的人数:" cin>>m>>n; display(m,n); int a=0,b=0; /男生和女生的编号，以判断他们在第几首歌时能在一起跳舞 char quit='y

16、9; /判断是否继续输入,如果继续输入，则输入'y'；否则输入'n' while(quit!='n') cout<<"请输入男生和女生的编号:" cin>>a>>b; while(a>m)|(b>n) /如果输入错误 cout<<"输入的编号过大，请重新输入:" cin>>a>>b; charge(a,b); cout<<"是否继续(是请输入'y',否则请输入'n'):&

17、quot; 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+1); cirularQueue<int> woman(n+1); Initqueue(man,m); Initqueue(woman,n); cout<<"请输入曲目数:" cin>&

18、gt;songnum; cout<<"每曲的配对情况为:"<<endl; for(int k=1;k<=songnum;k+) int x=0,y=0; /男生和女生的编号 man.Pop(x); /男生按顺序出对跳舞 woman.Pop(y); /女生按顺序出对跳舞 cout<<"第"<<k<<"曲:t"<<x<<"号男生<->"<<y<<"号女生"<<en

19、dl; /他们在一起跳舞 man.push(x); /跳完舞后男生再次进入队列等在下一次跳舞 woman.push(y); /跳完舞后男生再次进入队列等在下一次跳舞 void charge(int a,int b) int count=0; /定义舞曲计数以记录他们能在第几曲时在一起跳舞 cirularQueue<int> man1(m+1); cirularQueue<int> woman1(n+1); Initqueue(man1,m); Initqueue(woman1,n); while(count<=songnum) int x, y; count+;

20、man1.Pop(x); woman1.Pop(y); man1.push(x); woman1.push(y); if(x=a)&&(y=b) cout<<"第"<<count<<"首曲:t"<<a<<"号男生<->"<<b<<"号女生"<<endl; break; /如果他们在这个舞会上不能在一起跳舞，则输出 if(count=songnum+1) cout<<"他们

21、在这个舞会上不可能在一起跳舞"<<endl; 结 论设计采用的是循环队列的基本操作顺利的解决学生舞曲搭配问题，主要利用用循环队列的环状结构，循环地执行出列入列操作并在出队列时进行配对并输出配对情况，而整个过程不需要不需要移动元素使程序在空间复杂度上降到最小，采用指针的移动大大加快了程序的执行效率。并且对输入进行了改进，以防止用户随意输入时出现的各种意想不到的错误。本次程序设计中所用语言为C+，程序开始定义了类cirular，其中有头指针，尾指针及数据域等。随之定义了析构函数，释放对象，然后进行了队列的基本操作，有队列的申明，判断队空及队满，出队，入队，其核心是displa

22、y()函数和charge()函数，其中display()用于对各位同学编号和每队的输出情况，charge()用于计算已编号的同学在第几曲中进行配对。循环队列是一种环状的队列并且对头元素指向队尾元素，学生搭配问题是典型的只有采用循环队列才能解决的问题，实验表明该算法的空间复杂度优于其他算法。 致 谢 踉踉跄跄地忙碌近三四天，我的实训报告也终将告一段落。点击运行，也基本达到预期的效果，虚荣的成就感在没人的时候也总会冒上心头。但由于能力和时间的关系，总是觉得有很多不尽人意的地方。可是，我又会有点自恋式地安慰自己：做一件事情，不必过于在乎最终的结果，可贵的是过程中的收获。以此语言来安抚我尚没平复的心。感谢，衷心的感谢。在实训设计完成之际，衷心感谢我的老师周海岩老师对我的导和教诲。周老师开阔的思维、敏锐的洞察力以及详细的修改意见给我大的启发。金老师不仅专业学识渊博、治学严谨，待人平易近人；同时他对工作的积极热情、对学生认真负责、实事求是的态度，给我留下了深刻的印象，使我受益非浅。唯一的遗憾是我自己不够主动，错过了许多与您交流的机会。在此，我再次向周老师表示衷心的感谢和深深的敬意。 感谢我的母校给我们授课的各位尊敬的老师和计算机系培养我的领导与辅导老