数
据
结
构
课
程
设
计
东北大学
计算机科学与工程学院
计算机科学与技术专业1503班组长邵威学号组员崔超学号组员吴越学号
f数据结构课程设计任务书B类
f目录
1课题概述1
11课题任务1
12课题原理1
2需求分析1
21课题调研1
22功能需求1
3方案设计1
31总体功能设计1
32数据结构设计2
33函数原型设计2
34用户界面设计3
4方案实现3
41开发环境与工具3
42个人设计实现按组员分小节
421邵威设计实现4
422崔超设计实现7
423吴越设计实现9
5测试与调试11
51个人测试按组员分小节
511邵威测试11
512崔超测试14
513吴越测试16
52系统运行16
6课题总结20
61课题性能分析20
f62课题评价与与团队协作20
63个人设计小结按组员分小节20
631邵威设计小结20
632崔超设计小结21
633吴越设计小结21
7附录A课题任务分工22
A1课题程序设计分工22
A2课题报告分工23
8附录B源程序代码24
f1课题概述
11课题任务
设计基于二分图的匹配算法求解教务排课表程序。具体的设计任务如下
1采用STL的邻接矩阵结构图等数据结构。
2应用基本运算实现按照增广路径的算法求解教务排课表。
12课题原理
针对本次课程设计的具体要求我们设计了如下方案我们采用匈牙利算法求解教务排课表采用大一下离散数学课上提供的算法输出一种最大匹配。
对于数据我们用3个文件分别存储教师课程及教师与课程关系。并在程序中设有增加删除输出信息的功能。
对于教师和课程我们选择STL中vector动态数组来处理。
对于教师与课程关系我们选择二维数组存储。
2需求分析
21课题调研
为了完成本次课程设计任务我们对二分图的知识点进行了复习学习了求解二分图最大匹配问题的匈牙利算法。为本次课程设计任务的完成打下了良好的基础。
22功能需求
此次设计任务要求设计基于二分图的匹配算法求解教务排课表程序。一是求出最大匹配数二是输出一种最大匹配。为了避免每次都需要输入的繁琐我们设计文件来存储管理数据。
3方案设计
31总体功能设计
本次课程设计共分为四个主要功能
1文件读写
2数据添加删除输出
3求最大匹配数
4输出一种最大匹配
对于文件的操作调用了C语言文件操作函数fwritefread。数据以二进制文件保存。
对于数据添加删除直接调用push_backerase函数处理。
对于求最大匹配数我们选用匈牙利算法。
对于输出一种最大匹配的算法如下图所示
f此外我们还设计文件重置函数使数据重置更加方便。
32数据结构设r