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