拓撲排序課程設計報告

1、航空航天大學課程設計報告Word資料課程設計名稱:課程設計題目:數(shù)據(jù)結(jié)構(gòu)課程設計 拓撲排序算法院（系）：計算機學院專 業(yè)：計算機科學與技術(shù)（嵌入式系統(tǒng)方向）班 級：14010105班學 號：2011040101221姓 名：王蒞然指導教師：丁一軍1課程設計介紹11.1 課程設計容11.2 課程設計要求12課程設計原理22.1 課設題目粗略分析22.2 原理圖介紹32.2.1 功能模塊圖32.2.2 流程圖分析33數(shù)據(jù)結(jié)構(gòu)分析83.1 存儲結(jié)構(gòu)83.2 算法描述84調(diào)試與分析1.5.4.1 調(diào)試過程154.2 程序執(zhí)行過程.15參考文獻1.8.附 錄（關(guān)鍵部分程序清單） 19.Word資料1課程

2、設計介紹1.1 課程設計容由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。若在圖一的有向圖上人為的加一個表示V2<=V3的?。?lt;二”表的2領(lǐng)先于V3）則圖一表示的亦為全序且這個全序稱為拓撲有序 ，而由偏序定義得到 拓撲有序的操作便是拓撲排序。 在AOV網(wǎng)中為了更好地完成工程，必須滿足 活動之間先后關(guān)系，需要將各活動排一個先后次序即為拓撲排序。編寫算法 建立有向無環(huán)圖，主要功能如下：1 .能夠求解該有向無環(huán)圖的拓撲排序并輸出出來；2 .拓撲排序應該能處理出現(xiàn)環(huán)的情況；3 .頂點信息要有幾種情況可以選擇。1.2 課程設計要求1 .輸出拓撲排序數(shù)據(jù)外，還要輸出鄰接表

3、數(shù)據(jù)；2 .參考相應的資料，獨立完成課程設計任務；3 .交規(guī)課程設計報告和軟件代碼。2 課程設計原理2.1課設題目粗略分析本課設題目要求編寫算法能夠建立有向無環(huán)圖，有向無環(huán)圖，顧名思義，即一個 無環(huán)的有向圖，是一類較有向圖更一般的特殊有向圖。其功能要求及個人在寫程序時對該功能的實現(xiàn)作如下分析：1 .將圖以合適的方式存儲起來。圖有多種存儲方式，其中最常用的存儲方式有圖 的鄰接矩陣和鄰接表。本人在構(gòu)思時使用鄰接表來建立有向無環(huán)圖，將其存儲起 來；2 .求解該有向無環(huán)圖的拓撲排序，并將其輸出出來。若通過構(gòu)造，建立了一個有 向無環(huán)圖，那么一定可以求出其拓撲排序，其原理比較簡單。即統(tǒng)計每個節(jié)點的 入度，

4、將入度為0的結(jié)點提取出來，然后再統(tǒng)計剩下的結(jié)點的入度，再次將入度 為零的結(jié)點提取出來，以此類推，這樣就形成了一個序列，這樣的序列就是該圖 的拓撲排序序列；3 .拓撲排序算法應能夠處理出現(xiàn)環(huán)的情況。個人在寫程序時，考慮到構(gòu)造圖時， 會有構(gòu)造成有向有環(huán)圖的情況，應該在運行程序時，試著統(tǒng)計依次按照入讀為零 的節(jié)點輸出的節(jié)點數(shù)是否為整個節(jié)點的總數(shù)，如果是，那么拓撲排序成功，輸出 拓撲排序的結(jié)果，否者輸出“有環(huán)出現(xiàn)”；4 .輸出除拓撲排序外，還要求輸出鄰接表數(shù)據(jù)。由于圖是用鄰接表存儲的，所以 將鄰接表按照順序依次打印輸出。5 .2原理圖介紹2.2.1 功能模塊圖Word資料拓撲排序算法拓撲排序打印鄰接表

5、圖的建立入讀為零的依次輸出有向無環(huán)圖可進行鄰接表鄰接矩陣圖2.1功能模塊圖2.2.2 流程圖分析1 .如圖2.2所示，根據(jù)題目要求建立一個有向無環(huán)圖，按照提示，依次輸 入節(jié)點數(shù)和變數(shù)，然后卒&入兩個聯(lián)通的節(jié)點<u,v> ,前者指向后者，當輸入邊數(shù)為所要輸入的數(shù)目時，輸入結(jié)束，有向圖建立完成（未判斷是否有環(huán)）。建立有向無環(huán)圖輸入節(jié)點數(shù)i,邊數(shù)n, j=0Nj<n結(jié)束圖2.2建立有向無環(huán)圖2 .如圖2,3所示，判斷有向圖是否為有向無環(huán)圖。按照輸入的有向圖建立 一個鄰接表，將圖儲存在鄰接表中，并將鄰接表打印，然后對該鄰接表進行拓撲 排序，依次取入度為零的節(jié)點，入棧，并刪除該

6、節(jié)點和該節(jié)點有關(guān)的所邊，若入 棧節(jié)點個數(shù)與節(jié)點數(shù)相同，則全部入棧，該圖為無環(huán)圖，可以進行拓撲排序，若 該圖節(jié)點數(shù)大于入棧節(jié)點數(shù)，則該圖為有環(huán)圖。、開始k_J建立鄰接表并打印取入度為零的節(jié)點入 棧，刪除該節(jié)點，繼 續(xù)遍歷其他節(jié)點入棧節(jié)點數(shù)等 于節(jié)點總數(shù)Y該圖為無環(huán)圖該圖為有環(huán)圖ff結(jié)束</圖2.3判斷是否為無環(huán)圖3 .此時該圖為有向無環(huán)圖，可進行拓撲排序，在上一過程中，所有節(jié)點已經(jīng)入棧，將棧頂彈出進入另一個空棧，然后依次輸出棧頂，拓撲排序成功。如圖2.4所示。開始圖2.4輸出拓撲排序結(jié)果4.具體容開始圖2.5拓撲排序3數(shù)據(jù)結(jié)構(gòu)分析3.1 存儲結(jié)構(gòu)一個無環(huán)的有向圖叫做有向無環(huán)圖，簡稱DAG圖

7、。本算法首先要建立一個有 向無環(huán)圖，即通過輸入各邊的數(shù)據(jù)，搭建圖的結(jié)構(gòu)。對于圖的存儲，用到鄰接表, 是一種鏈式存儲結(jié)構(gòu)?；〗Y(jié)點結(jié)構(gòu)類型：typedef struct ArcNodeint adjvex;/*該弧指向的頂點的位置*/struct ArcNode *nextarc;/*指向下一條弧的指針 */ArcNode;鄰接表頭結(jié)點類型：typedef struct VNodeint data;/*頂點信息*/ArcNode *firstarc;/*指向第一條依附于該點的弧的指針*/VNode,AdjListMAX_VEXTEX_NUM;3.2 算法描述1 .鄰接表的構(gòu)建創(chuàng)建一個鄰接表，首先要

8、輸入節(jié)點數(shù)和邊數(shù)，然后輸入確定一條邊的兩個節(jié)點，通過輸入順序來確定邊的方向，構(gòu)成有向圖，具體方法如下：初始化頭結(jié)點for (i=1; i<=G->vexnum;i+)G->verticesi.data=i;/*編寫頂點的位置序號*/G->verticesi.firstarc=NULL;先將頭結(jié)點清零，編寫頂點位置序號。輸入確定弧的兩點，如果輸入數(shù)字大于節(jié)點數(shù)或者小于零，則輸出錯誤信息 并重新輸入一組節(jié)點，申請新的節(jié)點來儲存新的節(jié)點信息，該弧指向位置編號為 m的節(jié)點，下一條弧指向的是依附于n的第一條弧，最后打印生成的鄰接表。for (i=1;i<=G->arc

9、num;i+)printf("n輸入確定弧的兩個頂點 u, v:");scanf("%d %d",&n,&m);while (n<0|n>G->vexnum|m<0|m>G->vexnum)printf("輸入的頂點序號不正確請重新輸入:");scanf("%d%d",&n,&m);p=(ArcNode*)malloc(sizeof(ArcNode); /*開辟新的弧結(jié)點 */ if(p=NULL)printf("ERROR!"

10、);exit(1);p->adjvex=m;/*該弧指向位置編號為 m的結(jié)點*/p->nextarc=G->verticesn.firstarc;G->verticesn.firstarc=p;printf("n建立的鄰接表為：n"); /*打印生成的鄰接表(以一定的格式)*/for(i=1;i<=G->vexnum;i+)printf("%d”,G->verticesi.data);for(p=G->verticesi.firstarc;p;p=p->nextarc)printf("->%d”

11、,p->adjvex);printf("n"); 鄰接表構(gòu)建完成。2 .入棧操作在本算法中棧主要用來構(gòu)造拓撲排序序列。由于棧具有先入后出的特點，所 以，將每次選擇入度為零的結(jié)點入棧，這樣當結(jié)點都入棧的時候，再依次出棧，進入另一個新棧，這樣，排序序列顯而易見。它將圖這樣的非線性結(jié)構(gòu)轉(zhuǎn)化為棧這樣的線性結(jié)構(gòu)。建立空棧typedef structint *base;/* 棧底指針 */int *top;/*棧頂指針*/int stacksize;SqStack;初始化棧void InitStack(SqStack *S)S->base=(int *)malloc(STA

12、CK_INIT_SIZE*sizeof(int);if(!S->base)/*存儲分配失敗*/printf("ERROR!");exit；S->top=S->base;S->stacksize=STACK_INIT_SIZE;入棧操作，壓入新的元素為棧頂,e為新的棧頂元素void Push(SqStack *S,int e)/* 壓入新的元素為棧頂 */if(S->top-S->base>=S->stacksize)S->base=(int*)realloc(S->base,(S->stacksize+STA

13、CKINCREMENT)*sizeof(int);if(!S->base)printf("ERROR!");exit；S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;*S->top+=e;3 .拓撲排序本程序的拓撲排序，必須在圖的鄰接表已知的情況下。它還有另外一個功能:判斷一個圖是不是無環(huán)圖。確切的說，不能單純的叫拓撲排序，但考慮它主要的 作用，在不引起誤解的情況下就叫拓撲排序算法。判斷一個圖是否為有向無環(huán)圖并進行拓撲排序，對于本題目來說，由于本題 要對有向無環(huán)圖進行拓撲排

14、序，其主要方法是將入度為零的結(jié)點依次輸出出來， 知道圖的所有定點全部輸出為止。那么若圖為有環(huán)圖，在環(huán)上的結(jié)點在其他結(jié)點 都選擇出來后，入度都不為零，即無法被輸出出來。那么就可以認為按照拓撲排 序的方法輸出結(jié)點后，若不是將節(jié)點全部輸出出來的，則此圖為有環(huán)圖。輸出有 向圖有環(huán)，拓撲排序失敗。若無環(huán)，則進行拓撲排序。通過入棧出棧的操作來完 成拓撲排序。主要算法如下：void TopoSort(ALGraph G) int indegreeM;int i, k, n;int count=0;/*初始化輸出計數(shù)器*/ArcNode *p;SqStack S;FindInDegree(G,indegree

15、);InitStack(&S);printf("n");for(i=1;i<=G.vexnum;i+)/*入度為 0 的入棧*/ if(!indegreei)Push(&S,i);printf("n拓撲排序序列為:");while(!StackEmpty(&S)/*棧不為空*/Pop(&S,&n);/* 彈出棧頂 */printf("%4d",G.verticesn.data); /*輸出棧頂并計數(shù) */ count+;for(p=G.verticesn.firstarc; p!=NULL

16、;p=p->nextarc)k=p->adjvex;*/if(!(-indegreek)/*若入度減為零，則再入棧Push(&S,k);if(count<G.vexnum) printf("有向圖中有環(huán)");else printf("排序成功!");4調(diào)試與分析4.1 調(diào)試過程在調(diào)試程序是主要遇到一下幾類問題：1 .數(shù)組的數(shù)據(jù)容易出現(xiàn)混亂，比如節(jié)點用數(shù)字標識，數(shù)組結(jié)點的位置是從0 開始，而標識符往往從1開始，這在程序的開始就應該注意到；2 .各函數(shù)的形參和實參的區(qū)別，全局變量，局部變量的區(qū)別，特別是在做大 型程序的時候，如果多個

17、函數(shù)都要用到一個變量，那么就應把該變量定義為全局 變量，若錯誤的定義為局部變量，很容易出現(xiàn)錯誤；3 .程序應該調(diào)理清晰，結(jié)構(gòu)明朗，各個函數(shù)代表各個模塊，起到不同的作用， 并協(xié)調(diào)運作，形成含有不同功能的程序。開始時因為程序的結(jié)構(gòu)混亂而導致很難 調(diào)試，無法找到錯誤的根源。4.2 程序執(zhí)行過程系統(tǒng)使用說明：1 .圖的創(chuàng)建；2 .打印鄰接表；3 .進行拓撲排序；4 .退出程序。具體容：輸入邊數(shù)及節(jié)點數(shù)，如圖4.1所示清福人指令:12 3 0圖4.1主菜單圖的創(chuàng)建，如圖4.2所示:圖4.2圖的創(chuàng)建打印鄰接表，如圖4.3所示:青輸入指令工2 卜立的鄰接表為:k- >3 >2Q>4(3&g

18、t;4圖4.3打印鄰接表進行拓撲排序，如圖4.4所示:請輸入指令 3進行拓撲排序= = = L =124排序成功，圖4.4進行拓撲排序退出程序，如圖4,5所示:圖4.5退出程序參考文獻1嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)M.:清華大學，2007.2長海，娟.C程序設計M.:高等教育,2004.3譚浩強.C程序設計M.:清華大學，2005.4嚴蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）M.清華大學，2005.5高婷，明莉.實用數(shù)據(jù)結(jié)構(gòu)習題與實踐M.:清華大學，2011.6殷人昆.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅc C+描述）M.:清華大學，2007口寧正元.算法與數(shù)據(jù)結(jié)構(gòu)習題精解和實驗指導M.:清華大學,2005附 錄（關(guān)鍵部分

19、程序清單）程序代碼#include<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 10typedef struct ArcNode/* 弧結(jié)點結(jié)構(gòu)類型 */int adjvex;/*該弧指向的頂點的位置*/struct ArcNode *nextarc;/*指向下一條弧的指針*/ArcNode;typedef struct

20、VNodeint data;ArcNode *firstarc;的指針*/VNode,AdjListMAX_VEXTEX_NUM;typedef structAdjList vertices;int vexnum, arcnum;ALGraph;void CreatGraph(ALGraph *G)int m, n, i,j;ArcNode *p;/*鄰接表頭結(jié)點類型*/*頂點信息*/*指向第一條依附于該點的弧/*AdjList為鄰接表類型*/*創(chuàng)建一個圖的鄰接表*/printf(" =")；printf("n輸入頂點數(shù):");scanf("%

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

22、");scanf("%d %d",&n,&m);while (n<0|n>G->vexnum|m<0|m>G->vexnum)printf("輸入的頂點序號不正確請重新輸入:");scanf("%d%d",&n,&m);)p=(ArcNode*)malloc(sizeof(ArcNode); /* 申請新的弧結(jié)點來存儲用戶輸入的弧信息*/if(p=NULL)printf("ERROR!");exit；)p->adjvex=m;/*該

23、弧指向位置編號為m的結(jié)點*/p->nextarc=G->verticesn.firstarc;/*下一條弧指向的是依附于n的第一條弧*/G->verticesn.firstarc=p;) printf("= =");printf("n請輸入指令：")；scanf("%d",&j);if(j=3)printf(" n進行拓撲排序n");if(j=2)printf("n建立的鄰接表為：n");/*打印生成的鄰接表(以一定的格式)*/for(i=1;i<=G->v

24、exnum;i+)printf("%d”,G->verticesi.data);for(p=G->verticesi.firstarc;p;p=p->nextarc)printf("->%d”,p->adjvex);printf("n");printf("n請輸入指令：");scanf("%d",&j);if(j=0)printf("感您的使用！");exit(0);)elseif(j=3)printf("n進行拓撲排序");elsepr

25、intf("n指令錯誤)printf("=")；)typedef struct(int *base;int *top;int stacksize;SqStack;void InitStack(SqStack *S)/*棧的存儲結(jié)構(gòu)*/*棧底指針*/*棧頂指針*/*初始化棧*/(S->base=(int *)malloc(STACK_INIT_SIZE*sizeof(int);if(!S->base)/*存儲分配失敗*/printf("ERROR!");exit；S->top=S->base;S->stacksize

26、=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->stac

27、ksize+=STACKINCREMENT;*S->top+=e;int Pop(SqStack *S,int *e)if(S->top=S->base)return false;*e=*-S->top;return 0;int StackEmpty(SqStack *S)1,不為空返回0*/*e作為新的棧頂元素*/*彈出棧頂，用e返回*/*棧為空*/*判斷棧是否為空，為空返回if(S->top=S->base)return true;elsereturn false;void FindInDegree(ALGraph G, int indegree口)/*

28、 對各頂點求入度 */int i;for(i=1; i<=G.vexnum;i+)/*入度賦初值 0*/indegreei=0;for(i=1;i<=G.vexnum;i+)while(G.verticesi.firstarc)indegreeG.verticesi.firstarc->adjvex+;/*出度不為零，則該頂點firstarc域指向的弧指向的頂點入度加一 */G.verticesi.firstarc = G.verticesi.firstarc->nextarc;void TopoSort(ALGraph G)int indegreeM;int i, k

29、, n;int count=0;ArcNode *p;SqStack S;FindInDegree(G,indegree);InitStack(&S);printf("n");for(i=1;i<=G.vexnum;i+)/*初始化輸出計數(shù)器*/*入度為0的入棧*/if(!indegreei)Push(&S,i);printf("n拓撲排序序列為：")；while(!StackEmpty(&S)/* 棧不為空 */Pop(&S,&n);/* 彈出棧頂*/printf("%4d",G.verticesn.data); /* 輸出棧頂并計數(shù) */ count+;for(p=G.verticesn.firstarc; p!=NULL;p=p->nextarc)/*n號頂點的每個鄰接點入度減一 */k=p->adjvex;if(!(-indegreek) /*若入度減為零，則再入棧*/ Push(&S,k); if(count<G.vexnum)/*輸出頂點數(shù)小于原始圖的頂點數(shù)，有向圖中有回路*/printf（"有向圖中有環(huán)"）;)else(printf("排序成功!"