數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告教學(xué)計(jì)劃編制

數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告題目:教學(xué)計(jì)劃編制目錄一、需求分析.....................................................................31.1系統(tǒng)概述...................................................................31.1.1研究背景..................................................................31.1.2研究意義及目的........................................................31.2具體分析......................................................................41.2.1功能需求分析...........................................................41.2.2運(yùn)行環(huán)境..................................................................4二、總體設(shè)計(jì)......................................................................5三、數(shù)據(jù)儲(chǔ)存結(jié)構(gòu)的設(shè)計(jì)...........................................................6 3.1采用鄰接表的方式儲(chǔ)存先修關(guān)系圖 ..............................................6 3.2鄰接表儲(chǔ)存的代碼實(shí)現(xiàn) .........................................................6 3.2.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) .............................................................63.2.2AOV圖的創(chuàng)建代碼......................................................7四、功能實(shí)現(xiàn)算法設(shè)計(jì)...............................................................9 4.1拓?fù)渑判蛩惴ㄔO(shè)計(jì) ............................................................9 4.2獲取各個(gè)頂點(diǎn)的入度算法設(shè)計(jì) ................................................114.3分類型輸出算法設(shè)計(jì).........................................................11五、程序代碼.......................................................................12六、運(yùn)行結(jié)果.....................................................................20七、課程設(shè)計(jì)總結(jié)...................................................................22教學(xué)計(jì)劃編制問題課程設(shè)計(jì)報(bào)告一、需求分析1.1系統(tǒng)概述1.1.1研究背景大學(xué)的每個(gè)專業(yè)都要制定教學(xué)計(jì)劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長(zhǎng)度和學(xué)分上限值均相等。每個(gè)專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時(shí)間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個(gè)學(xué)期。試在這樣的前提下設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序。1.1.2研究意義及目的具體說來，教學(xué)計(jì)劃編制是以課程先修關(guān)系為基礎(chǔ)，分析教學(xué)中的問題和需要，確定教學(xué)目標(biāo)，建立解決問題的步驟，合理組合和安排各種教學(xué)要素，為優(yōu)化教學(xué)效果而制定實(shí)施方案的系統(tǒng)的計(jì)劃過程。由此可以看出，教學(xué)設(shè)計(jì)的過程實(shí)際上就是為教學(xué)活動(dòng)制定藍(lán)圖的過程。通過教學(xué)設(shè)計(jì)，教師可以對(duì)教學(xué)活動(dòng)的基本過程有個(gè)整體的把握，可以根據(jù)教學(xué)情境的需要和教育對(duì)象的特點(diǎn)確定合理的教學(xué)目標(biāo)，選擇適當(dāng)?shù)慕虒W(xué)方法、教學(xué)略策，采用有效的教學(xué)手段，創(chuàng)設(shè)良好的教學(xué)環(huán)境，實(shí)施可行的評(píng)價(jià)方案，從而保證教學(xué)活動(dòng)的順利進(jìn)行。另外，通過教學(xué)設(shè)計(jì)，教師還可以有效地掌握學(xué)生學(xué)習(xí)的初始狀態(tài)和學(xué)習(xí)后的狀態(tài)，從而及時(shí)調(diào)整教學(xué)策略、方法，采取必要的教學(xué)措施，為下一階段的教學(xué)奠定良好基礎(chǔ)。從這個(gè)意義上說，教學(xué)設(shè)計(jì)是教學(xué)活動(dòng)得以順利進(jìn)行的基本保證。好的教學(xué)設(shè)計(jì)可以為教學(xué)活動(dòng)提供科學(xué)的行動(dòng)綱領(lǐng)，使教師在教學(xué)工作中事半功倍，取得良好的教學(xué)效果。忽視教學(xué)設(shè)計(jì)，則不僅難以取得好的教學(xué)效果，而且容易使教學(xué)走彎路，影響教學(xué)任務(wù)的完成。1.2具體分析1.2.1功能需求分析(1)輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號(hào)、學(xué)分和直接先修課的課程號(hào)。(2)允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個(gè)學(xué)期中。1.2.2運(yùn)行環(huán)境本系統(tǒng)源代碼是使用VisualStudio2015編寫編制完成，在該平臺(tái)上能夠正常運(yùn)行。生成通用的exe后對(duì)計(jì)算機(jī)的硬件需求很低，幾乎日常使用的計(jì)算機(jī)都能夠正常運(yùn)行。二、總體設(shè)計(jì)在win32控制臺(tái)下，顯示出一個(gè)簡(jiǎn)易的界面，供用戶選擇所需要的功能。由用戶輸入課程號(hào)和課程學(xué)分，再根據(jù)提示輸入先修關(guān)系，輸入學(xué)期總數(shù)和學(xué)期學(xué)分上限，然后根據(jù)時(shí)間優(yōu)先或平均分配排序出不同的方案。輸入課程號(hào)輸入課程號(hào)，課程學(xué)分輸入課程先修關(guān)系輸入學(xué)期數(shù),學(xué)期學(xué)分上限課程盡量集中前幾個(gè)學(xué)期各學(xué)期負(fù)擔(dān)均勻教學(xué)計(jì)劃編制系統(tǒng)總體設(shè)計(jì)三、數(shù)據(jù)儲(chǔ)存結(jié)構(gòu)的設(shè)計(jì)3.1采用鄰接表的方式儲(chǔ)存先修關(guān)系圖眾多課程以及其先修關(guān)系組成在一起，剛好構(gòu)成一個(gè)AOV網(wǎng)，對(duì)于這個(gè)AOV網(wǎng)，采取鄰接表的方式儲(chǔ)存。鄰接表中，對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊（對(duì)有向圖是以頂點(diǎn)Vi為尾的?。?。鄰接表中的表結(jié)點(diǎn)和頭結(jié)點(diǎn)結(jié)構(gòu)：表結(jié)點(diǎn):頭節(jié)點(diǎn)頭節(jié)點(diǎn):AdjvexNextarcinfoDatafiDatafirstarc圖的鄰接表舉例：3.2鄰接表儲(chǔ)存的代碼實(shí)現(xiàn)3.2.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) structcourse //應(yīng)用于data,保存課程號(hào)和學(xué)分。依據(jù)課程號(hào)的先修關(guān)系和學(xué)分進(jìn)行拓?fù)渑判騵stringcourse_no;intcredit;};structArcNode//邊/弧鄰接表結(jié)點(diǎn){ intadjvex; //鄰接點(diǎn)下標(biāo)//intweight;//權(quán)值A(chǔ)rcNode*nextarc;};structVNode //頂點(diǎn){ coursedata; //數(shù)值域ArcNode*firstarc;};classALGraph{private:VNode*vertices;intvexNum,arcNum;//頂點(diǎn)數(shù)邊數(shù)bool*visited;//用于判斷是否訪問過，遍歷時(shí)使用}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<<"請(qǐng)輸入分別輸入課程個(gè)數(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<<"請(qǐng)輸入第"<<i+1<<"門課程，學(xué)分:";cin>>vertices[i].data.course_no;cin>>vertices[i].data.credit;}system("cls");for(intk=0;k<arcNum;k++){ cout<<"請(qǐng)輸入第"<<k+1<<"個(gè)先修關(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;}}四、功能實(shí)現(xiàn)算法設(shè)計(jì)4.1拓?fù)渑判蛩惴ㄔO(shè)計(jì)對(duì)于有向圖采用鄰接表存儲(chǔ)結(jié)構(gòu)，并設(shè)置一個(gè)數(shù)組indegree來保存圖中各頂點(diǎn)的入度值。而為了方便選擇入度為0的頂點(diǎn)，再設(shè)置一個(gè)隊(duì)列來保存所有入度為0的頂點(diǎn)。而拓?fù)渑判虻姆椒ǘ?，拓?fù)渑判虻年P(guān)鍵問題是第二步，即如何刪除一個(gè)頂點(diǎn)以及所有從它發(fā)出的弧。由于圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，頻繁的進(jìn)行刪除操作勢(shì)必會(huì)影響算法的效率，實(shí)際上，在輸出一個(gè)頂點(diǎn)后，之所以要?jiǎng)h除它以及所有從它發(fā)出的弧，是為了方便找到當(dāng)前入度為0的頂點(diǎn)。在設(shè)計(jì)算法時(shí)，刪除一個(gè)頂點(diǎn)以及所有從它發(fā)出的弧可用將它的所有鄰接頂點(diǎn)的入度值減1來代替，而不是真正的在物理上刪除它。拓?fù)渑判蛩惴ǖ脑O(shè)計(jì)可用下面四個(gè)步驟來完成：遍歷整個(gè)圖的鄰接表求所有頂點(diǎn)的入度值。將入度為0的頂點(diǎn)入隊(duì)。當(dāng)隊(duì)列不為空時(shí)，執(zhí)行出隊(duì)操作。出隊(duì)的頂點(diǎn)必定是入隊(duì)為0的頂點(diǎn)，輸出他即可。然后將它的所有的鄰接頂點(diǎn)的入度值減1，若到了零，則再將其入隊(duì)。重復(fù)這個(gè)過程，直到隊(duì)列為空為止。若已經(jīng)輸出的頂點(diǎn)個(gè)數(shù)等于圖的頂點(diǎn)個(gè)數(shù)，則輸出的是一個(gè)拓?fù)渑判颍駝t，說明圖中存在回路。遍歷鄰接表，求所有遍歷鄰接表，求所有頂點(diǎn)的入度出度頂點(diǎn)的所有鄰接頂點(diǎn)的入度‐1入隊(duì)出隊(duì)拓?fù)渑判虺晒?，正常輸出入?0？否是否隊(duì)列為空？是是出隊(duì)個(gè)數(shù)=頂點(diǎn)個(gè)數(shù)？否該圖存在回路，拓?fù)渑判蚴⊥負(fù)渑判蛩惴ㄔO(shè)計(jì)4.2獲取各個(gè)頂點(diǎn)的入度算法設(shè)計(jì)傳入數(shù)組傳入數(shù)組a保存入度從1遍歷頂點(diǎn)遍歷點(diǎn)下標(biāo)+1遍歷點(diǎn)下標(biāo)+1遍歷該定點(diǎn)的所有鄰接頂點(diǎn)是是是否超出下標(biāo)范圍？否否是否超出下標(biāo)范圍？是當(dāng)前頂點(diǎn)？是是否是否為最后一個(gè)鄰接頂點(diǎn)？是否否個(gè)否該鄰接頂點(diǎn)是否為當(dāng)前操作點(diǎn)？是遍歷到下一個(gè)鄰接頂點(diǎn)當(dāng)前操作的頂點(diǎn)入度+1獲得所有頂點(diǎn)入度算法4.3分類型輸出算法設(shè)計(jì)輸入學(xué)期數(shù)，輸入學(xué)期數(shù)，學(xué)期學(xué)分上限各學(xué)期學(xué)習(xí)負(fù)擔(dān)均勻課程集中到前幾個(gè)學(xué)期課程數(shù)除以學(xué)期數(shù)均分按照學(xué)分累加判斷五、程序代碼#include<iostream>#include<stack>//直接用系統(tǒng)封裝的模板棧#include<queue>//系統(tǒng)封裝的模板隊(duì)列#include<string>#include<fstream>usingnamespacestd;stringresult;structcourse //應(yīng)用于data,保存課程號(hào)和學(xué)分。依據(jù)課程號(hào)的先修關(guān)系和學(xué)分進(jìn)行拓?fù)渑判騵stringcourse_no;intcredit;};structArcNode//邊/弧鄰接表結(jié)點(diǎn){ intadjvex; //鄰接點(diǎn)下標(biāo)//intweight;//權(quán)值A(chǔ)rcNode*nextarc;};structVNode //頂點(diǎn){coursedata; //數(shù)值域ArcNode*firstarc;};classALGraph{private:VNode*vertices;intvexNum,arcNum;//頂點(diǎn)數(shù)邊數(shù)bool*visited;//用于判斷是否訪問過，遍歷時(shí)使用public: ALGraph() //構(gòu)造函數(shù)確定定點(diǎn)數(shù)和邊的數(shù)量{}~ALGraph()//析構(gòu)函數(shù)，釋放鄰接表中各邊表結(jié)點(diǎn)的存儲(chǔ)空間{}boolIsExitint(i){} intLocated(VNodev){for(inti=0;i<vexNum;i++){if(vertices[i].data.course_no==v.data.course_no) returni;}return-1;}voidCreatALGraph() //此圖為有向圖{cout<<"請(qǐng)輸入分別輸入課程個(gè)數(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<<"請(qǐng)輸入第"<<i+1<<"門課程，學(xué)分:";cin>>vertices[i].data.course_no;cin>>vertices[i].data.credit;}system("cls");for(intk=0;k<arcNum;k++){ cout<<"請(qǐng)輸入第"<<k+1<<"個(gè)先修關(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) //獲取各個(gè)頂點(diǎn)的入度{for(inti=0;i<vexNum;i++){intcount=0;ArcNode*p;for(intj=0;j!&j=<i&vexNum;j++){p=vertices[j].firstarc;while(p){if(p->adjvex==i ) count++;p=p->nextarc;}}indegree[i]=count;}} voidtopologicalSort(inta[]) //數(shù)組a獲得拓?fù)渑判蚪Y(jié)果的下標(biāo){intv,count=0,*indegree;ArcNode*p;queue<int>Q;indegree=newint(vexNum);findIndegree(indegree);for(v=0;v<vexNum;v++)if(indegree[v]==.push(v);0)Qwhile(!Q.empty()){ a[count]=Q.front(); //用數(shù)組記錄拓?fù)渑判虻奈恢孟聵?biāo)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圖存在回路)，請(qǐng)重新創(chuàng)建！"<<endl; exit(0);}elsecout<<"系統(tǒng)已完成規(guī)劃！"<<endl;}voidfinal_sort(){int*a=newint(vexNum);//申請(qǐng)動(dòng)態(tài)數(shù)組存放拓?fù)渑判蚪Y(jié)果topologicalSort(a);system("cls");intterm_num; //學(xué)期數(shù)inthest_score;//學(xué)期最高學(xué)分cout<<"系統(tǒng)已完成規(guī)劃！"<<endl;cout<<"請(qǐng)輸入學(xué)期數(shù)，學(xué)期學(xué)分上限：";cin>>term_num>>hest_score;inti;cout<<"********************************************************"<<endl;cout<<"**"<<endl; cout<<"* 系統(tǒng)已經(jīng)完成規(guī)劃，請(qǐng)選擇輸出方案*"<<endl;cout<<"**"<<endl;cout<<"**"<<endl;1.學(xué)習(xí)負(fù)擔(dān)盡量均勻。cout<<"*2.盡可能地集中在前幾個(gè)學(xué)期中。*"<<endl;cout<<"**"<<endl;cout<<"********************************************************"<<endl;cout<<"請(qǐng)輸入您要選擇的功能：";cin>>i;switch(i){case1: //學(xué)習(xí)負(fù)擔(dān)盡量均勻。{fstreamfile1("G:\\text.txt",ios::out||ios::app);system("cls")int;x=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: //盡可能地集中在前幾個(gè)學(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<<"*能。 *"<<endl;cout<<"**"<<endl;歡迎進(jìn)入教學(xué)計(jì)劃編制系統(tǒng)，請(qǐng)根據(jù)提示選擇操作功cout<<"**"<<endl;