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

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

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

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

4、算法44.2.1主函數(shù)偽碼算法44.2.2鄰接表偽碼算法44.2.3拓?fù)渑判虻膫未a算法：54.3 主函數(shù)流程圖65 程序編碼76 程序調(diào)試與測(cè)試137 結(jié)果分析168 總結(jié)17參考文獻(xiàn)181 課題描述根根據(jù)設(shè)計(jì)要求運(yùn)用C語言程序設(shè)計(jì)了一個(gè)對(duì)有向圖進(jìn)行拓?fù)渑判虻乃惴?，該算法首先用鄰接表?gòu)造有向圖的存儲(chǔ)結(jié)構(gòu)，然后對(duì)此有向圖進(jìn)行拓?fù)渑判?，輸出拓?fù)渑判虻慕Y(jié)果。如給定一個(gè)有向無環(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.02 問題分析和

5、任務(wù)定義對(duì)一個(gè)有向無環(huán)圖G進(jìn)行拓?fù)渑判?，是將G中所有頂點(diǎn)排成一個(gè)線性序列，使得圖中任意一對(duì)由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作就稱之為拓?fù)渑判颉Ｆ蚣现袃H有部分成員之間顆比較，而全序指集合中全體成員之間均可比較，而由偏序定義得到拓?fù)溆行虻牟僮鞅闶峭負(fù)渑判?。一個(gè)表示偏序的有向圖可用來表示一個(gè)流程圖，通過抽象出來就是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)。3 邏輯設(shè)計(jì)主函數(shù)3.1程序模塊功能圖拓?fù)渑判蚬?jié)點(diǎn)入度棧的初始化創(chuàng)建鄰接表有向圖初始化圖3.1程序模塊功能圖3.2 抽象數(shù)據(jù)類型ADT ALGraph數(shù)據(jù)對(duì)象：D=V|V是具有相同特性的數(shù)據(jù)元素的集合，即頂點(diǎn)集數(shù)據(jù)關(guān)系：R=<v,w>|v,wV,<v,w>表示頂點(diǎn)v到頂點(diǎn)w的弧基本操作P:CreatGraphlist(ALGraph *G)初始條件：成對(duì)輸入頂點(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()操作

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

8、st是鄰接表類型*/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鄰接表偽碼算

9、法：#define MAX_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; /*圖的類型*/開始定義一個(gè)指針P置i的初值為1鄰接表中所有頭結(jié)點(diǎn)指針置初值當(dāng)i<=G-ve

10、xnum時(shí)自加，執(zhí)行下面操作：輸出數(shù)據(jù)域里的頂點(diǎn)信息使指針p指向頂點(diǎn)i第一條弧的頭結(jié)點(diǎn)輸出訪問頂點(diǎn)使指針p指向頂點(diǎn)i的下一條弧的頭結(jié)點(diǎn)類此循環(huán)到輸出最后一個(gè)頂點(diǎn)結(jié)束4.2.3拓?fù)渑判虻膫未a算法開始引入棧操作函數(shù)和入度操作函數(shù)訪問鄰接存儲(chǔ)表中的頂點(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 程序編碼#incl

11、ude<stdio.h>#include<stdlib.h>#define true 1#define false 0#define MAX_VEXTEX_NUM 20#define M 20#define STACK_INIT_SIZE 100#define STACKINCREMENT 10/*-圖的鄰接表存儲(chǔ)結(jié)構(gòu)-*/typedef struct ArcNode /*弧結(jié)點(diǎn)結(jié)構(gòu)類型*/ int adjvex; /*該弧指向的頂點(diǎn)的位置*/ struct ArcNode *nextarc; /*指向下一條弧的指針*/ArcNode;typedef struct VN

12、ode /*鄰接表頭結(jié)點(diǎn)類型*/ int data; /*頂點(diǎn)信息*/ ArcNode *firstarc; /*指向第一條依附于該點(diǎn)的弧的指針*/ VNode,AdjListMAX_VEXTEX_NUM; /*AdjList為鄰接表類型*/typedef struct AdjList vertices; int vexnum, arcnum;ALGraph;/*-*/void CreatGraph(ALGraph *G) /*通過用戶交互產(chǎn)生一個(gè)圖的鄰接表*/ int m, n, i; ArcNode *p; printf("="); printf("n輸入頂點(diǎn)

13、數(shù):"); scanf("%d",&G->vexnum); printf("n輸入邊數(shù):"); scanf("%d",&G->arcnum); printf("="); for (i=1; i<=G->vexnum;i+) /*初始化各頂點(diǎn)*/ G->verticesi.data=i; /*編寫頂點(diǎn)的位置序號(hào)*/ G->verticesi.firstarc=NULL; for (i=1;i<=G->arcnum;i+) /*記錄圖中由兩點(diǎn)確定

14、的弧*/ printf("n輸入確定弧的兩個(gè)頂點(diǎn)u，v:"); scanf("%d %d",&n,&m); while (n<0|n>G->vexnum|m<0|m>G->vexnum) printf("輸入的頂點(diǎn)序號(hào)不正確 請(qǐng)重新輸入:"); scanf("%d%d",&n,&m); p=(ArcNode*)malloc(sizeof(ArcNode); /*開辟新的弧結(jié)點(diǎn)來存儲(chǔ)用戶輸入的弧信息*/ if(p=NULL) printf("

15、;ERROR!"); exit(1); p->adjvex=m; /*該弧指向位置編號(hào)為m的結(jié)點(diǎn)*/ p->nextarc=G->verticesn.firstarc;/*下一條弧指向的是依附于n的第一條弧*/ G->verticesn.firstarc=p; printf("="); printf("n建立的鄰接表為:n"); /*打印生成的鄰接表（以一定的格式）*/ for(i=1;i<=G->vexnum;i+) printf("%d",G->verticesi.data);

16、for(p=G->verticesi.firstarc;p;p=p->nextarc) printf("->%d",p->adjvex); printf("n"); printf("=");/*-*/typedef struct /*棧的存儲(chǔ)結(jié)構(gòu)*/ int *base; /*棧底指針*/ int *top; /*棧頂指針*/ int stacksize;SqStack;/*-*/void InitStack(SqStack *S) /*初始化棧*/ S->base=(int *)malloc(STACK

17、_INIT_SIZE*sizeof(int); if(!S->base) /*存儲(chǔ)分配失敗*/ printf("ERROR!"); exit(1); S->top=S->base; S->stacksize=STACK_INIT_SIZE;/*-*/void Push(SqStack *S,int e) /*壓入新的元素為棧頂*/ if(S->top-S->base>=S->stacksize) S->base=(int *)realloc(S->base,(S->stacksize+STACKINCREME

18、NT)*sizeof(int); /*追加新空間*/ if(!S->base) /*存儲(chǔ)分配失敗*/ printf("ERROR!"); exit(1); S->top=S->base+S->stacksize; S->stacksize+=STACKINCREMENT; *S->top+=e; /*e作為新的棧頂元素*/*-*/int Pop(SqStack *S,int *e) /*彈出棧頂，用e返回*/ if(S->top=S->base) /*棧為空*/ return false; *e=*-S->top;ret

19、urn 0;/*-*/int StackEmpty(SqStack *S) /*判斷棧是否為空，為空返回1，不為空返回0*/ if(S->top=S->base) return true; else return false;/*-*/void FindInDegree(ALGraph G, int indegree) /*對(duì)各頂點(diǎn)求入度*/ int i; for(i=1; i<=G.vexnum;i+) /*入度賦初值0*/ indegreei=0; for(i=1;i<=G.vexnum;i+) while(G.verticesi.firstarc) indegre

20、eG.verticesi.firstarc->adjvex+; /*出度不為零，則該頂點(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; /*初始化輸出計(jì)數(shù)器*/ ArcNode *p; SqStack S; FindInDegree(G,indegree); InitStack(&S); for(i=1;i<=G.vex

21、num;i+) printf("n"); printf("indegree%d = %d n",i,indegreei); /*輸出入度*/ printf("n"); for(i=1;i<=G.vexnum;i+) /*入度為0的入棧*/ if(!indegreei) Push(&S,i); printf("="); printf("nn拓?fù)渑判蛐蛄袨?"); while(!StackEmpty(&S) /*棧不為空*/ Pop(&S,&n); /*彈出棧頂

22、*/ printf("%4d",G.verticesn.data); /*輸出棧頂并計(jì)數(shù)*/ count+; for(p=G.verticesn.firstarc; p!=NULL;p=p->nextarc)/*n號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)入度減一*/ k=p->adjvex; if(!(-indegreek) /*若入度減為零，則再入棧*/ Push(&S,k); if(count<G.vexnum)/*輸出頂點(diǎn)數(shù)小于原始圖的頂點(diǎn)數(shù)，有向圖中有回路*/ printf("ERROR 出現(xiàn)錯(cuò)誤!"); else printf("

23、 排序成功!");/*-*/main(void) /*編寫主調(diào)函數(shù)以調(diào)用上述被調(diào)函數(shù)*/ ALGraph G; CreatGraph(&G); /*建立鄰接表*/ TopoSort(G); /*對(duì)圖G進(jìn)行拓?fù)渑判?/printf("nn"); system("pause"); /*調(diào)用系統(tǒng)的dos命令：pause;顯示:"按任意鍵繼續(xù)."*/ return 0;6 程序調(diào)試與測(cè)試（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）輸入檢驗(yàn)圖如圖6.5所示：

24、圖6.5 檢驗(yàn)圖由鄰接表定義可以得到上圖的鄰接表如圖6.6所示：圖6.6鄰接表其中一種拓?fù)湫蛄校?2 7 1 3 4 6 5將圖輸入到程序中結(jié)果如圖6.7所示：圖6.8 檢驗(yàn)圖的輸出所得結(jié)果與預(yù)計(jì)結(jié)果一致。7 結(jié)果分析對(duì)于算法的時(shí)間復(fù)雜度和空間復(fù)雜度， 拓?fù)渑判驅(qū)嶋H是對(duì)鄰接表表示的圖G進(jìn)行遍歷的過程，每次訪問一個(gè)入度為零的頂點(diǎn)，若圖G中沒有回路，則需掃描鄰接表中的所有邊結(jié)點(diǎn)，在算法開始時(shí)，為建立入度數(shù)組D需訪問表頭向量中的所有邊結(jié)點(diǎn)，算法的時(shí)間復(fù)雜度為O(n+e)。其次在編寫代碼時(shí)應(yīng)根據(jù)流程圖進(jìn)行同步編寫，綜合考慮需求分析進(jìn)行編輯。否則會(huì)出現(xiàn)偏離主題的錯(cuò)誤。當(dāng)然在輸出結(jié)果后，為避免輸入引起的錯(cuò)

25、誤，因該先對(duì)開始與結(jié)束結(jié)果進(jìn)行先得出，與運(yùn)行結(jié)果對(duì)照，小的問題應(yīng)該進(jìn)行盡量的避免，或減小到最小值。8 總結(jié)平時(shí)我就比較愛好編程，有時(shí)候自己也會(huì)設(shè)想一些小程序，然后通過自己的努力來實(shí)現(xiàn)。因此我把本次課程設(shè)計(jì)當(dāng)作了又一次鍛煉，拿到題目后，經(jīng)過與組員的討論便開始了程序的編寫。大家都知道，編程是一件很需要耐心的事。因?yàn)閹缀趺恳粋€(gè)程序的編寫，都需要學(xué)習(xí)新的知識(shí)才能進(jìn)行，同時(shí)程序調(diào)試過程很枯燥，有時(shí)候一點(diǎn)小錯(cuò)意味著長(zhǎng)時(shí)間的查錯(cuò)。如語法錯(cuò)誤中，“;”丟失、“”與“”不匹配等問題最難定位到出錯(cuò)語句；邏輯錯(cuò)誤中，作為循環(huán)變量的“i”與“j”相互混淆、對(duì)未分配空間的節(jié)點(diǎn)進(jìn)行操作等，都會(huì)使程序運(yùn)行出錯(cuò)而難以找到原因。算法設(shè)計(jì)、程序調(diào)試的過程中，經(jīng)常遇到看似簡(jiǎn)單但又無法解決的問題，這時(shí)候很容易灰心喪氣，此時(shí)切不可煩躁，一定要冷靜的思考，認(rèn)真的分析；而解決問題，完成程序后，那種興奮感與成就感也令人振奮?？梢哉f編寫程序既是一件艱苦的工作，又是一件愉快的事情。我的小組課程設(shè)計(jì)題目的核心是“拓?fù)渑判颉薄ｋm然平時(shí)對(duì)拓?fù)渑判蛴幸恍┝私?，上課也學(xué)過，但真正應(yīng)用到程序中，寫出算法卻一點(diǎn)也不簡(jiǎn)單。拓?fù)渑判颍紫刃枰斜慌判虻闹黧w，也就是有向圖，于是先要實(shí)現(xiàn)有向圖的建立及相關(guān)操作；有向圖的建立，該選取怎樣的數(shù)據(jù)結(jié)構(gòu)，是鄰接矩陣還是鄰接表，本著盡量靠近實(shí)際應(yīng)用的