数据结构男女运动员最佳组合

东北大学信息科学与工程学院数据结构课程设计报告题目： 男女运动员最佳组合课题组长 王逸飞课题组成员 王嘉琦 李聪专业名称 计算机科学与技术班级 计1307指导教师：杨雷2015年1月课程设计任务书题目：男女运动员最佳组合问题描述：设有N个男羽毛球运动员和N个女羽毛球运动员，现组成N对男女混合最佳组合。每个男运动员对每个女运动员都有一个满意度排序，用矩阵mf0:n-10:n-1表示。mfij表示第i个男运动员对第j个女运动员的满意度，满意度值越高，满意程度越高。同理，每个女运动员对每个男运动员也有一个满意度排序，用矩阵fm0:n-10:n-1表示。男女运动员之间的一个完全匹配称为一个组合。设计要求：设计对于给定的满意度，求最佳组合的程序，使得满意度总和达到最大。（1）采用STL的向量等数据结构。（2）实现STL的一维向量类vector。（3）利用一维向量类构造二维向量矩阵。（4）尝试采用不同数据结构的多种解法。指导教师签字：年月日目录1课题概述11.1 课题任务11.2 课题原理11.3 相关知识32 方案设计72.1 总体功能设计72.2 数据结构设计82.3 函数原型设计102.4 主算法设计122.5 用户界面设计143 方案实现153.1 开发环境与工具153.2 程序设计关键技术163.3 个人设计实现（按组员分工）3.3.1王逸飞设计实现173.3.2王嘉琦设计实现173.3.3李聪设计实现174 测试与调试234.1 个人测试（按组员分工）234.1.1王逸飞测试234.1.2王嘉琦测试234.1.2李聪测试234.2组装与系统测试334.3 系统运行365 课题总结395.1 课题评价395.2团队协作405.3团队协作415.4个人设计小结（按组员分工）425.4.1王逸飞设计小结425.4.2王嘉琦设计小结425.4.3李聪设计小结426附录A 课题任务分工50A-1 课题程序设计分工50A-2 课题报告分工51 附录B 课题设计文档（光盘）52B-1课程设计报告（电子版）52B-2源程序代码（*.H，*.CPP）52B-3工程与可执行文件52B-4屏幕演示录像文件（可选）52附录C 用户操作手册（可选）53C.1 运行环境说明53C.2 操作说明541 课题概述1.1课题任务【问题描述】设有N个男羽毛球运动员和N个女羽毛球运动员，现组成N对男女混合最佳组合。每个男运动员对每个女运动员都有一个满意度排序，用矩阵mf0:n-10:n-1表示。mfij表示第i个男运动员对第j个女运动员的满意度，满意度值越高，满意程度越高。同理，每个女运动员对每个男运动员也有一个满意度排序，用矩阵fm0:n-10:n-1表示。男女运动员之间的一个完全匹配称为一个组合。【设计要求】设计对于给定的满意度，求最佳组合的程序，使得满意度总和达到最大。（1）采用STL的向量等数据结构。（2）实现STL的一维向量类vector。（3）利用一维向量类构造二维向量矩阵。（4）尝试采用不同数据结构的多种解法。1.2 课题原理采用STL的向量等数据结构，利用一维向量类构造二维向量矩阵，使用递归函数进行比较，以及一些基本操作。1.3 相关知识vector的定义，表示，C语言实现，函数的递归调用。 2 方案设计2.1 总体功能设计（1）实现输入（2）实现后台运算和匹配（3）实现输出结果3.2 数据结构设计男，女，匹配结果，运算的vector：vector vector mf( N);vector vector fm( N);vector a(N,0); /开辟数组保存所有男女匹配，并初始化0vector b(N,0); /运算需要我们将结构的创建，初始化，插入删除等基本2.3 函数原型设计void input() /输入男女满意度数据int recMaxAdv(int i) /递归调用求解int run() /调用之前的函数，运行int main()主函数2.4 主算法设计2.5 用户界面设计由于时间原因，低级版本在没有实现可视化界面，采用DOS来显示得到的结果。3 方案实现3.1 开发环境与工具编程环境为visual c+6.0，vim。工具为C语言。3.2 程序设计关键技术STL的向量等数据结构。3.3 个人设计实现（按组员分小节）3.3.1 王逸飞、王嘉琦、李聪设计实现1.课题任务（1）建立vector：男，女，匹配结果，运算需要（2）函数：按长度输入数据（3）函数：递归调用求解，比较（4）函数：循环调用（2）函数，输入，调用（3）比较，输出（5）主函数：调用（4），输出结果 2.程序源代码#include using namespace std;#include #define N 3vector vector mf( N);vector vector fm( N);vector a(N,0); /开辟数组保存所有男女匹配，并初始化0vector b(N,0); /运算需要void input() /输入男女满意度数据/依次输入男队员对女队员的满意度vector vector :iterator iiter;vector:iterator iter;cout请依次输入男队员对女队员的满意度：begin(); iter!=iiter-end(); +iter )cin*iter; /依次输入女队员对男队员的满意度cout请依次输入女队员对男队员的满意度：begin(); iter!=iiter-end(); +iter )cin*iter;int *s; /si男i的配合者int maxA; /当前最大总和int sumA; /当前总和int recMaxAdv(int i) /递归调用求解if(i=N) /组合完毕if(maxAsumA) /方案是目前最佳的 maxA = sumA;for (int k=0; kN;k+)ak=bk;return 0;for(int j=i; jN; j+)swap(si, sj);sumA += mfisi+fmsii;/coutsumAn;bi=si;/couttbin;recMaxAdv(i+1);sumA -= mfisi+fmsii;swap(si, sj);return 0;int run() /run函数定义s= new intN;maxA = 0;for (int i=0; iN; i+)si=i; /初始配合方案i男配i女sumA = 0;recMaxAdv(0);cout最大满意度为：maxAendl;delete s;return 0;int main() /主函数input();run(); /运行求解函数cout最佳匹配为：endl;for (int m=0;mN;m+)cout第m+1个男的配第am+1个女的！endl;return 0;44.1系统测试操作名称操作流程操作结果和输出输入开始输入数据数据男女，女男的数据，储存与vector数据处理对已输入的数据进行递归比较比较，递归，读取下一个数，记录结果输出输出匹配结果输出匹配结果4.2 系统运行系统运行结果如下：5 课题总结5.1 课题分析完成了课题要求功能，容易封装便于使用。5.2 团队协作本次课程设计，让我们感受到了在程序编写软件设计中团队你的力量。一个人的力量对于编写一个大型的程序来说简直是渺茫的，但是编写程序这种工作又是不能忽略每一个个体的，因为只要一个人有一个小小的疏忽，就可能导致整个程序无法运行，甚至崩溃。我们充分利用现代社会知识信息交流充分发展的机会，我们遇到困难时就去学校图书馆查找相关书籍或在网上查找相关资料。今后的学习也应该注重理论与实践的结合，多观察多思考，知道自己所学知识在实际应用中的作用。5.3 个人设计小结（分组员小结） 5.3.1王逸飞设计小结总体上，巩固了所学的有关c语言的知识，强化了对数据结构的理解。强化了我们对计算机编程操作技能，充实了有关数据结构的理论知识，拓宽了有关数据结构的知识面，通过数据结构课程设计的学习，找到了自身知识点的漏洞与欠缺，加深我们对数据结构的理解，最关键的是对编程思想的理解，对程序开发过程中的有了较深层次的而理解，具体来说，加深了我对基本抽象数据类型的理解，例如结构体链表的操作，间接地也巩固了之前的有关C语言的知识，例如基本数据类型的操作等，文件的操作也更加的熟练。 5.3.1 王嘉琦设计小结通过本次程序设计课程，我发现编程最重要的便是可行以及合理，否则也是毫无用处的程序，没有丝毫意义。刚开始的时候，总是在空想函数该怎样编写，而没有考虑实际生活中图书馆的功能以及工作流程，导致做出来的东西很不切实际。吸取教训了以后，我仔细思考借鉴了我们学校图书馆的操作流程，才写出行之有效的代码。 5.3.1 李聪设计小结此次课程设计，我通过上网查找资料学习，深刻理解了线性表及其应用。查询函数中主要需要对线性表进行访问查询，线性表的访问需要遍历线性表中的元素。在查询函数设计