教务排课表的二分图问题.doc

《教务排课表的二分图问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计东北大学计算机科学与工程学院计算机科学与技术专业1503班组长：邵威学号：20154349组员：崔超学号：20154499组员：吴越学号：20154306-30-数据结构课程设计任务书（B类）题目：教务排课表的二分图问题问题描述：如果一个无向图的顶点集合可以分为两个互不相交的子集，并且图中每条边的两个顶点都属于两个不同的顶点集。则称该图为一个二分图。可以用一个二分图表示教师与课程的排课关系。假设每位教师可以胜任多门课程，但一个学期只能讲授一门课程，每学期的每门课程只需一位教师讲授。在二分图中，边数最多的匹配称为图的最大

2、匹配。图的所有顶点都是某条匹配边的顶点，称这个匹配为完全匹配。设计要求：设计基于二分图的匹配算法求解教务排课表程序。（1）采用STL的邻接矩阵结构图等数据结构。（2）应用基本运算，实现按照增广路径的算法求解教务排课表。　　　　　　　　　　　　指导教师签字：年　　月　　日-30-目录1课题概述11.1课题任务11.2课题原理12需求分析12.1课题调研12.2功能需求13方案设计13.1总体功能设计13.2数据结构设计23.3函数原型设计23.4用户界面设计34方案实现34.1开发环境与工具34.2个人设计实现（按组员分小节）4.2.1

3、邵威设计实现44.2.2崔超设计实现74.2.3吴越设计实现95测试与调试115.1个人测试（按组员分小节）5.1.1邵威测试115.1.2崔超测试145.1.3吴越测试165.2系统运行166课题总结206.1课题性能分析20-30-6.2课题评价与与团队协作206.3个人设计小结（按组员分小节）206.3.1.邵威设计小结206.3.2崔超设计小结216.3.3吴越设计小结217附录A课题任务分工22A-1课题程序设计分工22A-2课题报告分工238附录B源程序代码24-30-1课题概述1.1课题任务设计基于二分图的匹配算法求解教

4、务排课表程序。具体的设计任务如下：（1）采用STL的邻接矩阵结构图等数据结构。（2）应用基本运算，实现按照增广路径的算法求解教务排课表。1.2课题原理针对本次课程设计的具体要求，我们设计了如下方案：我们采用匈牙利算法求解教务排课表，采用大一下离散数学课上提供的算法，输出一种最大匹配。对于数据：我们用3个文件分别存储教师，课程及教师与课程关系。并在程序中设有增加，删除，输出信息的功能。对于教师和课程我们选择STL中vector动态数组来处理。对于教师与课程关系，我们选择二维数组存储。2需求分析2.1课题调研为了完成本次课程设计任务，我们

5、对二分图的知识点进行了复习，学习了求解二分图最大匹配问题的匈牙利算法。为本次课程设计任务的完成打下了良好的基础。2.2功能需求此次设计任务，要求设计基于二分图的匹配算法求解教务排课表程序。一是求出最大匹配数，二是输出一种最大匹配。为了避免每次都需要输入的繁琐，我们设计文件来存储，管理数据。3方案设计3.1总体功能设计本次课程设计共分为四个主要功能：（1）文件读写（2）数据添加，删除，输出（3）求最大匹配数（4）输出一种最大匹配对于文件的操作，调用了C语言文件操作函数fwrite(),fread()。数据以二进制文件保存。对于数据添加删

6、除，直接调用push_back()，erase()函数处理。对于求最大匹配数，我们选用匈牙利算法。对于输出一种最大匹配的算法如下图所示：-30-此外，我们还设计文件重置函数，使数据重置更加方便。3.2数据结构设计本次课程设计主要使用了图，vector动态数组，具体的设计方案和操作过程将在个人报告中给出，在此不再赘述。3.3函数原型设计intmain(){vectortea;vectorcou;printf("欢迎使用教务排课系统");printf("正在导入数据库。。。");ReadTeach

7、er(tea);ReadCourse(cou);ReadMatrix(mat);printf("导入数据库成功！");printf("请按任意键进入主菜单");system("pause");system("cls");while(1){printf("1.添加教师");printf("2.添加课程");printf("3.添加教师可任课课程");-30-printf("4.输出教师信息");printf("5.输出课程信息");printf("6.输出教师可任课课程");printf("7.求最大匹配

8、数");printf("8.求一种最大匹配方案");printf("9.清空数据库");printf("10.删除教师信息：");printf("11.删除课程信息：");printf("12.关闭程