圖的基本操作與實現(xiàn)的課程設(shè)計報告

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

已閱讀1頁，還剩27頁未讀，繼續(xù)免費(fèi)閱讀

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

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)　　課程設(shè)計報告　　設(shè)計題目：圖的基本操作與實現(xiàn)　　專業(yè) 　　班級 　　學(xué)

2、生 　　學(xué) 號 　　指導(dǎo)教師 　　起止時間 　　年學(xué)期　　目

3、錄　　1.問題描述：實現(xiàn)圖的一些基本操作3　　2.基本要求：3　　(2)求每個頂點(diǎn)的度,輸出結(jié)果；3　　3.測試數(shù)據(jù)：3<

4、;b>　　4.算法思想：3　　(1)自選存儲結(jié)構(gòu)創(chuàng)建一個圖：3　　(2)求每個頂點(diǎn)的度：3　　(3)圖的深度優(yōu)先遍歷：4　　(4)圖的廣度優(yōu)先遍歷：4　　(5)判斷有向圖的強(qiáng)連通性：4<

5、/p>　　(6)用鄰接矩陣的信息生成鄰接表：4　　6.數(shù)據(jù)結(jié)構(gòu)：5　　7.功能模塊圖7　　8.源程序：8　　9.心得體會：

6、28　　1.問題描述：實現(xiàn)圖的一些基本操作　　2.基本要求：　　(1)自選存儲結(jié)構(gòu),輸入含n個頂點(diǎn)（用字符表示頂點(diǎn)）和e條邊的圖G；　　(2)求每個頂點(diǎn)的度,輸出結(jié)果；　　(3)指定任意頂點(diǎn)

7、x為初始頂點(diǎn),對圖G作DFS遍歷,輸出DFS頂點(diǎn)序列(提示:使用一個棧實現(xiàn)DFS)；　　(4)指定任意頂點(diǎn)x為初始頂點(diǎn),對圖G作BFS遍歷,輸出BFS頂點(diǎn)序列(提示:使用一個隊列實現(xiàn)BFS)；　　(5)輸入頂點(diǎn)x,查找圖G:若存在含x的頂點(diǎn),則刪除該結(jié)點(diǎn)及與之相關(guān)連的邊,并作DFS遍歷(執(zhí)行操作3)；否則輸出信息“無x”；<

8、;p>　　(6)判斷圖G是否是連通圖，輸出信息“YES”/“NO”；　　(7)如果選用的存儲結(jié)構(gòu)是鄰接矩陣,則用鄰接矩陣的信息生成圖G的鄰接表,即復(fù)制圖G,然再執(zhí)行操作(2)；反之亦然。　　3.測試數(shù)據(jù)：　　有向圖的頂點(diǎn)數(shù)n和有向圖的邊數(shù)e由用戶從鍵盤敲入</p&

9、gt;　　4.算法思想：　　(1)自選存儲結(jié)構(gòu)創(chuàng)建一個圖：通過用戶從鍵盤敲入的兩個數(shù)值分別確定圖的頂點(diǎn)數(shù)和邊數(shù)，選擇鄰接矩陣存儲結(jié)構(gòu)將圖的結(jié)點(diǎn)信息存儲在一個順序表中，圖的邊信息存儲在一個二維數(shù)組中。　　(2)求每個頂點(diǎn)的度：　　1.鄰接矩陣存儲結(jié)構(gòu)下求每

10、個頂點(diǎn)的度：利用圖的鄰接矩陣，每個頂點(diǎn)所在行和所在列的邊的權(quán)值如果存在則該頂點(diǎn)的度+1，依次算出每個頂點(diǎn)的度，并且記錄在一個數(shù)組中輸出。　　2.鄰接表存儲結(jié)構(gòu)下求每個頂點(diǎn)的度：定義一個鄰接邊指針循環(huán)指向頂點(diǎn)的鄰接邊單鏈表頭結(jié)點(diǎn)，當(dāng)結(jié)點(diǎn)不空時，該頂點(diǎn)的出度+1,鄰接邊弧頭結(jié)點(diǎn)的入度+1，依次求出每個頂點(diǎn)的出度和入度之和就為該頂點(diǎn)的度。　　(3)圖的深度優(yōu)先

11、遍歷：采取鄰接矩陣結(jié)構(gòu)，指定任意頂點(diǎn)x為初始頂點(diǎn)　　1.訪問結(jié)點(diǎn)v并標(biāo)記結(jié)點(diǎn)v已訪問；　　2.查找結(jié)點(diǎn)v的第一個鄰接結(jié)點(diǎn)w；　　3.若結(jié)點(diǎn)v的鄰接結(jié)點(diǎn)w存在，則繼續(xù)執(zhí)行，否則算法結(jié)束；　　4.若結(jié)點(diǎn)w尚未被訪問，則遞歸訪問結(jié)點(diǎn)w；

12、　　5.查找結(jié)點(diǎn)v的w鄰接結(jié)點(diǎn)的下一個鄰接結(jié)點(diǎn)w,轉(zhuǎn)到步驟3。　　(4)圖的廣度優(yōu)先遍歷：采取鄰接矩陣結(jié)構(gòu)，指定任意頂點(diǎn)x為初始頂點(diǎn)，利用順序循環(huán)隊列以保持訪問過的結(jié)點(diǎn)的順序　　1.首先訪問初始結(jié)點(diǎn)v并標(biāo)記結(jié)點(diǎn)v為已訪問；　　2.結(jié)點(diǎn)v入隊列；<

13、p>　　3.當(dāng)隊列非空時則繼續(xù)執(zhí)行，否則算法結(jié)束；　　4.出隊列取得隊頭結(jié)點(diǎn)u；　　5.查找u的第一個鄰接結(jié)點(diǎn)w；　　6.若u的鄰接結(jié)點(diǎn)w不存在則轉(zhuǎn)到步驟3，否則循環(huán)執(zhí)行下列步驟：　　6.1若結(jié)點(diǎn)w尚未被訪問，則訪問結(jié)點(diǎn)w并標(biāo)記結(jié)點(diǎn)w為已訪問；

14、　　6.2結(jié)點(diǎn)w入隊列；　　6.3查找結(jié)點(diǎn)u的w鄰接結(jié)點(diǎn)的下一個鄰接結(jié)點(diǎn)w，轉(zhuǎn)到步驟6 。　　(5)判斷有向圖的強(qiáng)連通性：采取鄰接表結(jié)構(gòu)，在圖中尋找一個包含所有頂點(diǎn)且首尾相連的環(huán)，若這樣的環(huán)存在，則該圖為強(qiáng)連通圖，否則不為強(qiáng)連通圖。　　(6)用鄰接矩陣的信息生成鄰接表：定義一個鄰接表的邊信息結(jié)

15、構(gòu)體，將鄰接矩陣的邊信息轉(zhuǎn)換成鄰接表的邊信息存儲到鄰接邊的單鏈表中。　　5.模塊劃分：　　mian():主函數(shù)模塊。在主函數(shù)模塊中調(diào)用以下函數(shù)：　　void CreatGraph(AdjMGraph *G,DataType v[],int n,RowColWeight E[]

16、,int e)：創(chuàng)建一個鄰接矩陣存儲結(jié)構(gòu)的圖；　　void Print(AdjMGraph *G)：輸出圖的鄰接矩陣；　　void MVertices(AdjMGraph *G,DataType a[])：求出鄰接矩陣存儲結(jié)構(gòu)下圖的每個頂點(diǎn)的度；　　void CreatLGraph(AdjLGraph *G,Da

17、taType v[],int n,RowCol d[],int e)：用鄰接矩陣的信息生成鄰接表；　　void LVertices(AdjLGraph *G,DataType a[])：求出鄰接表存儲結(jié)構(gòu)下圖的每個頂點(diǎn)的度；　　int LianTong(AdjLGraph *G,DataType a[])：判斷有向圖的強(qiáng)連通性；&

18、lt;p>　　void DepthFirstSearch(AdjMGraph G,void Visit(DataType item))：對圖作DFS遍歷,輸出DFS頂點(diǎn)序列；　　void BroadFirstSearch(AdjMGraph G,void Visit(DataType item))：對圖作BFS遍歷,輸出BFS頂點(diǎn)序列；　　int

19、ChaZhao(AdjMGraph *G,int v)：查找頂點(diǎn)v；　　void MDelete(AdjMGraph *G,int v)：刪除查找到的結(jié)點(diǎn)v并刪除該結(jié)點(diǎn)及與之相關(guān)的邊；　　6.數(shù)據(jù)結(jié)構(gòu)：　　(1)有向圖頂點(diǎn)的數(shù)據(jù)類型DataType 定義如下：</p&g

20、t;　　typedef int DataType ；　　(2)鄰接矩陣存儲結(jié)構(gòu)下圖的結(jié)構(gòu)體定義如下：　　typedef struct　　{　　SeqList Vertices； //存放結(jié)點(diǎn)的順序表</p&

21、gt;　　int edge[MaxVertices][MaxVertices]； //存放邊的鄰接矩陣　　int numOfEdges； //邊的條數(shù)　　}AdjMGraph； //邊的結(jié)構(gòu)體定義　　(3)鄰接矩陣存儲結(jié)構(gòu)下圖的邊信息結(jié)構(gòu)體定義如下：<p&g

22、t;　　typedef struct　　{　　int row； //行下標(biāo)　　int col； //列下標(biāo)　　int weight； //權(quán)值　　}RowColWeight； //邊信息結(jié)

23、構(gòu)體定義　　(4)鄰接表存儲結(jié)構(gòu)下圖的結(jié)構(gòu)體定義如下：　　typedef struct Node 　　{　　int dest； //鄰接邊的弧頭結(jié)點(diǎn)序號　　struct Node *nex

24、t； 　　}Edge； //鄰接邊單鏈表的結(jié)點(diǎn)結(jié)構(gòu)體　　typedef struct　　{　　DataType data； //結(jié)點(diǎn)數(shù)據(jù)元素 　　int sorce； //鄰接邊的弧尾結(jié)

25、點(diǎn)序號　　Edge *adj； //鄰接邊的頭指針　　}AdjLHeight； //數(shù)組的數(shù)據(jù)元素類型結(jié)構(gòu)體　　typedef struct　　{　　AdjLHeight a[MaxVert

26、ices]； //鄰接表數(shù)組　　int numOfVerts； //結(jié)點(diǎn)個數(shù)　　int numOfEdges； //邊個數(shù)　　}AdjLGraph； //鄰接表結(jié)構(gòu)體　　(5)鄰接表存儲結(jié)構(gòu)下圖的邊信息結(jié)構(gòu)體定義如下：

27、typedef struct　　{　　int row； //行下標(biāo)　　int col； //列下標(biāo)　　}RowCol； //邊信息結(jié)構(gòu)體定義　　(6)順序循環(huán)隊列的結(jié)構(gòu)體定義如下：<

28、;/p>　　typedef struct 　　{　　DataType queue[MaxQueueSize]；　　int rear；　　int front；</p

29、>　　int count；　　}SeqCQueue；　　(7)順序表的結(jié)構(gòu)體定義如下：　　typedef struct　　{　　DataType list[MaxS

30、ize]；　　int size；　　}SeqList；　　7.功能模塊圖：　　8.源程序：<

31、;p>　　源程序存放在八個文件夾中，文件SeqList.h是順序表的結(jié)構(gòu)體定義和操作函數(shù)，文件SeqCQueue.h是順序循環(huán)隊列的結(jié)構(gòu)體定義和操作函數(shù)，文件AdjMGraph.h是鄰接矩陣存儲結(jié)構(gòu)下圖的結(jié)構(gòu)體定義和操作函數(shù)，文件AdjMGraphCreate.h是鄰接矩陣存儲結(jié)構(gòu)下圖的創(chuàng)建函數(shù)，文件AdjLGraph.h是鄰接表存儲結(jié)構(gòu)下圖的結(jié)構(gòu)體定義和操作函數(shù)，文件AdjLGraphCreate.h是鄰接表存儲結(jié)構(gòu)下圖的創(chuàng)建函

32、數(shù)，文件AdjMGraphTraverse.h是鄰接矩陣存儲結(jié)構(gòu)下圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷操作函數(shù)，文件圖的基本操作與實現(xiàn).c是主函數(shù)。　　(1)/* 文件SeqList.h */　　typedef struct　　{　　Dat

33、aType list[MaxSize];　　int size;　　}SeqList;　　void ListInitiate(SeqList *L)　　{<

34、;/p>　　L->size=0;　　}　　int ListLength(SeqList L)　　{　　return L.size;<

35、p>　　}　　int ListInsert(SeqList *L,int i,DataType x)　　{　　int j;　　if(L->size

36、>=MaxSize)　　{　　printf("數(shù)組已滿無法插入！\n");　　return 0;　　}<

37、;p>　　else if(i<0||i>L->size)　　{　　printf("參數(shù)不合法！\n");　　return 0;　　}&

38、lt;/b>　　else　　{　　for(j=L->size;j>i;i--)L->list[j]=L->list[j-1];　　L->list[i]=x;&l

39、t;/p>　　L->size++;　　return 1;　　}　　}　　int ListDelete(SeqList *L,

40、int i,DataType *x)　　{　　int j;　　if(L->size<=0)　　{　　pr

41、intf("順序表已空無數(shù)據(jù)元素可刪！\n");　　return 0;　　}　　else if(i<0||i>L->size-1)　　{&l

42、t;/b>　　printf("參數(shù)i不合法！\n");　　return 0;　　}　　else<p&g

43、t;　　{　　*x=L->list[i];　　for(j=i+1;j<=L->size-1;j++)L->list[j-1]=L->list[j];　　L->size--;　　re

44、turn 1;　　}　　}　　int ListGet(SeqList L,int i,DataType *x)　　{

45、　　if(i<0||i>L.size-1)　　{　　printf("參數(shù)i不合法！\n");　　return 0;　　}<

46、;/b>　　else　　{　　*x=L.list[i];　　return 1;　　}<

47、/b>　　}　　(2)/* 文件SeqCQueue.h */　　typedef struct 　　{　　DataType queue[MaxQueu

48、eSize];　　int rear;　　int front;　　int count;　　}SeqCQueue;　　void QueueInitiate(SeqCQueue *Q)</p&

49、gt;　　{　　Q->rear=0;　　Q->front =0;　　Q->count =0;　　}　　int Qu

50、eueNotEmpty(SeqCQueue Q)　　{　　if(Q.count !=0) return 1;　　else return 0;　　}　　i

51、nt QueueAppend(SeqCQueue *Q,DataType x)　　{　　if(Q->count>0&&Q->rear==Q->front)　　{<p&g

52、t;　　printf("隊列已滿無法插入!");　　return 0;　　}　　else 　　{&l

53、t;/p>　　Q->queue [Q->rear]=x;　　Q->rear =(Q->rear +1)%MaxQueueSize;　　Q->count ++;　　return 1;<p&g

54、t;　　}　　}　　int QueueDelete(SeqCQueue *Q,DataType *d)　　{　　if(Q->count ==0)<

55、/p>　　{　　printf("隊列已空無數(shù)據(jù)出隊列!\n");　　return 0;　　}

56、　　else　　{　　*d=Q->queue[Q->front];　　Q->front=(Q->front+1)%MaxQueueSize;　　Q->count --;</p&g

57、t;　　return 1;　　}　　}　　int QueueGet(SeqCQueue Q,DataType*d)

58、{　　if(Q.count ==0)　　{　　printf("隊列已空無數(shù)據(jù)出隊列!\n");　　return 0;

59、;　　}　　else　　{　　*d=Q.queue [Q.front ];　　return 1;

60、　　}　　}　　(3)/* 文件AdjMGraph.h*/　　#include"SeqList.h"　　typedef struct&

61、lt;p>　　{　　SeqList Vertices; //存放結(jié)點(diǎn)的順序表　　int edge[MaxVertices][MaxVertices]; //存放邊的鄰接矩陣　　int numOfEdges; //邊的條數(shù)

62、　}AdjMGraph; //邊的結(jié)構(gòu)體定義　　void Initiate(AdjMGraph *G,int n) //初始化　　{　　int i,j;　　for(i=0;i<n;i+

63、+)　　for(j=0;j<n;j++)　　{　　if(i==j)　　G->edge[i][j]=0;　　else</

64、b>　　G->edge[i][j]=MaxWeight;　　}　　G->numOfEdges=0; //邊的條數(shù)置為0　　ListInitiate(&G->Vertices); //順序表初始化

65、　　}　　void InsertVertex(AdjMGraph *G,DataType vertex) //在圖G中插入結(jié)點(diǎn)vertex　　{　　ListInsert(&G->V

66、ertices,G->Vertices.size,vertex); //順序表尾插入　　}　　void InsertEdge(AdjMGraph *G,int v1,int v2,int weight)　　//在圖G中插入邊<v1,v2>,邊<v1,

67、v2>的權(quán)為weight　　{　　if(v1<0||v1>G->Vertices.size||v2<0||v2>G->Vertices.size)　　{

68、　printf("參數(shù)v1或v2越界出錯!\n");　　exit(1);　　}　　G->edge[v1][v2]=weight;　　G->numOfEdges++;

69、　　}　　void DeleteEdge(AdjMGraph *G,int v1,int v2) //在圖中刪除邊<v1,v2>　　{　　if(v1<0||v1>G-&g

70、t;Vertices.size||v2<0||v2>G->Vertices.size||v1==v2)　　{　　printf("參數(shù)v1或v2越界出錯!\n");　　exit(1);

71、;　　}　　if(G->edge[v1][v2]==MaxWeight||v1==v2)　　{　　printf("該邊不存在!\n");<b&

72、gt;　　exit(0);　　}　　G->edge[v1][v2]=MaxWeight;　　G->numOfEdges--;　　}<p

73、>　　void DeleteVerten(AdjMGraph *G,int v) //刪除結(jié)點(diǎn)v　　{　　int n=ListLength(G->Vertices),i,j; 　　DataType x;　　for(i=

74、0;i<n;i++) //計算刪除后的邊數(shù)　　{　　for(j=0;j<n;j++)　　if((i==v||j==v)&&G->edge[i][j]>0&&G->edge[i][j]<MaxWeight)&

75、lt;/p>　　G->numOfEdges--; //計算被刪除邊　　}　　for(i=v;i<n;i++) //刪除第v行　　{　　for(j=0;j

76、<n;j++)　　G->edge[i][j]=G->edge[i+1][j];　　}　　for(i=0;i<n;i++) //刪除第v列　　{&l

77、t;p>　　for(j=v;j<n;j++)　　G->edge[i][j]=G->edge[i][j+1];　　}　　ListDelete(&G->Vertices,v,&x); //刪除結(jié)點(diǎn)v<p

78、>　　}　　int GetFistVex(AdjMGraph *G,int v) 　　//在圖G中尋找序號為v的結(jié)點(diǎn)的第一個鄰接結(jié)點(diǎn)　　//如果這樣的鄰接結(jié)點(diǎn)存在，返回該鄰接結(jié)點(diǎn)的序號；否則，返回-1　　{&

79、lt;/b>　　int col;　　if(v<0||v>G->Vertices.size)　　{　　printf("參數(shù)v1越界出錯!\n");<

80、/p>　　exit(1);　　}　　for(col=0;col<G->Vertices.size;col++)　　if(G->edge[v][col]>0&&G->

81、edge[v][col]<MaxWeight)return col;　　return -1;　　}　　int GetNextVex(AdjMGraph*G,int v1,int v2)　　//在圖中尋找v1結(jié)點(diǎn)的鄰接結(jié)點(diǎn)v2的下

82、一個鄰接結(jié)點(diǎn)　　//如果這樣的結(jié)點(diǎn)存在，返回該鄰接結(jié)點(diǎn)的序號；否則，返回-1　　//v1和v2都是相應(yīng)結(jié)點(diǎn)的序號　　{　　int col;　　if(v1&

83、lt;0||v1>G->Vertices.size||v2<0||v2>G->Vertices.size)　　{　　printf("參數(shù)v1或v2越界出錯!\n");　　exit(1); <

84、p>　　}　　for(col=v2+1;col<G->Vertices.size;col++)　　if(G->edge[v1][col]>0&&G->edge[v1][col]<MaxWeight)return col;

85、;　　return -1;　　}　　//輸出圖G的鄰接矩陣　　void Print(AdjMGraph *G) 　　{　　int i,

86、j;　　for(i=0;i<G->Vertices.size;i++)　　{　　for(j=0;j<G->Vertices.size;j++)　　printf("%6d "

87、;,G->edge[i][j]);　　printf("\n");　　}　　}　　//鄰接矩陣存儲結(jié)構(gòu)下求出每個頂點(diǎn)的度并輸出

88、void MVertices(AdjMGraph *G,DataType a[]) 　　{　　int i,j,m;　　DataType b[MaxVertices];//用數(shù)組b[]記錄相應(yīng)結(jié)點(diǎn)的度　　for(i=0;i<G-

89、>Vertices.size;i++)　　b[i]=0; //置0　　printf("鄰接矩陣存儲結(jié)構(gòu)下圖的頂點(diǎn)的度為:\n");　　for(m=0;m<G->Vertices.size;m++) //求出每個結(jié)點(diǎn)的度<b&

90、gt;　　{　　for(i=0;i<G->Vertices.size;i++)　　for(j=0;j<G->Vertices.size;j++)　　{　　if(i==m&&G

91、->edge[i][j]>0&&G->edge[i][j]<MaxWeight)　　//求出鄰接矩陣第i行權(quán)值存在的邊的個數(shù),當(dāng)邊<m,j>存在時,b[m]加1　　b[m]++;　　if(j==m&&i!=m

92、&&G->edge[i][j]>0&&G->edge[i][j]<MaxWeight)　　//求出鄰接矩陣第j列權(quán)值存在的邊的個數(shù),當(dāng)邊<i,m>存在時，b[m]加1　　b[m]++;　　}

93、　　printf("頂點(diǎn)%d的度為:%d\n",a[m],b[m]);　　}　　}　　//查找圖G中是否存在點(diǎn)v

94、　int ChaZhao(AdjMGraph *G,int v) 　　{　　if(0<=v&&v<G->Vertices.size)　　{　　printf(&q

95、uot;存在頂點(diǎn)%d\n",v);　　return 1;　　}　　else　　{<

96、;p>　　printf("不存在頂點(diǎn)%d\n",v);　　return 0;　　}　　}　　//刪除查找到的結(jié)點(diǎn)v并刪除該結(jié)點(diǎn)及與之

97、相關(guān)的邊　　void MDelete(AdjMGraph *G,int v)　　{　　int i;　　for(i=0;i<G->Vertices.size;i++)

98、　　{　　if(G->edge[v][i]>0&&G->edge[v][i]<MaxWeight)　　//當(dāng)鄰接矩陣的第v行有邊<v,i>存在時,刪除邊<v,i>　　DeleteEdge(G

99、,v,i);　　if(G->edge[i][v]>0&&G->edge[i][v]<MaxWeight)　　//當(dāng)鄰接矩陣的第j行有邊<i,v>存在時,刪除邊<i,v>　　DeleteEdge(G,i,v);

100、　　}　　DeleteVerten(G,v);//刪除結(jié)點(diǎn)v　　}　　(4)/* 文件AdjMGraphCreate.h */　　typedef struct<p&g

101、t;　　{　　int row; //行下標(biāo)　　int col; //列下標(biāo)　　int weight; //權(quán)值　　}RowColWeight; //邊信息結(jié)構(gòu)體定義　　void Cre

102、atGraph(AdjMGraph *G,DataType v[],int n,RowColWeight E[],int e)　　//在圖G中插入n個結(jié)點(diǎn)信息v和e條邊信息E　　{　　int i,k;<p&g

103、t;　　Initiate(G,n); //結(jié)點(diǎn)順序表初始化　　for(i=0;i<n;i++)　　InsertVertex(G,v[i]); //結(jié)點(diǎn)插入　　for(k=0;k<e;k++)　　InsertEdge(G,E[k].row,E[k].col,

104、E[k].weight); //邊插入　　}　　(5)/* 文件AdjLGraph.h */　　//鄰接表的存儲結(jié)構(gòu)　　typedef struct Node 　　{&l

105、t;/b>　　int dest; //鄰接邊的弧頭結(jié)點(diǎn)序號　　struct Node *next; 　　}Edge; //鄰接邊單鏈表的結(jié)點(diǎn)結(jié)構(gòu)體　　typedef struct　　{</b&g

106、t;　　DataType data; //結(jié)點(diǎn)數(shù)據(jù)元素 　　int sorce; //鄰接邊的弧尾結(jié)點(diǎn)序號　　Edge *adj; //鄰接邊的頭指針　　}AdjLHeight; //數(shù)組的數(shù)據(jù)元素類型結(jié)構(gòu)體　　typed

107、ef struct　　{　　AdjLHeight a[MaxVertices]; //鄰接表數(shù)組　　int numOfVerts; //結(jié)點(diǎn)個數(shù)　　int numOfEdges; //邊個數(shù)<p&g

108、t;　　}AdjLGraph; //鄰接表結(jié)構(gòu)體　　//初始化操作函數(shù)　　void LAdjInitiate(AdjLGraph *G)　　{　　int i;

109、;　　G->numOfVerts=0;　　G->numOfEdges=0;　　for(i=0;i<MaxVertices;i++)　　{　　G->a[i].sorce=

110、i;　　G->a[i].adj=NULL;　　}　　}　　//撤銷操作函數(shù)　　void LAdjDestroy

111、(AdjLGraph *G)　　//撤銷圖G中的所有鄰接邊單鏈表　　{　　int i;　　Edge *p,*q;　　for(i=0;i<G->

112、numOfVerts;i++)　　{　　p=G->a[i].adj;　　while(p!=NULL)　　{　　q=p->next;</p

113、>　　free(p);　　p=q;　　}　　}　　}&

114、lt;/p>　　//插入結(jié)點(diǎn)操作函數(shù)　　void LInsertVertex(AdjLGraph *G,int i,DataType vertex)　　//在圖G中的第i(0<=i<MaxVertices)個位置插入結(jié)點(diǎn)數(shù)據(jù)元素vertex　　{</

115、b>　　if(i>=0&&i<MaxVertices)　　{　　G->a[i].data=vertex; //存儲結(jié)點(diǎn)數(shù)據(jù)元素vertex　　G->numOfVerts++;

116、//個數(shù)加1　　}　　else　　printf("結(jié)點(diǎn)越界");　　}　　//

117、插入邊操作函數(shù)　　void LInsertEdge(AdjLGraph *G,int v1,int v2)　　//在圖G中加入邊<v1,v2>的信息　　{　　Edge *p; //定義一個鄰接邊指針&

118、lt;/p>　　if(v1<0||v1>=G->numOfVerts||v2<0||v2>=G->numOfVerts)　　{　　printf("參數(shù)v1或v2越界出錯");

119、　　exit(0);　　}　　p=(Edge *)malloc(sizeof(Edge)); //申請鄰接邊單鏈表結(jié)點(diǎn)空間　　p->dest=v2; //置鄰接邊弧頭序號　　p->next=G-&g

120、t;a[v1].adj; //新結(jié)點(diǎn)插入單鏈表的表頭　　G->a[v1].adj=p; //頭指針指向新的單鏈表表頭　　G->numOfEdges++; //邊數(shù)個數(shù)加1　　} 　　//刪除邊操作函

121、數(shù)　　void LDeleteEdge(AdjLGraph *G,int v1,int v2)　　//刪除圖G中的邊<v1,v2>信息　　{　　Edge *curr,*pre;&

122、lt;p>　　if(v1<0||v1>=G->numOfVerts||v2<0||v2>=G->numOfVerts)　　{　　printf("參數(shù)v1或v2越界出錯!");　　exit(0);&

123、lt;/b>　　}　　pre=NULL;　　curr=G->a[v1].adj;　　while(curr!=NULL&&curr->dest!=v2)</p

124、>　　//在v1結(jié)點(diǎn)的鄰接邊單鏈表中查找v2結(jié)點(diǎn)　　{　　pre=curr;　　curr=curr->next;　　}<

125、;/p>　　//刪除表示鄰接邊<v1,v2>的結(jié)點(diǎn)　　if(curr!=NULL&&curr->dest==v2&&pre==NULL)　　//當(dāng)鄰接邊<v1,v2>的結(jié)點(diǎn)是單鏈表的第一個結(jié)點(diǎn)時　　{<

126、;/b>　　G->a[v1].adj=curr->next;　　free(curr);　　G->numOfEdges--;　　}　　else if(curr!=NULL

127、&&curr->dest==v2&&pre!=NULL)　　//當(dāng)鄰接邊<v1,v2>的結(jié)點(diǎn)不是單鏈表的第一個結(jié)點(diǎn)時　　{　　pre->next=curr->next;

128、　free(curr);　　G->numOfEdges--;　　}　　else　　//當(dāng)鄰接邊<v1,v2>結(jié)點(diǎn)不存在時　　printf

129、("邊<v1,v2>不存在時");　　}　　//取第一個鄰接結(jié)點(diǎn)　　int LGetFirstVex(AdjLGraph *G,int v)　　//取圖G中結(jié)點(diǎn)v的第一個鄰接結(jié)點(diǎn)

130、　　//取到時返回該鄰接結(jié)點(diǎn)的對應(yīng)序號，否則返回-1　　{　　Edge *p;　　if(v<0||v>G->numOfVerts)　　{<

131、;/b>　　printf("參數(shù)v1或v2越界出錯!");　　exit(0);　　}　　p=G->a[v].adj;　　i

132、f(p!=NULL)　　return p->dest; //返回該鄰接結(jié)點(diǎn)的對應(yīng)序號　　else　　return -1; //返回-1　　}

133、//取下一個鄰接結(jié)點(diǎn)　　int LGetNextVex(AdjLGraph *G,int v1,int v2)　　//取圖G中結(jié)點(diǎn)v1的鄰接結(jié)點(diǎn)v2的下一個鄰接結(jié)點(diǎn)　　//取到時返回該鄰接結(jié)點(diǎn)的對應(yīng)序號，否則返回-1　　{</p

134、>　　Edge *p;　　if(v1<0||v1>G->numOfVerts||v2<0||v2>G->numOfVerts)　　{　　printf("參數(shù)v1或v

135、2越界出錯!");　　exit(0);　　}　　p=G->a[v1].adj;　　while(p!=NULL) //尋找結(jié)點(diǎn)v1的鄰接結(jié)點(diǎn)v2<p&

136、gt;　　{　　if(p->dest!=v2)　　{　　p=p->next;　　continue;<

137、;b>　　}　　else　　break;　　}　　p=p->next; //p指向鄰接結(jié)點(diǎn)v2的下一個鄰接結(jié)點(diǎn)</p&

138、gt;　　if(p!=NULL)　　return p->dest; //返回該鄰接結(jié)點(diǎn)的對應(yīng)序號　　else　　return -1; //返回-1　　}</p

139、>　　//鄰接表存儲下求每個頂點(diǎn)的度并輸出結(jié)果　　void LVertices(AdjLGraph *G,DataType a[])　　{　　printf("鄰接表存儲結(jié)構(gòu)下的圖的頂點(diǎn)的度為:\n");&

140、lt;p>　　int OutDegree[MaxVertices],InDegree[MaxVertices];//定義一個出度和入度的數(shù)組　　int i;　　for(i=0;i<G->numOfVerts;i++) //首先將出度和入度數(shù)組的每個成員都置0

141、;　　{　　OutDegree[i]=0;　　InDegree[i]=0;　　}　　Edge *p; //定義一個鄰接邊指針　　for(i=0;i<

142、;G->numOfVerts;i++)　　{　　p=G->a[i].adj; //指針指向a[i]的鄰接邊單鏈表頭結(jié)點(diǎn)　　while(p!=NULL)//當(dāng)p所指向的鄰接邊結(jié)點(diǎn)不空時　　{</b&

143、gt;　　OutDegree[i]++; //出度加1　　InDegree[p->dest]++; //鄰接邊弧頭結(jié)點(diǎn)的入度加1　　p=p->next; //p指向下一個鄰接邊結(jié)點(diǎn)　　}<p&

144、gt;　　}　　for(i=0;i<G->numOfVerts;i++) //輸出每個結(jié)點(diǎn)的度　　{　　printf("頂點(diǎn)%d的度為:",a[i]);　　prin

145、tf("%d",OutDegree[i]+InDegree[i]); //每個結(jié)點(diǎn)的度即出度與入度相加的和　　printf("\n");　　}　　}　　//

146、判斷有向圖G是否為強(qiáng)連通圖　　int LianTong(AdjLGraph *G,DataType a[]) 　　{　　int i,b[MaxVertices],k=0;　　for(i=0;i<G->numOfVerts;

147、i++)　　b[i]=0;　　Edge *q,*p; //定義一個鄰接邊指針　　for(i=0;i<G->numOfVerts;i++)　　{

148、;　　q=G->a[i].adj;　　while(q!=NULL)　　{　　b[i]++;　　q=q->next;　　}&l

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

溫馨提示

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

圖的基本操作與實現(xiàn)的課程設(shè)計報告

文檔簡介

溫馨提示

最新文檔

評論

圖的基本操作與實現(xiàn)的課程設(shè)計報告

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載