拓?fù)渑判蛘n程設(shè)計報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計題目： 有向圖拓?fù)渑判?專 業(yè)： 信息與計算科學(xué) 學(xué) 號： 0 姓 名： 黃秋實 指導(dǎo)教師： 文 軍 2013年11月28日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 -拓?fù)渑判蛞?需求分析1.問題描述 本次課程設(shè)計題目是：用鄰接表構(gòu)造圖 然后進(jìn)行拓?fù)渑判?，輸出拓?fù)渑判蛐蛄型負(fù)渑判虻幕舅枷霝椋?1).從有向圖中選一個無前驅(qū)的頂點輸出；2).將此頂點和以它為起點的弧刪除；3). 重復(fù)1),2)直到不存在無前驅(qū)的頂點；4). 若此時輸出的頂點數(shù)小于有向圖中的頂點數(shù)，則說明有向圖中存在回路，否則輸出的頂點的順序即為一個拓?fù)湫蛄小?2. 拓?fù)渑判?有向圖拓樸排序算法的基本步驟如下

2、： 從圖中選擇一個入度為0的頂點，輸出該頂點； 從圖中刪除該頂點及其相關(guān)聯(lián)的弧，調(diào)整被刪弧的弧頭結(jié)點的入度（入度-1）； 重復(fù)執(zhí)行、直到所有頂點均被輸出，拓樸排序完成或者圖中再也沒有入度為0的頂點（此種情況說明原有向圖含有環(huán)）。3基本要求輸入的形式和輸入值的范圍； 首先是輸入要排序的頂點數(shù)和弧數(shù)，都為整型，中間用分隔符隔開；再輸入各頂點的值，為正型，中間用分隔符隔開；然后輸入各條弧的兩個頂點值，先輸入弧頭，再輸入弧尾，中間用分隔符隔開，輸入的值只能是開始輸入的頂點值否則系統(tǒng)會提示輸入的值的頂點值不正確，請重新輸入，只要繼續(xù)輸入正確的值就行。輸出的形式； 首先輸出建立的鄰接表，然后是最終各頂點的

3、出度數(shù)，再是拓?fù)渑判虻男蛄?，并且每輸出一個頂點，就會輸出一次各頂點的入度數(shù)。(3) 程序所能達(dá)到的功能； 因為該程序是求拓?fù)渑判?，所以算法的功能就是要輸出拓?fù)渑判虻男蛄校谝粋€有向圖中，若用頂點表示活動，有向邊就表示活動間先后順序，那么輸出的拓?fù)湫蛄芯捅硎靖黜旤c間的關(guān)系為反映出各點的存儲結(jié)構(gòu)，以鄰接表存儲并輸出各頂點的入度。二 概要設(shè)計1. 算法中用到的所有各種數(shù)據(jù)類型的定義在該程序中用鄰接表作為圖的存儲結(jié)構(gòu)。首先，定義表結(jié)點和頭結(jié)點的結(jié)構(gòu)類型，然后定義圖的結(jié)構(gòu)類型。創(chuàng)建圖用鄰接表存儲的函數(shù)，其中根據(jù)要求輸入圖的頂點和邊數(shù)，并根據(jù)要求設(shè)定每條邊的起始位置，構(gòu)建鄰接表依次將頂點插入到鄰接表中。拓

4、撲排序的函數(shù)在該函數(shù)中首先要對各頂點求入度，其中要用到求入度的函數(shù)，為了避免重復(fù)檢測入度為零的頂點，設(shè)置一個輔助棧，因此要定義順序棧類型，以及棧的函數(shù)：入棧，出棧，判斷棧是否為空。2.各程序模塊之間的層次調(diào)用關(guān)系 第一部分，void ALGraph *G函數(shù)構(gòu)建圖，用鄰接表存儲。這個函數(shù)沒有調(diào)用函數(shù)。 第二部分，void TopologicalSort(ALGraph *G)輸出拓?fù)渑判蚝瘮?shù)，這個函數(shù)首先調(diào)用FindInDegree(G,indegree)對各頂點求入度indegree0vernum-1;然后設(shè)置了一個輔助棧，調(diào)用InitStack(&S)初始化棧，在調(diào)用Push(&a

5、mp;S,i)入度為0者進(jìn)棧，while(!StackEmpty(&S)棧不為空時，調(diào)用Pop(&sS,&n)輸出棧中頂點并將以該頂點為起點的邊刪除，入度indegreek-,當(dāng)輸出某一入度為0的頂點時，便將它從棧中刪除。 第三部分，主函數(shù)，先后調(diào)用void CreatGraph(ALGraph *G)函數(shù)構(gòu)建圖、void TopologicalSort(ALGraph *G)函數(shù)輸出拓?fù)渑判驅(qū)崿F(xiàn)整個程序。3.設(shè)計的主程序流程(見附頁)三 詳細(xì)設(shè)計 （實現(xiàn)概要設(shè)計中定義的所有數(shù)據(jù)類型,對每個操作寫出偽碼算法；對主程序和其他模塊也都需要寫出偽碼算法(偽碼算法達(dá)到的詳細(xì)程度

6、建議為；按照偽碼算法可以在計算機鍵盤直接輸入高級程序設(shè)計語言程序);寫出出函數(shù)和過程的調(diào)用關(guān)系。）1.實現(xiàn)概要設(shè)計中定義的所有數(shù)據(jù)類型#include<> #include<> #define MAX_VEXTEX_NUM 100 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define M 100 #define ERROR 0 typedef int ElemType; typedef struct ArcNode int adjvex; struct ArcNode *ne

7、xtarc; ArcNode; typedef struct VNode int data; ArcNode *firstarc; VNode,AdjListMAX_VEXTEX_NUM; typedef struct AdjList vertices; int vexnum, arcnum; ALGraph; typedef struct ElemType *base; ElemType *top; int stacksize; SqStack;2.算法和各模塊的代碼程序中各函數(shù)算法思想如下： void InitStack(SqStack *S) 初始化棧將棧的空間設(shè)為 STACK-INIT

8、-SIZE。 int Pop(SqStack *S,ElemType *e)出棧操作，若站不空，刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR。 void Push(SqStack *S,ElemType e) 進(jìn)棧操作，插入元素e為新的棧頂元素。 int StackEmpty(SqStack *S) 判斷棧是否為空,語句if (S->top=S->base )判斷，若棧不為空，則刪除S的棧頂元素，并返回OK；否則返回ERROR。 void CreatGraph (ALGraph *G) 構(gòu)建圖，用鄰接表存儲，首先定義鄰接表指針變量，輸入頂點數(shù)和弧數(shù)，初始化鄰接表，

9、將表頭向量域置空，輸入存在弧的點集合，當(dāng)輸入頂點值超出輸入值的范圍就會出錯，否則依次插入進(jìn)鄰接表，最后輸出建立好的鄰接表。 void FindInDegree(ALGrap G, int indegreee)求入度操作，設(shè)一個存放各頂點入度的數(shù)組indegreee，然后indegreeei=0賦初值，for循環(huán)indegreee+，存儲入度數(shù)。 void TopologicalISort(ALGraph G)輸出拓?fù)渑判蚝瘮?shù)。其思路是若G無回路，則輸出G的頂點的一個拓?fù)湫蛄胁⒎祷豋K，否則返回ERROR。首先由于鄰接表的存儲結(jié)構(gòu)入度為零的頂點即為沒有前驅(qū)的頂點，我們可以附設(shè)一個存放個頂點入度的

10、數(shù)組，調(diào)用FindInDegree( G, indegreee)對各頂點求入度；為了避免重復(fù)檢測入度為零0的頂點，設(shè)置一個棧，調(diào)用InitStack(&S)初始化棧，在調(diào)用Push(&S,i)入度為0者進(jìn)棧，while(!StackEmpty(&S)棧不為空時，調(diào)用Pop(&sS,&n)輸出棧中頂點并將以該頂點為起點的邊刪除，入度indegreek-,當(dāng)輸出某一入度為0的頂點時，便將它從棧中刪除。3.算法的時間復(fù)雜度和空間復(fù)雜度 拓?fù)渑判驅(qū)嶋H是對鄰接表表示的圖G進(jìn)行遍歷的過程，每次訪問一個入度為零的頂點，若圖G中沒有回路，則需掃描鄰接表中的所有邊結(jié)點，在

11、算法開始時，為建立入度數(shù)組D需訪問表頭向量中的所有邊結(jié)點，算法的時間復(fù)雜度為O(n+e)。四 測試與分析對有向無環(huán)圖【下圖】進(jìn)行拓?fù)渑判?。輸入：結(jié)果如下：五 總結(jié)拓?fù)渑判蚓褪菍σ粋€有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進(jìn)行拓?fù)渑判?，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若<u，v> E(G)，則u在線性序列中出現(xiàn)在v之前。在進(jìn)行課程設(shè)計中，更好的認(rèn)識了拓?fù)渑判?。理清了各個模塊之間算法之間的條理。認(rèn)識了偽代碼（Pseudocode）是一種算法描述語言。使用偽代碼的目的是為了使被描述的算法可以容易地以任何一種編程語言（Pascal

12、，C，Java，etc）實現(xiàn)。因此，偽代碼必須結(jié)構(gòu)清晰、代碼簡單、可讀性好，并且類似自然語言。 介于自然語言與編程語言之間。它是一種讓人便于理解的代碼。不依賴于語言的，用來表示程序執(zhí)行過程，而不一定能編譯運行的代碼。在數(shù)據(jù)結(jié)構(gòu)講算法的時候用的很多。在設(shè)計中，我們遇到了程序正確，卻對某些無向圖無法進(jìn)行拓?fù)渑判虻膯栴}。多次對程序進(jìn)行修改后，才可以進(jìn)行拓?fù)渑判?。問題出在調(diào)用函數(shù)的錯誤理解，模塊之間的聯(lián)系模糊不清。 六附錄：源程序：#include<> #include<> #define MAX_VEXTEX_NUM 100 #define STACK_INIT_SIZE 1

13、00 #define STACKINCREMENT 10 #define OK 1 #define M 100 #define ERROR 0 typedef int ElemType; typedef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode; typedef struct VNode int data; ArcNode *firstarc; VNode,AdjListMAX_VEXTEX_NUM; typedef struct AdjList vertices; int vexnum, arcnum; ALGra

14、ph; typedef struct ElemType *base; ElemType *top; int stacksize; SqStack; void InitStack(SqStack *); int Pop(SqStack *, ElemType *); void Push(SqStack *,ElemType ); int StackEmpty(SqStack *); void CreatGraph(ALGraph *); void FindInDegree(ALGraph , int * ); void TopologicalSort(ALGraph ); void InitSt

15、ack(SqStack *S) S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType); if(!S->base) printf("內(nèi)存分配失敗，請檢查儲存位置，再見"); exit(1); S->top=S->base; S->stacksize=STACK_INIT_SIZE; int Pop(SqStack *S,ElemType *e) if(S->top=S->base) return ERROR; *e=*-S->top; return 0; void

16、 Push(SqStack *S,ElemType e) if(S->top-S->base>=S->stacksize) S->base = (ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType); if(!S->base) printf("內(nèi)存分配失敗，請檢查儲存位置，再見"); exit(1); S->top = S->base+S->stacksize; S->stacksize+=STACKINCRE

17、MENT; *S->top+=e; int StackEmpty(SqStack *S) if(S->top=S->base) return OK; else return ERROR; void CreatGraph(ALGraph *G) int m, n, i; ArcNode *p; printf("請輸入頂點數(shù)和邊數(shù):"); scanf("%d%d",&G->vexnum,&G->arcnum); for (i = 1; i <= G->vexnum; i+) G->vertice

18、si.data = i; G->verticesi.firstarc = NULL; for (i = 1; i <= G->arcnum; i+) printf("n請輸入存在邊的兩個頂點的序號，先輸入弧尾，再輸入弧頭:"); scanf("%d%d",&n,&m); while (n < 0 | n > G->vexnum | m < 0 | m > G->vexnum) printf("輸入的頂點序號不正確 請重新輸入:"); scanf("%d%d

19、",&n,&m); p = (ArcNode*)malloc(sizeof(ArcNode); if (p = NULL) printf("內(nèi)存分配失敗，請檢查儲存位置，再見"); exit(1); p->adjvex = m; p->nextarc = G->verticesn.firstarc; G->verticesn.firstarc = p; void FindInDegree(ALGraph G, int indegree) int i; for (i = 1; i <= ; i+) indegreei = 0; for (i = 1; i <= ; i+) while i.firstarc) indegreei.firstarc->adjvex+; i.firstarc = i.firstarc->nextarc; void TopologicalSort(ALGraph G) int indegreeM; in