【文章內(nèi)容簡介】 棧Pop（）：出棧 FindInDegree（）：求頂點(diǎn)的入度TopologicalSort（）：輸出G頂點(diǎn)的拓?fù)渑判蚪Y(jié)果流程圖（具體流程圖見詳細(xì)設(shè)計(jì)偽碼流程）主程序構(gòu)造圖GreateGraph ( )拓?fù)渑判騎opologicalSort開始結(jié)束目標(biāo)測試正確測試：錯誤測試：二、詳細(xì)設(shè)計(jì)運(yùn)行環(huán)境：（1）WINDOWS 7系統(tǒng)（2）CFree 開發(fā)工具： C語言涉及知識點(diǎn)：(1) 棧。用到有關(guān)棧的操作有初始化棧、判斷棧是否為空、入棧和出棧。其中棧主要用來存放入度為零的頂點(diǎn)，即當(dāng)前無先修關(guān)系可以編排的課程。(2) 圖。用到有關(guān)圖的操作有創(chuàng)建圖、統(tǒng)計(jì)圖中各頂點(diǎn)的入度。利用鄰接表作為有向圖的存儲結(jié)構(gòu)，且在頭結(jié)點(diǎn)中增加一個存放頂點(diǎn)入度的數(shù)組（indegree）。入度為零的頂點(diǎn)即為沒有前驅(qū)的頂點(diǎn)，刪除頂點(diǎn)及以它為尾的弧的操作，則可換以弧頭頂點(diǎn)入度減一來實(shí)現(xiàn)。(3) 拓?fù)渑判颉? （a）在有向圖中選一個沒有前驅(qū)的頂點(diǎn)且輸出之。 （b）從圖中刪除該頂點(diǎn)和所有以它為尾的弧。重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出，或者當(dāng)前圖中不存在無前驅(qū)的頂點(diǎn)為止，后一種情況則說明有向圖中存在環(huán)。數(shù)據(jù)結(jié)構(gòu)定義及基本操作：define MAX_VERTEX_NUM 100 //最大課程總數(shù)define STACK_INIT_SIZE 100 //存儲空間的初始分配量define STACKINCREMENT 10 //存儲空間的分配增量//圖的鄰接表存儲表示typedef struct ArcNode{ int adjvex。//該弧所指向頂點(diǎn)的位置 struct ArcNode *nextarc。//指向下一條弧的指針}ArcNode。typedef struct VNode{ char name[24]。//課程名 int classid。 //課程號 int credit。//課程的學(xué)分 int indegree。//該結(jié)點(diǎn)的入度 int state。//該節(jié)點(diǎn)的狀態(tài)，1代表已學(xué)，0代表未學(xué) ArcNode *firstarc。 //指向第一條依附該頂點(diǎn)的弧的指針}VNode,AdjList[MAX_VERTEX_NUM]。typedef struct{ AdjList vertices。//頂點(diǎn)向量 int vexnum,arum。//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}ALGraph。typedef int ElemType。//棧的順序存儲表示typedef struct //棧{ ElemType *base。 ElemType *top。 int stacksize。}SqStack。：（1） void CreatGraph(ALGraph amp。G)構(gòu)建圖。先輸入各頂點(diǎn)（課程）的信息，包括課程名、課程號、課程學(xué)分。再輸入弧信息（先修關(guān)系），將弧中頂點(diǎn)賦為弧尾。（2） void InitStack(SqStack amp。S)構(gòu)造空棧int StackEmpty(SqStack amp。S)判斷是否為空棧void Push(SqStack amp。S,int e)入棧 int Pop(SqStack amp。S, int *e)出棧（3） void FindInDegree(ALGraph G, int indegree[])求圖中各節(jié)點(diǎn)的入度。從每個節(jié)點(diǎn)的第一條依附于該節(jié)點(diǎn)的弧出發(fā)，將該節(jié)點(diǎn)對應(yīng)的入度加1，接著指向下一條弧執(zhí)行同樣的操作，直至指針為空。（3）void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)按課程盡可能集中到前幾個學(xué)期進(jìn)行編排。當(dāng)每個學(xué)期的學(xué)分總數(shù)不超過學(xué)分上限時，在有向圖中選一個沒有前驅(qū)的頂點(diǎn)（課程）且輸出之。從圖中刪除該頂點(diǎn)（課程）和所有以它為尾的弧。當(dāng)某學(xué)期的學(xué)分已滿時，進(jìn)入下一學(xué)期的編排。重復(fù)上述幾步，直至全部頂點(diǎn)（課程）均已輸出，或者當(dāng)前圖中不存在無前驅(qū)的頂點(diǎn)（課程）為止，后一種情況則說明有向圖中存在環(huán)。（4）void TopologicalSort_2(ALGraph G,int numterm,int uplcredit)按課程盡量均勻分布編排。當(dāng)每個學(xué)期的學(xué)分總數(shù)不超過學(xué)分上限且課程數(shù)不超過課程數(shù)上限時，在有向圖中選一個沒有前驅(qū)的頂點(diǎn)（課程）且輸出之。從圖中刪除該頂點(diǎn)（課程）和所有以它為尾的弧。當(dāng)某學(xué)期的學(xué)分已滿或課程數(shù)已滿時，進(jìn)入下一學(xué)期的編排。重復(fù)上述幾步，直至全部頂點(diǎn)（課程）均已輸出，或者當(dāng)前圖中不存在無前驅(qū)的頂點(diǎn)（課程）為止，后一種情況則說明有向圖中存在環(huán)。（5）int main()主函數(shù)。在主函數(shù)中輸出交互界面，要求用戶輸入各項(xiàng)信息。調(diào)用CreateGraph函數(shù)創(chuàng)建圖，之后根據(jù)用戶選擇調(diào)用TopologicalSort_1或者TopologicalSort_2函數(shù)進(jìn)行拓?fù)渑判虿⑤敵鼍幣沤Y(jié)果，寫入文件中。函數(shù)調(diào)用關(guān)系圖Main函數(shù)GreateGraph ( )TopologicalSort_1或TopologicalSort _2FILE *fpFindInDegree ( )InitStack ( )Push ( )Pop ( )StackEmpty ( )偽碼流程（1）void CreatGraph(ALGraph amp。G) （2）void FindInDegree(ALGraph G, int 構(gòu)造圖 indegree[])求圖中各節(jié)點(diǎn)的入度 (4) void TopologicalSort_1 (5)void TopologicalSort_2 (ALGraph G,int numterm, (ALGraph G,int numterm, int uplcredit) int uplcredit)有向圖G采用鄰接表存儲結(jié)構(gòu) 有向圖G采用鄰接表存儲結(jié)構(gòu)(6)Main主函數(shù)三、調(diào)試分析調(diào)試過程中遇到的問題與解決方法我在實(shí)驗(yàn)過程中遇到的最大難題是兩個課程排序算法的編寫。剛開始的時候沒有任何的思路，書上、網(wǎng)上也只有拓?fù)渑判虻乃惴?，對于課程設(shè)計(jì)要求的排序算法沒有任何頭緒。經(jīng)過請教老師和同學(xué)以及翻閱了一些相關(guān)書籍，并在網(wǎng)上的搜索有了排序算法的大體思路。經(jīng)過三天的修改，終于寫出了符合要求的排序算法。在設(shè)計(jì)過程中，我的程序有不少漏洞，例如在選擇一次編排后，按任意鍵就會退出，不可以繼續(xù)選擇編排策略，經(jīng)過一系列的修改，成功地將程序添加選擇是否繼續(xù)的功能。算法的時空分析對有n個頂點(diǎn)和e條弧的有向圖而言，將建立求各頂點(diǎn)的入度的時間復(fù)雜度為O(e)；建立入度定點(diǎn)棧的時間復(fù)雜度為O(n)，在拓?fù)渑判蜻^程中，若有向圖無環(huán)，則每個頂點(diǎn)進(jìn)一次棧，出一次棧，入度減1的操作在while語句中總共執(zhí)行e次，所以，總的時間復(fù)雜度為O(n+e)。改進(jìn)思想，可設(shè)計(jì)更簡潔美觀的界面。，分步太多，可編寫程序進(jìn)行改善，如一步輸入課程名、課程號、學(xué)分。,02等形式，也可改為CC2的形式。經(jīng)驗(yàn)體會在這次課設(shè)中，我進(jìn)行了大量的資料查閱，包括上網(wǎng)查詢和求助老師同學(xué)，對所學(xué)知識進(jìn)行復(fù)習(xí)。通過這些努力，我對數(shù)據(jù)結(jié)構(gòu)這門課程有了新的認(rèn)識，對編程的步驟，有了具體的體會。更重要的是，這個課題完全脫離于只限于書本上的問題，多用在實(shí)際生活當(dāng)中，讓我對計(jì)算機(jī)行業(yè)，充