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

數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告題目:教學(xué)計(jì)劃編制數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第1頁。數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第1頁。目錄一、需求分析 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ì) 63.1采用鄰接表的方式儲(chǔ)存先修關(guān)系圖 63.2鄰接表儲(chǔ)存的代碼實(shí)現(xiàn) 63.2.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 63.2.2圖的創(chuàng)建代碼 7四、功能實(shí)現(xiàn)算法設(shè)計(jì) 94.1拓?fù)渑判蛩惴ㄔO(shè)計(jì) 94.2獲取各個(gè)頂點(diǎn)的入度算法設(shè)計(jì) 114.3分類型輸出算法設(shè)計(jì) 11五、程序代碼 12六、運(yùn)行結(jié)果 20數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第2頁。七、課程設(shè)計(jì)總結(jié) 22數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第2頁。教學(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í)間長度和學(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ì)劃過程。數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第3頁。由此可以看出，教學(xué)設(shè)計(jì)的過程實(shí)際上就是為教學(xué)活動(dòng)制定藍(lán)圖的過程。通過教學(xué)設(shè)計(jì)，教師可以對教學(xué)活動(dòng)的基本過程有個(gè)整體的把握，可以根據(jù)教學(xué)情境的需要和教育對象的特點(diǎn)確定合理的教學(xué)目標(biāo)，選擇適當(dāng)?shù)慕虒W(xué)方法、教學(xué)策略，采用有效的教學(xué)手段，創(chuàng)設(shè)良好的教學(xué)環(huán)境，實(shí)施可行的評價(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)，使數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第3頁。教師在教學(xué)工作中事半功倍，取得良好的教學(xué)效果。忽視教學(xué)設(shè)計(jì)，則不僅難以取得好的教學(xué)效果，而且容易使教學(xué)走彎路，影響教學(xué)任務(wù)的完成。1.2具體分析1.2.1功能需求分析(1)輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號、學(xué)分和直接先修課的課程號。(2)允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個(gè)學(xué)期中。1.2.2運(yùn)行環(huán)境數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第4頁。本系統(tǒng)源代碼是使用VisualStudio2015編寫編制完成，在該平臺(tái)上能夠正常運(yùn)行。生成通用的exe后對計(jì)算機(jī)的硬件需求很低，幾乎日常使用的計(jì)算機(jī)都能夠正常運(yùn)行。數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第4頁。二、總體設(shè)計(jì)輸入課程號，課程學(xué)分輸入課程先修關(guān)系輸入學(xué)期數(shù),學(xué)期學(xué)分上限在輸入課程號，課程學(xué)分輸入課程先修關(guān)系輸入學(xué)期數(shù),學(xué)期學(xué)分上限課程盡量集中前幾個(gè)學(xué)期各學(xué)期負(fù)擔(dān)均勻數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第5頁。教學(xué)計(jì)劃編制系統(tǒng)總體設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第5頁。三、數(shù)據(jù)儲(chǔ)存結(jié)構(gòu)的設(shè)計(jì)3.1采用鄰接表的方式儲(chǔ)存先修關(guān)系圖眾多課程以及其先修關(guān)系組成在一起，剛好構(gòu)成一個(gè)網(wǎng)，采取鄰接表的方式儲(chǔ)存。鄰接表中，對圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)的邊（對有向圖是以頂點(diǎn)AdjvexNextarcinfo鄰接表中的表結(jié)點(diǎn)和頭結(jié)點(diǎn)結(jié)構(gòu)：AdjvexNextarcinfo頭節(jié)點(diǎn):DataDatafirstarc圖的鄰接表舉例：3.2鄰接表儲(chǔ)存的代碼實(shí)現(xiàn)3.2.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第6頁。structcourse //應(yīng)用于data,保存課程號和學(xué)分依據(jù)課程號的先修關(guān)數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第6頁。系和學(xué)分進(jìn)行拓?fù)渑判騵stringcourse_no;intcredit;};structc//邊/弧鄰接表結(jié)點(diǎn){intadjvex; //鄰接點(diǎn)下標(biāo)//intight; //權(quán)值c*nextarc;};struct//頂點(diǎn){coursedata; //數(shù)值域c*firstarc;};classaph{private:*vertices;intarc//頂點(diǎn)數(shù)邊數(shù)bool*visited; //用于判斷是否訪問過，遍歷時(shí)使用}3.2.2圖的創(chuàng)建代碼intLocated(v){for(inti=0;i<i{if(vertices[i].data.course_nodata.course_no) returni;}return-1;}voideataph() //此圖為有向圖{cout請輸入分別輸入課程個(gè)數(shù)和先修關(guān)系數(shù)（VOA圖的邊數(shù)）："數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第7頁。endl;數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第7頁。cinvexNumarcvertices=new[;visited=newbool[;for(inti=0;i<i{vertices[i].firstarc=visited[i]=false;}c*p;inti=0,j;v1,v2;for(;i<i{cout請輸入第"i+1門課程，學(xué)分:";cinvertices[i].data.course_no;cinvertices[i].data.credit;}syste"cls");for(intk=0;k<arc{endl;

cout請輸入第"k+1個(gè)先修關(guān)系(先修，直接后修)："cinv1.data.course_nov2.data.course_no;if((i=Located(v1))-1){couterror!"endl;return;}if((j=Located(v2))-1){couterror!"endl;return;}p=nec;p-djvex=j;p-xtarc=vertices[i].firstarc;vertices[i].firstarc=p;}數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第8頁。}數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第8頁。四、功能實(shí)現(xiàn)算法設(shè)計(jì)4.1拓?fù)渑判蛩惴ㄔO(shè)計(jì)對于有向圖采用鄰接表存儲(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)行刪除操作勢必會(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è)步驟來完成：1、遍歷整個(gè)圖的鄰接表求所有頂點(diǎn)的入度值。2、將入度為0的頂點(diǎn)入隊(duì)。3、當(dāng)隊(duì)列不為空時(shí)，執(zhí)行出隊(duì)操作。出隊(duì)的頂點(diǎn)必定是入隊(duì)為0的頂點(diǎn)，輸出他即可。然后將它的所有的鄰接頂點(diǎn)的入度值減1，若到了零，則再將其入隊(duì)。重復(fù)這個(gè)過程，直到隊(duì)列為空為止。數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第9頁。4、若已經(jīng)輸出的頂點(diǎn)個(gè)數(shù)等于圖的頂點(diǎn)個(gè)數(shù)，則輸出的是一個(gè)拓?fù)渑判?，否則，說明圖中存在回路。數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第9頁。遍歷鄰接遍歷鄰接表，求所有頂點(diǎn)的入度出度頂點(diǎn)的所有鄰接頂點(diǎn)的入度入隊(duì)出隊(duì)拓?fù)渑判虺晒?，正常輸出入度？否是否?duì)列為空？是是出隊(duì)個(gè)數(shù)點(diǎn)個(gè)數(shù)？否該圖存在回路，拓?fù)渑判蚴?shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第10頁。拓?fù)渑判蛩惴ㄔO(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第10頁。4.2獲取各個(gè)頂點(diǎn)的入度算法設(shè)計(jì)傳入數(shù)組a傳入數(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)入獲得所有頂點(diǎn)入度算法數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第11頁。4.3分類型輸出算法設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第11頁。輸輸入學(xué)期數(shù)，學(xué)期學(xué)分上限各學(xué)期學(xué)習(xí)負(fù)擔(dān)均勻課程集中到前幾個(gè)學(xué)期課程數(shù)除以學(xué)期數(shù)均分按照學(xué)分累加判斷五、程序代碼ncludeostreancludetack> //直接用系統(tǒng)封裝的模板棧ncludeue> //系統(tǒng)封裝的模板隊(duì)列ncludetring>ncludestreausingnaspacestd;stringresult;structcourse //應(yīng)用于data,保存課程號和學(xué)分。依據(jù)課程號的先修關(guān)系和學(xué)分進(jìn)行拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第12頁。{數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第12頁。stringcourse_no;intcredit;};structc//邊/弧鄰接表結(jié)點(diǎn){intadjvex; //鄰接點(diǎn)下標(biāo)//intight; //權(quán)值c*nextarc;};struct//頂點(diǎn){coursedata; //數(shù)值域c*firstarc;};classaph{private:*vertices;intarc//頂點(diǎn)數(shù)邊數(shù)bool*visited; //用于判斷是否訪問過，遍歷時(shí)使用public:aph() //構(gòu)造函數(shù)確定定點(diǎn)數(shù)和邊的數(shù)量{}aph() //析構(gòu)函數(shù)，釋放鄰接表中各邊表結(jié)點(diǎn)的存儲(chǔ)空間{}boolIst(inti){數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第13頁。}數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第13頁。intLocated(v){for(inti=0;i<i{if(vertices[i].data.course_nodata.course_no) returni;}return-1;}voideataph() //此圖為有向圖{endl;

cout請輸入分別輸入課程個(gè)數(shù)和先修關(guān)系數(shù)（VOA圖的邊數(shù)）："cinvexNumarcvertices=new[;visited=newbool[;for(inti=0;i<i{vertices[i].firstarc=visited[i]=false;}c*p;inti=0,j;v1,v2;for(;i<i{cout請輸入第"i+1門課程，學(xué)分:";cinvertices[i].data.course_no;cinvertices[i].data.credit;}syste"cls");for(intk=0;k<arc{endl;

cout請輸入第"k+1個(gè)先修關(guān)系(先修，直接后修)："cinv1.data.course_nov2.data.course_no;if((i=Located(v1))-1){couterror!"endl;return;數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第14頁。}數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第14頁。if((j=Located(v2))-1){couterror!"endl;return;}p=nec;p-djvex=j;p-xtarc=vertices[i].firstarc;vertices[i].firstarc=p;}}voidfindIndegree(int*indegree) //獲取各個(gè)頂點(diǎn)的入度{for(inti=0;i<i{intcount=0;c*p;for(intj=0;j!=i<j{p=vertices[j].firstarc;le(p){if(p-djvexi) countp=p-xtarc;}}indegree[i]=count;}}voidtopologicalSort(inta[]) //數(shù)組a獲得拓?fù)渑判蚪Y(jié)果的下標(biāo){intv,count=0,*indegree;c*p;queuent>indegree=nent(;findIndegree(indegree);for(v=0;v<數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第15頁。if(indegree[v]0)push(v);數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第15頁。le(!ey()){a[count]front(); //用數(shù)組記錄拓?fù)渑判虻奈恢孟聵?biāo)v=a[count];countpop();p=vertices[v].firstarc;le(p){indegree[p-djvex]--;if(indegree[p-djvex]0)push(p-djvex);p=p-xtarc;}}if(count<{endl;}

cout先修關(guān)系存在問題(，請重新創(chuàng)建！"exit(0);elsecout系統(tǒng)已完成規(guī)劃！"endl;}voidfinal_sort(){int*ant(; //申請動(dòng)態(tài)數(shù)組存放拓?fù)渑判蚪Y(jié)果topologicalSort(a);syste"cls");intter//學(xué)期數(shù)inthest_score;//學(xué)期最高學(xué)分cout系統(tǒng)已完成規(guī)劃！"endl;cout請輸入學(xué)期數(shù)，學(xué)期學(xué)分上限：";cinterhest_score;inti;cout********************************************************"endl;cout**"endl;cout* 系統(tǒng)已經(jīng)完成規(guī)劃，請選擇輸出方案*"endl;數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第16頁。cout*數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第16頁。*"endl;cout* 1.學(xué)習(xí)負(fù)擔(dān)盡量均勻。*"endl;cout* 2.盡可能地集中在前幾個(gè)學(xué)期中。*"endl;cout**"endl;cout********************************************************"endl;cout請輸入您要選擇的功能：";cini;stch(i){case1: //學(xué)習(xí)負(fù)擔(dān)盡量均勻。{fstreamfile1("\\text.txt",ios::out||ios::app);syste"cls");intx=1;for(intm=0;m<{if(m0){file第"x學(xué)期：";cout第"x學(xué)期：";}file1vertices[a[].data.course_no";coutvertices[a[].data.course_no";if((m+1)%(vexNum/ter+1)0{fileendl第"x學(xué)期：";coutendl第"x學(xué)期：";}}file1.close();break;}case2: //盡可能地集中在前幾個(gè)學(xué)期中。{數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第17頁。fstreamfile1("\\text.txt",ios::out||ios::app);數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第17頁。syste"cls");intx=1;intcount=0;for(intm=0;m<{if(m0){file第"x學(xué)期：";cout第"x學(xué)期：";}count=count+vertices[a[].data.credit;if(counthest_score){filevertices[a[].data.course_no";coutvertices[a[].data.course_no";}else{file學(xué)期總學(xué)分："count-vertices[a[].data.creditendl第"x學(xué)期：";cout學(xué)期總學(xué)分："count-vertices[a[].data.credit;coutndl第"x學(xué)期：";count=0;-;}}file1學(xué)期總學(xué)分："countendl;cout學(xué)期總學(xué)分："countendl;file1.close();break;}}/*for(inti=0;i<i{couta[i];coutvertices[a[i]].data.course_no" ";數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第18頁。}數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告--教學(xué)計(jì)劃編制全文共22頁，當(dāng)前為第18頁。*/}voidfirstSight(){inti;cout****************************************************************"<<endl;cout****************************************************************"<<endl;cout**"endl;cout* 歡迎進(jìn)入教學(xué)計(jì)劃編制系統(tǒng)，請根據(jù)提示選擇操作功能。 *"endl;cout**"endl;cout* 1.創(chuàng)建新的教學(xué)計(jì)劃編制。*"endl;cout* 2.退出。*"endl;cout**"endl;cout**"endl;cout****************************************************************"<<endl;cout****************************************************************"<<endl;cout請輸入您要選擇的功能：";cini;syste