數(shù)據(jù)結(jié)構(gòu)課程設(shè)計：有向圖拓?fù)渑判蛩惴ǖ膶崿F(xiàn)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計說明書有向圖拓?fù)渑判蛩惴ǖ膶崿F(xiàn)學(xué)生姓名樊佳佳學(xué)號1318064017班級網(wǎng)絡(luò)工程1301成績指導(dǎo)教師申靜數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院2016年1月4日課程設(shè)計任務(wù)書 20152016學(xué)年第一學(xué)期課程設(shè)計名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 課程設(shè)計題目： 圖的拓?fù)渑判蛩惴ǖ膶崿F(xiàn) 完 成 期 限：自 2015年 12月20日至 2016年 1 月 3 日共 2 周設(shè)計內(nèi)容：1、設(shè)計任務(wù)（1）給出一個有向無環(huán)圖，遍歷所有的節(jié)點(diǎn)；（2）能夠?qū)崿F(xiàn)對所有頂點(diǎn)的拓?fù)洌?3)界面友好，可操作性強(qiáng)。2、需求分析對系統(tǒng)的功能及性能要求進(jìn)行分析，寫出需求規(guī)格說明書（可行性分析報告、系統(tǒng)的分層DFD圖）。3、軟件設(shè)

2、計軟件設(shè)計分兩個階段進(jìn)行：總體設(shè)計和詳細(xì)設(shè)計；總體設(shè)計：確定系統(tǒng)總體設(shè)計方案，完成系統(tǒng)的模塊結(jié)構(gòu)圖及模塊的功能說明；詳細(xì)設(shè)計：對模塊內(nèi)部過程及數(shù)據(jù)結(jié)構(gòu)進(jìn)行設(shè)計，以及進(jìn)行數(shù)據(jù)庫設(shè)計、用戶界面設(shè)計等編寫出該項目的詳細(xì)設(shè)計報告；4、具體編碼編寫程序，要求給出詳細(xì)的注釋，包括：模塊名、模塊功能、中間過程的功能、 變量說明等。同時編寫用戶使用手冊、程序模塊說明等文檔；5、軟件測試所有測試過程要求采用綜合測試策略：先作靜態(tài)分析，再作動態(tài)測試。應(yīng)事先制訂測試計劃，并要求保留所有測試用例，完成測試報告。指導(dǎo)教師：申靜 教研室負(fù)責(zé)人：申靜課程設(shè)計評閱評語： 指導(dǎo)教師簽名： 年 月 日摘 要設(shè)計了一個對有向圖進(jìn)行

3、拓?fù)渑判虻乃惴?，該算法首先用鄰接表?gòu)造有向圖的存儲結(jié)構(gòu)，然后對此有向圖進(jìn)行拓?fù)渑判?，輸出拓?fù)渑判虻慕Y(jié)果。用VC+作為軟件開發(fā)環(huán)境，以鄰接表作為圖的存儲結(jié)構(gòu)，將圖中所有頂點(diǎn)排成一個線性序列，輸出拓?fù)渑判蚪Y(jié)果。拓?fù)渑判虺Ｓ脕泶_定一個依賴關(guān)系集中，事物發(fā)生的順序。拓?fù)渑判蚴菍τ邢驘o環(huán)圖的頂點(diǎn)的一種排序，它使得如果存在一條從頂點(diǎn)A到頂點(diǎn)B的路徑，那么在排序中B出現(xiàn)在A的后面。關(guān)鍵詞：鄰接表；有向無環(huán)圖；拓?fù)渑判蚰?錄1 課題描述12 問題分析和任務(wù)定義23 邏輯設(shè)計33.1程序模塊功能圖33.2 抽象數(shù)據(jù)類型34 詳細(xì)設(shè)計44.1 C語言定義的相關(guān)數(shù)據(jù)類型44.2 主要模塊的偽碼算法44.2.1主函數(shù)

4、偽碼算法44.2.2鄰接表偽碼算法44.2.3拓?fù)渑判虻膫未a算法：54.3 主函數(shù)流程圖65 程序編碼76 程序調(diào)試與測試137 結(jié)果分析168 總結(jié)17參考文獻(xiàn)181 課題描述根根據(jù)設(shè)計要求運(yùn)用C語言程序設(shè)計了一個對有向圖進(jìn)行拓?fù)渑判虻乃惴?，該算法首先用鄰接表?gòu)造有向圖的存儲結(jié)構(gòu)，然后對此有向圖進(jìn)行拓?fù)渑判?，輸出拓?fù)渑判虻慕Y(jié)果。如給定一個有向無環(huán)圖如圖1.1所示。在此圖中，從入度為0的頂點(diǎn)出發(fā)，刪除此頂點(diǎn)和所有以它為尾的??；重復(fù)直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止。 23 1 4 5圖1.1 有向無環(huán)圖開發(fā)工具：Visual C+ 6.0第 1 頁 共18 頁2 問題分析和

5、任務(wù)定義對一個有向無環(huán)圖G進(jìn)行拓?fù)渑判?，是將G中所有頂點(diǎn)排成一個線性序列，使得圖中任意一對由某個集合上的一個偏序得到該集合上的一個全序，這個操作就稱之為拓?fù)渑判?。偏序集合中僅有部分成員之間顆比較，而全序指集合中全體成員之間均可比較，而由偏序定義得到拓?fù)溆行虻牟僮鞅闶峭負(fù)渑判?。一個表示偏序的有向圖可用來表示一個流程圖，通過抽象出來就是AOV-網(wǎng)，若從頂點(diǎn)i到頂點(diǎn)j有一條有向路徑，則i是j的前驅(qū)，j是i的后繼。若（i，j）是一條弧，則i是j的直接前驅(qū)；j是i的直接后繼。在AOV-網(wǎng)中，不應(yīng)該出現(xiàn)有向環(huán)，用拓?fù)渑判蚓涂梢耘袛嗑W(wǎng)中是否有環(huán)，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV-網(wǎng)必定不存在

6、環(huán)。第 18 頁 共 18 頁3 邏輯設(shè)計主函數(shù)3.1程序模塊功能圖拓?fù)渑判蚬?jié)點(diǎn)入度棧的初始化創(chuàng)建鄰接表有向圖初始化圖3.1程序模塊功能圖3.2 抽象數(shù)據(jù)類型ADT ALGraph數(shù)據(jù)對象：D=V|V是具有相同特性的數(shù)據(jù)元素的集合，即頂點(diǎn)集數(shù)據(jù)關(guān)系：R=|v,wV,表示頂點(diǎn)v到頂點(diǎn)w的弧基本操作P:CreatGraphlist(ALGraph *G)初始條件：成對輸入頂點(diǎn)集V中的點(diǎn)。操作結(jié)果：構(gòu)造圖G的鄰接表。FindInDegree(ALGraph G, int indegree)初始條件：圖G的鄰接表中存在結(jié)點(diǎn)V。操作結(jié)果：找到圖中入度為0結(jié)點(diǎn)。Initgraph()操作結(jié)果：完成圖形初始

7、化。TopologicalSort(ALGraph G)初始條件：構(gòu)造的有向圖G已初始化。操作結(jié)果：對于有向圖G根據(jù)鄰接存儲表進(jìn)行拓?fù)渑判颉? 詳細(xì)設(shè)計4.1 C語言定義的相關(guān)數(shù)據(jù)類型#define max_vextex_num 20 /*宏定義最大頂點(diǎn)個數(shù)*/ #define stack_init_size 100 /*宏定義棧的存儲空間大小*/ typedef int ElemType; typedef struct VNode /*鄰接表頭結(jié)點(diǎn)的類型*/int data; /*頂點(diǎn)信息,數(shù)據(jù)域*/VNode, AdjListMAX_VEXTEX_NUM; /*AdjList是鄰接表類型*

8、/typedef struct AdjList vertices; /*鄰接表*/ int vexnum, arcnum; /*圖中頂點(diǎn)數(shù)vexn和邊數(shù)arcn*/ALGraph; /*圖的類型*/typedef struct /構(gòu)建棧 ElemType *base; /*數(shù)據(jù)域*/ ElemType *top; /*棧指針域*/int stacksize; SqStack;4.2 主要模塊的偽碼算法4.2.1主函數(shù)偽碼算法：開始 創(chuàng)建及輸出鄰接表CreatGraphlist(&G);輸出排序后的輸出序列TopologicalSort(G);結(jié)束4.2.2鄰接表偽碼算法：#define MAX

9、_VEXTEX_NUM 20typedef struct VNode /*鄰接表頭結(jié)點(diǎn)的類型*/ int data; /*頂點(diǎn)信息,數(shù)據(jù)域*/ ArcNode *firstarc; /*指向第一條弧*/VNode, AdjListMAX_VEXTEX_NUM; /*AdjList是鄰接表類型*/typedef struct AdjList vertices; /*鄰接表*/ int vexnum, arcnum; /*圖中頂點(diǎn)數(shù)vexn和邊數(shù)arcn*/ALGraph; /*圖的類型*/開始定義一個指針P置i的初值為1鄰接表中所有頭結(jié)點(diǎn)指針置初值當(dāng)i=G-vexnum時自加，執(zhí)行下面操作：輸出

10、數(shù)據(jù)域里的頂點(diǎn)信息使指針p指向頂點(diǎn)i第一條弧的頭結(jié)點(diǎn)輸出訪問頂點(diǎn)使指針p指向頂點(diǎn)i的下一條弧的頭結(jié)點(diǎn)類此循環(huán)到輸出最后一個頂點(diǎn)結(jié)束4.2.3拓?fù)渑判虻膫未a算法開始引入棧操作函數(shù)和入度操作函數(shù)訪問鄰接存儲表中的頂點(diǎn)nIf該頂點(diǎn)入度為0頂點(diǎn)進(jìn)棧循環(huán)操作到所有頂點(diǎn)入棧當(dāng)棧不為空頂點(diǎn)出棧結(jié)束4.3 主函數(shù)流程圖主函數(shù)流程圖如圖4.3所示開始輸入頂點(diǎn)數(shù)和弧數(shù)N輸入判斷是否滿足條件 Y根據(jù)輸入信息建立鄰接表 建棧在鄰接表中尋找入度為零的頂點(diǎn)，使其入棧N輸出棧頂元素，打印，將與棧頂元素鄰接的頂點(diǎn)的入度減1判斷是否空棧 Y 結(jié)束圖4.3 主函數(shù)程序流程圖5 程序編碼#include#include#defin

11、e true 1#define false 0#define MAX_VEXTEX_NUM 20#define M 20#define STACK_INIT_SIZE 100#define STACKINCREMENT 10/*-圖的鄰接表存儲結(jié)構(gòu)-*/typedef struct ArcNode /*弧結(jié)點(diǎn)結(jié)構(gòu)類型*/ int adjvex; /*該弧指向的頂點(diǎn)的位置*/ struct ArcNode *nextarc; /*指向下一條弧的指針*/ArcNode;typedef struct VNode /*鄰接表頭結(jié)點(diǎn)類型*/ int data; /*頂點(diǎn)信息*/ ArcNode *fir

12、starc; /*指向第一條依附于該點(diǎn)的弧的指針*/ VNode,AdjListMAX_VEXTEX_NUM; /*AdjList為鄰接表類型*/typedef struct AdjList vertices; int vexnum, arcnum;ALGraph;/*-*/void CreatGraph(ALGraph *G) /*通過用戶交互產(chǎn)生一個圖的鄰接表*/ int m, n, i; ArcNode *p; printf(=); printf(n輸入頂點(diǎn)數(shù):); scanf(%d,&G-vexnum); printf(n輸入邊數(shù):); scanf(%d,&G-arcnum); pri

13、ntf(=); for (i=1; ivexnum;i+) /*初始化各頂點(diǎn)*/ G-verticesi.data=i; /*編寫頂點(diǎn)的位置序號*/ G-verticesi.firstarc=NULL; for (i=1;iarcnum;i+) /*記錄圖中由兩點(diǎn)確定的弧*/ printf(n輸入確定弧的兩個頂點(diǎn)u，v:); scanf(%d %d,&n,&m); while (nG-vexnum|mG-vexnum) printf(輸入的頂點(diǎn)序號不正確 請重新輸入:); scanf(%d%d,&n,&m); p=(ArcNode*)malloc(sizeof(ArcNode); /*開辟新的

14、弧結(jié)點(diǎn)來存儲用戶輸入的弧信息*/ if(p=NULL) printf(ERROR!); exit(1); p-adjvex=m; /*該弧指向位置編號為m的結(jié)點(diǎn)*/ p-nextarc=G-verticesn.firstarc;/*下一條弧指向的是依附于n的第一條弧*/ G-verticesn.firstarc=p; printf(=); printf(n建立的鄰接表為:n); /*打印生成的鄰接表（以一定的格式）*/ for(i=1;ivexnum;i+) printf(%d,G-verticesi.data); for(p=G-verticesi.firstarc;p;p=p-nextar

15、c) printf(-%d,p-adjvex); printf(n); printf(=);/*-*/typedef struct /*棧的存儲結(jié)構(gòu)*/ int *base; /*棧底指針*/ int *top; /*棧頂指針*/ int stacksize;SqStack;/*-*/void InitStack(SqStack *S) /*初始化棧*/ S-base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!S-base) /*存儲分配失敗*/ printf(ERROR!); exit(1); S-top=S-base; S-stacksi

16、ze=STACK_INIT_SIZE;/*-*/void Push(SqStack *S,int e) /*壓入新的元素為棧頂*/ if(S-top-S-base=S-stacksize) S-base=(int *)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(int); /*追加新空間*/ if(!S-base) /*存儲分配失敗*/ printf(ERROR!); exit(1); S-top=S-base+S-stacksize; S-stacksize+=STACKINCREMENT; *S-top+=e; /*e作為新的棧頂元

17、素*/*-*/int Pop(SqStack *S,int *e) /*彈出棧頂，用e返回*/ if(S-top=S-base) /*棧為空*/ return false; *e=*-S-top;return 0;/*-*/int StackEmpty(SqStack *S) /*判斷棧是否為空，為空返回1，不為空返回0*/ if(S-top=S-base) return true; else return false;/*-*/void FindInDegree(ALGraph G, int indegree) /*對各頂點(diǎn)求入度*/ int i; for(i=1; i=G.vexnum;i

18、+) /*入度賦初值0*/ indegreei=0; for(i=1;iadjvex+; /*出度不為零，則該頂點(diǎn)firstarc域指向的弧指向的頂點(diǎn)入度加一*/ G.verticesi.firstarc = G.verticesi.firstarc-nextarc; /*-*/void TopoSort(ALGraph G) int indegreeM; int i, k, n; int count=0; /*初始化輸出計數(shù)器*/ ArcNode *p; SqStack S; FindInDegree(G,indegree); InitStack(&S); for(i=1;i=G.vexnu

19、m;i+) printf(n); printf(indegree%d = %d n,i,indegreei); /*輸出入度*/ printf(n); for(i=1;inextarc)/*n號頂點(diǎn)的每個鄰接點(diǎn)入度減一*/ k=p-adjvex; if(!(-indegreek) /*若入度減為零，則再入棧*/ Push(&S,k); if(countG.vexnum)/*輸出頂點(diǎn)數(shù)小于原始圖的頂點(diǎn)數(shù)，有向圖中有回路*/ printf(ERROR 出現(xiàn)錯誤!); else printf( 排序成功!);/*-*/main(void) /*編寫主調(diào)函數(shù)以調(diào)用上述被調(diào)函數(shù)*/ ALGraph G;

20、 CreatGraph(&G); /*建立鄰接表*/ TopoSort(G); /*對圖G進(jìn)行拓?fù)渑判?/printf(nn); system(pause); /*調(diào)用系統(tǒng)的dos命令：pause;顯示:按任意鍵繼續(xù).*/ return 0;6 程序調(diào)試與測試（1）當(dāng)為有向有環(huán)圖結(jié)構(gòu)如圖6.3所示圖6.3 有向有環(huán)圖結(jié)構(gòu)輸出結(jié)果如圖6.4所示圖6.4有向有環(huán)圖的輸出（2）輸入檢驗圖如圖6.5所示：圖6.5 檢驗圖由鄰接表定義可以得到上圖的鄰接表如圖6.6所示：圖6.6鄰接表其中一種拓?fù)湫蛄校?2 7 1 3 4 6 5將圖輸入到程序中結(jié)果如圖6.7所示：圖6.8 檢驗圖的輸出所得結(jié)果與預(yù)計結(jié)果

21、一致。7 結(jié)果分析對于算法的時間復(fù)雜度和空間復(fù)雜度， 拓?fù)渑判驅(qū)嶋H是對鄰接表表示的圖G進(jìn)行遍歷的過程，每次訪問一個入度為零的頂點(diǎn)，若圖G中沒有回路，則需掃描鄰接表中的所有邊結(jié)點(diǎn)，在算法開始時，為建立入度數(shù)組D需訪問表頭向量中的所有邊結(jié)點(diǎn)，算法的時間復(fù)雜度為O(n+e)。其次在編寫代碼時應(yīng)根據(jù)流程圖進(jìn)行同步編寫，綜合考慮需求分析進(jìn)行編輯。否則會出現(xiàn)偏離主題的錯誤。當(dāng)然在輸出結(jié)果后，為避免輸入引起的錯誤，因該先對開始與結(jié)束結(jié)果進(jìn)行先得出，與運(yùn)行結(jié)果對照，小的問題應(yīng)該進(jìn)行盡量的避免，或減小到最小值。8 總結(jié)平時我就比較愛好編程，有時候自己也會設(shè)想一些小程序，然后通過自己的努力來實現(xiàn)。因此我把本次課程

22、設(shè)計當(dāng)作了又一次鍛煉，拿到題目后，經(jīng)過與組員的討論便開始了程序的編寫。大家都知道，編程是一件很需要耐心的事。因為幾乎每一個程序的編寫，都需要學(xué)習(xí)新的知識才能進(jìn)行，同時程序調(diào)試過程很枯燥，有時候一點(diǎn)小錯意味著長時間的查錯。如語法錯誤中，“;”丟失、“”與“”不匹配等問題最難定位到出錯語句；邏輯錯誤中，作為循環(huán)變量的“i”與“j”相互混淆、對未分配空間的節(jié)點(diǎn)進(jìn)行操作等，都會使程序運(yùn)行出錯而難以找到原因。算法設(shè)計、程序調(diào)試的過程中，經(jīng)常遇到看似簡單但又無法解決的問題，這時候很容易灰心喪氣，此時切不可煩躁，一定要冷靜的思考，認(rèn)真的分析；而解決問題，完成程序后，那種興奮感與成就感也令人振奮。可以說編寫程序既是一件艱苦的工作，又是一件愉快的事情。我的小組課程設(shè)計題目的核心是“拓?fù)渑判颉?。雖然平時對拓?fù)渑判蛴幸恍┝私?，上課也學(xué)過，但真正應(yīng)用到程序中，寫出算法卻一點(diǎn)也不簡單。拓?fù)渑判?，首先需要有被排序的主體，也就是有向圖，于是先要實現(xiàn)有向圖的建立及相關(guān)操作；有向圖的建立，該選取怎樣的數(shù)據(jù)結(jié)構(gòu)，是鄰接矩陣還是鄰接表，本著盡量靠近實際應(yīng)用的態(tài)度，我選擇了節(jié)省存儲空間的鄰接表；拓?fù)渑判蛞獙D中零入度頂點(diǎn)先輸出，可利用棧或隊列實現(xiàn)，而本程序的一個應(yīng)用是實現(xiàn)教學(xué)計劃的安排，考慮到教學(xué)計劃安排的實際情況，一般先學(xué)各門基礎(chǔ)課（入度為零），再學(xué)專業(yè)