數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-- 圖的遍歷和生成樹求解

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

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

已閱讀1頁(yè)，還剩22頁(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、　　圖的遍歷和生成樹求解　　摘要：圖是一種比線形表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在圖形結(jié)構(gòu)中，節(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。本程序是采用鄰接矩陣、鄰接表結(jié)構(gòu)存儲(chǔ)來(lái)實(shí)現(xiàn)對(duì)圖的存儲(chǔ)。采用鄰接矩陣即為數(shù)組表示法，鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。對(duì)圖的遍歷分別采用了廣度優(yōu)先遍歷和深度優(yōu)先遍歷。圖的最小生成樹基于圖的兩種存儲(chǔ)結(jié)構(gòu)，采用Prim算法和Kruskal

2、算法對(duì)圖的最小生成樹進(jìn)行求解。　　關(guān)鍵詞：圖；存儲(chǔ)結(jié)構(gòu)；遍歷；最小生成樹　　目錄　　1.設(shè)計(jì)背景………………………………………………………1　　1.1課程設(shè)計(jì)目的………………………………………………1

3、　　1.2題目要求……………………………………………………1　　2.設(shè)計(jì)方案………………………………………………………1　　2.1設(shè)計(jì)方法……………………………………………………1　　2.2方法實(shí)現(xiàn)……………………………………………………2　　3. 方案

4、實(shí)施………………………………………………………3　　3.1采用的數(shù)據(jù)結(jié)構(gòu)說(shuō)明及類型的定義………………………3　　3.2函數(shù)功能描述及相關(guān)函數(shù)的實(shí)現(xiàn)…………………………5　　3.3程序中需說(shuō)明的地方，如用到的宏及代表的意義………16　　4. 結(jié)果與結(jié)論……………………………

5、…………………… 17　　4.1測(cè)試數(shù)據(jù)及測(cè)試結(jié)果………………………………………17　　4.2實(shí)驗(yàn)結(jié)論……………………………………………………19　　5.收獲與致謝…………………………………………………19　　6.參考文獻(xiàn)……………………………………………………20<

6、;/p>　　設(shè)計(jì)背景　　1.1課程設(shè)計(jì)目的　　通過(guò)本課程設(shè)計(jì)，加深對(duì)《面向?qū)ο蟪绦蛟O(shè)計(jì)C++》課程所學(xué)知識(shí)的理解，熟練掌握和鞏固C++語(yǔ)言的基本知識(shí)和語(yǔ)法規(guī)范,掌握使用面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言C++，或面向?qū)ο箝_發(fā)平臺(tái)Visual C++等,培養(yǎng)調(diào)查研究、

7、查閱技術(shù)文獻(xiàn)、資料、手冊(cè)以及編寫技術(shù)文獻(xiàn)的能力。學(xué)會(huì)編制結(jié)構(gòu)清晰、風(fēng)格良好的C++語(yǔ)言程序，從而具備利用計(jì)算機(jī)編程分析解決綜合性實(shí)際問(wèn)題的初步能力。　　1.2題目要求　　課程設(shè)計(jì)是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識(shí),發(fā)現(xiàn),提出,分析和解決實(shí)際問(wèn)題,鍛煉實(shí)踐能力的重要環(huán)節(jié),是對(duì)學(xué)生實(shí)際工作能力的具體訓(xùn)練和考察過(guò)程. 通過(guò)課程設(shè)計(jì)

8、，鞏固和加深對(duì)隊(duì)列以及圖等理論知識(shí)的理解；掌握現(xiàn)實(shí)復(fù)雜問(wèn)題的分析建模和解決方法，掌握包括問(wèn)題描述、系統(tǒng)分析、設(shè)計(jì)建模、代碼實(shí)現(xiàn)、結(jié)果分析等的方法；提高利用計(jì)算機(jī)分析解決綜合性實(shí)際問(wèn)題的基本能力；鍛煉個(gè)人動(dòng)手能力，歷練自身素質(zhì)。　　2.設(shè)計(jì)方案　　2.1設(shè)計(jì)方法

9、　　2.1.1問(wèn)題的分析和結(jié)構(gòu)的設(shè)計(jì)思路　　1）圖的遍歷和生成樹求解所有功能：圖的生成、圖的遍歷、最小生成樹求解。　　2）需要?jiǎng)?chuàng)建所有圖的存儲(chǔ)結(jié)構(gòu)(鄰接矩陣存儲(chǔ)結(jié)構(gòu)和鄰接表存儲(chǔ)結(jié)構(gòu))。　　3）程序設(shè)計(jì)的目的是通過(guò)屏幕上輸出的提示語(yǔ)句，進(jìn)行相應(yīng)的操作。<p&g

10、t;　　4）選擇適當(dāng)?shù)乃惴?，?shí)現(xiàn)圖的遍歷和最小生成樹的求解等功能。　　5）選擇適當(dāng)?shù)淖兞?，?lái)表示圖相應(yīng)的頂點(diǎn)、邊、邊的權(quán)值等信息。　　6）當(dāng)輸入的信息出錯(cuò)時(shí)，程序應(yīng)給錯(cuò)誤信息提示，使程序設(shè)計(jì)得全面周密。　　2.1.2圖的遍歷和生成樹求解的算法思想及設(shè)計(jì)　　1）由于圖的存

11、儲(chǔ)結(jié)構(gòu)不同，故采用鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)建立圖。　　2）對(duì)圖的深度遍歷基于鄰接矩陣，廣度遍歷基于鄰接表。　　3）基于鄰接矩陣存儲(chǔ)結(jié)構(gòu)，用prim算法求圖的最小生成樹。　　4）基于鄰接表存儲(chǔ)結(jié)構(gòu)，用Kruskal算法求圖的最小生成樹。　　5）綜合1、2、3三點(diǎn)因素，可

12、以采用隊(duì)列來(lái)實(shí)現(xiàn)對(duì)圖的廣度優(yōu)先遍歷的算法，其示意圖如下：　　6）圖遍歷和生成樹求解的總體結(jié)構(gòu)框圖如下：　　2.2方法實(shí)現(xiàn)　　2.2.1創(chuàng)建結(jié)點(diǎn)　　1）建立隊(duì)列LinkQueue，以及隊(duì)頭指針fro

13、nt、隊(duì)尾指針rear。　　2)建立圖的存儲(chǔ)類型MGraph,以及頂點(diǎn)向量vexs[]。　　3)建立圖的鄰接矩陣AdjMatrix[][]，以及邊的權(quán)值。　　4)建立圖的鄰接表ALGraph,以及鄰接表頭結(jié)點(diǎn)的類型AdjList[]，弧的結(jié)點(diǎn)結(jié)構(gòu)類型ArcNode。<

14、;b>　　2.2.2編寫函數(shù)　　建立具體的功能實(shí)現(xiàn)函數(shù)，如初始化、錄入、輸出等。　　1.基于鄰接矩陣創(chuàng)建圖CreateUDN(MGraph &G,AdjMatrix &GA)　　2.基于鄰接表建立圖CreateALGraph(ALGraph &G) </p&

15、gt;　　3.鄰接矩陣的輸出Display(MGraph G,AdjMatrix GA)　　4.鄰接表的輸出DisplayG(ALGraph G) 　　5.基于鄰接矩陣圖進(jìn)行深度優(yōu)先遍歷DFS1(MGraph G,int n,int v)　　6.對(duì)結(jié)點(diǎn)隊(duì)列初始化InitQueue (Link

16、Queue &Q) 　　7.判斷隊(duì)列是否為空 QueueEmpty (LinkQueue Q)　　8.頂點(diǎn)信息入隊(duì)EnQueue (LinkQueue &Q,int e)　　9.頂點(diǎn)信息出隊(duì)DeQueue (LinkQueue &Q,int &e)<p

17、>　　10.基于鄰接表對(duì)圖進(jìn)行廣度優(yōu)先遍歷BFS(ALGraph G,int v)　　11.Prim求生成樹MiniSpanTree_PRIM(MGraph G,AdjMatrix GA,VertexType u) 　　12.Kruskal求生成樹Kruskal(ALGraph G)　　13. 求頂點(diǎn)在圖中

18、位置LocateVex(MGraph G,VertexType u)，LocateVexG(ALGraph G,vertexType e)　　14.主函數(shù)main()　　3.方案實(shí)施　　3.1 采用的數(shù)據(jù)結(jié)構(gòu)說(shuō)明及類型的定義　　1．鄰

19、接矩陣的存儲(chǔ)表示如下　　typedef struct ArcCell　　{　　VRType adj; //VRType是頂點(diǎn)關(guān)系類型，對(duì)無(wú)權(quán)圖，用0和1；對(duì)有權(quán)圖，則為權(quán)值類型 　　InfoType *info; //該弧相關(guān)信

20、息的指針(可無(wú))　　}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];　　typedef struct 　　{　　VertexType vexs[MAX_VERTEX_NUM];//

21、頂點(diǎn)向量　　AdjMatrix arcs;//鄰接矩陣　　int vexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)　　GraphKind kind;//圖的種類標(biāo)志　　}MGraph;

22、2．鄰接表的存儲(chǔ)表示如下　　typedef struct ArcNode{ //弧的結(jié)點(diǎn)結(jié)構(gòu)類型　　int adjvex;//該弧所指向的頂點(diǎn)的位置　　int weight;/*該弧的權(quán)重*/　　struct ArcNode *nextarc;//指向下一條弧的指針&

23、lt;/p>　　InfoType *info;//該弧相關(guān)信息的指針(可無(wú))　　}ArcNode;　　typedef struct VNode{//鄰接表頭結(jié)點(diǎn)的類型　　vertexType data;//頂點(diǎn)信息<

24、;p>　　ArcNode *firstarc;//指向第一條依附該頂點(diǎn)的弧的指針　　}VNode,AdjList[MAX_VERTEX_NUM];　　typedef struct{//鄰接表　　AdjList vertices;　　int vexnum,arcnum

25、;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)　　}ALGraph　　3．隊(duì)列的存儲(chǔ)結(jié)構(gòu)　　typedef struct QNode　　{

26、;　　TElemType data;　　QNode *next;　　}QNode,*QueuePtr;　　typedef struct　　{　　QueuePtr front;//隊(duì)頭指針<

27、;/p>　　QueuePtr rear;//隊(duì)尾指針　　}LinkQueue;　　4．Prim算法輔助數(shù)組存儲(chǔ)結(jié)構(gòu)　　typedef struct //輔助數(shù)組存儲(chǔ)結(jié)構(gòu)　　{&l

28、t;p>　　VertexType adjvex;　　VRType lowcost;　　}Closedge[ MAX_VERTEX_NUM];　　3.2函數(shù)功能描述及相關(guān)函數(shù)的實(shí)現(xiàn)　　1.基于鄰接矩陣創(chuàng)建圖CreateUDN(MGraph &G,AdjMatr

29、ix &GA)　　Status CreateUDN(MGraph &G,AdjMatrix &GA)　　{//用鄰接矩陣表示法，構(gòu)造無(wú)向網(wǎng)G，以及表示出其鄰接矩陣GA　　int i,j,k,w;　　VertexType v1,v2;</p&g

30、t;　　printf("請(qǐng)輸入無(wú)向網(wǎng)G的頂點(diǎn)數(shù),邊數(shù):\n");　　scanf("%d,%d",&G.vexnum,&G.arcnum,);　　printf("請(qǐng)輸入%d個(gè)頂點(diǎn)的值:\n",G.vexnum);　　f

31、or(i=1;i<=G.vexnum;++i) 　　scanf("%s",&G.vexs[i]); //構(gòu)造頂點(diǎn)向量　　getchar();　　for(i=1;i<=G.vexnum;i++)　　{for(j=1;j<=G.

32、vexnum;j++) //初始化鄰接矩陣　　{　　GA[i][j].adj=INFINITY;　　GA[i][j].info=NULL;　　}&

33、lt;b>　　}　　printf("請(qǐng)輸入%d條邊的頂點(diǎn)1頂點(diǎn)2和權(quán)值(以空格作為間隔):\n",G.arcnum);　　for(k=1;k<=G.arcnum;k++)　　{　　s

34、canf("%s%s%d",&v1,&v2,&w); //輸入一條邊依附的頂點(diǎn)和權(quán)值　　i=LocateVex(G,v1);　　j=LocateVex(G,v2); //確定v1和v2在G中的位置　　GA[i][j].adj=GA[j][i].adj=w; //弧&

35、lt;v1,v2>的權(quán)值和<v2,v1>的對(duì)稱弧　　}　　return OK;　　}　　2.基于鄰接表建立圖CreateALGraph(ALGraph &G)</

36、p>　　Status CreateALGraph(ALGraph &G)　　{//用鄰接表表示法，構(gòu)建無(wú)向網(wǎng)G　　int i,j,k,w;　　ArcNode *s,*p;　　printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為:頂點(diǎn)

37、數(shù),邊數(shù))：\n");　　scanf("%d,%d",&(G.vexnum),&(G.arcnum)); 　　vertexType v1,v2;　　printf("請(qǐng)輸入頂點(diǎn)信息：\n");　　for (

38、i=1;i<=G.vexnum;i++) 　　{　　scanf("\n%c",&(G.vertices[i].data)); //初始化鄰接表的頭結(jié)點(diǎn)　　G.vertices[i].firstarc=NULL; <

39、;p>　　}　　printf("請(qǐng)輸入邊的信息(輸入格式為:v1,v2,w)：\n");　　for (k=1;k<=G.arcnum;k++)　　{　　scanf(

40、"\n%c,%c,%d",&v1,&v2,&w); //輸入一條邊依附的頂點(diǎn)和權(quán)值　　j= LocateVexG(G,v2);　　i= LocateVexG(G,v1); //確定v1和v2在G中的位置　　s=(ArcNode*)malloc(sizeof(ArcNod

41、e)); 　　s->adjvex=j;　　s->weight=w;　　s->nextarc=G.vertices[i].firstarc; 　　G.vertices[i].firstarc=s;//將下標(biāo)為j的結(jié)點(diǎn)連接在下標(biāo)為i的結(jié)點(diǎn)后面</p&g

42、t;　　p=(ArcNode*)malloc(sizeof(ArcNode));　　p->adjvex=i;　　p->weight=w;　　p->nextarc=G.vertices[j].firstarc;　　G.vertices

43、[j].firstarc=p; //將下標(biāo)為i的結(jié)點(diǎn)連接在下標(biāo)為j的結(jié)點(diǎn)后面　　}　　return OK;　　}　　3.鄰接矩陣的輸出Display(MGraph G,AdjMatrix GA)&

44、lt;/p>　　void Display(MGraph G,AdjMatrix GA)　　{ //鄰接矩陣的輸出　　int i,j;　　for(i=1;i<=G.vexnum;i++) <p&

45、gt;　　printf("G.vexs[%d]=%c\n",i,G.vexs[i]); //輸出頂點(diǎn)向量　　printf("鄰接矩陣GA.adj:\n"); 　　for(i=1;i<=G.vexnum;i++)

46、{　　for(j=1;j<=G.vexnum;j++)　　printf("%5d",GA[i][j].adj);　　printf("\n");　　}

47、;　　} 　　4.鄰接表的輸出DisplayG(ALGraph G) 　　void DisplayG(ALGraph G) 　　{//鄰接表的輸出

48、　　int i;　　ArcNode *p;　　for(i=1; i<=G.vexnum; i++)　　{　　p=G.vertices[i].firs

49、tarc;　　printf("(%d | %c)-> ",i,G.vertices[i].data);　　while(p)　　{　　if(p->nextarc)&l

50、t;/p>　　printf("[%d,%c,%d]->",p->adjvex,G.vertices[p->adjvex].data,p->weight);　　else　　printf("[%d,%c,%d]->/\\",

51、p->adjvex,G.vertices[p->adjvex].data,p->weight);　　p=p->nextarc;　　}　　printf("\n");　　}&l

52、t;/b>　　}　　5.基于鄰接矩陣圖進(jìn)行深度優(yōu)先遍歷DFS1(MGraph G,int n,int v)　　int visited[MAX_VERTEX_NUM]; //初始化標(biāo)志數(shù)組　　Status DFS1(MGraph

53、 G,int n,int v)　　{//基于鄰接矩陣，對(duì)圖G進(jìn)行深度優(yōu)先搜索　　int j;　　AdjMatrix A;　　printf("%3d",v);　　printf

54、("%c",G.vexs[v]);　　visited[v]=1;　　for(j=1;j<=n;j++)　　if(A[v][j].adj!=0&&!visited[j])　　DFS1(G,n,j);<p

55、>　　return OK;　　}　　6.對(duì)結(jié)點(diǎn)隊(duì)列初始化InitQueue (LinkQueue &Q) 　　Status InitQueue (LinkQueue &Q)　　{//建立一個(gè)空隊(duì)列</p&g

56、t;　　Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));　　if(!Q.front) return ERROR;　　Q.front->next=NULL;　　return OK;

57、　}　　7.判斷隊(duì)列是否為空 QueueEmpty (LinkQueue Q)　　int QueueEmpty (LinkQueue Q)　　{//判斷隊(duì)列是否為空　　if(Q.front==Q.rear)&l

58、t;b>　　return 1;　　return 0;　　}　　8.頂點(diǎn)信息入隊(duì)EnQueue (LinkQueue &Q,int e)　　Status EnQue

59、ue (LinkQueue &Q,int e)　　{//結(jié)點(diǎn)進(jìn)隊(duì)　　QNode *p;　　p=(QNode*)malloc(sizeof(QNode));　　if(!p) return E

60、RROR;　　p->data=e;　　p->next=NULL;　　Q.rear->next=p;　　Q.rear=p;　　return OK;<

61、;p>　　}　　9.頂點(diǎn)信息出隊(duì)DeQueue (LinkQueue &Q,int &e)　　int DeQueue (LinkQueue &Q,int &e)　　{//結(jié)點(diǎn)出隊(duì)

62、　　if(Q.front==Q.rear)　　printf("隊(duì)列為空！\n");　　QNode *p;　　p=(QNode*)malloc(sizeof(QNode));　　if(!p) re

63、turn ERROR;　　p=Q.front->next;　　e=p->data;　　Q.front->next=p->next;　　if(Q.rear==p)　　Q.rear=Q.front;</p

64、>　　free(p);　　return OK;　　}　　10.基于鄰接表對(duì)圖進(jìn)行廣度優(yōu)先遍歷BFS(ALGraph G,int v)　　int visited1[MAX

65、_VERTEX_NUM];//初始化標(biāo)志數(shù)組　　Status BFS(ALGraph G,int v)　　{//基于鄰接表，對(duì)無(wú)向圖G進(jìn)行廣度優(yōu)先搜索　　int u, w;　　LinkQueue Q;<p

66、>　　InitQueue(Q);　　if(!visited1[v])　　{　　visited1[v]=1;　　printf("%c\t",G.vertices[v].data);<

67、;p>　　EnQueue(Q,v);　　while(!QueueEmpty(Q))　　{　　DeQueue(Q,u);　　for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))&l

68、t;/p>　　if(!visited1[w])　　{　　visited1[w]=1;　　printf("%c\t",G.vertices[w].data);　　EnQueue(Q,w);

69、　　}　　}　　}　　return OK;　　}<

70、;p>　　11.Prim求生成樹MiniSpanTree_PRIM(MGraph G,AdjMatrix GA,VertexType u)　　Status MiniSpanTree_PRIM(MGraph G,AdjMatrix GA,VertexType u)　　{//用Prim算法從第u個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹T，輸出T的各邊 </

71、p>　　int k,j,i;　　Closedge closedge;　　k=LocateVex(G,u);　　for(j=1;j<=G.vexnum;j++)　　{<p&

72、gt;　　if(j!=k)　　{　　closedge[j].adjvex=u;　　closedge[j].lowcost=GA[k][j].adj;// 輔助數(shù)組初始化　　}&l

73、t;/b>　　}　　closedge[j].adjvex = '\0';　　closedge[j].lowcost = 88;　　closedge[k].adjvex = u;<p&

74、gt;　　closedge[k].lowcost=0;//初始U={u}　　printf("最小生成樹的各條邊為:\n");　　for(i=2;i<=G.vexnum;++i)　　{//選擇其余的G.vexnum-1個(gè)頂點(diǎn)　　k=minimum(

75、closedge); //求出T的下一個(gè)結(jié)點(diǎn)；第k個(gè)頂點(diǎn)　　printf("%c--%c\n",closedge[k].adjvex,G.vexs[k]);//輸出生成樹的邊　　closedge[k].lowcost=0;//第k頂點(diǎn)并入U(xiǎn)集　　for(j=1;j<=G.vexnum;+

76、+j)　　if(GA[k][j].adj<closedge[j].lowcost)　　{//新頂點(diǎn)并入U(xiǎn)集后，重新選擇最小邊　　closedge[j].adjvex=G.vexs[k];　　closedge[j].lowcost=GA[k][j].adj;</

77、p>　　}　　}　　return OK;　　}　　12.Kruskal求生成樹Kruskal(ALGraph G)</p&g

78、t;　　Status Kruskal(ALGraph G)　　{　　int i,j,min = INFINITY,k = 1;//min用于記錄最小權(quán)值，k表示當(dāng)前構(gòu)造的第幾條邊　　int set[MAX_VERTEX_NUM];//用于判斷兩個(gè)點(diǎn)是否在

79、同一集合里　　ArcNode *p,*q,*s;　　for(i = 1; i <= G.vexnum; ++i) set[i] = i;//初始化，將每個(gè)點(diǎn)自身作為一個(gè)集合　　while(k<G.vexnum&&k<=G.arcnum )

80、　　{　　for(i = 1; i <= G.vexnum; ++i)　　{　　if(G.vertices[i].firstarc!=NULL)　　{//若第i+1個(gè)點(diǎn)沒有鄰邊，則下一循環(huán)&

81、lt;/p>　　for(p=G.vertices[i].firstarc;p!=NULL;p=p->nextarc)//查找最小權(quán)值的邊　　if(p->weight < min)　　{　　min = p->weight;&l

82、t;/p>　　q = p;　　j = i;　　}　　}　　}</b&

83、gt;　　if(G.vertices[j].firstarc == q) 　　G.vertices[j].firstarc = q->nextarc; //if-else用于刪除最小權(quán)值的邊　　else　　{

84、　　for(p = G.vertices[j].firstarc; p != q; p = p->nextarc) 　　s = p;　　s->nextarc = q->nextarc;<b&

85、gt;　　}　　if(set[j]!=set[q->adjvex])　　{//判斷兩點(diǎn)是否在同一集合,若不在，則輸出這條邊　　printf("(%c,%c) %d\n",G.vertices[j].data,G.vertices[q->adjvex].data,

86、q->weight);　　k++;　　/*int s2=set[j];*/　　for(i=1;i<=G.vexnum;i++)　　if(set[i]==set[j]/*s2*/)

87、　set[i]=set[q->adjvex];　　}　　min = INFINITY; //將min置為最大值　　}　　return OK;<

88、b>　　}　　13.求頂點(diǎn)在圖中位置LocateVex(MGraph G,VertexType u)，LocateVexG(ALGraph G,vertexType e)　　Status LocateVex(MGraph G,VertexType u)　　{ int

89、i;　　for(i=1;i<=G.vexnum;++i)　　if(G.vexs[i]==u)　　return i;　　return -1;　　}&l

90、t;/b>　　Status LocateVexG(ALGraph G,vertexType e)　　{ for(int i=1;i<=G.vexnum;i++)　　{　　if(G.vertices[i].data==e)

91、　　return i;　　}　　return -1;　　}　　14.主函數(shù)main()　　int mai

92、n()　　{ ALGraph A;　　MGraph G;　　AdjMatrix S;　　int n,v;　　VertexType u;</p&g

93、t;　　printf("用圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)建無(wú)向網(wǎng):\n");　　CreateUDN(G,S);　　printf("輸出鄰接矩陣：\n");　　Display(G,S);　　printf("用圖的

94、鄰接表存儲(chǔ)結(jié)構(gòu)建無(wú)向網(wǎng)：\n");　　CreateALGraph(A);　　printf("輸出鄰接表：\n");　　DisplayG(A);printf("\n");　　printf("輸入圖的結(jié)點(diǎn)個(gè)數(shù)以及訪問(wèn)

95、的起始結(jié)點(diǎn)的位序(格式如：2,1)：\n");　　scanf("%d,%d",&n,&v);　　printf("對(duì)圖進(jìn)行深度優(yōu)先遍歷（鄰接矩陣）：\n");　　DFS1(G,n,v);　　printf(&q

96、uot;\n");　　printf("對(duì)圖進(jìn)行深度優(yōu)先遍歷（鄰接表）：\n");　　DFS2(A,v);　　printf("\n");　　printf("對(duì)圖進(jìn)行廣度優(yōu)先遍歷（鄰接表）：\n");<

97、;/p>　　BFS(A,v);　　printf("\n");　　printf("利用PRIM算法求最小生成樹\n");　　u=G.vexs[1];　　MiniSpan

98、Tree_PRIM(G,S,u);　　printf("利用Kruskal算法求最小生成樹\n");　　Kruskal(A);　　printf("\n");　　return OK;<b&

99、gt;　　}　　3.3 程序中需說(shuō)明的地方，如用到的宏及代表的意義　　#define OK 1　　#define ERROR 0　　#define INFINITY 88 //最大值（表示無(wú)窮大）　　#defi

100、ne MAX_VERTEX_NUM 20 //最大頂點(diǎn)個(gè)數(shù)　　#define MAX_INFO 20　　#define MAX_NAME 5　　typedef int Status; 　　typedef char VertexType;<p&

101、gt;　　typedef int VRType;　　typedef char vertexType;　　typedef char InfoType;　　typedef enum{DG,DN,UDG,UDN}GraphKind; //{有向圖,有向網(wǎng),無(wú)向圖,無(wú)向網(wǎng)}

102、typedef int TElemType;　　4. 結(jié)果與結(jié)論　　4.1測(cè)試數(shù)據(jù)及測(cè)試結(jié)果　　1.程序運(yùn)行開始界面：　　2.測(cè)試錄入頂點(diǎn)信息以及邊的信息，錄入數(shù)據(jù)及錄入結(jié)果如下：　　3.測(cè)試

103、輸出鄰接矩陣的函數(shù)　　4．測(cè)試基于鄰接表構(gòu)造圖函數(shù)　　5. 測(cè)試輸出鄰接表的函數(shù)　　6. 測(cè)試基于鄰接矩陣對(duì)圖進(jìn)行深度優(yōu)先遍歷的函數(shù)　　7.測(cè)試基于鄰接表對(duì)圖進(jìn)行廣度優(yōu)先遍歷的函數(shù)　　8.測(cè)試Prim算法求最小生成樹的函數(shù)<

104、/p>　　9.測(cè)試Kruskal算法求最小生成樹的函數(shù)　　4.2實(shí)驗(yàn)結(jié)論　　通過(guò)以上程序演示的結(jié)果，其測(cè)試功能包含本次課程設(shè)計(jì)所要求的圖的主要功能，包括對(duì)圖的深度遍歷、廣度遍歷、Prim求最小生成樹、Kruskal求最小生成樹等功能。　　數(shù)據(jù)結(jié)構(gòu)的

105、構(gòu)造及初始化無(wú)誤，能夠滿足對(duì)圖的遍歷和最小生成樹求解的要求。　　錄入數(shù)據(jù)能夠驗(yàn)證其效果。　　鄰接矩陣的建立，結(jié)果中鄰接矩陣的輸出結(jié)果能驗(yàn)證其效果。　　鄰接表的建立，結(jié)果中鄰接表的輸出結(jié)果能驗(yàn)證其效果。。　　基于鄰接矩陣對(duì)圖的深度優(yōu)先遍歷，可以有預(yù)期的結(jié)果

106、;　　基于鄰接表對(duì)圖的廣度優(yōu)先遍歷，可以有預(yù)期的結(jié)果。　　Prim算法求得最小生成樹，可以有預(yù)期的結(jié)果。　　Kruskal算法求得最小生成樹，可以有預(yù)期的結(jié)果。　　至此，本課程設(shè)計(jì)所提出的設(shè)計(jì)方法均得到有效的驗(yàn)證及證實(shí)，各個(gè)功能均能完成其設(shè)計(jì)需要，各部分功能之間能夠相互協(xié)調(diào)印證，整個(gè)設(shè)計(jì)的結(jié)

107、果與預(yù)期相符。　　但是，還存在需要改進(jìn)的地方，課程要求是隨機(jī)生成一個(gè)無(wú)向連通圖，而此程序是先人為構(gòu)建一個(gè)無(wú)向連通圖，然后對(duì)圖進(jìn)行遍歷和生成樹求解。對(duì)于隨機(jī)生成無(wú)向連通圖，已有還不夠成熟的算法，由于時(shí)間有限，以后會(huì)對(duì)程序進(jìn)行改進(jìn)，已完成題目的要求。　　收獲與致謝 　　本次實(shí)驗(yàn)主

108、要用到了數(shù)據(jù)結(jié)構(gòu)中圖以及隊(duì)列的相關(guān)知識(shí)，使我對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程有了更加深入的學(xué)習(xí)和運(yùn)用，另外，在運(yùn)用數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問(wèn)題的編程能力方面有了很大的提高，對(duì)于數(shù)據(jù)結(jié)構(gòu)的相關(guān)算法思想有了更深層次的理解，對(duì)于C語(yǔ)言程序設(shè)計(jì)的運(yùn)用有了進(jìn)一步第的鞏固和提高。在對(duì)于編寫程序的上下連貫性有了進(jìn)一步的提高。與此同時(shí)，編寫程序會(huì)出現(xiàn)很多錯(cuò)誤，對(duì)于調(diào)試程序，也使我進(jìn)一步了解了算法，培養(yǎng)了編程思想。　　本次實(shí)驗(yàn)中，由于

109、變量及相關(guān)的功能函數(shù)比較多，需要全面考慮問(wèn)題，使我對(duì)問(wèn)題的分析能力有了很大的幫助，通過(guò)對(duì)程序的編程和測(cè)試，使我對(duì)于程序設(shè)計(jì)的周全思維提高很多。　　誠(chéng)然，我的多方面的提高，離不開老師的幫助，在此，我真誠(chéng)地向指導(dǎo)教師閆老師表示真心的感謝！　　6. 參考文獻(xiàn)　　[1] 嚴(yán)蔚敏，吳偉

眾賞文庫(kù)> 全部分類> 畢業(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ù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
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ù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-- 圖的遍歷和生成樹求解

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-- 圖的遍歷和生成樹求解

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載