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

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：26 大小：105.00KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題（含答案詳解+作文范文）_第1頁(yè)

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

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

文檔簡(jiǎn)介

1、　　《軟件認(rèn)知實(shí)踐》報(bào)告　　姓名：學(xué) 號(hào)： 　　專(zhuān) 業(yè)： 　　設(shè)計(jì)題目： 　　指導(dǎo)教師： <p&g

2、t;　　2013年12月30日　　目錄　　第1章題目概述2　　第1.1節(jié) 題目要求2　　第1.2節(jié) 主要難點(diǎn)3　　第2章系統(tǒng)流程圖4<p&g

3、t;　　第3章數(shù)據(jù)結(jié)構(gòu)和算法5　　第4章核心代碼分析6　　第5章復(fù)雜度分析25　　參考文獻(xiàn)25　　題目概述　　第1.1節(jié) 題目要求</

4、p>　　(1)自選存儲(chǔ)結(jié)構(gòu),輸入含n個(gè)頂點(diǎn)（用字符表示頂點(diǎn)）和e條邊的圖G；　　(2)求每個(gè)頂點(diǎn)的度,輸出結(jié)果；　　(3)指定任意頂點(diǎn)x為初始頂點(diǎn),對(duì)圖G作DFS遍歷,輸出DFS頂點(diǎn)序列(提示:使用一個(gè)棧實(shí)現(xiàn)DFS)；　　(4)指定任意頂點(diǎn)x為初始頂點(diǎn),對(duì)圖G作BFS遍歷,輸出BFS頂

5、點(diǎn)序列(提示:使用一個(gè)隊(duì)列實(shí)現(xiàn)BFS)；　　(5)輸入頂點(diǎn)x,查找圖G:若存在含x的頂點(diǎn),則刪除該結(jié)點(diǎn)及與之相關(guān)連的邊,并作DFS遍歷(執(zhí)行操作3)；否則輸出信息“無(wú)x”；　　(6)判斷圖G是否是連通圖，輸出信息“YES”/“NO”；　　(7)如果選用的存儲(chǔ)結(jié)構(gòu)是鄰接矩陣,則用鄰接矩陣的信息生成圖G的鄰接表,即

6、復(fù)制圖G,然再執(zhí)行操作(2)；反之亦然。　　第1.2節(jié) 主要難點(diǎn)　　(1)自選存儲(chǔ)結(jié)構(gòu)創(chuàng)建一個(gè)圖：通過(guò)用戶從鍵盤(pán)敲入的兩個(gè)數(shù)值分別確定圖的頂點(diǎn)數(shù)和邊數(shù)，選擇鄰接矩陣存儲(chǔ)結(jié)構(gòu)將圖的結(jié)點(diǎn)信息存儲(chǔ)在一個(gè)順序表中，圖的邊信息存儲(chǔ)在一個(gè)二維數(shù)組中。　　(2)求每個(gè)頂點(diǎn)的度：　　1.

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

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

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

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

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

12、義一個(gè)鄰接表的邊信息結(jié)構(gòu)體，將鄰接矩陣的邊信息轉(zhuǎn)換成鄰接表的邊信息存儲(chǔ)到鄰接邊的單鏈表中。　　第二章系統(tǒng)流程圖　　數(shù)據(jù)結(jié)構(gòu)和算法　　(1)有向圖頂點(diǎn)的數(shù)據(jù)類(lèi)型DataType 定義如下：　　ty

13、pedef int DataType ；　　(2)鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的結(jié)構(gòu)體定義如下：　　typedef struct　　{　　SeqList Vertices； 　　int edge[Ma

14、xVertices][MaxVertices]；　　int numOfEdges； 　　}AdjMGraph； 　　(3)鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的邊信息結(jié)構(gòu)體定義如下：　　typedef struct　　{<

15、;/b>　　int row； 　　int col； 　　int weight； 　　}RowColWeight； 　　(4)鄰接表存儲(chǔ)結(jié)構(gòu)下圖的

16、結(jié)構(gòu)體定義如下：　　typedef struct Node 　　{　　int dest； 　　struct Node *next； 　　}Edge；

17、;　　typedef struct　　{　　DataType data； 　　int sorce； 　　Edge *adj； 　　}AdjLH

18、eight； 　　typedef struct　　{　　AdjLHeight a[MaxVertices]； 　　int numOfVerts； 　　int numOfEdges； &l

19、t;/p>　　}AdjLGraph； 　　(5)鄰接表存儲(chǔ)結(jié)構(gòu)下圖的邊信息結(jié)構(gòu)體定義如下：　　typedef struct　　{　　int row； 　　int

20、 col； 　　}RowCol； 　　(6)順序循環(huán)隊(duì)列的結(jié)構(gòu)體定義如下：　　typedef struct 　　{　　DataType queue[MaxQueueSize]；</p

21、>　　int rear；　　int front；　　int count；　　}SeqCQueue；　　(7)順序表的結(jié)構(gòu)體定義如下：　　typedef struct

22、　　{　　DataType list[MaxSize]；　　int size；　　}SeqList；　　第四章核心

23、代碼分析　　源程序存放在八個(gè)文件夾中，文件SeqList.h是順序表的結(jié)構(gòu)體定義和操作函數(shù)，文件SeqCQueue.h是順序循環(huán)隊(duì)列的結(jié)構(gòu)體定義和操作函數(shù)，文件AdjMGraph.h是鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的結(jié)構(gòu)體定義和操作函數(shù)，文件AdjMGraphCreate.h是鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的創(chuàng)建函數(shù)，文件AdjLGraph.h是鄰接表存儲(chǔ)結(jié)構(gòu)下圖的結(jié)構(gòu)體定義和操作函數(shù)，文件AdjLGraphCre

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

25、gt;　　DataType list[MaxSize];　　int size;　　}SeqList;　　void ListInitiate(SeqList *L)<b&

26、gt;　　{　　L->size=0;　　}　　int ListLength(SeqList L)　　{　　return L.si

27、ze;　　}　　int ListInsert(SeqList *L,int i,DataType x)　　{　　int j;<p

28、>　　if(L->size>=MaxSize)　　{　　printf("數(shù)組已滿無(wú)法插入！\n");　　return 0;　　}</b

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

30、;p>　　}　　else　　{　　for(j=L->size;j>i;i--)L->list[j]=L->list[j-1];

31、　L->list[i]=x;　　L->size++;　　return 1;　　}　　}　　int Lis

32、tDelete(SeqList *L,int i,DataType *x)　　{　　int j;　　if(L->size<=0)　　{</p

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

34、p>　　{　　printf("參數(shù)i不合法！\n");　　return 0;　　}　　else

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

36、;p>　　return 1;　　}　　}　　int ListGet(SeqList L,int i,DataType *x)　　{&l

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

38、>　　}　　else　　{　　*x=L.list[i];　　return 1;<p&

39、gt;　　}　　}　　(2)/* 文件SeqCQueue.h */　　typedef struct 　　{　　Dat

40、aType queue[MaxQueueSize];　　int rear;　　int front;　　int count;　　}SeqCQueue;　　void QueueInitiate(S

41、eqCQueue *Q)　　{　　Q->rear=0;　　Q->front =0;　　Q->count =0;　　}

42、　　int QueueNotEmpty(SeqCQueue Q)　　{　　if(Q.count !=0) return 1;　　else return 0;　　}</

43、p>　　int QueueAppend(SeqCQueue *Q,DataType x)　　{　　if(Q->count>0&&Q->rear==Q->front)　　{

44、　　printf("隊(duì)列已滿無(wú)法插入!");　　return 0;　　}　　else <b

45、>　　{　　Q->queue [Q->rear]=x;　　Q->rear =(Q->rear +1)%MaxQueueSize;　　Q->count ++;　　return 1;

46、　　}　　}　　int QueueDelete(SeqCQueue *Q,DataType *d)　　{　　if(Q

47、->count ==0)　　{　　printf("隊(duì)列已空無(wú)數(shù)據(jù)出隊(duì)列!\n");　　return 0;　　}

48、　　else　　{　　*d=Q->queue[Q->front];　　Q->front=(Q->front+1)%MaxQueueSize;　　Q-&g

49、t;count --;　　return 1;　　}　　}　　int QueueGet(SeqCQueue Q,DataType*d)&

50、lt;p>　　{　　if(Q.count ==0)　　{　　printf("隊(duì)列已空無(wú)數(shù)據(jù)出隊(duì)列!\n");　　return 0;&

51、lt;/p>　　}　　else　　{　　*d=Q.queue [Q.front ];　　return 1;<

52、;/b>　　}　　}　　(3)/* 文件AdjMGraph.h*/　　#include"SeqList.h"　　typedef

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

54、;/p>　　}AdjMGraph; //邊的結(jié)構(gòu)體定義　　void Initiate(AdjMGraph *G,int n) //初始化　　{　　int i,j;

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

56、lt;b>　　else　　G->edge[i][j]=MaxWeight;　　}　　G->numOfEdges=0; //邊的條數(shù)置為0　　ListInitiate(&G->V

57、ertices); //順序表初始化　　}　　void InsertVertex(AdjMGraph *G,DataType vertex) //在圖G中插入結(jié)點(diǎn)vertex　　{　　List

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

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

60、;/p>　　printf("參數(shù)v1或v2越界出錯(cuò)!\n");　　exit(1);　　}　　G->edge[v1][v2]=weight;

61、G->numOfEdges++;　　}　　void DeleteEdge(AdjMGraph *G,int v1,int v2) //在圖中刪除邊<v1,v2>　　{　　if(

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

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

64、t;　　exit(0);　　}　　G->edge[v1][v2]=MaxWeight;　　G->numOfEdges--;　　}</b&g

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

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

67、][j]<MaxWeight)　　G->numOfEdges--; //計(jì)算被刪除邊　　}　　for(i=v;i<n;i++) //刪除第v行　　{&

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

69、b>　　for(j=v;j<n;j++)　　G->edge[i][j]=G->edge[i][j+1];　　}　　ListDelete(&G->Vertices,v,&x); //刪除結(jié)

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

71、;p>　　{　　int col;　　if(v<0||v>G->Vertices.size)　　{　　printf("參數(shù)v1

72、越界出錯(cuò)!\n");　　exit(1);　　}　　for(col=0;col<G->Vertices.size;col++)　　if(G->edge[v][col]&g

73、t;0&&G->edge[v][col]<MaxWeight)return col;　　return -1;　　}　　int GetNextVex(AdjMGraph*G,int v1,int v2)　　/

74、/在圖中尋找v1結(jié)點(diǎn)的鄰接結(jié)點(diǎn)v2的下一個(gè)鄰接結(jié)點(diǎn)　　//如果這樣的結(jié)點(diǎn)存在，返回該鄰接結(jié)點(diǎn)的序號(hào)；否則，返回-1　　//v1和v2都是相應(yīng)結(jié)點(diǎn)的序號(hào)　　{　　int col;

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

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

77、lt;/p>　　return -1;　　}　　//輸出圖G的鄰接矩陣　　void Print(AdjMGraph *G) 　　{<p&g

78、t;　　int i,j;　　for(i=0;i<G->Vertices.size;i++)　　{　　for(j=0;j<G->Vertices.size;j++)　　pri

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

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

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

82、t;　　{　　for(i=0;i<G->Vertices.size;i++)　　for(j=0;j<G->Vertices.size;j++)　　{

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

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

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

86、;/p>　　int ChaZhao(AdjMGraph *G,int v) 　　{　　if(0<=v&&v<G->Vertices.size)　　{&

87、lt;p>　　printf("存在頂點(diǎn)%d\n",v);　　return 1;　　}　　else　　{</b

88、>　　printf("不存在頂點(diǎn)%d\n",v);　　return 0;　　}　　}　　/

89、/刪除查找到的結(jié)點(diǎn)v并刪除該結(jié)點(diǎn)及與之相關(guān)的邊　　void MDelete(AdjMGraph *G,int v)　　{　　int i;　　for(i=0;i<G->Vertices.

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

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

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

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

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

95、　　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

96、,E[k].row,E[k].col,E[k].weight); //邊插入　　}　　(5)/* 文件AdjLGraph.h */　　//鄰接表的存儲(chǔ)結(jié)構(gòu)　　typedef struct Node <

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

98、lt;b>　　{　　DataType data; //結(jié)點(diǎn)數(shù)據(jù)元素 　　int sorce; //鄰接邊的弧尾結(jié)點(diǎn)序號(hào)　　Edge *adj; //鄰接邊的頭指針　　}AdjLHeight; //數(shù)組的數(shù)據(jù)元素類(lèi)型結(jié)構(gòu)體

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

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

101、t;　　int i;　　G->numOfVerts=0;　　G->numOfEdges=0;　　for(i=0;i<MaxVertices;i++)　　{

102、　　G->a[i].sorce=i;　　G->a[i].adj=NULL;　　}　　}　　//撤銷(xiāo)操作函數(shù)

103、;　　void LAdjDestroy(AdjLGraph *G)　　//撤銷(xiāo)圖G中的所有鄰接邊單鏈表　　{　　int i;　　Edge *p,*q;

104、for(i=0;i<G->numOfVerts;i++)　　{　　p=G->a[i].adj;　　while(p!=NULL)　　{

105、q=p->next;　　free(p);　　p=q;　　}　　}<

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

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

108、numOfVerts++; //個(gè)數(shù)加1　　}　　else　　printf("結(jié)點(diǎn)越界");　　}<

109、;p>　　//插入邊操作函數(shù)　　void LInsertEdge(AdjLGraph *G,int v1,int v2)　　//在圖G中加入邊<v1,v2>的信息　　{　　Edg

110、e *p; //定義一個(gè)鄰接邊指針　　if(v1<0||v1>=G->numOfVerts||v2<0||v2>=G->numOfVerts)　　{　　printf("參數(shù)v1或v2越界出錯(cuò)");

111、　　exit(0);　　}　　p=(Edge *)malloc(sizeof(Edge)); //申請(qǐng)鄰接邊單鏈表結(jié)點(diǎn)空間　　p->dest=v2; //置鄰接邊弧頭序號(hào)<p&g

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

113、　　//刪除邊操作函數(shù)　　void LDeleteEdge(AdjLGraph *G,int v1,int v2)　　//刪除圖G中的邊<v1,v2>信息　　{　　Edge *curr

114、,*pre;　　if(v1<0||v1>=G->numOfVerts||v2<0||v2>=G->numOfVerts)　　{　　printf("參數(shù)v1或v2越界出錯(cuò)!");&

115、lt;b>　　exit(0);　　}　　pre=NULL;　　curr=G->a[v1].adj;　　while(curr!=NULL&&curr-

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

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

118、>　　{　　G->a[v1].adj=curr->next;　　free(curr);　　G->numOfEdges--;　　}

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

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

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

122、第一個(gè)鄰接結(jié)點(diǎn)　　//取到時(shí)返回該鄰接結(jié)點(diǎn)的對(duì)應(yīng)序號(hào)，否則返回-1　　{　　Edge *p;　　if(v<0||v>G->numOfVerts)<p

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

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

125、/p>　　//取下一個(gè)鄰接結(jié)點(diǎn)　　int LGetNextVex(AdjLGraph *G,int v1,int v2)　　//取圖G中結(jié)點(diǎn)v1的鄰接結(jié)點(diǎn)v2的下一個(gè)鄰接結(jié)點(diǎn)　　//取到時(shí)返回該鄰接結(jié)點(diǎn)的對(duì)應(yīng)序號(hào)，否則返回-1

126、　　{　　Edge *p;　　if(v1<0||v1>G->numOfVerts||v2<0||v2>G->numOfVerts)　　{

127、printf("參數(shù)v1或v2越界出錯(cuò)!");　　exit(0);　　}　　p=G->a[v1].adj;　　while(p!=NULL) //尋找結(jié)點(diǎn)v1的鄰接結(jié)點(diǎn)v

128、2　　{　　if(p->dest!=v2)　　{　　p=p->next;　　continue;</

129、p>　　}　　else　　break;　　}　　p=p->next; //p指向鄰接

130、結(jié)點(diǎn)v2的下一個(gè)鄰接結(jié)點(diǎn)　　if(p!=NULL)　　return p->dest; //返回該鄰接結(jié)點(diǎn)的對(duì)應(yīng)序號(hào)　　else　　return -1; //返回-1

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

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

133、lt;/p>　　{　　OutDegree[i]=0;　　InDegree[i]=0;　　}　　Edge *p; //定義一個(gè)鄰接邊指針<

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

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

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

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

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

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

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

141、p>　　}　　}　　for(i=0;i<G->numOfVerts;i++)　　{　　if(b[i]==1)<

142、p>　　k++;　　}　　p=G->a[G->numOfVerts-1].adj;　　if(k==G->numOfVerts&&p->dest==a[0])<p&

143、gt;　　return 1;　　else　　return 0;　　}　　(6)/* 文件AdjLGraphCreate.

144、h */　　typedef struct　　{　　int row; //行下標(biāo)　　int col; //列下標(biāo)　　}RowCol; //邊信息結(jié)構(gòu)體定義<p

145、>　　void CreatLGraph(AdjLGraph *G,DataType v[],int n,RowCol d[],int e)　　{　　int i,k;　　LAdjInitiate(G);<

146、p>　　for(i=0;i<n;i++)　　LInsertVertex(G,i,v[i]);　　for(k=0;k<e;k++)　　LInsertEdge(G,d[k].row,d[k].col);　　}</p

147、>　　(7)/* 文件AdjMGraphTraverse.h */　　void Visit(DataType item)　　{　　printf("%d ",item);

148、　　}　　void DepthFSearch(AdjMGraph G,int v,int visited[],void Visit(DataType item))　　//連通圖G以v為初始結(jié)點(diǎn)的訪問(wèn)操作為Visit()的深度優(yōu)先遍歷　　//數(shù)組visited標(biāo)記了相應(yīng)結(jié)點(diǎn)是否已訪問(wèn)過(guò)，0表示未

149、訪問(wèn)，1表示已訪問(wèn)　　{　　int w;　　Visit(G.Vertices.list[v]); //訪問(wèn)結(jié)點(diǎn)v　　visited[v]=1; //置已訪問(wèn)標(biāo)記<

眾賞文庫(kù)> 全部分類(lèi)> 畢業(yè)設(shè)計(jì)

溫馨提示

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

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載