版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、HUNAN UNIVERSITY實(shí)驗(yàn)五最終報(bào)告題 目 教學(xué)計(jì)劃編制問題 學(xué)生姓名 學(xué)生學(xué)號 專業(yè)班級 指導(dǎo)老師 李曉鴻 完 成 日 期 2015年12月17日 一需求分析1.程序的功能 用戶通過鍵盤輸入課程總數(shù)、每門課的課程編號和直接先修的課程號等的參數(shù)。用有向網(wǎng)表示教學(xué)計(jì)劃,其中頂點(diǎn)表示某門課程,有向邊表示課程之間的先修關(guān)系(如果A課程是B課程的先修課程,那么A到B之間有一條有向邊從A指向B)。最終輸出一個(gè)不沖突的線性的課程教學(xué)流程。2.輸入形式 請輸入課程總數(shù): /輸入一個(gè)正整數(shù)n 請輸入課程1的名稱: /輸入任意字符串 請輸入課程2的名稱: . 請輸入課程n的名稱: (課程1)否是有先修
2、(1/0): /輸入1表示有,0表示沒有若輸入1: 請輸入先修課程的名稱: /輸入存在的先修課程名稱 . (課程n)否是有先修(1/0): 請輸入先修課程的名稱:3. 輸出形式 輸出成功: 課程表的排序?yàn)椋?/輸出沒有沖突的課表排序 輸出失?。?課程輸入錯(cuò)誤!教學(xué)計(jì)劃編制失敗,請重新輸入。4.測試數(shù)據(jù): .正常的輸入輸入: 輸入課程總數(shù):3請輸入課程1的名稱:小學(xué)數(shù)學(xué)請輸入課程2的名稱:初中數(shù)學(xué)請輸入課程3的名稱:大學(xué)數(shù)學(xué)小學(xué)數(shù)學(xué)是否有先修(1/0):0初中數(shù)學(xué)是否有先修(1/0):1請輸入先修課程的名稱:小學(xué)數(shù)學(xué)高中數(shù)學(xué)是否有先修(1/0):1請輸入先修課程的名稱:初中數(shù)學(xué)輸出: 課程表的排
3、序?yàn)椋?小學(xué)數(shù)學(xué) 初中數(shù)學(xué) 高中數(shù)學(xué) .正常的輸入輸入: 輸入課程總數(shù):4請輸入課程1的名稱:1請輸入課程2的名稱:2請輸入課程3的名稱:3請輸入課程4的名稱:4 1是否有先修(1/0):0請輸入先修課程的名稱:42是否有先修(1/0):1請輸入先修課程的名稱:33是否有先修(1/0):1請輸入先修課程的名稱:44是否有先修(1/0):0輸出: 課程表的排序?yàn)椋? 1 3 2有兩個(gè)先修課程的情況輸入: 輸入課程總數(shù):4請輸入課程1的名稱:A請輸入課程2的名稱:B請輸入課程3的名稱:C請輸入課程4的名稱:D A是否有先修(1/0):0B是否有先修(1/0):1請輸入先修課程的名稱:AC是否有先修
4、(1/0):1請輸入先修課程的名稱:AD是否有先修(1/0):1請輸入先修課程的名稱:C輸出: 課程表的排序?yàn)椋篈 B C D有三個(gè)先修課程的情況輸入: 輸入課程總數(shù):4請輸入課程1的名稱:A請輸入課程2的名稱:B請輸入課程3的名稱:C請輸入課程4的名稱:D A是否有先修(1/0):1請輸入先修課程的名稱:DB是否有先修(1/0):1請輸入先修課程的名稱:DC是否有先修(1/0):1請輸入先修課程的名稱:DD是否有先修(1/0):0輸出: 課程表的排序?yàn)椋篋 A B C所有課程無先修輸入: 輸入課程總數(shù):3請輸入課程1的名稱:1請輸入課程2的名稱:2請輸入課程3的名稱:3 A是否有先修(1/0
5、):0B是否有先修(1/0):0C是否有先修(1/0):0輸出: 課程表的排序?yàn)椋? 2 3 二、概要設(shè)計(jì)1.抽象數(shù)據(jù)類型 題設(shè)要求使用一個(gè)有向圖表示教學(xué)計(jì)劃,頂點(diǎn)表示某門課程,有向邊表示課程之間的先修關(guān)系,數(shù)據(jù)的對象是圖中的每一個(gè)頂點(diǎn)和有向邊。由此為本問題確定一個(gè)圖的數(shù)據(jù)關(guān)系。 本題目需要一個(gè)數(shù)據(jù)結(jié)構(gòu)來儲(chǔ)存遍歷過的圖的結(jié)點(diǎn),該數(shù)據(jù)結(jié)構(gòu)滿足先進(jìn)先出,所以用隊(duì)列來實(shí)現(xiàn)。 2.ADTADT Edge數(shù)據(jù)對象: N(邊的名稱) V(標(biāo)記) F(先修課結(jié)點(diǎn))數(shù)據(jù)關(guān)系:(N&&V&&F)R (R1&&R2&&Rn)Graph基本操作: st
6、ring getVal(int v)/返回邊的名稱 int getMark(int v)/返回標(biāo)記 void setVal(int v, string val)/設(shè)邊的名稱 void setMark(int v, int Mark)/設(shè)置標(biāo)記 void setfirst(int v)/設(shè)置先修結(jié)點(diǎn)標(biāo)記ADT Graph數(shù)據(jù)對象:V,R(分別代表某門課程的頂點(diǎn)組成的一個(gè)頂點(diǎn)集 V 和代表課程先修關(guān)系 的有向弧邊組成的一個(gè)弧集 R。)數(shù)據(jù)關(guān)系:VR<v,w>| v,wV 且 P(v,w)<v,w>表示從 v 到 w 的一條弧,并稱 v 為弧頭,
7、w 為弧尾。 基本操作:int n(); /返回圖中的頂點(diǎn)數(shù)int first(int); /返回該點(diǎn)的第一條鄰邊int next(int); /返回該店的下一條鄰邊void setEdge(int,int,int); /為有向邊設(shè)置權(quán)值void Find(string search, int& v) int n()ADT queue數(shù)據(jù)對象: 前指針front,后指針rear數(shù)據(jù)關(guān)系:R=<ai-1 ,ai>|ai-1,aicar,i=1,2,3.n約定a1 為隊(duì)列頭,an為隊(duì)列尾。基本操作:queue(); /隊(duì)列結(jié)構(gòu)初始化queue(); /結(jié)構(gòu)銷毀操作bool pu
8、sh(const int& it); /數(shù)據(jù)入列bool pop(int& it); /數(shù)據(jù)出列int size(); /獲取隊(duì)列長度3.算法的基本思想通過用戶輸入的頂點(diǎn)的個(gè)數(shù)(課程數(shù))初始化一個(gè)表示有向圖的相鄰矩陣,初始化邊的訪問次數(shù)全部設(shè)置為零,通過輸入邊的信息和先修關(guān)系,設(shè)置先修關(guān)系的計(jì)數(shù)器,記錄每條邊先修關(guān)系的數(shù)量,完成對有項(xiàng)圖的構(gòu)建。將先修關(guān)系為零的邊放入隊(duì)列,然后開始處理隊(duì)列。當(dāng)從隊(duì)列中刪除一個(gè)頂點(diǎn)時(shí),把它打印出來,同時(shí)將其所有相鄰頂點(diǎn)的先修關(guān)系計(jì)數(shù)器減一。當(dāng)某個(gè)相鄰頂點(diǎn)的計(jì)數(shù)器為0時(shí),就將其放入隊(duì)列。如果還有頂點(diǎn)未被打印,而隊(duì)列已經(jīng)為空,則圖中必然包含回路(既不可
9、能不違反先決條件完成任務(wù))。4.程序的流程 (1) 初始化模塊:輸入課程總數(shù),再輸入相應(yīng)數(shù)量的課程編號及每個(gè)課程的先修課程,用這些信息初始化一個(gè)有向圖。(2) 拓?fù)渑判蚰K:對有向圖進(jìn)行拓?fù)渑判?。?) 輸出模塊:根據(jù)有向圖是否為空輸出。為空時(shí),輸出拓?fù)渑判蚪Y(jié)果;不為空時(shí)輸出輸入錯(cuò)誤提示。三、詳細(xì)設(shè)計(jì)1.物理數(shù)據(jù)類型用戶輸入的課程個(gè)數(shù)不定,所以存儲(chǔ)拓?fù)渑判蚝蟮捻旤c(diǎn)的個(gè)數(shù)不定,對于圖有兩種存儲(chǔ)方式,本題中用鄰接矩陣來存儲(chǔ)圖的信息,對于邊很少的圖來說,雖然用鄰接矩陣有些浪費(fèi)空間,但是題目做起來相對方便。由于用戶輸入的課程個(gè)數(shù)不定,使用鏈?zhǔn)綏?。使用string類型儲(chǔ)存用戶信息和邊的信息。2. 算法的
10、具體步驟 初始化一個(gè)有向圖先修信息的儲(chǔ)存拓?fù)渑判蚺c輸出初始化一個(gè)有向圖:包括初始化被訪問標(biāo)記和先修標(biāo)記,動(dòng)態(tài)創(chuàng)建二維數(shù)組和用于儲(chǔ)存邊信息的一維數(shù)組。 Graph(int numVert)int i, j;numVertex = numVert;numEdge = 0;mark = new PointnumVert; / Initialize mark arrayfor (i = 0; i < numVertex; i+)marki.visit = -1;/包括初始化被訪問標(biāo)記和先修標(biāo)記marki.first = 0;matrix = (int*) new int*numVertex; /
11、 Make matrixfor (i = 0; i < numVertex; i+)matrixi = new intnumVertex;for (i = 0; i < numVertex; i+)/Edges start w/0 weightfor (int j = 0; j < numVertex; j+) matrixij = 0; .先修信息的存儲(chǔ):由用戶輸入是否有先修課程后,用戶每輸入一個(gè)先修課程,就將這個(gè)課程對應(yīng)的先修標(biāo)記加1. cout << a.getVal(i) << "是否有先修(1/0)"cin >>
12、; judge;if (judge)a.setfirst(i);cout << "請輸入先修課程的名稱:"cin >> Ch1;a.Find(Ch1, v1);a.setEdge(v1, i, 10); void setfirst(int v) markv.first+;拓?fù)渑判蚺c輸出:定義兩個(gè)隊(duì)列A和 B,將先修關(guān)系為零的邊放入隊(duì)列A,然后開始處理隊(duì)列。當(dāng)從隊(duì)列A中刪除一個(gè)頂點(diǎn)時(shí),該頂點(diǎn)進(jìn)入B隊(duì)列,再把該頂點(diǎn)打印出來,同時(shí)將其所有相鄰頂點(diǎn)的先修關(guān)系計(jì)數(shù)器減一。當(dāng)某個(gè)相鄰頂點(diǎn)的計(jì)數(shù)器為0時(shí),就將其放入隊(duì)列。如果還有頂點(diǎn)未被打印,而隊(duì)列已經(jīng)為空,則圖中
13、必然包含回路(既不可能不違反先決條件完成任務(wù))。輸出:重復(fù)將隊(duì)列B中首元素輸出并刪除,直到隊(duì)列為空,就是課程表的排序。void DFS(Graph* G, queue<int> *Q, queue<int> *L)for (int v = 0; v < n(); v+)if (markv.first = 0)Q->push(v);setMark(v, 1);while (Q->size() != 0)int i = Q->front();/獲取Q棧首元素Q->pop();/彈出Q棧L->push(i);/進(jìn)L棧for (int w =
14、 first(i); w < n(); w = next(i, w)markw.first-;if (markw.first = 0)Q->push(w); setMark(w, 1);for (int i = 0; i < n(); i+)if (getMark(i) = -1) /為0時(shí)表示還未被刪除,圖不為空cout << "課程輸入錯(cuò)誤!教學(xué)計(jì)劃編制失敗,請重新輸入。" << endl;exit(0); 3.算法的時(shí)空分析及改進(jìn)設(shè)想因?yàn)閳D的鄰接矩陣是一個(gè)|V|×|V|矩陣,所以鄰接矩陣的空間代價(jià)為(|V|2),對于
15、有n個(gè)頂點(diǎn)的和E條弧的有向圖而言,對此圖的拓?fù)渑判蛩惴〞r(shí)間復(fù)雜度為(V+E) 4.輸入和輸出的格式輸入: 1.輸入課程數(shù)ncout << "請輸入課程總數(shù):"cin >> n;if (n <= 0)cout << "輸入錯(cuò)誤重新輸入(大于零的整數(shù))" << endl;cout << "請輸入課程總數(shù):"cin >> n;2.輸入每門課的課程編號for (int i = 0; i < n; i+)cout << "請輸入課程&quo
16、t; << i + 1 << "名稱:"cin >> Ch;a.setVal(i, Ch); 3. 獲得先修的課程編號for (int i = 0; i < n; i+)judge = 0;cout << a.getVal(i) << "是否有先修(1/0)"cin >> judge;if (judge)a.setfirst(i);cout << "請輸入先修課程的名稱:"cin >> Ch1;a.Find(Ch1, v1);a.se
17、tEdge(v1, i, 10);輸出:1. 編制成功,把隊(duì)列S中的頂點(diǎn)序列輸出。 cout << "課程表的排序?yàn)?" << endl;a.DFS(&a, &Q, &L);for (int i = 0; i < n; i+)int j = L.front();cout << a.getVal(j) << " "L.pop();2. 編制失敗,圖中有回路,輸出錯(cuò)誤信息,結(jié)束程序。if(G.getMark(i)=0) /為0時(shí)表示該頂點(diǎn)未經(jīng)過拓?fù)渑判?cout<<&q
18、uot;課程輸入錯(cuò)誤!教學(xué)計(jì)劃編制失敗,請重新輸入。"<<endl;exit(0);四調(diào)試分析 DFS問題,書上思路很明確并且有很多源碼,沒有大的問題。五測試結(jié)果1. 正常的輸入輸出 .正常的輸入3.有兩個(gè)先修課程的情況有三個(gè)先修課程的情況所有課程無先修附錄#include<iostream>#include<queue>#include<fstream>#include<string>#include<iomanip>using namespace std;class Pointpublic:string Le
19、ssonName;int visit;int first;/1有先修,0無;class Graph/Implement adjacency matrixprivate:int numVertex, numEdge;/Store number of vertices edgesint *matrix; / Pointer to adjacency matrixPoint *mark; / Pointer to mark arraypublic:Graph(int numVert)/ Make graph w/ numVert verticesint i, j;numVertex = numVer
20、t;numEdge = 0;mark = new PointnumVert; / Initialize mark arrayfor (i = 0; i < numVertex; i+)marki.visit = -1;marki.first = 0;matrix = (int*) new int*numVertex; / Make matrixfor (i = 0; i < numVertex; i+)matrixi = new intnumVertex;for (i = 0; i < numVertex; i+)/Edges start w/0 weightfor (int
21、 j = 0; j < numVertex; j+) matrixij = 0;Graph()delete mark;for (int i = 0; i < numVertex; i+)delete matrixi;delete matrix;int n()return numVertex;int e()return numEdge;int first(int v)/ Return v's first neighborint i;for (i = 0; i < numVertex; i+)if (matrixvi != 0 && marki.visit
22、 = -1) return i;return i; / Return n if noneint next(int v1, int v2)/ Get v1's neighbor after v2int i;for (i = v2 + 1; i < numVertex; i+)if (matrixv1i != 0 && marki.visit = -1)/cout<<"此時(shí)next的i值是:"<<v1+1<<" "<<i+1<<endl; return i;return
23、 i;/ Set edge (v1, v2) to wgtvoid setEdge(int v1, int v2, int wgt)numEdge+;/ERRORmatrixv1v2 = wgt;void delEdge(int v1, int v2) / Delete edge (v1, v2)if (matrixv1v2 != 0)numEdge-;matrixv1v2 = 0;int weight(int v1, int v2)return matrixv1v2;string getVal(int v)return markv.LessonName;int getMark(int v)r
24、eturn markv.visit;void setVal(int v, string val)markv.LessonName = val;void setMark(int v, int Mark)markv.visit = Mark;void setfirst(int v)markv.first+;void Find(string search, int& v)for (int i = 0; i < numVertex; i+)if (marki.LessonName = search)v = i;return;cout << "路徑錯(cuò)誤" &
25、lt;< endl;return;void DFS(Graph* G, queue<int> *Q, queue<int> *L)for (int v = 0; v < n(); v+)if (markv.first = 0)Q->push(v);setMark(v, 1);while (Q->size() != 0)int i = Q->front();/獲取Q棧首元素Q->pop();/彈出Q棧L->push(i);/進(jìn)L棧for (int w = first(i); w < n(); w = next(i, w)markw.first-;if (markw.first = 0)Q->push(w); setMark(w, 1);for (int i = 0; i < n(); i+)if (getMark(i) = -1) /為0時(shí)表示還未被刪除,圖不為空cout << "課程輸入錯(cuò)誤!教學(xué)計(jì)劃編制失敗,請重新輸入。" << endl;exit(0);int main()int n;int v1;int v2;int
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2023年百色市右江區(qū)醫(yī)療衛(wèi)生事業(yè)單位招聘衛(wèi)生專業(yè)技術(shù)人員筆試真題
- 白描花鳥課程設(shè)計(jì)
- 2024年工業(yè)自動(dòng)調(diào)節(jié)儀表與控制系統(tǒng)項(xiàng)目申請報(bào)告
- 2023年安徽省白湖農(nóng)場集團(tuán)有限責(zé)任公司招聘考試真題
- 病毒思政課程設(shè)計(jì)
- 班組管理培訓(xùn)書課程設(shè)計(jì)
- 班級布置特色課程設(shè)計(jì)
- 玻璃鋼蓋板施工方案
- 玻璃裝飾材料行業(yè)研究報(bào)告
- 玻璃砂采購方案
- 江蘇省南通市2024-2025學(xué)年七年級上學(xué)期期中英語試卷(含答案解析)
- 2022年甘肅省公務(wù)員錄用考試《行測》真題及答案解析
- 排球正面上手發(fā)球課件
- 稅收的經(jīng)濟(jì)效應(yīng)課件
- GB/T 16915.1-2024家用和類似用途固定式電氣裝置的開關(guān)第1部分:通用要求
- 2025屆高考語文一輪復(fù)習(xí):小說物象含義及作用
- 湖北省襄陽市2023-2024學(xué)年六年級上學(xué)期英語期中試卷(含答案)
- 交通安全知識培訓(xùn)試題(帶答案)試卷打印版
- 山東省濰坊市2023-2024學(xué)年度高二上學(xué)期期中考試化學(xué)試題(帶答案)
- 大學(xué)生生涯發(fā)展展示 (修改)
評論
0/150
提交評論