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

1、拓?fù)渑判?拓?fù)渑判蛞?、問題描述 一、問題描述在 AOV 網(wǎng)中為了更好地完成工程，必須滿足活動(dòng)之間先后關(guān)系，需要將各活動(dòng)排一個(gè)先后次序即為拓?fù)渑判?。拓?fù)渑判蚩梢詰?yīng)用于教學(xué)計(jì)劃的安排，根據(jù)課程之間的依賴關(guān)系，制定課程安排計(jì)劃。按照用戶輸入的課程數(shù)，課程間的先后關(guān)系數(shù)目以及課程間兩兩間的先后關(guān)系，程序執(zhí)行后會(huì)給出符合拓?fù)渑判虻恼n程安排計(jì)劃。二、基本要求 二、基本要求1、選擇合適的存儲(chǔ)結(jié)構(gòu)，建立有向無環(huán)圖，并輸出該圖；2、實(shí)現(xiàn)拓?fù)渑判蛩惴ǎ?、

2、運(yùn)用拓?fù)渑判驅(qū)崿F(xiàn)對(duì)教學(xué)計(jì)劃安排的檢驗(yàn)。三、算法思想 三、算法思想1、采用鄰接表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)有向圖；有向圖需通過頂點(diǎn)數(shù)、弧數(shù)、頂點(diǎn)以及弧等信息建立。2、拓?fù)渑判蛩惴?void TopologicalSort(ALGraph G) 中，先輸出入度為零的頂點(diǎn)，而后輸出新的入度為零的頂點(diǎn)，此操作可利用?；蜿?duì)列實(shí)現(xiàn)?？紤]到教學(xué)計(jì)劃安排的實(shí)際情況，一般先學(xué)基礎(chǔ)課（入度為零），再學(xué)專業(yè)課（入度不為零），與隊(duì)列先進(jìn)先出的特點(diǎn)相符，故采用隊(duì)列實(shí)現(xiàn)。3、拓

3、撲排序算法 void TopologicalSort(ALGraph G)，大體思想為：1)遍歷有向圖各頂點(diǎn)的入度，將所有入度為零的頂點(diǎn)入隊(duì)列；2)隊(duì)列非空時(shí)，輸出一個(gè)頂點(diǎn)，并對(duì)輸出的頂點(diǎn)數(shù)計(jì)數(shù)；3)該頂點(diǎn)的所有鄰接點(diǎn)入度減一，若減一后入度為零則入隊(duì)列；4)重復(fù) 2)、3)，直到隊(duì)列為空，若輸出的頂點(diǎn)數(shù)與圖的頂點(diǎn)數(shù)相等則該圖可拓?fù)渑判?，否則圖中有環(huán)。4、要對(duì)教學(xué)計(jì)劃安排進(jìn)行檢驗(yàn)，因此編寫了檢測(cè)用戶輸入的課程序列是否是拓?fù)湫蛄械乃惴?vo

4、id TopSortCheck(ALGraph G)，大體思想為：1)用戶輸入待檢測(cè)的課程序列，將其存入數(shù)組；2)檢查課程序列下一個(gè)元素是否是圖中的頂點(diǎn)（課程），是則執(zhí)行 3)，否則輸出“課程 XX 不存在”并跳出；3)判斷該頂點(diǎn)的入度是否為零，是則執(zhí)行 4)，否則輸出“入度不為零”并跳出；4)該頂點(diǎn)的所有鄰接點(diǎn)入度減一；5)重復(fù) 2)、3)、4)直到課程序列中所有元素均被遍歷，則該序列是拓?fù)湫蛄校駝t不是拓?fù)湫蛄?。功能：元素出?duì)列參數(shù)

5、：*Q 待操作的隊(duì)列；*e 記錄出隊(duì)列元素的變量2、有向圖 、有向圖(DAG) (DAG)鄰接表存儲(chǔ)結(jié)構(gòu) 鄰接表存儲(chǔ)結(jié)構(gòu)(ALG) (ALG)的操作 的操作1) int LocateVex(ALGraph G,VertexType v)功能：頂點(diǎn)在頭結(jié)點(diǎn)數(shù)組中的定位參數(shù)：G 待操作的圖；v 要在圖中定位的頂點(diǎn)返回值：頂點(diǎn)存在則返回在頭結(jié)點(diǎn)數(shù)組中的下標(biāo)；否則返回圖的頂點(diǎn)數(shù)2) int CreateGraph(ALGraph *G)功能：建

6、立圖函數(shù)內(nèi)包含了由用戶輸入頂點(diǎn)數(shù)、弧數(shù)、頂點(diǎn)以及弧的操作參數(shù)：*G 待操作的圖返回值：圖建立成功返回 1；圖建立失敗返回 0錯(cuò)誤判斷：包含頂點(diǎn)數(shù)、弧數(shù)是否正確的判斷；包含用戶輸入的弧的頂點(diǎn)是否存在的判斷3) void PrintGraph(ALGraph G)功能：輸出有向圖參數(shù)：G 待輸出的圖4) int CreateGraph2(ALGraph *G)功能：建立預(yù)置課程圖（輸出函數(shù)內(nèi)預(yù)置課程信息，并自動(dòng)建立有向圖）參數(shù)：*G 待操作

7、的圖返回值：圖建立成功返回 1；圖建立失敗返回 0錯(cuò)誤判斷：包含頂點(diǎn)數(shù)、弧數(shù)是否正確的判斷包含弧的頂點(diǎn)是否存在的判斷5) void PrintGraph2(ALGraph G)功能：輸出預(yù)置課程圖參數(shù)：G 待輸出的圖3、拓?fù)渑判蚣巴負(fù)錂z測(cè)算法 、拓?fù)渑判蚣巴負(fù)錂z測(cè)算法1) void TopologicalSort(ALGraph G)功能：實(shí)現(xiàn)拓?fù)渑判騾?shù)：G 待進(jìn)行拓?fù)渑判虻膱D錯(cuò)誤判斷：包含有向圖是否有環(huán)的判斷2) void TopS