教務(wù)排課表的二分圖問題

1、精品文檔- 3 - 歡迎下載。據(jù) 結(jié)構(gòu) 課程 設(shè)計(jì)東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)1503 班組長(zhǎng)：邵威學(xué)號(hào)：20154349組員：崔超學(xué)號(hào)：20154499B 類）組員：吳越學(xué)號(hào)：20154306數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書（題目：教務(wù)排課表的二分圖問題問題描述：如果一個(gè)無向圖的頂點(diǎn)集合可以分為兩個(gè)互不相交的子集，并 且圖中每條邊的兩個(gè)頂點(diǎn)都屬于兩個(gè)不同的頂點(diǎn)集。則稱該圖為一 個(gè)二分圖?？梢杂靡粋€(gè)二分圖表示教師與課程的排課關(guān)系。假設(shè)每 位教師可以勝任多門課程，但一個(gè)學(xué)期只能講授一門課程，每學(xué)期 的每門課程只需一位教師講授。在二分圖中，邊數(shù)最多的匹配稱為 圖的最大匹配。圖的所有頂點(diǎn)都

2、是某條匹配邊的頂點(diǎn)，稱這個(gè)匹配 為完全匹配。設(shè)計(jì)要求：設(shè)計(jì)基于二分圖的匹配算法求解教務(wù)排課表程序。(1)采用STL的鄰接矩陣結(jié)構(gòu)圖等數(shù)據(jù)結(jié)構(gòu)。(2)應(yīng)用基本運(yùn)算，實(shí)現(xiàn)按照增廣路徑的算法求解教務(wù)排課表指導(dǎo)教師簽字：年 月 日目錄1 課題概述11.1 課題任務(wù) 11.2 課題原理 12 需求分析12.1 課題調(diào)研 12.2 功能需求 13 方案設(shè)計(jì)13.1 總體功能設(shè)計(jì)13.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)23.3 函數(shù)原型設(shè)計(jì)23.4 用戶界面設(shè)計(jì)34 方案實(shí)現(xiàn)34.1 開發(fā)環(huán)境與工具34.2 個(gè)人設(shè)計(jì)實(shí)現(xiàn)（按組員分小節(jié)）4.2.1 邵威設(shè)計(jì)實(shí)現(xiàn) 44.2.2 崔超設(shè)計(jì)實(shí)現(xiàn) 74.2.3 吳越設(shè)計(jì)實(shí)現(xiàn) 95 測(cè)

3、試與調(diào)試115.1 個(gè)人測(cè)試（按組員分小節(jié)）5.1.1 邵威測(cè)試115.1.2 崔超測(cè)試145.1.3 吳越測(cè)試165.2 系統(tǒng)運(yùn)行166 課題總結(jié)206.1 課題性能分析206.2 課題評(píng)價(jià)與與團(tuán)隊(duì)協(xié)作206.3 個(gè)人設(shè)計(jì)小結(jié)（按組員分小節(jié)）20精品文檔6.3.1 .邵威設(shè)計(jì)小結(jié) 206.3.2 崔超設(shè)計(jì)小結(jié) 216.3.3 吳越設(shè)計(jì)小結(jié) 217 附錄 A 課題任務(wù)分工22A-1 課題程序設(shè)計(jì)分工22A-2 課題報(bào)告分工238 附錄 B 源程序代碼24- # - 歡迎下載。精品文檔1課題概述1.1 課題任務(wù)設(shè)計(jì)基于二分圖的匹配算法求解教務(wù)排課表程序。具體的設(shè)計(jì)任務(wù)如下:(1)采用STL的鄰接

4、矩陣結(jié)構(gòu)圖等數(shù)據(jù)結(jié)構(gòu)。(2)應(yīng)用基本運(yùn)算，實(shí)現(xiàn)按照增廣路徑的算法求解教務(wù)排課表。1.2 課題原理針對(duì)本次課程設(shè)計(jì)的具體要求，我們?cè)O(shè)計(jì)了如下方案：我們采用匈牙利算法求解教務(wù)排 課表，采用大一下離散數(shù)學(xué)課上提供的算法，輸出一種最大匹配。對(duì)于數(shù)據(jù)：我們用3個(gè)文件分別存儲(chǔ)教師，課程及教師與課程關(guān)系。并在程序中設(shè)有增加，刪除，輸出信息的功能。對(duì)于教師和課程我們選擇 STL中vector動(dòng)態(tài)數(shù)組來處理。對(duì)于教師與課程關(guān)系，我們選擇二維數(shù)組存儲(chǔ)。2需求分析2.1 課題調(diào)研為了完成本次課程設(shè)計(jì)任務(wù)，我們對(duì)二分圖的知識(shí)點(diǎn)進(jìn)行了復(fù)習(xí)，學(xué)習(xí)了求解二分圖最大匹配問題的匈牙利算法。為本次課程設(shè)計(jì)任務(wù)的完成打下了良好的基

5、礎(chǔ)。2.2 功能需求此次設(shè)計(jì)任務(wù)，要求設(shè)計(jì)基于二分圖的匹配算法求解教務(wù)排課表程序。一是求出最大匹 配數(shù)，二是輸出一種最大匹配。為了避免每次都需要輸入的繁瑣，我們?cè)O(shè)計(jì)文件來存儲(chǔ)，管 理數(shù)據(jù)。3方案設(shè)計(jì)1.1 總體功能設(shè)計(jì)本次課程設(shè)計(jì)共分為四個(gè)主要功能：(1)文件讀寫(2)數(shù)據(jù)添加，刪除，輸出(3)求最大匹配數(shù)(4)輸出一種最大匹配對(duì)于文件的操彳調(diào)用了 C語言文件操作函數(shù)fwrite(),fread() 。數(shù)據(jù)以二進(jìn)制文件 保存。對(duì)于數(shù)據(jù)添加刪除，直接調(diào)用push_back() , erase()函數(shù)處理。對(duì)于求最大匹配數(shù)，我們選用匈牙利算法。對(duì)于輸出一種最大匹配的算法如下圖所示：求匹總算法：設(shè)G

6、廣匕.石產(chǎn)是二部圖，直切魚：匕二外 £產(chǎn)0 G產(chǎn)G。石累3是率圖，倒自束，得旦。否則在匕中進(jìn)取度 景小的結(jié)點(diǎn)，不有設(shè)這個(gè)姑息是明 且與相鄰越的一小姑點(diǎn)為6,取用3域,EEU蚓從圖3中制去結(jié)點(diǎn)，力（即匕=匕-m處），得到圖Gj我對(duì)古圖執(zhí)行以上算法科時(shí)。此外，我們還設(shè)計(jì)文件重置函數(shù)，使數(shù)據(jù)重置更加方便。1.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)本次課程設(shè)計(jì)主要使用了圖，vector動(dòng)態(tài)數(shù)組，具體的設(shè)計(jì)方案和操作過程將在個(gè)人報(bào)告中給出，在此不再贅述。1.3 函數(shù)原型設(shè)計(jì)int main()vector<teacher> tea;vector<course> cou;printf(&quo

7、t;歡迎使用教務(wù)排課系統(tǒng)n");printf("正在導(dǎo)入數(shù)據(jù)庫。n");ReadTeacher(tea);ReadCourse(cou);ReadMatrix(mat);printf("導(dǎo)入數(shù)據(jù)庫成功！ n");printf("請(qǐng)按任意鍵進(jìn)入主菜單n");system ("pause");system ("cls");while(1)printf("1.添加教師 n");printf("2.添加課程 n");printf("3.添加教師

8、可任課課程n");-# -歡迎下載精品文檔printf("4.輸出教師信息n");printf("5.輸出課程信息n");printf("6.輸出教師可任課課程n");printf("7.求最大匹配數(shù)n");printf("8.求一種最大匹配方案n");printf("9. 清空數(shù)據(jù)庫n");printf("10.刪除教師信息：n");printf("11.刪除課程信息：n");printf("12.關(guān)閉程序：n&q

9、uot;);printf(" 請(qǐng)輸入正確的選項(xiàng)");int i = 0;scanf("%d",&i);getchar();switch(i)case 1:AddTeacher(tea);break;case 2:AddCourse(cou);break;case 3:AddMatrix(mat,tea,cou);break;case 4:PrintTeacher(tea);break;case 5:PrintCourse(cou);break;case 6:PrintMartix(mat,tea,cou);break;case 7:Get_t_c

10、(tea,cou);ANS();printf("%dn",ans);break;case 8:Get_t_c(tea,cou);solve(tea,cou);break;case 9:Reset(mat,tea,cou);break;case 10:DeleteTeacher(tea);memset(mat,0,sizeof(mat);break;case 11:DeleteCourse(cou);memset(mat,0,sizeof(mat);break;case 12:system ("cls");printf("謝謝使用！")

11、;exit(0);break;default:printf("輸入的選項(xiàng)不正確：");system ("pause");system ("cls");return 0;1.4 用戶界面設(shè)計(jì)運(yùn)行時(shí)為DOS#面，通過輸入選項(xiàng)選擇操作。4 方案實(shí)現(xiàn)4.1 開發(fā)環(huán)境與工具開發(fā)環(huán)境：Code:Blocks13.124.2 個(gè)人設(shè)計(jì)實(shí)現(xiàn)(按組員分小節(jié))4.2.1 邵威設(shè)計(jì)實(shí)現(xiàn)( 1 )文件讀取void ReadTeacher(vector<teacher> &tea)/ 讀取教師文件 tea.clear();FILE *Tea

12、;if(Tea = fopen("teacher.txt","rb+") = NULL)/打開操作不成功printf("teacher.txt can not be opened n");exit(1);/結(jié)束程序的執(zhí)行teacher a;while(fread(&a,sizeof(struct teacher),1,Tea) != 0) tea.push_back(a);fclose(Tea);void ReadCourse(vector<course> &cou)/ 讀取課程文件cou.clear();

13、FILE *Cou;if(Cou = fopen("course.txt","rb+") = NULL)/打開操作不成功printf("course.txt can not be opened n");exit(1);/結(jié)束程序的執(zhí)行course a;while(fread(&a,sizeof(struct course),1,Cou) != 0) cou.push_back(a);fclose(Cou);void ReadMatrix(matrix &mat)/ 讀取鄰接矩陣FILE *Mat;if(Mat = fo

14、pen("matrix.txt","rb+") = NULL)/打開操作不成功printf("matrix.txt can not be opened n");exit(1);/結(jié)束程序的執(zhí)行fread(mat,sizeof(bool),N*N,Mat);fclose(Mat);(2)文件寫入void WriteTeacher(vector<teacher> tea)/寫入教師文件FILE *Tea;if(Tea = fopen("teacher.txt","wb+") = NULL

15、)/打開操作不成功printf("teacher.txt can not be opened n");exit(1);/結(jié)束程序的執(zhí)行vector<teacher>:iterator it;for(it=tea.begin();it!=tea.end();it+)fwrite(&(*it).name),sizeof(struct teacher),1,Tea);fclose(Tea);void WriteCourse(vector<course> cou)/ 寫入課程文件FILE *Cou;if(Cou = fopen("cours

16、e.txt","wb+") = NULL)/打開操作不成功printf("course.txt can not be opened n");exit(1);/結(jié)束程序的執(zhí)行vector<course>:iterator it;for(it=cou.begin();it!=cou.end();it+)fwrite(&(*it).name),sizeof(struct course),1,Cou);fclose(Cou);void WriteMatrix(matrix mat)/ 寫入鄰接矩陣FILE *Mat;if(Mat =

17、 fopen("matrix.txt","wb+") = NULL)/打開操作不成功printf("matrix.txt can not be opened n");exit(1);/結(jié)束程序的執(zhí)行fwrite(mat,sizeof(bool),N*N,Mat);fclose(Mat);(3)數(shù)據(jù)添加添加教師（添加后要保存寫入文件）添加課程（ 添加后要保存寫入文件）void AddTeacher(vector<teacher> &tea)/int n = 0;teacher a;cout<<"

18、 請(qǐng)輸入添加教師的個(gè)數(shù)："cin>>n;cout<<" 請(qǐng)輸入教師姓名：n"for(int i = 1; i <= n; i+)cin>>;tea.push_back(a);WriteTeacher(tea);void AddCourse(vector<course> &cou)/int n = 0;course a;cout<<" 請(qǐng)輸入添加課程的個(gè)數(shù)："- 5 - 歡迎下載。精品文檔cin>>n;cout<<" 請(qǐng)輸入課程

19、名稱：n"for(int i = 1; i <= n; i+)cin>>;cou.push_back(a);WriteCourse(cou);void AddMatrix(matrix &mat,vector<teacher> tea,vector<course> cou)/添加關(guān)系( 添加后要保存寫入文件 )int n = 0;cout<<" 請(qǐng)輸入添加關(guān)系的數(shù)目："cin>>n;PrintTeacherPlus(tea);PrintCoursePlus(cou);for(in

20、t i = 1; i <= n; i+)int tn,m,tc;cout<<" 請(qǐng)輸入教師編號(hào):"cin>>tn;cout<<" 請(qǐng)輸入該教師可任教的課數(shù):"cin>>m;cout<<" 請(qǐng)輸入該教師所能任教的課程編號(hào):"while(m-)cin>>tc;mattntc = true;WriteMatrix(mat);( 4)輸出其中一種最大匹配void solve(vector<teacher> tea,vector<course>

21、 cou)/輸出其中一種最大匹配ANS();while(ans-)/輸出其中一種最大匹配memset(p,0,sizeof(p);for(int i = 1;i <= t;i+)/求度for(int a = 1;a <= c;a+)if(matia = true) pi+;int MIN = 0;for(int i = 1;i <= t;i+)/初始化 MINif(pi != 0)MIN = i;break;- 9 - 歡迎下載。for(int i = 1;i <= t;i+)/if(pMIN > pi && pi != 0) MIN = i;fo

22、r(int i = 1;i <= c;i+)/if(matMINi = true) cout<<teaMIN-1.name<<" for(int a = 1;a <= c;a+)/matMINa = false;for(int a = 1;a <= t;a+)/ matai = false;break;ReadMatrix(mat);求最小度處理最小度老師任 "<<<<" 課 "<<endl;刪除該老師刪除該課4.2.2 崔超設(shè)計(jì)實(shí)現(xiàn)( 1 )匈牙利算法求

23、最大匹配數(shù)bool Find(int i)/匈牙利算法for(int n = 1;n <= t;n+)/為每位老師找一個(gè)課if(matin && !usen)/如果老師找到課并且這個(gè)課沒有其他老師任教usen = true;/標(biāo)記此課有老師任教if(pn = 0|Find(pn)/pi這位老師還沒找到課或者 能夠找到他的課pn = i;/標(biāo)記此老師有課return true;return false;void ANS()/ 求最大匹配數(shù)ans = 0;memset(p,0,sizeof(p);for(int i = 1;i <= c;i+)memset(use,0,

24、sizeof(use);if(Find(i) ans+;void Get_t_c(vector<teacher> tea,vector<course> cou)/獲取教師數(shù)和課程數(shù)t = tea.size();c = cou.size();(2)數(shù)據(jù)刪除void DeleteTeacher(vector<teacher> &tea)/ 刪除教師信息 teacher a;vector<teacher>:iterator it = tea.begin();cout<<" 請(qǐng)輸入刪除教師名字：n"cin>&

25、gt;;while(it != tea.end()if(strcmp(,(*it).name) = 0)it = tea.erase(it);elseit+;cout<<" 教師刪除成功：n"PrintTeacher(tea);WriteTeacher(tea);ReadTeacher(tea);void DeleteCourse(vector<course> &cou)/ 刪除課程信息 course a;vector<course>:iterator it = cou.begin();cout<&l

26、t;" 請(qǐng)輸入刪除課程名稱：n"cin>>;while(it != cou.end()if(strcmp(,(*it).name) = 0)it = cou.erase(it);elseit+;cout<<" 教師刪除成功：n"PrintCourse(cou);WriteCourse(cou);ReadCourse(cou);( 1 )數(shù)據(jù)輸出void PrintTeacher(vector<teacher> tea)/4.2.3 吳越設(shè)計(jì)實(shí)現(xiàn)輸出教師信息cout<<" 教

27、師名單如下："<<endl;for(int i = 0;i < tea.size();i+)cout<<<<endl;void PrintCourse(vector<course> cou)/ 輸出課程信息cout<<" 課程名單如下："<<endl;for(int i = 0;i < cou.size();i+)cout<<<<endl;void PrintMartix(matrix mat,vector<teac

28、her> tea,vector<course> cou)/輸出鄰接矩陣for(int i = 0;i < N;i+)for(int n = 0;n < N;n+)if(matin = true)cout<<<<"老師可以任"<<<<" 課 "<<endl;void PrintTeacherPlus(vector<teacher> tea)/輸出教師信息和編號(hào)cout<<" 教師名單及編號(hào)如

29、下："<<endl;for(int i = 0;i < tea.size();i+)cout<<" 編號(hào)： "<<i+1<<" "<<" 姓名 "<<<<endl;void PrintCoursePlus(vector<course> cou)/輸出課程信息和編號(hào)cout<<" 課程名單及編號(hào)如下："<<endl;for(int i = 0;i < cou.

30、size();i+)cout<<" 編號(hào)： "<<i+1<<" "<<" 名稱 "<<<<endl;(2)文件重置void Reset(matrix &mat,vector<teacher> &tea,vector<course> &cou)/重置文件FILE *Tea;if(Tea = fopen("teacher.txt","w+") = NULL)/打開

31、操作不成功printf("teacher.txt can not be opened n");exit(1);/結(jié)束程序的執(zhí)行fclose(Tea);FILE *Cou;if(Cou = fopen("course.txt","w+") = NULL)/打開操作不成功printf("course.txt can not be opened n");exit(1);/結(jié)束程序的執(zhí)行精品文檔fclose(Cou);FILE *Mat;打開操作不成功if(Mat = fopen("matrix.txt"

32、;,"w+") = NULL)/ printf("matrix.txt can not be opened n");exit(1);/結(jié)束程序的執(zhí)行fclose(Mat);ReadTeacher(tea);ReadCourse(cou);ReadMatrix(mat);(3)主函數(shù)int main()vector<teacher> tea;vector<course> cou;printf("歡迎使用教務(wù)排課系統(tǒng)n");printf("正在導(dǎo)入數(shù)據(jù)庫。n");ReadTeacher(tea)

33、;ReadCourse(cou);ReadMatrix(mat);printf(" 導(dǎo)入數(shù)據(jù)庫成功！n");printf(" 請(qǐng)按任意鍵進(jìn)入主菜單n");system ("pause");system ("cls");while(1)printf("1.添加教師n");printf("2.添加課程n");printf("3.添加教師可任課課程n");printf("4.輸出教師信息n");printf("5.輸出課程信息n&q

34、uot;);printf("6.輸出教師可任課課程n");printf("7.求最大匹配數(shù)n");printf("8.求一種最大匹配方案n");printf("9.清空數(shù)據(jù)庫n");printf("10.刪除教師信息：n");printf("11.刪除課程信息：n");printf("12.關(guān)閉程序：n");printf("請(qǐng)輸入正確的選項(xiàng)");int i = 0;scanf("%d",&i);getchar

35、();switch(i)case 1:AddTeacher(tea);break;case 2:AddCourse(cou);break;case 3:AddMatrix(mat,tea,cou);break;case 4:PrintTeacher(tea);break;case 5:PrintCourse(cou);break;case 6:PrintMartix(mat,tea,cou);break;case 7:Get_t_c(tea,cou);ANS();printf("%dn",ans);break;case 8:Get_t_c(tea,cou);solve(te

36、a,cou);break;case 9:Reset(mat,tea,cou);break;case 10:DeleteTeacher(tea);memset(mat,0,sizeof(mat);break;case 11:DeleteCourse(cou);memset(mat,0,sizeof(mat);break;case 12:system ("cls");printf("謝謝使用！");exit(0);break;default:printf("輸入的選項(xiàng)不正確：");system ("pause");sy

37、stem ("cls");return 0;5 測(cè)試與調(diào)試5.1 個(gè)人測(cè)試(按組員分小節(jié))5.1.1 邵威測(cè)試/ 測(cè)試內(nèi)容：輸出一種最大匹配#include<stdio.h>#include<string.h>#include<iostream>using namespace std;/ 測(cè)試序列5 5 2 2 5 3 2 3 4 2 1 5 3 1 2 5 1 2#define N 205#define SIZEt 50;#define SIZEc 50;int n,m,x,u,ans;bool useN;int pN;bool lin

38、eNN;typedef struct teacherchar name32;teacher;typedef struct coursechar name32;course;bool find(int x)/ 匈牙利算法為每位老師找一個(gè)課如果老師找到課并且這個(gè)課沒有其他老師任教 標(biāo)記此課有老師任教if(pi = 0|find(pi)/pi這位老師還沒找到課或者 能夠找到他的課for(int i = 1;i <= m;i+)/ if(linexi && !usei)/ usei = true;/pi = x;/標(biāo)記此老師有課return true;return false;v

39、oid solve()/ 輸出其中一種最大匹配while(ans-)/輸出其中一種最大匹配memset(p,0,sizeof(p);for(int i = 1;i <= n;i+)/求度for(int a = 1;a <= m;a+) if(lineia = true) pi+;int MIN = 0;for(int i = 1;i <= n;i+)/初始化 MINif(pi != 0)MIN = i;break;for(int i = 1;i <= n;i+)/求最小度if(pMIN > pi && pi != 0) MIN = i;for(in

40、t i = 1;i <= m;i+)/處理最小度if(lineMINi = true)printf("第d老師任第 d門課n",MIN,i);for(int a = 1;a <= m;a+)/刪除該老師lineMINa = false;for(int a = 1;a <= n;a+)/刪除該課lineai = false; break;void ANS()/ 求最大匹配數(shù)- 13 。-歡迎下載精品文檔for(int i = 1;i <= n;i+)memset(use,0,sizeof(use);if(find(i) ans+;int main()p

41、rintf("請(qǐng)輸入老師人數(shù)和課程的數(shù)目")；scanf("%d%d”,&n,&m);/n 老師，m 課ans=0;memset(line,0,sizeof(line);memset(p,0,sizeof(p);printf(" 按順序輸入老師能上的課程 n");for(int i = 1;i <= n;i+)/構(gòu)建鄰接矩陣i表示第i位老師u表示第i門課scanf("%d",&x);while(x-)scanf("%d",&u);lineiu = true;ANS()

42、;solve();return 0;5.1.2 崔超測(cè)試/測(cè)試內(nèi)容：匈牙利算法輸出最大匹配數(shù)#include<stdio.h>#include<string.h>#include<iostream>using namespace std;/ 測(cè)試序列5 5 2 2 5 3 2 3 4 2 1 5 3 1 2 5 1 2#define N 205#define SIZEt 50;#define SIZEc 50;int n,m,x,u,ans;bool useN;int pN;bool lineNN;typedef struct teacherchar nam

43、e32;teacher;typedef struct coursechar name32;course;bool find(int x)/ 匈牙利算法for(int i = 1;i <= m;i+)/為每位老師找一個(gè)課if(linexi && !usei)/如果老師找到課并且這個(gè)課沒有其他老師任教usei = true;/標(biāo)記此課有老師任教if(pi = 0|find(pi)/pi這位老師還沒找到課或者 能夠找到他的課pi = x;/標(biāo)記此老師有課return true;return false; void ANS()/ 求最大匹配數(shù)for(int i = 1;i <

44、;= n;i+)memset(use,0,sizeof(use);if(find(i) ans+;printf("%dn",ans);int main()printf(" 請(qǐng)輸入老師人數(shù)和課程的數(shù)目");scanf("%d%d”,&n,&m);/n 老師，m 課ans=0;memset(line,0,sizeof(line);memset(p,0,sizeof(p);printf(" 按順序輸入老師能上的課程n");for(int i = 1;i <= n;i+)/構(gòu)建鄰接矩陣i 表示第 i 位老師 u

45、 表示第 i 門課scanf("%d",&x);while(x-)scanf("%d",&u);lineiu = true;ANS();return 0;5.1.3吳越測(cè)試吳越設(shè)計(jì)部分的測(cè)試將在系統(tǒng)運(yùn)行中給出，在此不再贅述。5.2系統(tǒng)運(yùn)行初始化界面：-15獨(dú)迎下載精品文檔-21獨(dú)迎下載耳：，上二 HA據(jù)范庭 任導(dǎo)效任任 - 灰LIE仔謂濡王采單界面:功能一：添加教師（添加課程，教師可任課課程類似，不逐一演示）功能二：輸出教師信息（輸出課程，教師可任課課程類似，不逐一演示）功能三：求最大匹配數(shù)1申加教師 已弗如深理a渾加彼邦可任深課程 :i

46、語出於麗信旦 工輸出潺桂尼E 心轄出教帥可佇課黑理 【泵苗L2配場(chǎng)&.求一腫最大匹配方案 足清空勤揩庫 10.翻除鼓時(shí)信皂： ILf蕓課程信息i 12.關(guān)司存序 離語入正通妁選項(xiàng)7功能四：求一種最大匹配方案功能六：清空數(shù)據(jù)庫功能七：刪除教師（刪除課程類似，不逐一演示）E播加課隹 赤兀裁培可任照理度 偉國戟用信息 u希巴便程信息 E 一驗(yàn)巴教huh三出現(xiàn)程 E京最大匕配彼 艮單一和星丁江配方安 ,港三處據(jù)國 .（.可.摩工.*七9： Ri.ei除調(diào)件侑.由 -5關(guān)母程序: 灣省人止沖的丘慶10 K近人聊除我At名字小王k技任意罐組紙一，一功能八：退出6課題總結(jié)6.1 課題性能分析本次課程

47、設(shè)計(jì)，我們經(jīng)過詳細(xì)的前期調(diào)研和問題分析，按照題目要求，圖作為基本的數(shù)據(jù)結(jié)構(gòu)，利用匈牙利算法求解最大匹配數(shù)，輸出一種最大匹配匈牙利算法時(shí)間復(fù)雜度:O (n)空間復(fù)雜度:O (1)輸出一種最大匹配時(shí)間復(fù)雜度：O (n2)空間復(fù)雜度：O (1)6.2 課題評(píng)價(jià)與與團(tuán)隊(duì)協(xié)作本次課程設(shè)計(jì)由三名同學(xué)共同完成，雖然系統(tǒng)仍然有這樣那樣的問題和不足，但更重要的是在這個(gè)過程中大家所學(xué)到的一切。在整個(gè)設(shè)計(jì)和完成的過程中，每位組員都十分認(rèn)真對(duì)待自己負(fù)責(zé)的部分，時(shí)刻保持與其他組員進(jìn)行交流，就完成課程設(shè)計(jì)任務(wù)中出現(xiàn)的問題和瑕疵進(jìn)行改正和優(yōu)化。小組中人人各司其職，從前期算法討論到最后的調(diào)試優(yōu)化，每個(gè)人都秉持互相尊重，精誠合

48、作的宗旨，使本次課程設(shè)計(jì)的任務(wù)圓滿順利完成。6.3 個(gè)人設(shè)計(jì)小結(jié)(按組員分小節(jié))6.3.1 邵威設(shè)計(jì)小結(jié)我主要輸出一種最大匹配的功能，為了實(shí)現(xiàn)這個(gè)功能，我翻閱了離散數(shù)學(xué)(下)的課本 和課件，將老師所授的算法予以實(shí)現(xiàn)。最大的收獲就是能夠把其他學(xué)科的知識(shí)化為代碼，為我們所用，來解決生活中的問題。通過這次實(shí)驗(yàn)，我復(fù)習(xí)了 C語言文件函數(shù)的使用，學(xué)習(xí)了調(diào)用STL中的vector動(dòng)態(tài)數(shù)組來處理問題，對(duì)STL 了使用有了深刻的認(rèn)識(shí)和體會(huì)，此外我還深切的體會(huì)到團(tuán)隊(duì)合作的重要性，在實(shí)踐過程中不僅要完成好自己的任務(wù)，也要積極配合團(tuán)隊(duì)。 在應(yīng)用的時(shí)候發(fā)現(xiàn)自己的不足，這次課程設(shè)計(jì)不同于平時(shí)練習(xí)，平時(shí)練習(xí)都是小程序雖然

49、知道模塊化編程的好處但精品文檔沒有真正的去實(shí)踐，所以這次實(shí)驗(yàn)讓我體會(huì)很深。6.3.2 崔超設(shè)計(jì)小結(jié)此次課程設(shè)計(jì)，我主要負(fù)責(zé)對(duì)教師課程及關(guān)系矩陣的刪除操作及部分文件的讀寫，我們采用了 c+標(biāo)準(zhǔn)庫中的vector容器,首先我們輸入變量并 while循環(huán)，通過迭代器找到所在 位置，利用STL中vector的刪除函數(shù)將其刪除，然后將數(shù)組中被刪除元素后元素前移一個(gè) 單位，此次我們決定用"+rb" 方式對(duì)文件進(jìn)行讀寫，由此創(chuàng)建一個(gè)二進(jìn)制文件，通過字符大小進(jìn)行輸入輸出較為方便。通過這個(gè)課程設(shè)計(jì)，我對(duì)類的使用進(jìn)行了復(fù)習(xí)，加深了掌握程度，同時(shí)也用了鏈表這一數(shù)據(jù)結(jié)構(gòu)， 對(duì)其概念有了更深刻的認(rèn)識(shí)

50、，也熟練了自己對(duì)數(shù)據(jù)結(jié)構(gòu)的使用。這一部分由自己獨(dú)立完成，切實(shí)鍛煉了自己的編程能力，并且也得到同學(xué)對(duì)一些錯(cuò)誤和細(xì)節(jié)上的幫忙修改訂正，和對(duì)我的不斷鼓勵(lì)，在此非常感謝他們。6.3.3 吳越設(shè)計(jì)小結(jié)由于我在小組分工中負(fù)責(zé)A 類的可視化部分, 所以只結(jié)合Vector 模板類 , 編寫了輸出教師、課程以及教師與課程關(guān)系的函數(shù), 然后由于數(shù)據(jù)是存儲(chǔ)在外部文件當(dāng)中, 因而同時(shí)負(fù)責(zé)了編寫重置文件的函數(shù). 本次實(shí)驗(yàn)沒有采用可視化, 所以我還簡(jiǎn)單地對(duì)主函數(shù)界面進(jìn)行了美化 , 使其功能劃分更加清晰便于操作.通過此次課程設(shè)計(jì)，我對(duì)數(shù)據(jù)結(jié)構(gòu)知識(shí)有了更加熟練的應(yīng)用, 對(duì)模板類有了更加深刻的認(rèn)識(shí) , 深深體會(huì)到了它的便利性.

51、 我認(rèn)為在實(shí)際的上機(jī)操作過程中，不僅讓我們了解數(shù)據(jù)結(jié)構(gòu)的理論知識(shí)，更重要的是培養(yǎng)解決實(shí)際問題的能力，所以相信通過此次課程設(shè)計(jì)任務(wù)，可以提高我分析設(shè)計(jì)的能力和編程能力，為后續(xù)的學(xué)習(xí)打好基礎(chǔ)。以后我會(huì)努力學(xué)好每門專業(yè)課，讓自己擁有更多的知識(shí)，解決更多問題。附錄AA-1課題程序設(shè)計(jì)分工課題程序設(shè)計(jì)分工學(xué)號(hào)姓名程序設(shè)計(jì)函數(shù)原型、類功能說明20154349邵威typedef struct teacher/教師類型typedef struct course/課程類型typedef bool matrixNN;/關(guān)系類型數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)void ReadTeacher(vector<teacher>

52、 &tea) ；void ReadCourse(vector<course> &cou) ；void ReadMatrix(matrix &mat) ；文件讀取void WriteTeacher(vector<teacher> tea)；void WriteCourse(vector<course> cou)；void WriteMatrix(matrix mat)；文件寫入void AddTeacher(vector<teacher> &tea) ；void AddCourse(vector<course&

53、gt; &cou) ；VoidAddMatrix(matrix&mat,vector<teacher>tea,vector<course> cou) ；數(shù)據(jù)添加void solve(vector<teacher>tea,vector<course>cou)；輸出一種最大匹配20154499崔超void DeleteTeacher(vector<teacher> &tea)；void DeleteCourse(vector<course> &cou) ；數(shù)據(jù)刪除void Get_t_c(vec

54、tor<teacher>tea,vector<course>cou)；bool Find(int i)；void ANS();匈牙利算法求最大 匹配數(shù)20154306吳越void PrintTeacher(vector<teacher> tea)；void PrintCourse(vector<course> cou)；Void PrintMartix(matrixmat,vector<teacher>tea,vector<course> cou);Void PrintTeacherPlus(vector<teach

55、er> tea)；void PrintCoursePlus(vector<course> cou)；數(shù)據(jù)輸出voidReset(matrix&mat,vector<teacher>&tea,vector<course> &cou) ；文件重置int main()；主函數(shù)設(shè)計(jì)工作量比重：邵威：崔超：吳越 =4 : 3 : 3A-2課題報(bào)告分工課題報(bào)告分工章節(jié)內(nèi)容完成人1課題概述1.1課題任務(wù)邵威1.2課題原理2需求分析2.1課題調(diào)研邵威2.2功能需求3方某設(shè)計(jì)3.1總體功能設(shè)計(jì)邵威3.2數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)3.3函數(shù)原型設(shè)計(jì)3.4用戶界面

56、設(shè)計(jì)4方案實(shí)現(xiàn)4.1開發(fā)環(huán)境與工具邵威4.2個(gè)人設(shè)計(jì)實(shí)現(xiàn)4.2.1邵威4.2.2崔超4.2.3吳越5測(cè)試與調(diào)試5.1個(gè)人測(cè)試5.1.1邵威5.1.2崔超5.1.3吳越5.2系統(tǒng)運(yùn)行吳越6課題總結(jié)6.1課題性能分析邵威6.2課題評(píng)價(jià)與團(tuán)隊(duì)協(xié)作邵威6.3個(gè)人設(shè)計(jì)小結(jié)6.3.1邵威6.3.2崔超6.3.3吳越-23獨(dú)迎下載精品文檔附錄 B 源程序代碼/ 教務(wù)排課表的二分圖問題#include<string.h>#include<iostream>#include<stdio.h>#include<stdlib.h>#include<vector&

57、gt;#define N 200using namespace std;typedef struct teacherchar name32;teacher;typedef struct coursechar name32;course;typedef bool matrixNN;matrix mat;/ 全局變量鄰接矩陣int t,c,ans;bool useN;int pN;void ReadTeacher(vector<teacher> &tea)/ 讀取教師文件tea.clear();FILE *Tea;if(Tea = fopen("teacher.txt","rb+") = NULL)/打開操作不成功printf("teacher.txt can not be opened n");exit(1);/結(jié)束程序的執(zhí)行teacher a;while(fread(&a,sizeof(struct teacher),1,Tea) != 0) tea.push_back(a);fclose