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

1淮阴工学院算法设计技能训练实习报告题目：学生搭配问题系（院）:计算机工程学院专业：微软班级：计1137学号：1131317726姓名：陆炎炜指导教师：周海岩学年学期:2014~2015学年第1学期2015年1月1日2算法设计技能训练任务书课题名称学生搭配问题设计目的1、通过算法设计技能训练，深入理解算法设计的意义和重要性，更好地掌握算法设计的知识。2、能够针对某一具体问题，设计算法进行解决。3、锻炼实践动手能力，提高解决问题的能力。实验环境硬件：1、PC机，奔腾Ⅳ以上CPU，512MB以上内存，80G以上硬盘；软件：VisualC++编程工具任务要求1、应用数据结构基础知识进行实际问题求解与分析2、作为一个完整的系统，应具有友好的界面和较强的容错能力3、上机能正常运行代码4、分析算法的运行效率5、按要求撰写课程设计报告和设计总结工作进度计划序号起止日期工作内容12014.12.29任务下达，查阅文献资料22014.12.29～2014.12.31总体设计、素材搜集、课题详细设计、调试32014.12.31～2015.1.3完善设计、撰写报告42015.1.4答辩指导教师（签章）：年月日3摘要针对学生搭配问题，循环队列是一种重要的链式结构，其特殊性在于需附设两个指针front和rear分别指示对头元素及队尾元素的位置且对头和队尾相邻接。在程序的设计过程中，运用了各种基本的算法，有判断队空及队满，出队，入队等.循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。学生搭配问题是典型的只有采用循环队列才能解决的问题，实验表明该算法的空间复杂度优于其他算法。本文用循环队列会很好的把这个程序设计出来，会有很好的效果。得出的程序运行结果能够很形象的把结果表示出来。关键词：学生搭配数据结构循环队列4目录一、设计目的............................................二、课程设计............................................1、设计内容.......................................2、设计思想.......................................3、关键算法.......................................4、测试结果.......................................三、实验程序...........................................四、结论...............................................五、致谢..............................................六、参考文献...........................................5一、设计目的1、通过算法设计技能训练，深入理解算法设计的意义和重要性，更好地掌握算法设计的知识。2、能够针对某一具体问题，设计算法进行解决。3、锻炼实践动手能力，提高解决问题的能力。二、课程设计1.设计内容一班有m个女生,有n个男生(m不等于n),现要开一个舞会.男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞,本曲没成功配对者坐着等待下一曲找舞伴.请设计一系统模拟动态地显示出上述过程,要求如下:1)输出每曲配对情况2)计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值.3)尽量设计出多种算法及程序,可视情况适当加分2、设计思想队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。循环队列的入队，出队，判队满，判队空。（1）要模拟动态地显示出现题目中所要求的循环，我们要先建立两个循环队列SqQueue和SqQueue2。（2）将男生、女生两组人分别存入这两个队列。以实现他们的循环配对输出，这是循环队列固有的特性。（3）利用循环队列的特性，将男女生分别进行入队列和出队列操作，且实现搭配输出。（4）循环队列的长度分别设为男女生的个数即可。（5）在计算机终端输出的结果是：根据要求输出男生女生搭配情况。3、关键算法建立两个链式循环队列来分别存储男生和女生，然后调用入队出队函数实现循环队列的配对输出。为充分利用向量空间，克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆6环，存储在其中成为循环队列。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界时、其加1操作是指向向量的下界。这样就可以通过出队再入队来实现男生女生的循环搭配。课程设计过程中的关键算法如下：1)关键算法之一：初始化队列voidInitQ(LinkQueue&Q){QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));Q.front=p;Q.rear=p;Q.front-next=NULL;}(2)关键算法之二：入队函数voidEnQueue(LinkQueue&Q,intnum)//入队函数{QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));p-num=num;p-next=NULL;Q.rear-next=p;Q.rear=p;}(3)关键算法之三：出队函数voidDeQueue(LinkQueue&Q,int&num)//出队函数{QueuePtrp,q;if(Q.front==Q.rear)printf(队列为空);p=Q.front-next;7num=p-num;Q.front-next=p-next;q=p-next;if(Q.rear==q)Q.rear=Q.front;free(p);}(4)关键算法之四：输出第i首曲子时女队的情况voidprintF(LinkQueue&F,inti)//输出第i首曲子时女队的情况{QueuePtrp;intn=1;while(ni){printf(_);n++;}p=F.front-next;while(F.rear!=p){printf(%d,p-num);p=p-next;}printf(%d\n,p-num);}84、测试结果：9三、实验程序#includeiostreamtemplateclassTclasscirularQueue//定义一个一个循环队列{private:intMaxSize;intfront;//头指针intrear;//尾指针T*data;public:cirularQueue(intMaxLength){MaxSize=MaxLength;front=rear=0;data=newT[MaxLength];}~cirularQueue()//定义析构函数，使对象在撤销时释放{front=rear=0;delete[]data;}voidInitqueue()//队列的申明{for(inti=0;imaxSize-1;i++)push(i);}boolIsFull()//判断队列是否已满{if((rear+1)%MaxSize==front)returntrue;elsereturnfalse;}10boolIsEmpty()//判断队列是否为空{if(front==rear)returntrue;elsereturnfalse;}voidpush(Tinfo)//入队{if(IsFull()){cout错误！队列已满！endl;exit(-1);}else{data[rear]=info;rear=(rear+1)%MaxSize;}}voidPop(T&info)//出队{if(IsEmpty()){cout错误！队列为空！endl;exit(-1);}else{info=data[front];front=(front+1)%MaxSize;}}voidGetHead(T&info)//取队首元素{if(IsEmpty()){cout错误！队列为空！endl;exit(-1);}else{info=data[front];}}};voidInitqueue(cirularQueueint&,int);voiddisplay(int,int);voidcharge(int,int);usingnamespacestd;staticintsongnum=0;//定义歌曲的数量并初始化为0staticintm=0,n=0;//男生和女生的人数intmain()//主函数11{cout请分别输入男生和女生的人数:;cinmn;display(m,n);inta=0,b=0;//男生和女生的编号，以判断他们在第几首歌时能在一起跳舞charquit='y';//判断是否继续输入,如果继续输入，则输入'y'；否则输入'n'while(quit!='n'){cout请输入男生和女生的编号:;cinab;while((am)||(bn))//如果输入错误{cout输入的编号过大，请重新输入:;cinab;}charge(a,b);cout是否继续(是请输入'y',否则请输入'n'):;cinquit;}return0;}voidInitqueue(cirularQueueint&Q,intm)//初始化队列{for(inti=1;i=m;i++)Q.push(i);}voiddisplay(intm,intn){cirularQueueintman(m+1);cirularQueueintwoman(n+1);Initqueue(man,m);Initqueue(woman,n);cout请输入曲目数:;cinsongnum;cout每曲的配对情况为:endl;for(intk=1;k=songnum;k++){intx=0,y=0;//男生和女生的编号man.Pop(x);//男生按顺序出对跳舞woman.Pop(y);//女生按顺序出对跳舞cout第k曲:\tx号男生-y号女生endl;//他们在一起跳舞man.push(x);//跳完舞后男生再次进入队列等在下一次跳舞woman.push(y);//跳完舞后男生再次进入队列等在下一次跳舞}}12voidcharge(inta,intb){intcount=0;//定义舞曲计数以记录他们能在第几曲时在一起跳舞cirularQueueintman1(m+1);cirularQueueintwoman1(n+1);Initqueue(man1,m);Initqueue(woman1,n);while(count=songnum){intx,y;count++;man1.Pop(x);woman1.Pop(y);man1.push(x);woman1.push(y);if((x==a)&&(y==b)){cout第count首曲:\ta号男生-b号女生endl;break;}}//如果他们在这个舞会上不能在一起跳舞，则输出if(count==songnum+1)cout他们在这个舞会上不可能在一起跳舞endl;}13结论设计采用的是循环队列的基本操作顺利的解决学生舞曲搭配问题，主要利用用循环队列的环状结构，