拓?fù)渑判?算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計)

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