數(shù)據(jù)結(jié)構(gòu)課程設計-拓撲排序

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：24 大?。?38.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩23頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　課程設計說明書　　課程名稱: 數(shù)據(jù)結(jié)構(gòu) 　　課程代碼: 　　題目: 拓撲排序

2、　　年級/專業(yè)/班:10級計算機科學與技術(shù)軟件工程二班　　目錄　　摘要2　　一、引言3　　二、設計目的與任務3<

3、;/p>　　1、課程設計目的3　　2、課程設計的任務3　　三、設計方案3　　1、需求分析3　　2、概要設計4</p

4、>　　3、詳細設計5　　四、調(diào)試分析與體會26　　五、運行結(jié)果27　　六、結(jié) 論27　　七、致謝

5、28　　八、參考文獻28　　摘要　　對一個有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序(Topological Sort),是將G中所有頂點排成一個線性序列,使得對圖中任意一

6、對頂點u和v,若＜u,v＞∈E(G),則u在線性序列中出現(xiàn)在v之前。通常將這樣的線性序列稱為滿足拓撲次序(Topolgical Order)的序列,簡稱拓撲序列。　　關(guān)鍵詞：拓撲；數(shù)據(jù)結(jié)構(gòu)；C；C++；　　Abstract 　　For a directed acyclic g

7、raph ( Directed Acyclic Graph DAG) G topological sort ( Topological Sort ), G is all vertices into a linear sequence of arbitrary graph, makes a pair of vertices u and V, if < u, V > E ( G ), u in linear occur in t

8、he sequence before v. Usually such linear sequences called meet the topological order ( Topolgical Order ) sequences, referred to as the topological sequence.　　Keywords: Topology; data structure; C;

9、 C + +;　　《數(shù)據(jù)結(jié)構(gòu)》課程設計　　----拓撲排序　　一、引言　　數(shù)據(jù)結(jié)構(gòu)是計算機程序設計的重要理論技術(shù)基礎(chǔ)，它不僅是計算機學科的核心課程，而且已成為其他理工專業(yè)的熱門選修課。<

10、/p>　　采用鄰接表存儲結(jié)構(gòu)實現(xiàn)有向圖；有向圖需通過頂點數(shù)、弧數(shù)、頂點以及弧等信息建立。　　用鄰接表構(gòu)造圖然后進行拓撲排序，輸出拓撲排序序列。　　二、設計目的與任務　　1、課程設計目的

11、　　1、選擇合適的存儲結(jié)構(gòu)，建立有向無環(huán)圖，并輸出該圖；　　2、實現(xiàn)拓撲排序算法；　　3、運用拓撲排序?qū)崿F(xiàn)對教學計劃安排的檢驗。　　2、課程設計的任務　　在AOV網(wǎng)中為了更好地完成工程，必須滿足活動之間先后關(guān)系，需

12、要將各活動排一個先后次序即為拓撲排序。拓撲排序可以應用于教學計劃的安排，根據(jù)課程之間的依賴關(guān)系，制定課程安排計劃。按照用戶輸入的課程數(shù)，課程間的先后關(guān)系數(shù)目以及課程間兩兩間的先后關(guān)系，程序執(zhí)行后會給出符合拓撲排序的課程安排計劃。　　三、設計方案　　1、需求分析

13、　　1) 問題描述　　本次課程設計題目是：用鄰接表構(gòu)造圖然后進行拓撲排序，輸出拓撲排序序列　　拓撲排序的基本思想為：　　1).從有向圖中選一個無前驅(qū)的頂點輸出； 　　2).將此頂點和以它為起點的弧刪除；

14、 　　3). 重復1),2)直到不存在無前驅(qū)的頂點； 　　4). 若此時輸出的頂點數(shù)小于有向圖中的頂點數(shù)，則說明有向圖中存在回路，否則輸出的頂點的順序即為一個拓撲序列。 　　2) 基于鄰接表的存儲結(jié)構(gòu)　　入度為零的頂點即為沒有前驅(qū)的頂點，我們可

15、以附設一個存放各頂點入度的數(shù)組indegree[ ]，于是有　　1）找G中無前驅(qū)的頂點——查找indegree[i]為零的頂點vi；　　2）刪除以i為起點的所有弧——對鏈在頂點i后面的所有鄰接頂點k，將對應的indegree[k] 減1。 　　為了避免重復檢測入度為零的頂點，可以再設置一個輔助棧，若某一頂點的入度

16、減為0，則將它入棧。每當輸出某一入度為0的頂點時，便將它從棧中刪　　3) 基本要求　　1) 首先是輸入要排序的頂點數(shù)和弧數(shù)，都為整型，中間用分隔符隔開；再輸入各頂點的值，為正型，中間用分隔符隔開；然后輸入各條弧的兩個頂點值，先輸入弧頭，再輸入弧尾，中間用分隔符隔開，輸入的值只能是開始輸入的頂點值否則系統(tǒng)會提示輸入的值

17、的頂點值不正確，請重新輸入，只要繼續(xù)輸入正確的值就行。　　2) 輸出的形式；　　首先輸出建立的鄰接表，然后是最終各頂點的出度數(shù)，再是拓撲排序的序列，并且每輸出一個頂點，就會輸出一次各頂點的入度數(shù)。　　3) 程序所能達到的功能；　　因為

18、該程序是求拓撲排序，所以算法的功能就是要輸出拓撲排序的序列，在一個有向圖中，若用頂點表示活動，有向邊就表示活動間先后順序，那么輸出的拓撲序列就表示各頂點間的關(guān)系為反映出各點的存儲結(jié)構(gòu)，以鄰接表存儲并輸出各頂點的入度。　　2、概要設計　　抽象數(shù)據(jù)類型(ADT)如下：　　ADT

19、ToplogicalSort　　{ 數(shù)據(jù)對象V：V是且有相同特性的數(shù)據(jù)元素的集合，稱為頂點集　　數(shù)據(jù)關(guān)系：R＝{VR}　　VR＝{<v,w>|v,w∈v且p(v,w),<v,w>表示從v到w的弧，　　謂詞p(v,w)定義了<v,w>的

20、意義或信息}　　基本操作：　　LocateVex(ALGraph G,VertexType u)　　初始條件: 圖G存在,u和G中頂點有相同特征 　　操作結(jié)果: 若G中存在頂點u,則返回該頂點在圖中位置;否則返回-1

21、;　　NextAdjVex(ALGraph G,VertexType v,VertexType w)　　初始條件: 圖G存在,v是G中某個頂點,w是v的鄰接頂點 　　操作結(jié)果: 返回v的(相對于w的)下一個鄰接頂點的序號。 　　VertexType* GetVex(ALGraph G

22、,int v)　　初始條件: 圖G存在,v是G中某個頂點的序號。　　操作結(jié)果: 返回v的值 */　　NextAdjVex(ALGraph G,VertexType v,VertexType w)　　初始條件: 圖G存在,v是G中某個頂點,w是v的鄰接頂點 </p&g

23、t;　　操作結(jié)果: 返回v的(相對于w的)下一個鄰接頂點的序號。 　　若w是v的最后一個鄰接點,則返回-1 　　VertexType* GetVex(ALGraph G,int v)　　初始條件: 圖G存在,v是G中某個頂點的序號。　　操作結(jié)果: 返

24、回v的值 　　}　　存儲結(jié)構(gòu)　　typedef struct SqStack　　{SElemType *base; /* 在棧構(gòu)造之前和銷毀之后，base的值為NULL */

25、　　SElemType *top; /* 棧頂指針 */　　int stacksize; /* 當前已分配的存儲空間，以元素為單位 */　　}SqStack; /* 順序棧 */　　typedef struct ArcNode　　{

26、　　int adjvex; /* 該弧所指向的頂點的位置 */　　struct ArcNode *nextarc; /* 指向下一條弧的指針 */　　InfoType *info; /* 網(wǎng)的權(quán)值指針） */　　}ArcNode; /* 表結(jié)點 */&

27、lt;/p>　　typedef struct　　{　　VertexType data; /* 頂點信息 */　　ArcNode *firstarc; /* 第一個表結(jié)點的地址,指向第一條依附該頂點的弧的指針 */<p&

28、gt;　　}VNode,AdjList[MAX_VERTEX_NUM]; /* 頭結(jié)點 */　　typedef struct　　{　　AdjList vertices;　　int vexnum,arcnum; /* 圖的當前頂點數(shù)和弧

29、數(shù) */　　int kind; /* 圖的種類標志 */　　}ALGraph;　　流程圖　　詳細設計　　#inclu

30、de<stdio.h> 　　#include<math.h> 　　#include<string.h>　　#include<stdlib.h>　　#define FALSE 0　　#

31、define OK 1　　#define ERROR 0　　#define INFEASIBLE -1　　typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */　　typedef int Boolean; /* Bo

32、olean是布爾類型,其值是TRUE或FALSE */　　#define MAX_NAME 5 /* 頂點字符串的最大長度 */　　typedef int InfoType;　　typedef char VertexType[MAX_NAME]; /* 字符串類型 */

33、　#define MAX_VERTEX_NUM 20　　typedef enum{DG,DN,AG,AN}GraphKind; /* {有向圖,有向網(wǎng),無向圖,無向網(wǎng)} */　　typedef struct ArcNode　　{　　i

34、nt adjvex; /* 該弧所指向的頂點的位置 */　　struct ArcNode *nextarc; /* 指向下一條弧的指針 */　　InfoType *info; /* 網(wǎng)的權(quán)值指針） */　　}ArcNode; /* 表結(jié)點 */　　typedef stru

35、ct　　{　　VertexType data; /* 頂點信息 */　　ArcNode *firstarc; /* 第一個表結(jié)點的地址,指向第一條依附該頂點的弧的指針 */　　}VNode,AdjList[MAX_VERTEX_NUM

36、]; /* 頭結(jié)點 */　　typedef struct　　{　　AdjList vertices;　　int vexnum,arcnum; /* 圖的當前頂點數(shù)和弧數(shù) */　　int kin

37、d; /* 圖的種類標志 */　　}ALGraph;　　int LocateVex(ALGraph G,VertexType u)　　{ /* 初始條件: 圖G存在,u和G中頂點有相同特征 */　　/* 操作結(jié)果: 若G中存在頂點u,

38、則返回該頂點在圖中位置;否則返回-1 */　　int i;　　for(i = 0;i < G.vexnum; ++i)　　if(strcmp(u,G.vertices[i].data) == 0)　　retur

39、n i;　　return -1;　　}　　Status CreateGraph(ALGraph *G)　　{ /* 采用鄰接表存儲結(jié)構(gòu),構(gòu)造沒有相關(guān)信息的圖G(用一個函數(shù)構(gòu)造4種圖) */&

40、lt;p>　　int i,j,k;　　int w; /* 權(quán)值 */　　VertexType va,vb;　　ArcNode *p;　　printf("請輸入圖的類型(有向圖:0,有向網(wǎng):1,無向圖:2,無向網(wǎng):3): ");

41、　　scanf("%d",&(*G).kind);　　printf("請輸入圖的頂點數(shù),邊數(shù): ");　　scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);　　printf(&

42、quot;請輸入%d個頂點的值(<%d個字符):\n",(*G).vexnum,MAX_NAME);　　for(i = 0;i < (*G).vexnum; ++i) /* 構(gòu)造頂點向量 */　　{　　scanf("%s",(*G).

43、vertices[i].data);　　(*G).vertices[i].firstarc = NULL;　　}　　if((*G).kind == 1 || (*G).kind == 3) /* 網(wǎng) */　　printf("

44、請順序輸入每條弧(邊)的權(quán)值、弧尾和弧頭(以空格作為間隔):\n");　　else /* 圖 */　　printf("請順序輸入每條弧(邊)的弧尾和弧頭(以空格作為間隔):\n");　　for(k = 0;k < (*G).arcnum; ++k) /* 構(gòu)造表結(jié)點鏈表 */&

45、lt;/p>　　{　　if((*G).kind == 1 || (*G).kind == 3) /* 網(wǎng) */　　scanf("%d%s%s",&w,va,vb);　　else /* 圖 */&l

46、t;p>　　scanf("%s%s",va,vb);　　i = LocateVex(*G,va); /* 弧尾 */　　j = LocateVex(*G,vb); /* 弧頭 */　　p = (ArcNode*)malloc(sizeof(ArcNode));&l

47、t;p>　　p -> adjvex = j;　　if((*G).kind == 1 || (*G).kind == 3) /* 網(wǎng) */　　{　　p -> info = (int *)malloc(sizeof(int));<p

48、>　　*(p -> info) = w;　　}　　else　　p -> info = NULL; /* 圖 */　　p -> nextarc = (*G).vertices

49、[i].firstarc; /* 插在表頭 */　　(*G).vertices[i].firstarc = p;　　if((*G).kind >= 2) /* 無向圖或網(wǎng),產(chǎn)生第二個表結(jié)點 */　　{　　p = (ArcNode

50、*)malloc(sizeof(ArcNode));　　p -> adjvex = i;　　if((*G).kind == 3) /* 無向網(wǎng) */　　{　　p -> info = (int*)malloc(sizeof(

51、int));　　*(p -> info) = w;　　}　　else　　p -> info = NULL; /* 無向圖 */　　p ->

52、; nextarc = (*G).vertices[j].firstarc; /* 插在表頭 */　　(*G).vertices[j].firstarc=p;　　}　　}　　return OK;&

53、lt;/p>　　}　　VertexType* GetVex(ALGraph G,int v)　　{ /* 初始條件: 圖G存在,v是G中某個頂點的序號。操作結(jié)果: 返回v的值 */　　if(v >= G.vexnum || v<0)&l

54、t;/p>　　exit(ERROR);　　return &G.vertices[v].data;　　}　　int FirstAdjVex(ALGraph G,VertexType v)　　{ /*

55、初始條件: 圖G存在,v是G中某個頂點 */　　/* 操作結(jié)果: 返回v的第一個鄰接頂點的序號。若頂點在G中沒有鄰接頂點,則返回-1 */　　ArcNode *p;　　int v1;　　v1 = LocateVex(G,v); /*

56、v1為頂點v在圖G中的序號 */　　p = G.vertices[v1].firstarc;　　if(p)　　return p -> adjvex;　　else<

57、;p>　　return -1;　　}　　int NextAdjVex(ALGraph G,VertexType v,VertexType w)　　{ /* 初始條件: 圖G存在,v是G中某個頂點,w是v的鄰接頂點 */　　/*

58、操作結(jié)果: 返回v的(相對于w的)下一個鄰接頂點的序號。 */　　/* 若w是v的最后一個鄰接點,則返回-1 */　　ArcNode *p;　　int v1,w1;　　v1 = LocateVex(G,v); /* v1為頂點v在圖G中的序號 */&l

59、t;/p>　　w1 = LocateVex(G,w); /* w1為頂點w在圖G中的序號 */　　p = G.vertices[v1].firstarc;　　while(p && p -> adjvex != w1) /* 指針p不空且所指表結(jié)點不是w */　　p

60、 = p -> nextarc;　　if(!p || !p -> nextarc) /* 沒找到w或w是最后一個鄰接點 */　　return -1;　　else /* p->adjvex==w */　　return p -> nextarc -&g

61、t; adjvex; /* 返回v的(相對于w的)下一個鄰接頂點的序號 */　　}　　Boolean visited[MAX_VERTEX_NUM]; /* 訪問標志數(shù)組(全局量) */　　void(*VisitFunc)(char* v); /* 函數(shù)變量(全局量) */&

62、lt;/p>　　void DFS(ALGraph G,int v)　　{ /* 從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G。*/　　int w;　　VertexType v1,w1;　　strcpy(v1,*G

63、etVex(G,v));　　visited[v] = TRUE; /* 設置訪問標志為TRUE(已訪問) */　　VisitFunc(G.vertices[v].data); /* 訪問第v個頂點 */　　for(w = FirstAdjVex(G,v1); w >= 0; w = NextAdjVex(G

64、,v1,strcpy(w1,*GetVex(G,w))))　　if(!visited[w])　　DFS(G,w); /* 對v的尚未訪問的鄰接點w遞歸調(diào)用DFS */　　}　　typedef int QElemType; /* 隊列類

65、型 */　　typedef struct QNode　　{　　QElemType data;　　struct QNode *next;　　}QNode,*QueuePtr;

66、　　typedef struct　　{　　QueuePtr front,rear; /* 隊頭、隊尾指針 */　　}LinkQueue;　　Status InitQueue(LinkQueue *Q)</p

67、>　　{ /* 構(gòu)造一個空隊列Q */　　(*Q).front = (*Q).rear = (QueuePtr)malloc(sizeof(QNode));　　if(!(*Q).front)　　exit(OVERFLOW);　　(*Q).fro

68、nt -> next = NULL;　　return OK;　　}　　Status QueueEmpty(LinkQueue Q)　　{ /* 若Q為空隊列,則返回TRUE,否則返回FALSE */<

69、;p>　　if(Q.front == Q.rear)　　return TRUE;　　else　　return FALSE;　　}　　Status E

70、nQueue(LinkQueue *Q,QElemType e)　　{ /* 插入元素e為Q的新的隊尾元素 */　　QueuePtr p = (QueuePtr)malloc(sizeof(QNode));　　if(!p) /* 存儲分配失敗 */　　exit(OVERF

71、LOW);　　p -> data = e;　　p -> next = NULL;　　(*Q).rear -> next = p;　　(*Q).rear = p;　　return OK;&l

72、t;p>　　}　　Status DeQueue(LinkQueue *Q,QElemType *e)　　{ /* 若隊列不空,刪除Q的隊頭元素,用e返回其值,并返回OK,否則返回ERROR */　　QueuePtr p;　　if

73、((*Q).front == (*Q).rear)　　return ERROR;　　p = (*Q).front -> next;　　*e = p -> data;　　(*Q).front -> next = p -> next;

74、;　　if((*Q).rear == p)　　(*Q).rear=(*Q).front;　　free(p);　　return OK;　　}<p&

75、gt;　　void BFSTraverse(ALGraph G,void(*Visit)(char*))　　{/*按廣度優(yōu)先非遞歸遍歷圖G。使用輔助隊列Q和訪問標志數(shù)組visited。算法7.6 */　　int v,u,w;　　VertexType u1,w1;　　Lin

76、kQueue Q;　　for(v = 0; v < G.vexnum; ++v)　　visited[v] = FALSE; /* 置初值 */　　InitQueue(&Q); /* 置空的輔助隊列Q */　　for(v = 0;v < G.vexnum

77、; v++) /* 如果是連通圖,只v=0就遍歷全圖 */　　if(!visited[v]) /* v尚未訪問 */　　{　　visited[v] = TRUE;　　Visit(G.vertices[v].data);</p&g

78、t;　　EnQueue(&Q,v); /* v入隊列 */　　while(!QueueEmpty(Q)) /* 隊列不空 */　　{　　DeQueue(&Q,&u); /* 隊頭元素出隊并置為u */<

79、;p>　　strcpy(u1,*GetVex(G,u));　　for(w=FirstAdjVex(G,u1);w>=0;w= NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))　　if(!visited[w]) /* w為u的尚未訪問的鄰接頂點 */

80、　{　　visited[w] = TRUE;　　Visit(G.vertices[w].data);　　EnQueue(&Q,w); /* w入隊 */　　}//end if<

81、p>　　}//end while　　}//end if　　printf("\n");　　}　　void Display(ALGraph G)<

82、;p>　　{ /* 輸出圖的鄰接矩陣G */　　int i;　　ArcNode *p;　　switch(G.kind)　　{　　case DG: p

83、rintf("有向圖\n");　　break;　　case DN: printf("有向網(wǎng)\n");　　break;　　case AG: printf(&q

84、uot;無向圖\n");　　break;　　case AN: printf("無向網(wǎng)\n");　　}　　printf("%d個頂點：\n",G.v

85、exnum);　　for(i = 0;i < G.vexnum; ++i)　　printf("%s ",G.vertices[i].data);　　printf("\n%d條弧(邊):\n",G.arcnum);　　for(i

86、 = 0;i < G.vexnum; i++)　　{　　p = G.vertices[i].firstarc;　　while(p)　　{</p&g

87、t;　　if(G.kind <= 1) /* 有向 */　　{　　printf("%s→%s ",G.vertices[i].data,G.vertices[p -> adjvex].data);　　if(G.kind =

88、= DN) /* 網(wǎng) */　　printf(":%d ",*(p -> info));　　}　　else /* 無向(避免輸出兩次) */　　{&

89、lt;p>　　if(i adjvex)　　{　　printf("%s－%s ",G.vertices[i].data,G.vertices[p -> adjvex].data);　　if(G.kind == AN) /

90、* 網(wǎng) */　　printf(":%d ",*(p -> info));　　}　　}　　p = p -> nextarc;

91、　　}　　printf("\n");　　}　　}　　void FindInDegree(ALGraph G,int indegree[])

92、　　{ /* 求頂點的入度*/　　int i;　　ArcNode *p;　　for(i = 0;i < G.vexnum; i++)　　indegree[i] = 0; /* 賦初值 *

93、/　　for(i = 0;i < G.vexnum; i++)　　{　　p = G.vertices[i].firstarc;　　while(p)&

94、lt;b>　　{　　indegree[p -> adjvex]++;　　p = p-> nextarc;　　}　　}

95、　　}　　typedef int SElemType; /* 棧類型 */　　#define STACK_INIT_SIZE 10 /* 存儲空間初始分配量 */　　#define STACKINCREMENT 2 /* 存儲空間分配增量 */<

96、p>　　typedef struct SqStack　　{　　SElemType *base; /* 在棧構(gòu)造之前和銷毀之后，base的值為NULL */　　SElemType *top; /* 棧頂指針 */　　int sta

97、cksize; /* 當前已分配的存儲空間，以元素為單位 */　　}SqStack; /* 順序棧 */　　Status InitStack(SqStack *S)　　{ /* 構(gòu)造一個空棧S */　　(*S).base = (SElemType *)malloc(STA

98、CK_INIT_SIZE*sizeof(SElemType));　　if(!(*S).base)　　exit(OVERFLOW); /* 存儲分配失敗 */　　(*S).top = (*S).base;　　(*S).stacksize = STACK_INIT_SIZE;

99、　　return OK;　　}　　Status StackEmpty(SqStack S)　　{ /* 若棧S為空棧，則返回TRUE，否則返回FALSE */　　if(S.top == S.b

100、ase)　　return TRUE;　　else　　return FALSE;　　}　　Status Push(SqStack *S,SElemType

101、e)　　{ /* 插入元素e為新的棧頂元素 */　　if((*S).top - (*S).base >= (*S).stacksize) /* 棧滿，追加存儲空間 */　　{ (*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+

102、;　　STACKINCREMENT)*sizeof(SElemType));　　if(!(*S).base)　　exit(OVERFLOW); /* 存儲分配失敗 */　　(*S).top = (*S).base + (*S).stacksize;

103、　(*S).stacksize += STACKINCREMENT;　　}　　*((*S).top)++ = e;　　return OK;　　}　　Sta

104、tus Pop(SqStack *S,SElemType *e)　　{ /* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */　　if((*S).top == (*S).base)　　return ERROR;　　*e = *--(*S).

105、top;　　return OK;　　}　　Status TopologicalSort(ALGraph G)　　{ /* 有向圖G采用鄰接表存儲結(jié)構(gòu)。若G無回路,則輸出G的頂點的一個拓撲序列并返回OK, */&

106、lt;p>　　/* 否則返回ERROR。*/　　int i,k,count,indegree[MAX_VERTEX_NUM];　　SqStack S;　　ArcNode *p;　　FindInDegree(G,indegree); /* 對各頂點求入度indegre

107、e[0..vernum-1] */　　InitStack(&S); /* 初始化棧 */　　for(i = 0; i < G.vexnum; ++i) /* 建零入度頂點棧S */　　if(!indegree[i])　　Push(&S,i); /*

108、入度為0者進棧 */　　count = 0; /* 對輸出頂點計數(shù) */　　while(!StackEmpty(S))　　{ /* 棧不空 */　　Pop(&S,&i);　　printf("%s &quo

109、t;,G.vertices[i].data); /* 輸出i號頂點并計數(shù) */　　++count;　　for(p = G.vertices[i].firstarc; p; p = p -> nextarc)　　{ /* 對i號頂點的每個鄰接點的入度減1 */</p

110、>　　k = p -> adjvex;　　if(!(--indegree[k])) /* 若入度減為0,則入棧 */　　Push(&S,k);　　}　　}

111、　　if(count < G.vexnum)　　{　　printf("此有向圖有回路\n");　　return ERROR;　　}

112、;　　else　　{　　printf("為一個拓撲序列。\n");　　return OK;　　}

113、　　}　　int main()　　{　　ALGraph f;　　printf("請選擇有向圖\n");<

114、p>　　CreateGraph(&f);　　Display(f);　　TopologicalSort(f);　　system("pause");　　return 0;<p

115、>　　}　　重要程序段1：　　Status CreateGraph(ALGraph *G)　　{ /* 采用鄰接表存儲結(jié)構(gòu),構(gòu)造沒有相關(guān)信息的圖G(用一個函數(shù)構(gòu)造4種圖) */　　int i

116、,j,k;　　int w; /* 權(quán)值 */　　VertexType va,vb;　　ArcNode *p;　　printf("請輸入圖的類型(有向圖:0,有向網(wǎng):1,無向圖:2,無向網(wǎng):3): ");　　sc

117、anf("%d",&(*G).kind);　　printf("請輸入圖的頂點數(shù),邊數(shù): ");　　scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);　　printf("請輸入%d個頂點的值

118、(<%d個字符):\n",(*G).vexnum,MAX_NAME);　　for(i = 0;i < (*G).vexnum; ++i) /* 構(gòu)造頂點向量 */　　{　　scanf("%s",(*G).vertices[i].dat

119、a);　　(*G).vertices[i].firstarc = NULL;　　}　　if((*G).kind == 1 || (*G).kind == 3) /* 網(wǎng) */　　printf("請順序輸入每條弧(邊)的權(quán)值、

120、弧尾和弧頭(以空格作為間隔):\n");　　else /* 圖 */　　printf("請順序輸入每條弧(邊)的弧尾和弧頭(以空格作為間隔):\n");　　for(k = 0;k < (*G).arcnum; ++k) /* 構(gòu)造表結(jié)點鏈表 */<

121、p>　　{　　if((*G).kind == 1 || (*G).kind == 3) /* 網(wǎng) */　　scanf("%d%s%s",&w,va,vb);　　else /* 圖 */　　scanf(

122、"%s%s",va,vb);　　i = LocateVex(*G,va); /* 弧尾 */　　j = LocateVex(*G,vb); /* 弧頭 */　　p = (ArcNode*)malloc(sizeof(ArcNode));　　p ->

123、; adjvex = j;　　if((*G).kind == 1 || (*G).kind == 3) /* 網(wǎng) */　　{　　p -> info = (int *)malloc(sizeof(int));　　*(p ->

124、 info) = w;　　}　　else　　p -> info = NULL; /* 圖 */　　p -> nextarc = (*G).vertices[i].firstarc; /

125、* 插在表頭 */　　(*G).vertices[i].firstarc = p;　　if((*G).kind >= 2) /* 無向圖或網(wǎng),產(chǎn)生第二個表結(jié)點 */　　{　　p = (ArcNode*)malloc(sizeof

126、(ArcNode));　　p -> adjvex = i;　　if((*G).kind == 3) /* 無向網(wǎng) */　　{　　p -> info = (int*)malloc(sizeof(int));

127、;　　*(p -> info) = w;　　}　　else　　p -> info = NULL; /* 無向圖 */　　p -> nextarc = (*G

128、).vertices[j].firstarc; /* 插在表頭 */　　(*G).vertices[j].firstarc=p;　　}　　}　　return OK;<

129、p>　　}　　重要程序段2：　　int NextAdjVex(ALGraph G,VertexType v,VertexType w)　　{ 　　Arc

130、Node *p;　　int v1,w1;　　v1 = LocateVex(G,v); /* v1為頂點v在圖G中的序號 */　　w1 = LocateVex(G,w); /* w1為頂點w在圖G中的序號 */　　p = G.vertices[v1].firstarc;&l

131、t;/p>　　while(p && p -> adjvex != w1) /* 指針p不空且所指表結(jié)點不是w */　　p = p -> nextarc;　　if(!p || !p -> nextarc) /* 沒找到w或w是最后一個鄰接點 */　　re

132、turn -1;　　else /* p->adjvex==w */　　return p -> nextarc -> adjvex; /* 返回v的(相對于w的)下一個鄰接頂點的序號 */　　}　　重

133、要程序段3：　　void DFS(ALGraph G,int v)　　{ /* 從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G。*/　　int w;　　VertexType v1,w1;<p&

134、gt;　　strcpy(v1,*GetVex(G,v));　　visited[v] = TRUE; /* 設置訪問標志為TRUE(已訪問) */　　VisitFunc(G.vertices[v].data); /* 訪問第v個頂點 */　　for(w = FirstAdjVex(G,v1); w >= 0;

135、 w = NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))　　if(!visited[w])　　DFS(G,w); /* 對v的尚未訪問的鄰接點w遞歸調(diào)用DFS */　　}　　重要程

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設計-拓撲排序

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設計-拓撲排序

文檔簡介

溫馨提示

最新文檔

評論

免費下載