搜索
数据结构课程设计报告书班级学号专业姓名课题描述：一、需求分析：1.设计内容一班有m个女生,有n个男生(m不等于n),现要开一个舞会.男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞,本曲没成功配对者坐着等待下一曲找舞伴.请设计一系统模拟动态地显示出上述过程,要求如下:1)输出每曲配对情况2)计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值.3)尽量设计出多种算法及程序,可视情况适当加分2.需求本课题要对数目不等的男生女生跳舞进行搭配，设计需要解决每一首曲子男生女生的搭配情况，要采用循环队列的模式来解决，男生和女生各在两个循环的队列中，每首曲子开始，便在两个队首各取一人成功配对跳舞，并进入队尾，等待下一次配对。例如：（3男5女情况）第一首：男1和女1第二首：男2和女2.........第四首：男1和女4二、总体结构设计：为实现上述功能和目的，要用到循环队列的相关知识，同时，要定义一定的抽的数据类型，主函数调用各个函数模块1.各模块函数介绍：1)classcirularQueue作用：定义一个一个循环队列2)~cirularQueue()作用：定义析构函数，使对象在撤销时释放3)boolIsFull()作用：判断队列是否已满4）boolIsEmpty()作用：判断队列是否为空，用于出队列前使用5）voidpush(Tinfo)作用：入队。每对舞伴跳完舞之后，做入队处理，到达队尾，等待下次跳舞。6）voidPop(T&info)作用：出队。每取曲子响起时男生队列和女生队列作出队处理，两人跳舞。7）voidGetHead(T&info)作用：取队首元素，对出队的男女进行识别。8）voidInitqueue(cirularQueueint&,int);作用：初始化队列9）voiddisplay(int,int);作用：根据男生和女生的人数和曲目的数目，来判断每曲歌的男女配对情况10）voidcharge(int,int);作用：判断指定组合能否配对成功2.本程序包含三个模块：1)主程序模块：voidmain(){初始化；do{接受命令；处理命令；}while(“命令”=”退出”)}2)、集合单元模块——实现集合的各个函数模块3)、结点结构单元模块——定义集合的结点结构三、各子模块设计：1主函数调用关系图图main()主函数k曲配对每曲配对数据输入输出编号classcirularQueue~cirularQueue()voidPop(T&info)IsEmpty()voidpush(Tinfo)voidGetHead(T&info)boolIsFull()2初始化示意否图voidInitqueue(cirularQueueint&Q,intm)3每曲配对函数调用关系图voiddisplay(int,int)否是iMaxsize-1Push(i)endbegan初始化男女循环队列k=songnummman.pop(x)woman.pop(y)输出k首男x女y跳舞man.push(x)woman.push(y)endk++图voiddisplay(int,int)4第k曲配对函数调用图voidcharge(int,int)图voidcharge(int,int)4队满判断boolIsFull()5对空判断原则boolIsEmpty()首尾指针相等队列为空首尾顺序相邻队列为满输出他们不会一起跳breakendcount=songnummman.pop(x)woman.pop(y)count++初始化男女循环队列(x==a)&&(y==b)man.push(x)woman.push(y)男a女b第count跳6入队流程voidpush(Tinfo)7出队流程voidPop(T&info)8.取队首元素代码voidGetHead(T&info)四、编程实现：#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;}boolIsEmpty()//判断队列是否为空{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()//主函数{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);//跳完舞后男生再次进入队列等在下一次跳舞}}voidcharge(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;}五、测试结果：六、总结：本设计采用的是循环队列的基本操作顺利的解决学生舞曲搭配问题，主要利用用循环队列的环状结构，循环地执行出列入列操作并在出队列时进行配对并输出配对情况，而整个过程不需要不需要移动元素使程序在空间复杂度上降到最小，采用指针的移动大大加快了程序的执行效率。并且对输入进行了改进，以防止用户随意输入时出现的各种意想不到的错误。本次程序设计中所用语言为C++，程序开始定义了类cirular，其中有头指针，尾指针及数据域等。随之定义了析构函数，释放对象，然后进行了队列的基本操作，有队列的申明，判断队空及队满，出队，入队，其核心是display()函数和charge()函数，其中display()用于对各位同学编号和每队的输出情况，charge()用于计算已编号的同学在第几曲中进行配对。循环队列是一种环状的队列并且对头元素指向队尾元素，学生搭配问题是典型的只有采用循环队列才能解决的问题，实验表明该算法的空间复杂度优于其他算法。通过这次实验，我发现自己在数据结构这方面真是知之甚少，以前学习的知识也多有遗忘。与其说这是一次学习，倒不如说这是一次检测。所以，这次实验让我很好的认清自己对数据结构这门课学习程度如何，知道自己哪些方面还存在不足、对该学科重视程度还不够，以后要努力学习。对一学期的学习的数据结构通过这次实训，虽然并没有掌握的非常好，但是对某些重点需要掌握和了解的还是有了深入的探讨，也让我明白学的东西再多也要学会运用，通过实例去探讨可能比理论上更容易理解。七、参考文献《实用数据结构基础（第二版）》陈元春等中国铁道出版社《C++程序》谭浩强编著2004年6月第1版