

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、拓?fù)渑判?拓?fù)渑判蛞?、問題描述 一、問題描述在 AOV 網(wǎng)中為了更好地完成工程,必須滿足活動之間先后關(guān)系,需要將各活動排一個先后次序即為拓?fù)渑判?。拓?fù)渑判蚩梢詰?yīng)用于教學(xué)計劃的安排,根據(jù)課程之間的依賴關(guān)系,制定課程安排計劃。按照用戶輸入的課程數(shù),課程間的先后關(guān)系數(shù)目以及課程間兩兩間的先后關(guān)系,程序執(zhí)行后會給出符合拓?fù)渑判虻恼n程安排計劃。二、基本要求 二、基本要求1、選擇合適的存儲結(jié)構(gòu),建立有向無環(huán)圖,并輸出該圖;2、實現(xiàn)拓?fù)渑判蛩惴ǎ?、
2、運(yùn)用拓?fù)渑判驅(qū)崿F(xiàn)對教學(xué)計劃安排的檢驗。三、算法思想 三、算法思想1、采用鄰接表存儲結(jié)構(gòu)實現(xiàn)有向圖;有向圖需通過頂點數(shù)、弧數(shù)、頂點以及弧等信息建立。2、拓?fù)渑判蛩惴?void TopologicalSort(ALGraph G) 中,先輸出入度為零的頂點,而后輸出新的入度為零的頂點,此操作可利用?;蜿犃袑崿F(xiàn)??紤]到教學(xué)計劃安排的實際情況,一般先學(xué)基礎(chǔ)課(入度為零),再學(xué)專業(yè)課(入度不為零),與隊列先進(jìn)先出的特點相符,故采用隊列實現(xiàn)。3、拓
3、撲排序算法 void TopologicalSort(ALGraph G),大體思想為:1)遍歷有向圖各頂點的入度,將所有入度為零的頂點入隊列;2)隊列非空時,輸出一個頂點,并對輸出的頂點數(shù)計數(shù);3)該頂點的所有鄰接點入度減一,若減一后入度為零則入隊列;4)重復(fù) 2)、3),直到隊列為空,若輸出的頂點數(shù)與圖的頂點數(shù)相等則該圖可拓?fù)渑判?,否則圖中有環(huán)。4、要對教學(xué)計劃安排進(jìn)行檢驗,因此編寫了檢測用戶輸入的課程序列是否是拓?fù)湫蛄械乃惴?vo
4、id TopSortCheck(ALGraph G),大體思想為:1)用戶輸入待檢測的課程序列,將其存入數(shù)組;2)檢查課程序列下一個元素是否是圖中的頂點(課程),是則執(zhí)行 3),否則輸出“課程 XX 不存在”并跳出;3)判斷該頂點的入度是否為零,是則執(zhí)行 4),否則輸出“入度不為零”并跳出;4)該頂點的所有鄰接點入度減一;5)重復(fù) 2)、3)、4)直到課程序列中所有元素均被遍歷,則該序列是拓?fù)湫蛄?,否則不是拓?fù)湫蛄?。功能:元素出隊列參?shù)
5、:*Q 待操作的隊列;*e 記錄出隊列元素的變量2、有向圖 、有向圖(DAG) (DAG)鄰接表存儲結(jié)構(gòu) 鄰接表存儲結(jié)構(gòu)(ALG) (ALG)的操作 的操作1) int LocateVex(ALGraph G,VertexType v)功能:頂點在頭結(jié)點數(shù)組中的定位參數(shù):G 待操作的圖;v 要在圖中定位的頂點返回值:頂點存在則返回在頭結(jié)點數(shù)組中的下標(biāo);否則返回圖的頂點數(shù)2) int CreateGraph(ALGraph *G)功能:建
6、立圖函數(shù)內(nèi)包含了由用戶輸入頂點數(shù)、弧數(shù)、頂點以及弧的操作參數(shù):*G 待操作的圖返回值:圖建立成功返回 1;圖建立失敗返回 0錯誤判斷:包含頂點數(shù)、弧數(shù)是否正確的判斷;包含用戶輸入的弧的頂點是否存在的判斷3) void PrintGraph(ALGraph G)功能:輸出有向圖參數(shù):G 待輸出的圖4) int CreateGraph2(ALGraph *G)功能:建立預(yù)置課程圖(輸出函數(shù)內(nèi)預(yù)置課程信息,并自動建立有向圖)參數(shù):*G 待操作
7、的圖返回值:圖建立成功返回 1;圖建立失敗返回 0錯誤判斷:包含頂點數(shù)、弧數(shù)是否正確的判斷包含弧的頂點是否存在的判斷5) void PrintGraph2(ALGraph G)功能:輸出預(yù)置課程圖參數(shù):G 待輸出的圖3、拓?fù)渑判蚣巴負(fù)錂z測算法 、拓?fù)渑判蚣巴負(fù)錂z測算法1) void TopologicalSort(ALGraph G)功能:實現(xiàn)拓?fù)渑判騾?shù):G 待進(jìn)行拓?fù)渑判虻膱D錯誤判斷:包含有向圖是否有環(huán)的判斷2) void TopS
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--排序算法
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---排序算法比較
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--排序算法比較
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計有向圖拓?fù)渑判蛩惴ǖ膶崿F(xiàn)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--排序算法演示系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---排序算法的實現(xiàn)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計----內(nèi)部排序算法性能分析
- 大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序算法演示系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--內(nèi)部排序算法的比較
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--幾種排序算法的演示
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告--排序
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---排序綜合
- 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告---排序算法的實現(xiàn)與比較
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告---幾種排序算法的演示
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---希爾排序,冒泡排序,快速排序
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告內(nèi)部排序的算法設(shè)計與分析
- 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計
- 大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序算法演示系統(tǒng)58165
評論
0/150
提交評論