有向圖拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)說明書有向圖拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)學(xué)生姓名學(xué)號(hào)班級(jí)成績(jī)指導(dǎo)教師魏佳計(jì)算機(jī)科學(xué)與技術(shù)系2010年2月22日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)評(píng)閱書題目有向圖拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)學(xué)生姓名學(xué)號(hào)指導(dǎo)教師評(píng)語(yǔ)及成績(jī)成績(jī)：教師簽名：年月日辯論教師評(píng)語(yǔ)及成績(jī)成績(jī)：教師簽名：年月日教研室意見總成績(jī)：室主任簽名：年月日注：指導(dǎo)教師成績(jī)60%，辯論成績(jī)40%，總成績(jī)合成后按五級(jí)制記入。課程設(shè)計(jì)任務(wù)書2010—2011學(xué)年第二學(xué)期專業(yè)：信息管理與信息系統(tǒng)學(xué)號(hào)：姓名：課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)題目：有向圖拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)完成期限：自2011年2月22日至2011年3月4日共2周設(shè)計(jì)內(nèi)容：用C/C++編寫一個(gè)程序?qū)崿F(xiàn)有向圖的建立和排序。要求建立有向圖的存儲(chǔ)結(jié)構(gòu)，從鍵盤輸入一個(gè)有向圖，程序能夠自動(dòng)進(jìn)行拓?fù)渑判?。設(shè)計(jì)要求:1〕問題分析和任務(wù)定義：根據(jù)設(shè)計(jì)題目的要求，充分地分析和理解問題，明確問題要求做什么？〔而不是怎么做？〕限制條件是什么？確定問題的輸入數(shù)據(jù)集合。2〕邏輯設(shè)計(jì)：對(duì)問題描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原那么劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計(jì)的結(jié)果應(yīng)寫出每個(gè)抽象數(shù)據(jù)類型的定義〔包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)根本操作的功能說明〕，各個(gè)主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖；3〕詳細(xì)設(shè)計(jì)：定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個(gè)過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡(jiǎn)單和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，根本操作的規(guī)格說明盡可能明確具體。詳細(xì)設(shè)計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和根本操作做出進(jìn)一步的求精，寫出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架；4〕程序編碼：把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語(yǔ)言程序。同時(shí)參加一些注解和斷言，使程序中邏輯概念清楚；5〕程序調(diào)試與測(cè)試：采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能，設(shè)計(jì)測(cè)試數(shù)據(jù)確定疑點(diǎn)，通過修改程序來證實(shí)它或繞過它。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果；6〕結(jié)果分析：程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。算法的時(shí)間、空間復(fù)雜性分析；7〕編寫課程設(shè)計(jì)報(bào)告；以上要求中前三個(gè)階段的任務(wù)完成后，先將設(shè)計(jì)說明數(shù)的草稿交指導(dǎo)老師面審，審查合格前方可進(jìn)入后續(xù)階段的工作。設(shè)計(jì)工作結(jié)束后，經(jīng)指導(dǎo)老師驗(yàn)收合格后將設(shè)計(jì)說明書打印裝訂，并進(jìn)行辯論。指導(dǎo)教師〔簽字〕：教研室主任〔簽字〕：批準(zhǔn)日期：2011年2月21日摘要設(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é)果。該算法操作簡(jiǎn)單，易于用戶操作接受。關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；有向圖；拓?fù)渑判蚰夸汿OC\o"1-3"\u1課題描述 12問題分析和任務(wù)定義 23邏輯設(shè)計(jì) 333.2抽象數(shù)據(jù)類型34詳細(xì)設(shè)計(jì) 44.1C語(yǔ)言定義的相關(guān)數(shù)據(jù)類型44.2主要模塊的偽碼算法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語(yǔ)言程序設(shè)計(jì)了一個(gè)對(duì)有向圖進(jìn)行拓?fù)渑判虻乃惴?，該算法首先用鄰接表?gòu)造有向圖的存儲(chǔ)結(jié)構(gòu)，然后對(duì)此有向圖進(jìn)行拓?fù)渑判颍敵鐾負(fù)渑判虻慕Y(jié)果。如給定一個(gè)有向無環(huán)圖如所示。在此圖中，從入度為0的頂點(diǎn)出發(fā)，刪除此頂點(diǎn)和所有以它為尾的?。恢貜?fù)直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止。圖1.1有向無環(huán)圖開發(fā)工具：visualc++6.0。2問題分析和任務(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)，假設(shè)從頂點(diǎn)i到頂點(diǎn)j有一條有向路徑，那么i是j的前驅(qū)，j是i的后繼。假設(shè)〔i，j〕是一條弧，那么i是j的直接前驅(qū)；j是i的直接后繼。在AOV-網(wǎng)中，不應(yīng)該出現(xiàn)有向環(huán)，用拓?fù)渑判蚓涂梢耘袛嗑W(wǎng)中是否有環(huán)，假設(shè)網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，那么該AOV-網(wǎng)必定不存在環(huán)。3邏輯設(shè)計(jì)抽象數(shù)據(jù)類型ADTALGraph｛數(shù)據(jù)對(duì)象：D={V|V是具有相同特性的數(shù)據(jù)元素的集合，即頂點(diǎn)集}數(shù)據(jù)關(guān)系：R={<v,w>|v,w∈V,<v,w>表示頂點(diǎn)v到頂點(diǎn)w的弧}根本操作P:CreatGraphlist(ALGraph*G)初始條件：成對(duì)輸入頂點(diǎn)集V中的點(diǎn)。操作結(jié)果：構(gòu)造圖G的鄰接表。FindInDegree(ALGraphG,intindegree[])初始條件：圖G的鄰接表中存在結(jié)點(diǎn)V。操作結(jié)果：找到圖中入度為0結(jié)點(diǎn)。Initgraph()操作結(jié)果：完成圖形初始化。TopologicalSort(ALGraphG)初始條件：構(gòu)造的有向圖G已初始化。操作結(jié)果：對(duì)于有向圖G根據(jù)鄰接存儲(chǔ)表進(jìn)行拓?fù)渑判?。}4詳細(xì)設(shè)計(jì)4.1C語(yǔ)言定義的相關(guān)數(shù)據(jù)類型#definemax_vextex_num20/*宏定義最大頂點(diǎn)個(gè)數(shù)*/#definestack_init_size100/*宏定義棧的存儲(chǔ)空間大小*/typedefintElemType;typedefstructVNode/*鄰接表頭結(jié)點(diǎn)的類型*/{intdata;/*頂點(diǎn)信息,數(shù)據(jù)域*/}VNode,AdjList[MAX_VEXTEX_NUM];/*AdjList是鄰接表類型*/typedefstruct{AdjListvertices;/*鄰接表*/intvexnum,arcnum;/*圖中頂點(diǎn)數(shù)vexn和邊數(shù)arcn*/}ALGraph;/*圖的類型*/typedefstruct//構(gòu)建棧{ElemType*base;/*數(shù)據(jù)域*/ElemType*top;/*棧指針域*/intstacksize;}SqStack;4.2主要模塊的偽碼算法主函數(shù)偽碼算法：開始{創(chuàng)立及輸出鄰接表CreatGraphlist(&G);輸出排序后的輸出序列TopologicalSort(G);}結(jié)束鄰接表偽碼算法：#defineMAX_VEXTEX_NUM20typedefstructVNode/*鄰接表頭結(jié)點(diǎn)的類型*/{intdata;/*頂點(diǎn)信息,數(shù)據(jù)域*/ArcNode*firstarc;/*指向第一條弧*/}VNode,AdjList[MAX_VEXTEX_NUM];/*AdjList是鄰接表類型*/typedefstruct{AdjListvertices;/*鄰接表*/intvexnum,arcnum;/*圖中頂點(diǎn)數(shù)vexn和邊數(shù)arcn*/}ALGraph;/*圖的類型*/開始{定義一個(gè)指針P置i的初值為1鄰接表中所有頭結(jié)點(diǎn)指針置初值當(dāng)i<=G-vexnum時(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é)束拓?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所示：圖4.3主函數(shù)程序流程圖5程序編碼#include<stdio.h>#include<stdlib.h>#definetrue1#definefalse0#defineMAX_VEXTEX_NUM20#defineM20#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10/*圖的鄰接表存儲(chǔ)結(jié)構(gòu)*/typedefstructArcNode/*弧結(jié)點(diǎn)結(jié)構(gòu)類型*/{intadjvex;/*該弧指向的頂點(diǎn)的位置*/structArcNode*nextarc;/*指向下一條弧的指針*/}ArcNode;typedefstructVNode/*鄰接表頭結(jié)點(diǎn)類型*/{intdata;/*頂點(diǎn)信息*/ArcNode*firstarc;/*指向第一條依附于該點(diǎn)的弧的指針*/}VNode,AdjList[MAX_VEXTEX_NUM];/*AdjList為鄰接表類型*/typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;/**/voidCreatGraph(ALGraph*G)/*通過用戶交互產(chǎn)生一個(gè)圖的鄰接表*/{intm,n,i;ArcNode*p;printf("=======================================================");printf("\n輸入頂點(diǎn)數(shù):");scanf("%d",&G->vexnum); printf("\n輸入邊數(shù):"); scanf("%d",&G->arcnum); printf("=======================================================");for(i=1;i<=G->vexnum;i++)/*初始化各頂點(diǎn)*/ {G->vertices[i].data=i;/*編寫頂點(diǎn)的位置序號(hào)*/G->vertices[i].firstarc=NULL; }for(i=1;i<=G->arcnum;i++)/*記錄圖中由兩點(diǎn)確定的弧*/ {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("ERROR!");exit(1); }p->adjvex=m;/*該弧指向位置編號(hào)為m的結(jié)點(diǎn)*/p->nextarc=G->vertices[n].firstarc;/*下一條弧指向的是依附于n的第一條弧*/G->vertices[n].firstarc=p; }printf("=======================================================");printf("\n建立的鄰接表為:\n");/*打印生成的鄰接表〔以一定的格式〕*/for(i=1;i<=G->vexnum;i++) {printf("%d",G->vertices[i].data);for(p=G->vertices[i].firstarc;p;p=p->nextarc)printf("-->%d",p->adjvex);printf("\n"); }printf("=======================================================");}/**/typedefstruct/*棧的存儲(chǔ)結(jié)構(gòu)*/{int*base;/*棧底指針*/int*top;/*棧頂指針*/intstacksize;}SqStack;/**/voidInitStack(SqStack*S)/*初始化棧*/{S->base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!S->base)/*存儲(chǔ)分配失敗*/{printf("ERROR!");exit(1);}S->top=S->base;S->stacksize=STACK_INIT_SIZE;}/**/voidPush(SqStack*S,inte)/*壓入新的元素為棧頂*/{if(S->top-S->base>=S->stacksize){S->base=(int*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(int));/*追加新空間*/if(!S->base)/*存儲(chǔ)分配失敗*/ {printf("ERROR!");exit(1); }S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;}*S->top++=e;/*e作為新的棧頂元素*/}/**/intPop(SqStack*S,int*e)/*彈出棧頂，用e返回*/{if(S->top==S->base)/*棧為空*/{returnfalse;}*e=*--S->top;return0;}/**/intStackEmpty(SqStack*S)/*判斷棧是否為空，為空返回1，不為空返回0*/{if(S->top==S->base)returntrue;elsereturnfalse;}/**/voidFindInDegree(ALGraphG,intindegree[])/*對(duì)各頂點(diǎn)求入度*/{inti;for(i=1;i<=G.vexnum;i++)/*入度賦初值0*/ {indegree[i]=0; }for(i=1;i<=G.vexnum;i++) {while(G.vertices[i].firstarc) {indegree[G.vertices[i].firstarc->adjvex]++; /*出度不為零，那么該頂點(diǎn)firstarc域指向的弧指向的頂點(diǎn)入度加一*/G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc; } }}/**/voidTopoSort(ALGraphG){intindegree[M];inti,k,n;intcount=0;/*初始化輸出計(jì)數(shù)器*/ArcNode*p;SqStackS;FindInDegree(G,indegree);InitStack(&S);for(i=1;i<=G.vexnum;i++) {printf("\n"); printf("indegree[%d]=%d\n",i,indegree[i]);/*輸出入度*/ }printf("\n");for(i=1;i<=G.vexnum;i++)/*入度為0的入棧*/ {if(!indegree[i])Push(&S,i); }printf("=======================================================");printf("\n\n拓?fù)渑判蛐蛄袨?");while(!StackEmpty(&S))/*棧不為空*/ {Pop(&S,&n);/*彈出棧頂*/printf("%4d",G.vertices[n].data);/*輸出棧頂并計(jì)數(shù)*/count++;for(p=G.vertices[n].firstarc;p!=NULL;p=p->nextarc)/*n號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)入度減一*/ {k=p->adjvex;if(!(--indegree[k]))/*假設(shè)入度減為零，那么再入棧*/ {Push(&S,k); } } }if(count<G.vexnum)/*輸出頂點(diǎn)數(shù)小于原始圖的頂點(diǎn)數(shù)，有向圖中有回路*/ {printf("ERROR出現(xiàn)錯(cuò)誤!"); }else {printf("排序成功!"); }}/**/main(void)/*編寫主調(diào)函數(shù)以調(diào)用上述被調(diào)函數(shù)*/{ALGraphG;CreatGraph(&G);/*建立鄰接表*/TopoSort(G);/*對(duì)圖G進(jìn)行拓?fù)渑判?/ printf("\n\n");system("pause"); /*調(diào)用系統(tǒng)的dos命令：pause;顯示:"按任意鍵繼續(xù)..."*/return0;}6程序調(diào)試與測(cè)試〔1〕當(dāng)為有向無環(huán)圖：圖6.1有向無環(huán)圖輸出結(jié)果如圖6.2為：圖6.2有向無環(huán)圖的輸出結(jié)果〔2〕當(dāng)為有向有環(huán)圖結(jié)構(gòu)如圖6.3所示：圖6.3有向有環(huán)圖結(jié)構(gòu)輸出結(jié)果如圖6.4所示：圖6.4有向有環(huán)圖的輸出〔3〕輸入檢驗(yàn)圖如圖6.5所示：圖6.5檢驗(yàn)圖由鄰接表定義可以得到上圖的鄰接表如圖6.6所示：圖6.6鄰接表其中一種拓?fù)湫蛄校?713465將圖輸入到程序中結(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)，假設(shè)圖G中沒有回路，那么需掃描鄰接表中的所有邊結(jié)點(diǎn)，在算法開始時(shí)，為建立入度數(shù)組D需訪問表頭向量中的所有邊結(jié)點(diǎn)，算法的時(shí)間復(fù)雜度為O(n+e)。其次