數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計報告題目:教學(xué)計劃編制學(xué)生姓名：吳深深學(xué)號：201420181013班級：1421801Z指導(dǎo)老師：高永平

目錄一、需求分析 31.1系統(tǒng)概述 31.1.1研究背景 31.1.2研究意義及目的 31.2具體分析 41.2.1功能需求分析 41.2.2運行環(huán)境 4二、總體設(shè)計 5三、數(shù)據(jù)儲存結(jié)構(gòu)的設(shè)計 63.1采用鄰接表的方式儲存先修關(guān)系圖 63.2鄰接表儲存的代碼實現(xiàn) 63.2.1數(shù)據(jù)結(jié)構(gòu)設(shè)計 63.2.2AOV圖的創(chuàng)建代碼 7四、功能實現(xiàn)算法設(shè)計 94.1拓撲排序算法設(shè)計 94.2獲取各個頂點的入度算法設(shè)計 114.3分類型輸出算法設(shè)計 11五、程序代碼 12六、運行結(jié)果 20七、課程設(shè)計總結(jié) 22

教學(xué)計劃編制問題課程設(shè)計報告一、需求分析1.1系統(tǒng)概述1.1.1研究背景大學(xué)的每個專業(yè)都要制定教學(xué)計劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限值均相等。每個專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學(xué)期。試在這樣的前提下設(shè)計一個教學(xué)計劃編制程序。1.1.2研究意義及目的具體說來，教學(xué)計劃編制是以課程先修關(guān)系為基礎(chǔ)，分析教學(xué)中的問題和需要，確定教學(xué)目標，建立解決問題的步驟，合理組合和安排各種教學(xué)要素，為優(yōu)化教學(xué)效果而制定實施方案的系統(tǒng)的計劃過程。由此可以看出，教學(xué)設(shè)計的過程實際上就是為教學(xué)活動制定藍圖的過程。通過教學(xué)設(shè)計，教師可以對教學(xué)活動的基本過程有個整體的把握，可以根據(jù)教學(xué)情境的需要和教育對象的特點確定合理的教學(xué)目標，選擇適當?shù)慕虒W(xué)方法、教學(xué)策略，采用有效的教學(xué)手段，創(chuàng)設(shè)良好的教學(xué)環(huán)境，實施可行的評價方案，從而保證教學(xué)活動的順利進行。另外，通過教學(xué)設(shè)計，教師還可以有效地掌握學(xué)生學(xué)習(xí)的初始狀態(tài)和學(xué)習(xí)后的狀態(tài)，從而及時調(diào)整教學(xué)策略、方法，采取必要的教學(xué)措施，為下一階段的教學(xué)奠定良好基礎(chǔ)。從這個意義上說，教學(xué)設(shè)計是教學(xué)活動得以順利進行的基本保證。好的教學(xué)設(shè)計可以為教學(xué)活動提供科學(xué)的行動綱領(lǐng)，使教師在教學(xué)工作中事半功倍，取得良好的教學(xué)效果。忽視教學(xué)設(shè)計，則不僅難以取得好的教學(xué)效果，而且容易使教學(xué)走彎路，影響教學(xué)任務(wù)的完成。1.2具體分析1.2.1功能需求分析(1)輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號、學(xué)分和直接先修課的課程號。

(2)允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負擔盡量均勻；二是使課程盡可能地集中在前幾個學(xué)期中。1.2.2運行環(huán)境本系統(tǒng)源代碼是使用VisualStudio2015編寫編制完成，在該平臺上能夠正常運行。生成通用的exe后對計算機的硬件需求很低，幾乎日常使用的計算機都能夠正常運行。

二、總體設(shè)計在win32控制臺下，顯示出一個簡易的界面，供用戶選擇所需要的功能。由用戶輸入課程號和課程學(xué)分，再根據(jù)提示輸入先修關(guān)系，輸入學(xué)期總數(shù)和學(xué)期學(xué)分上限，然后根據(jù)時間優(yōu)先或平均分配排序出不同的方案。三、數(shù)據(jù)儲存結(jié)構(gòu)的設(shè)計3.1采用鄰接表的方式儲存先修關(guān)系圖眾多課程以及其先修關(guān)系組成在一起，剛好構(gòu)成一個AOV網(wǎng)，對于這個AOV網(wǎng)，采取鄰接表的方式儲存。鄰接表中，對圖中每個頂點建立一個單鏈表，第i個單鏈表中的結(jié)點表示依附于頂點Vi的邊（對有向圖是以頂點Vi為尾的?。?。鄰接表中的表結(jié)點和頭結(jié)點結(jié)構(gòu)：表結(jié)點:AdjvexNextarcinfo頭節(jié)點:Datafirstarc圖的鄰接表舉例：3.2鄰接表儲存的代碼實現(xiàn)3.2.1數(shù)據(jù)結(jié)構(gòu)設(shè)計structcourse //應(yīng)用于data,保存課程號和學(xué)分。依據(jù)課程號的先修關(guān)系和學(xué)分進行拓撲排序{ stringcourse_no; intcredit;};structArcNode//邊/弧 鄰接表結(jié)點{ intadjvex; //鄰接點下標 //intweight; //權(quán)值 ArcNode*nextarc;};structVNode //頂點{ coursedata; //數(shù)值域 ArcNode*firstarc;};classALGraph{private: VNode*vertices; intvexNum,arcNum; //頂點數(shù)邊數(shù) bool*visited; //用于判斷是否訪問過，遍歷時使用}3.2.2AOV圖的創(chuàng)建代碼intLocated(VNodev) { for(inti=0;i<vexNum;i++) { if(vertices[i].data.course_no==v.data.course_no) returni; } return-1; } voidCreatALGraph() //此圖為有向圖 { cout<<"請輸入分別輸入課程個數(shù)和先修關(guān)系數(shù)（VOA圖的邊數(shù)）："<<endl; cin>>vexNum>>arcNum; vertices=newVNode[vexNum]; visited=newbool[vexNum]; for(inti=0;i<vexNum;i++) { vertices[i].firstarc=NULL; visited[i]=false; } ArcNode*p; inti=0,j; VNodev1,v2; for(;i<vexNum;i++) { cout<<"請輸入第"<<i+1<<"門課程，學(xué)分:"; cin>>vertices[i].data.course_no; cin>>vertices[i].data.credit; } system("cls"); for(intk=0;k<arcNum;k++) { cout<<"請輸入第"<<k+1<<"個先修關(guān)系(先修，直接后修)："<<endl; cin>>v1.data.course_no>>v2.data.course_no; if((i=Located(v1))==-1) { cout<<"error!"<<endl; return; } if((j=Located(v2))==-1) { cout<<"error!"<<endl; return; } p=newArcNode; p->adjvex=j; p->nextarc=vertices[i].firstarc; vertices[i].firstarc=p; } }四、功能實現(xiàn)算法設(shè)計4.1拓撲排序算法設(shè)計對于有向圖采用鄰接表存儲結(jié)構(gòu)，并設(shè)置一個數(shù)組indegree來保存圖中各頂點的入度值。而為了方便選擇入度為0的頂點，再設(shè)置一個隊列來保存所有入度為0的頂點。而拓撲排序的方法而知，拓撲排序的關(guān)鍵問題是第二步，即如何刪除一個頂點以及所有從它發(fā)出的弧。由于圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，頻繁的進行刪除操作勢必會影響算法的效率，實際上，在輸出一個頂點后，之所以要刪除它以及所有從它發(fā)出的弧，是為了方便找到當前入度為0的頂點。在設(shè)計算法時，刪除一個頂點以及所有從它發(fā)出的弧可用將它的所有鄰接頂點的入度值減1來代替，而不是真正的在物理上刪除它。拓撲排序算法的設(shè)計可用下面四個步驟來完成：遍歷整個圖的鄰接表求所有頂點的入度值。將入度為0的頂點入隊。當隊列不為空時，執(zhí)行出隊操作。出隊的頂點必定是入隊為0的頂點，輸出他即可。然后將它的所有的鄰接頂點的入度值減1，若到了零，則再將其入隊。重復(fù)這個過程，直到隊列為空為止。若已經(jīng)輸出的頂點個數(shù)等于圖的頂點個數(shù)，則輸出的是一個拓撲排序，否則，說明圖中存在回路。4.2獲取各個頂點的入度算法設(shè)計4.3分類型輸出算法設(shè)計五、程序代碼#include<iostream>#include<stack> //直接用系統(tǒng)封裝的模板棧#include<queue> //系統(tǒng)封裝的模板隊列#include<string>#include<fstream>usingnamespacestd;stringresult;structcourse //應(yīng)用于data,保存課程號和學(xué)分。依據(jù)課程號的先修關(guān)系和學(xué)分進行拓撲排序{ stringcourse_no; intcredit;};structArcNode//邊/弧 鄰接表結(jié)點{ intadjvex; //鄰接點下標 //intweight; //權(quán)值 ArcNode*nextarc;};structVNode //頂點{ coursedata; //數(shù)值域 ArcNode*firstarc;};classALGraph{private: VNode*vertices; intvexNum,arcNum; //頂點數(shù)邊數(shù) bool*visited; //用于判斷是否訪問過，遍歷時使用public: ALGraph()//構(gòu)造函數(shù)確定定點數(shù)和邊的數(shù)量 { } ~ALGraph()//析構(gòu)函數(shù)，釋放鄰接表中各邊表結(jié)點的存儲空間 { } boolIsExit(inti) { } intLocated(VNodev) { for(inti=0;i<vexNum;i++) { if(vertices[i].data.course_no==v.data.course_no) returni; } return-1; } voidCreatALGraph() //此圖為有向圖 { cout<<"請輸入分別輸入課程個數(shù)和先修關(guān)系數(shù)（VOA圖的邊數(shù)）："<<endl; cin>>vexNum>>arcNum; vertices=newVNode[vexNum]; visited=newbool[vexNum]; for(inti=0;i<vexNum;i++) { vertices[i].firstarc=NULL; visited[i]=false; } ArcNode*p; inti=0,j; VNodev1,v2; for(;i<vexNum;i++) { cout<<"請輸入第"<<i+1<<"門課程，學(xué)分:"; cin>>vertices[i].data.course_no; cin>>vertices[i].data.credit; } system("cls"); for(intk=0;k<arcNum;k++) { cout<<"請輸入第"<<k+1<<"個先修關(guān)系(先修，直接后修)："<<endl; cin>>v1.data.course_no>>v2.data.course_no; if((i=Located(v1))==-1) { cout<<"error!"<<endl; return; } if((j=Located(v2))==-1) { cout<<"error!"<<endl; return; } p=newArcNode; p->adjvex=j; p->nextarc=vertices[i].firstarc; vertices[i].firstarc=p; } } voidfindIndegree(int*indegree) //獲取各個頂點的入度 { for(inti=0;i<vexNum;i++) { intcount=0; ArcNode*p; for(intj=0;j!=i&&j<vexNum;j++) { p=vertices[j].firstarc; while(p) { if(p->adjvex==i)count++; p=p->nextarc; } } indegree[i]=count; } } voidtopologicalSort(inta[])//數(shù)組a獲得拓撲排序結(jié)果的下標 { intv,count=0,*indegree; ArcNode*p; queue<int>Q; indegree=newint(vexNum); findIndegree(indegree); for(v=0;v<vexNum;v++) if(indegree[v]==0)Q.push(v); while(!Q.empty()) { a[count]=Q.front(); //用數(shù)組記錄拓撲排序的位置下標 v=a[count]; count++; Q.pop(); p=vertices[v].firstarc; while(p) { indegree[p->adjvex]--; if(indegree[p->adjvex]==0)Q.push(p->adjvex); p=p->nextarc; } } if(count<vexNum) { cout<<"先修關(guān)系存在問題(AOV圖存在回路)，請重新創(chuàng)建！"<<endl; exit(0); } elsecout<<"系統(tǒng)已完成規(guī)劃！"<<endl; } voidfinal_sort() { int*a=newint(vexNum);//申請動態(tài)數(shù)組存放拓撲排序結(jié)果 topologicalSort(a); system("cls"); intterm_num;//學(xué)期數(shù) inthest_score;//學(xué)期最高學(xué)分 cout<<"系統(tǒng)已完成規(guī)劃！"<<endl; cout<<"請輸入學(xué)期數(shù)，學(xué)期學(xué)分上限："; cin>>term_num>>hest_score; inti; cout<<"********************************************************"<<endl; cout<<"**"<<endl; cout<<"*系統(tǒng)已經(jīng)完成規(guī)劃，請選擇輸出方案*"<<endl; cout<<"**"<<endl; cout<<"*1.學(xué)習(xí)負擔盡量均勻。*"<<endl; cout<<"*2.盡可能地集中在前幾個學(xué)期中。*"<<endl; cout<<"**"<<endl; cout<<"********************************************************"<<endl; cout<<"請輸入您要選擇的功能："; cin>>i; switch(i) { case1: //學(xué)習(xí)負擔盡量均勻。 { fstreamfile1("G:\\text.txt",ios::out||ios::app); system("cls"); intx=1; for(intm=0;m<vexNum;m++) { if(m==0) { file1<<"第"<<x<<"學(xué)期："; cout<<"第"<<x<<"學(xué)期："; x++; } file1<<vertices[a[m]].data.course_no<<" "; cout<<vertices[a[m]].data.course_no<<" "; if((m+1)%(vexNum/term_num+1)==0&&m+1<vexNum) { file1<<endl<<"第"<<x<<"學(xué)期："; cout<<endl<<"第"<<x<<"學(xué)期："; x++; } } file1.close(); break; } case2: //盡可能地集中在前幾個學(xué)期中。 { fstreamfile1("G:\\text.txt",ios::out||ios::app); system("cls"); intx=1; intcount=0; for(intm=0;m<vexNum;m++) { if(m==0) { file1<<"第"<<x<<"學(xué)期："; cout<<"第"<<x<<"學(xué)期："; x++; } count=count+vertices[a[m]].data.credit; if(count<=hest_score) { file1<<vertices[a[m]].data.course_no<<" "; cout<<vertices[a[m]].data.course_no<<" "; } else { file1<<"學(xué)期總學(xué)分："<<count-vertices[a[m]].data.credit<<endl<<"第"<<x<<"學(xué)期："; cout<<"學(xué)期總學(xué)分："<<count-vertices[a[m]].data.credit; cout<<endl<<"第"<<x<<"學(xué)期："; count=0; m--; x++; } } file1<<"學(xué)期總學(xué)分："<<count<<endl; cout<<"學(xué)期總學(xué)分："<<count<<endl; file1.close(); break; } } /* for(inti=0;i<vexNum;i++) { cout<<a[i]; cout<<vertices[a[i]].data.course_no<<" "; } */ } voidfirstSight() { inti; cout<<"****************************************************************"<<endl; cout<<"****************************************************************"<<endl; cout<<"**"<<endl; cout<<"*歡迎進入教學(xué)計劃編制系統(tǒng)，請根據(jù)提示選擇操作功能。*"<<endl; cout<<"**"<<endl; cout<<"*1.創(chuàng)建新的教學(xué)計劃編制。*"<<endl; cout<<"*2.退出。*"<<endl; cout<<"**"<<endl; cout<<"*