1、【精品文檔】如有侵權，請聯系網站刪除，僅供學習與交流數據結構課程設計拓撲排序.精品文檔.課程設計任務書學生姓名： 專業班級： 指導教師： 工作單位： 計算機科學系 題 目: 拓撲排序 初始條件：（1）采用鄰接表作為有向圖的存儲結構；（2）給出所有可能的拓撲序列。（3）測試用例見嚴蔚敏數據結構習題集(C語言版)p48題7.9圖要求完成的主要任務: （包括課程設計工作量及其技術要求，以及說明書撰寫等具體要求）課程設計報告按學校規定格式用A4紙打印（書寫），并應包含如下內容： 1. 問題描述簡述題目要解決的問題是什么。2. 設計存儲結構設計、主要算法設計（用類C/C+語言或用框圖描述）、測試用例設計

2、；3. 調試報告調試過程中遇到的問題是如何解決的；對設計和編碼的討論和分析。4. 經驗和體會（包括對算法改進的設想）5. 附源程序清單和運行結果。源程序要加注釋。如果題目規定了測試數據，則運行結果要包含這些測試數據和運行輸出。說明：1. 設計報告、程序不得相互抄襲和拷貝；若有雷同，則所有雷同者成績均為0分。2. 凡拷貝往年任務書或課程設計充數者，成績一律無效，以0分記。時間安排：1第17周完成，驗收時間由指導教師指定2驗收地點：實驗中心3驗收內容：可執行程序與源代碼、課程設計報告書。指導教師簽名： 2013年6月14日系主任（或責任教師）簽名： 年 月 日拓撲排序目錄1問題描述2具體設計2.1

3、存儲結構設計2.2主要算法設計 2.2.1拓撲排序的算法總體設計2.2.2將有向圖表示為鄰接表2.2.3拓撲排序函數的設計2.2.4順序表的運算設計2.3測試用例設計3調試報告 3.1設計和編碼的分析3.2調試過程問題及解決4經驗與體會5用戶使用說明6參考文獻7附錄源代碼與運行結果1問題描述題目：拓撲排序如果用有向圖表示一個工程，在這種有向圖中，用頂點表示活動，用有向邊<vi,vj>表示活動vi必須先于活動vj進行，這種有向圖叫做頂點表示活動的網絡，記作AOV網絡。對一個有向無環圖G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得AOV網絡中的所有應存在前驅和后繼的關系都能得到

4、滿足，這種構造AOV網絡全部頂點的拓撲有序序列的運算叫做拓撲排序。在AOV-網中，不應該出現有向環，用拓撲排序就可以判斷網中是否有環，若網中所有頂點都在它的拓撲有序序列中，則該AOV-網必定不存在環。進行拓撲排序步驟如下：1、輸入AOV網絡即有向圖。令n為頂點個數。2、從有向圖上選擇一個沒有入度的節點并輸出。3、從網中刪去該點，同時刪去從該頂點發出的全部有向邊。4、重復上述2，3，直到（1）、全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成。（2）、圖中還有未輸出的頂點，但已跳出處理循環。這說明圖中還剩下一些頂點，它們都有直接前驅，再也找不到沒有前驅的頂點了，這時AOV網絡中必定存在有向環。要

5、求：（1）、采用鄰接表作為有向圖的存儲結構；（2）、給出所有可能的拓撲序列。2具體設計2.1存儲結構設計本問題中，我將采用三種數據結構：鄰接表，順序表和數組。<1>鄰接表：鄰接表是圖的鏈式存儲結構，在鄰接表的存儲結構中，圖中的每個頂點對應一個單鏈表。從拓撲排序的步驟個方法來看，在整個排序過程中需要頻繁地檢查頂點的前驅以及作刪除頂點和邊的操作、恢復頂點和頂點前驅入度的操作。所以，可以采用鄰接表作為有向無環圖的存儲結構。為了快速的判斷頂點是否有前驅，可以在表頭結點中增加一個“入度域（into）”用來指示頂點當前的入度。當into域的值為0時，表明該頂點沒有前驅，可以加入到結果序列中。而

6、刪除頂點及以它為起點的邊操作時，可以通過把該頂點的所有鄰接點的入度域減一來完成，恢復則入度域加一。鄰接表的定義如下：typedef struct ARCNODE /表結點int adjvex; /鄰接點的位置ARCNODE *nextarc;/指向下一個結點ARCNODE; /鄰接表中的結點類型typedef struct VEXNODE /頭結點int vexdata; /頂點信息int into; /每個頂點的入度ARCNODE *firstarc; /指向第一個鄰接結點VEXNODE,AdjListMAX;/鄰接表的表頭結點類型typedef structAdjList vexs; /表

7、頭結點數組int vexnum,arcnum;/頂點數、邊數ALGraph; /鄰接表類型<2>順序表：在整個拓撲排序的過程中，把滿足條件（在此輪中未訪問過visitedi=0以及入度為0）的頂點加入到順序表的末尾，使last加1。當一輪排序結束后，輸出順序表中的排序。接著，是恢復部分，每恢復一步，都要把visiti置0并且相應的入度加1，把這個頂點從順序表中刪除，重新加入到圖中，進行下一輪的拓撲排序。鄰接表的順序表定義如下：typedef struct VEXNODE dataMAX;int last;Sequenlist; /順序表類型<2>數組：產生所有的拓撲排序

8、是一個遞歸（回溯）過程。其中，定義的visitedMAX數組是一個輔助變量，數組元素的初值為0，當第i個頂點被訪問后，便置visitedi為1.記錄該頂點是否被訪問過。VisitedMAX；2.2主要算法設計 2.2.1拓撲排序的算法總體設計 因為這個課程設計題目是讓AOV網絡產生所有的拓撲排序，所以我想必然要用到遞歸或者回溯的思想。 考慮到要不斷的對數據進行刪除，恢復，所以考慮了順序表，單鏈表，堆棧，發現用順序表刪除和插入都很簡單，好實施，只要在表尾插入或是刪除即可。在整個過程中主要用到三部分：一、從圖中刪除，添加到順序表中；二、遞歸；三、把刪除的頂點和邊恢復到圖中并從順序表中刪除。首先，在

9、整個圖中搜索即沒有被訪問過而且入度為0 的頂點Vi，進行拓撲排序。在拓撲排序的函數里，首先將這個頂點加入到順序表中，然后將這個頂點標志為被訪問過，即Visitedi=1。把以這個頂點為起點的鄰接點的入度均減1.然后，判斷順序表的表長是否等于圖的頂點數。如果不相等的話，則繼續判斷圖中是否還存在滿足拓撲排序條件的頂點，若存在就再次調用拓撲排序函數。接下來，就是使剛排序過的頂點Vi的標志恢復到原始狀態0，每個以Vi為起點的鄰接點的入度加1，恢復到原來的狀態。把頂點Vi從順序表中刪除。如果，順序表的表長等于圖的頂點數，那么就輸出這一種拓撲排序序列。計數器count加1之后，就是采用遞歸，不斷的調用拓撲

10、排序函數，不斷的恢復、刪除，直到排出所有的拓撲序列。 最后，如果count大于0的話，那么就輸出有count種拓撲排序。否則，輸出此圖不是AOV網，無拓撲排序序列產生。開始置空順序表A，表長賦初值0用鄰接表建立圖G，調用G=creat_AdjlistGraph();或者 i賦初值0初始化標志數組，visitedi置0i的值遞增1i<G.頂點數?J賦初值0Visitedj=0且Vj入度為0？調用函數Topusort(G, L, i);j的值遞增1j<G.頂點數？Count > 0？此圖不是AOV網，無拓撲排序序列結束YNNY該圖有count種排序YNYN2.2.2將有向圖表示為

11、鄰接表在產生拓撲排序的算法設計中，首先要將有向圖用鄰接表表示，主要流程如下：開始定義表頭結點數組 al輸入頂點數n和邊數e輸入e條邊的起點值j 和終點值 k將Vk的入度加一，并將結點Vk加入到鏈表中；邊數從0到e初始化al 的各項值：ali.vexdata=i; o=0; ali.firstarc=NULL;（i=0 to 圖的頂點數）定義圖 algn = alg.vexnum 頂點數；e = alg.arcnum 邊數 i賦初值0將al中的值、入度、指針 分別賦給圖alg中數組vexs的.各值；i的值遞增1i<結點數n？NY結束2.2.3拓撲排序函數的設計開始插入SqLi

12、nsert( L, vexsi)標志數visitedi賦初值0Vi 指向第一個結點指針PP !=NULL？P 指向頂點 VjVj 的入度減 1P 指向鏈表下一結點順序表長=頂點數？輸出Output (L )計數器Count加1;K賦初值0調用函數Topusort( L, G, k );Visitedk= =0且Vk 入度為0？ K的值遞增1k<頂點數？NYYNVi 指向的第一個結點的指針 PP！=NULL ？P 指向頂點 VjVj 的入度加 1P指向鏈表下一結點調用刪除函數SqLdelete( L, vexsi )結束YN2.2.4順序表的運算設計開始定義順序表 A順序表置空：setnu

13、ll()表長L->last+1賦初值0插入：SqLinsert(L,vexsi)刪 除：SqLdelete(L,vexsi);輸出：output(L);表長加 1 即L->last+1把結點X賦給順序表最后一位L->rL->last表長減 1；L->last-1I賦初值0輸出Vi I的值遞增1i<表長?結束NY2.3測試用例設計1234圖11234圖23416752圖3312456 圖43調試報告 3.1設計和編碼的分析 1、鄰接表實現拓撲序列shixian()在本函數里，首先定義一個順序表，然后把它置空。接著，以鄰接表創建一個圖，并且把它賦給圖G。接著，把

14、全局變量數組visited初始化。對于整個圖中，沒被訪問過的而且入度為0的頂點進行拓撲排序。如果常量count等于0的話，說明圖有回路，不能拓撲排序。否則，在拓撲排序函數中會輸出所有的拓撲排序序列。void shixian() Sequenlist A,*L=&A; L=(Sequenlist *)malloc(sizeof(Sequenlist); Setnull(L); ALGraph G; G=creatGraph(); for(int n=1;n<=G.vexnum;n+) visitedn=0; int i; cout<<"該圖的所有拓撲排序為：&

15、quot;<<endl; for(i=1;i<=G.vexnum;i+) if(G.o=0)&&(visitedi=0) topusort(L,G,i);if(count<=0)cout<<"您輸入的圖不是有向無環圖，故無拓撲排序序列產生."<<endl;else cout<<"此圖有"<<count<<"種拓撲排序nn" count=0;2、 鄰接表的主要算法拓撲排序topusort()void topusort(S

16、equenlist *L,ALGraph G,int i) int j,k; SqLinsert(L,G.vexsi); /把頂點Vi加入到順序表中 P=G.vexsi.firstarc; visitedi=1; /把排序過的點標記 while(P!=NULL) j=P->adjvex; G.o-; /把以Vi為頭的終止結點入度減1 P=P->nextarc; for(k=1;k<=G.vexnum;k+) if(visitedk=0)&&(G.o=0)/ 如果Vk在此輪中未被訪問過且入度為0 topusort(L,G,k)

17、; if(L->last=G.vexnum) /判斷順序表中一種拓撲排序完成 output(L); cout<<endl; count+; visitedi=0; /使Vi恢復為未訪問 while(P!=NULL) j=P->adjvex; G.o+; /使Vj的入度恢復 P=P->nextarc;SqLdelete(L,G.vexsi);3、順序表函數 在這個設計中，只有順序表的簡單應用，置空，插入，刪除和輸出。插入和刪除都只是在表尾插入和刪除。即只要把表長加1或是減1.Sequenlist *Setnull(Sequenlist *L)/順序

18、表置空 L->last=0; return(L);void SqLinsert(Sequenlist *L,VEXNODE x)/在順序表尾插入新接點 L->last=L->last+1; L->dataL->last=x;void SqLdelete(Sequenlist *L,VEXNODE x)/刪除順序表中的最后一個節點 L->last=L->last-1;int count=0;void output(Sequenlist *L) /輸出順序表中的元素 int i; for(i=1;i<=L->last;i+) if(i<L

19、->last) cout<<"V"<<L->datai.vexdata<<"->" else cout<<"V"<<L->datai.vexdata; cout<<endl<<endl;3.2調試過程問題及解決在調試的過程中出現了很多語法錯誤，如：開始沒有申明iostream頭文件，導致所有的<<，>>輸入輸出流都是錯誤的，還有error C2562: 'main' : 'void

20、' function returning a value，發現main函數被我定義為了void返回類型，可是我在函數語句里又使用了return 0；把main函數的返回值改成int即可，還有其他的語法錯誤都根據提示一一改進了。接著，我發現無論如何輸出的結果都是零種排序，于是找到了ALGraph creatGraph()函數的一組賦值語句，開始我是這樣寫的“G.vexs=al;”后來改成 for(i=0;i<alg.vexnum;i+)alg.vexsi.vexdata=ali.vexdata;alg.vexsi.indegree=ali.indegree; alg.vexsi.f

21、irstarc=ali.firstarc;再次運行時，輸出結果還是不對。最后發現在for語句前少了alg.vexnum=n;alg.arcnum=e;賦值語句。在topusort函數中下列語句使得運行結果一直為您輸入的圖不是有向無環圖，故無拓撲排序序列產生.for(k=1;k<=G.vexnum;k+) if(visitedk=0)&&(G.o=0)/ 如果Vk在此輪中未被訪問過且入度為0 if(L->last=G.vexnum) /判斷順序表中一種拓撲排序完成 output(L); cout<<endl; count+; topuso

22、rt(L,G,k);改成如下代碼即可：for(k=1;k<=G.vexnum;k+) if(visitedk=0)&&(G.o=0)/ 如果Vk在此輪中未被訪問過且入度為0 topusort(L,G,k); if(L->last=G.vexnum) /判斷順序表中一種拓撲排序完成 output(L); cout<<endl; count+;4經驗與體會此次課程設計為拓撲排序，利用c+語言實現的，此算法還有多發面可以改進，比如圖的表示利用的是鄰接表，還可以在代碼中增加鄰接矩陣的表示方法，使得對于兩種形式表示的圖都可以進行拓撲排序，還有在代

23、碼中并沒有把鄰接表很直觀的輸出給用戶，如果可以編寫代碼把鄰接表很直觀的輸出，會更有可讀性。在執行的過程中發現對于大量的數據，比如邊比較復雜的情況，程序執行就有可能會崩潰，說明程序的健壯性還有待提高。通過五天的課程設計，我鞏固了以前學過的知識，懂得了理論與實際相結合的重要性，只有理論知識是遠遠不夠的，理論知識是為將來的實踐服務的，理論知識很重要，實踐活動更重要。通過課程設計我看到自己實際操作能力的嚴重不足，知識理解不夠深刻，掌握不夠牢固，編程基礎薄弱，沒有耐心。在同學和相關資料的幫助下，最終完成了代碼。通過這次設計，我看到自身學習方法存在很多錯誤，我決心在以后的學習過程中，要多鍛煉自己處理實際問

24、題的能力，要提高獨立分析問題和解決問題的能力，多動手多上機操作。并且利用假期時間進一步鞏固數據結構課程與C+語言基礎，為今后的學習打下比較堅實的基礎。5用戶使用說明運行后，根據提示，“請輸入結點數”,即輸入圖的頂點數目，“請入邊總數數”，即輸入圖的邊數；接著依次輸入每條邊的起始點序號和終止點序號即可，輸出結果就可以一目了然。例如：請輸入頂點數：4請輸入弧數：4請輸入邊的信息：請輸入第一條邊：1 2請輸入第二條邊：1 3請輸入第三條邊：2 3請輸入第四條邊：3 46參考文獻：1.嚴蔚敏，吳偉民。 數據結構題集(c語言)。 清華大學出版社，2011年11月。2.殷人昆。 數據結構(用面向對象方法與

25、C+語言描述)(第2版)。清華大學出版社，2007年6月7附錄源代碼與運行結果源程序代碼（c+語言）#include <stdio.h>#include <string.h>#include <malloc.h>#include <iostream.h>#define NULL 0#define maxlen 100typedef struct ARCNODE /表結點 int adjvex;/接鄰點的位置 ARCNODE *nextarc;/指向下一個結點ARCNODE; /鄰接表中的結點類型typedef struct VEXNODE /頭結

26、點 int vexdata;/頂點的位置 int into; /頂點的入度 ARCNODE *firstarc;/指向第一個鄰接結點VEXNODE,AdjListmaxlen;/表頭結點類型typedef struct AdjList vexs;/表頭結點數組 int vexnum,arcnum;/頂點數、邊數ALGraph;/鄰接表類型typedef struct VEXNODE datamaxlen; int last;Sequenlist; /順序表類型typedef struct int datamaxlen; int last;Seqlist; /順序表ALGraph creatGr

27、aph() int n,e,i,j,k; ARCNODE *p; AdjList al; cout<<endl; cout<<"-拓撲排序-"<<endl<<endl; cout<<"請輸入結點數: " cin>>n;for(i=1;i<=n;i+) /初始化表頭結點數組 ali.vexdata=i; o=0; ali.firstarc=NULL; cout<<"請輸入邊總數: " cin>>e; cout<<

28、;"請依次輸入邊的信息:"<<endl; for(i=1;i<=e;i+) cout<<"請輸入第"<<i<<"條邊:" cin>>j>>k; /依次讀入邊的信息 p=(ARCNODE *)malloc(sizeof(ARCNODE); p->adjvex=k; o+; /把終止結點的入度加1 p->nextarc=alj.firstarc; /用頭插法把p插入到鏈表中 alj.firstarc=p; cout<<end

29、l; ALGraph alg; alg.vexnum=n; alg.arcnum=e; for(i=1;i<=alg.vexnum;i+) /把頭結點表頭數組的值賦給鄰接表表頭數組 alg.vexsi.vexdata=ali.vexdata; o=o; alg.vexsi.firstarc=ali.firstarc;return alg;Sequenlist *Setnull(Sequenlist *L)/順序表置空 L->last=0; return(L);void SqLinsert(Sequenlist *L,VEXNODE x)/在順

30、序表尾插入新接點 L->last=L->last+1; L->dataL->last=x;void SqLdelete(Sequenlist *L,VEXNODE x)/刪除順序表中的最后一個節點 L->last=L->last-1;int count=0;void output(Sequenlist *L) /輸出順序表中的元素 int i; for(i=1;i<=L->last;i+) if(i<L->last) cout<<"V"<<L->datai.vexdata<<

31、;"->" else cout<<"V"<<L->datai.vexdata; cout<<endl<<endl;ARCNODE *P;int n;int visitedmaxlen;void topusort(Sequenlist *L,ALGraph G,int i) int j,k; SqLinsert(L,G.vexsi); /把頂點Vi加入到順序表中 P=G.vexsi.firstarc; visitedi=1; /把排序過的點標記 while(P!=NULL) j=P->adjvex; G.vex