數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-最小生成樹

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

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

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

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

文檔簡(jiǎn)介

1、　　目錄　　一、設(shè)計(jì)目的……………………………………………………………….-2-　　二、算法思想分析………………………………………………………-2-　　1.算法思想………………………………………………………………..-3-<

2、p>　　1）普里姆（Prim）算法思想……………………………………………………….-3-　　2）克魯斯卡爾（Kruskal）算法思想..........................................-3-　　2.系統(tǒng)采用的數(shù)據(jù)結(jié)構(gòu)和算法………………………………-3-　　三、算法的描述與實(shí)

3、現(xiàn)……………………………………………….-4-　　四、用戶手冊(cè)………………………………………………………………-7-　　五、總結(jié)…………………………………………………………………….-10-　　六、參考文獻(xiàn)…………………………………………………………….-10-　　七、附

4、錄（源代碼）………………………………………………...-10-　　[摘要] 選擇一顆生成樹，使之總的消費(fèi)最少，也就是要構(gòu)造連通網(wǎng)的最小代價(jià)生成樹（簡(jiǎn)稱為最小生成樹）的問題，一顆生成樹的代價(jià)就是樹上各邊的代價(jià)之和，構(gòu)造最小生成樹可以有多種算法，其中多數(shù)算法利用了MST的性質(zhì)。　　關(guān)鍵詞：最小生成樹連通圖普里姆算法克魯斯卡爾算法 MST</p&g

5、t;　　設(shè)計(jì)目的　　了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；　　初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；　　提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力；&l

6、t;p>　　訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。　　算法思想分析　　該設(shè)計(jì)的要求是在n個(gè)城市之間建設(shè)網(wǎng)絡(luò)，不僅要保證連通，還要求是最經(jīng)濟(jì)的架設(shè)方法。根據(jù)克魯斯卡爾和普里姆算法的不同之處，該程序?qū)⒊鞘袀€(gè)數(shù)大于十個(gè)時(shí)應(yīng)用普里姆算法求最小生成樹，而城市個(gè)數(shù)小于

7、十個(gè)時(shí)則應(yīng)用克魯斯卡爾進(jìn)行計(jì)算。　　算法思想　　普里姆（Prim）算法思想　　選擇從0節(jié)點(diǎn)開始，并選擇0節(jié)點(diǎn)相關(guān)聯(lián)的最小權(quán)值邊，將與這條邊相關(guān)聯(lián)的另一頂點(diǎn)出列；　　在出列的節(jié)點(diǎn)中相關(guān)聯(lián)的所有邊中選擇一條不與另一個(gè)已出列的節(jié)點(diǎn)相關(guān)聯(lián)的權(quán)

8、值最小的邊，并將該邊相關(guān)聯(lián)的節(jié)點(diǎn)出列；　　重復(fù)b)直到所有的節(jié)點(diǎn)出列。　　克魯斯卡爾（Kruskal）算法思想　　為了使生成樹上總的權(quán)值之和最小，應(yīng)該使每一條邊上的權(quán)值盡可能的小，所以應(yīng)從權(quán)值最小的邊選起，直至選出n-1條不能構(gòu)成回路的權(quán)值最小的邊位置。　　具體做法如下：

9、首先構(gòu)造一個(gè)含n個(gè)頂點(diǎn)的森林，然后按權(quán)值從小到大從連通圖中選擇不使森林中產(chǎn)生回路的邊加入到森林中去，直至該森林變成一棵樹為止，這棵樹便是連通圖的最小生成樹。　　由于生成樹上不允許有回路，因此并非每一條居當(dāng)前最小的邊都可選。從生成樹的構(gòu)造過程可見，初始態(tài)為n個(gè)頂點(diǎn)分屬n棵樹，互不連通，每加入一條邊，就將兩棵樹合并為一棵樹，在同一棵樹上的兩個(gè)頂點(diǎn)之間自然相連通，由此判別當(dāng)前權(quán)值最小邊是否可取只要判別

10、它的兩個(gè)頂點(diǎn)是否在同一棵樹上即可。　　系統(tǒng)采用的數(shù)據(jù)結(jié)構(gòu)和算法　　數(shù)據(jù)結(jié)構(gòu)　　Typedef int Vertextype;　　Typedef int adimatrix[MaxVertexNum][MaxVertexNum];<

11、;/p>　　Typedef int Vertextype vexlist[MaxVertexNum];　　Typedef int VexType;　　Typedef int AdjType;　　Typedef struct edgeElem edgeset[MaxVertexNum];

12、　　struct edgeElem　　{int fromvex;//頭頂點(diǎn)　　int endvex;//尾頂點(diǎn)　　int weight;//權(quán)　　};

13、　　Typedef struct　　{int n;//圖的頂點(diǎn)個(gè)數(shù)　　AdjType acrs[MAXVEX][MAXVEX];//邊信息　　}GraphMatrix;　　Typedef struct　　{int start_ve

14、x,stop_vex;//邊的起點(diǎn)和終點(diǎn)　　AdjType weight;//邊的權(quán)　　}Edge;　　Edge mst[5];　　算法　　Great_a

15、djmatrix();　　Great_adjmatrix2();　　Kruskal();　　out_edgeaet();　　prim();　　算法的描述與實(shí)現(xiàn)</b&g

16、t;　　Great_adjmatrix()和Great_adjmatrix2()是兩種建立圖的方法；　　克魯斯卡爾算法（Kruskal）：　　Void kruskal(GraphMatrix * pgraph,Edge mst[])　　{int i,j,min,vx,vy

17、;　　int weight,minweight;　　Edge edge;　　for(i=0;i<pgraph->n-1;i++)　　{mst[i].start_vex = 0;　　Mst[i].stop_vex = i

18、+1;　　Mst[i].weight = pgraph->arcs[0][i+1];　　}　　for(i=0;i<pgraph->n-1;i++)//共n-1條邊　　{minweight = MAX;</p&g

19、t;　　min = i;　　for(j=i;j<pgraph->n-1;j++)　　//從所有（vx,vy）（vx∈U,vy∈V-U）中選出最短的邊　　if(mst[j].weight<minweight)&l

20、t;p>　　{minweight = mst[j].weight;　　min = j;　　}　　//mst[min]是最短的邊(vx,vy)(vx∈U,vy∈V-U),將mst[min]加入最小生成樹<

21、p>　　edge = mst[min];　　mst[min] = mst[i];　　mst[i] = edge;　　vx = mst[i].stop_vex;//vx為剛加入最小生成樹的頂點(diǎn)的下標(biāo)　　for(j=i+1;j<pgraph->n-1;j++

22、)　　{vy=mst[j].stop_vex;weight=pgraph->arcs[vx][vy];　　if(weight<mst[j].weight)　　{mst[j].weight=weight;　　mst[j].start_vex = vx;</

23、p>　　}　　}　　}　　}　　普里姆算法（Prim）：<p&

24、gt;　　void prim(adjmatrix GA,edgeset MST,int n)　　//利用prim算法從0點(diǎn)出發(fā)求圖的最小生成樹　　｛int i,j,t,k,w,min,m;　　struct edgeElem x;　　for(i=0;i<n;i++)&

25、lt;/p>　　if(i>0) //從0點(diǎn)連接其余頂點(diǎn)　?。鸐ST[i-1].fromvex=0;　　MST[i-1].endvex=i;　　MST[i-1].weight=GA[0][i];　　}

26、　　for(k=1;k<n;k++)　　{min=MaxValue;　　m=k-1;　　for(j=k-1;j<n-1;j++)　　if(MST[j].weight<min)

27、　　{min=MST[j].weight;　　M=j;　　}//選擇從0點(diǎn)出發(fā)權(quán)值最小的邊　　x=MST[k-1];MST[k-1]=MST[m];MST[m]=x;//交換位置　　j=MST

28、[k-1].endvex;//定位于權(quán)值最小邊的尾頂點(diǎn)　　for(i=k;i<n-1;i++)//選取輕邊　　{t=MST[i].endvex;　　w=GA[j][t];　　if(w<MST[i].weight)　　{

29、MST[i].weight=w;　　MST[i].fromvex=j;　　}　　}　　}　　}&l

30、t;/b>　　out_edgeset()功能為顯示最小生成樹。　　用戶手冊(cè)　　1.運(yùn)行程序，得到如下窗口：　　2.輸入頂點(diǎn)數(shù)，選擇算法：　　1）當(dāng)輸入的頂點(diǎn)數(shù)小于10時(shí)，選擇Kruska

31、l算法，如下圖　　2）當(dāng)輸入的頂點(diǎn)數(shù)大于10時(shí)，選擇Prim算法，如下圖　　五、總結(jié)　　該程序?qū)崿F(xiàn)了在n個(gè)城市之間建設(shè)網(wǎng)絡(luò)，既保證了連通性，也成為了最經(jīng)濟(jì)的架設(shè)方法。程序中應(yīng)用了普里姆算法和克魯斯卡爾算法，實(shí)現(xiàn)了矩陣的輸出以及最小生成樹的輸出。不過，該程序仍有不足之處，圖的輸

32、入數(shù)據(jù)過大，易出錯(cuò)，不易返回，仍需完善。　　六、參考文獻(xiàn)　　[1] 《數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)題典》李春葆編清華大學(xué)出版社　　[2] 《數(shù)據(jù)結(jié)構(gòu)（C語言版）》嚴(yán)蔚敏吳偉民編清華大學(xué)出版社　　[3] 《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》蘇仕華編機(jī)

33、械工業(yè)出版社　　七、附錄：（源代碼）　　#include<stdio.h>　　#include<stdlib.h>　　#define MaxVertexNum 12　　#define MaxEdgeN

34、um 20　　#define MaxValue 1000　　#define MAXVEX 6　　#define MAX 1e+8　　typedef int Vertextype;　　typedef int adjmatrix[Ma

35、xVertexNum][MaxVertexNum];　　typedef Vertextype vexlist[MaxVertexNum];　　typedef int VexType;　　typedef int AdjType;　　typedef struct edgeEl

36、em edgeset[MaxVertexNum]; 　　struct edgeElem　　{int fromvex;//頭頂點(diǎn)　　int endvex;//尾頂點(diǎn)　　int weight;//權(quán)　　};</

37、b>　　typedef struct {　　int n; /* 圖的頂點(diǎn)個(gè)數(shù) */　　/*VexType vexs[MAXVEX]; 頂點(diǎn)信息 */　　AdjType arcs[MAXVEX][MAX

38、VEX]; /* 邊信息 */　　} GraphMatrix;　　typedef struct{　　int start_vex, stop_vex; /* 邊的起點(diǎn)和終點(diǎn) */　　AdjType weight; /* 邊的

39、權(quán) */　　} Edge;Edge mst[5];　　void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e)　　{ int i,j,k,w;　　printf("輸入%d個(gè)頂點(diǎn)序號(hào)(0--n-1)：

40、",n);　　for(i=0;i<n;i++) //建立頂點(diǎn)表　　scanf("%d",&GV[i]);//讀入頂點(diǎn)信息　　for(i=0;i<n;i++)//建立邊表　　for(j=0;j<n;j++)//初始化邊

41、表　　if(i==j) GA[i][j]=0;　　else GA[i][j]=MaxValue;　　printf("輸入%d條無向帶權(quán)邊（序號(hào) 序號(hào) 權(quán)值）：\n",e);　　for(k=0;k<e;k++)//設(shè)置邊表&

42、lt;p>　　{ scanf("%d%d%d",&i,&j,&w);　　GA[i][j]=GA[j][i]=w;//對(duì)稱　　}　　}　　vo

43、id Creat_adjmatrix2(vexlist GV,adjmatrix GA,int m,int e,GraphMatrix &graph)　　{ int i,j,k,w,x,y;　　printf("輸入%d個(gè)頂點(diǎn)序號(hào)(0-m-1)，序號(hào)從0開始。",m);　　for(

44、i=0;i<m;i++) //建立頂點(diǎn)表　　{scanf("%d",&GV[i]);//讀入頂點(diǎn)信息　　if(GV[i]>=m) 　　{ printf("您輸入的序號(hào)有誤，請(qǐng)輸入0到%d-1之間的數(shù)，請(qǐng)重新輸入。\n",m);&l

45、t;p>　　scanf("%d",&GV[i]);}　　}　　for(i=0;i<m;i++)//建立邊表　　for(j=0;j<m;j++)//初始化邊表　　GA[i][j]=MaxVa

46、lue;　　printf("請(qǐng)輸入有多少條邊。\n");　　scanf("%d",&e);　　printf("輸入%d條無向帶權(quán)邊（序號(hào) 序號(hào) 權(quán)值）：\n",e);　　for(k=0;k<e;k+

47、+)//設(shè)置邊表　　{ scanf("%d%d%d",&i,&j,&w);　　GA[i][j]=GA[j][i]=w;//對(duì)稱　　}　　printf("您輸入的圖的存貯為下面表，

48、如果不可達(dá)則用1000表示。\n");　　graph.n =m;　　for(x=0;x<m;x++)　　{for(y=0;y<m;y++) {　　graph.arcs[x][y]=GA[x][y];　　pri

49、ntf("%-4d ",graph.arcs[x][y]);}　　printf("\n");　　}　　}　　void kruskal(GraphMatri

50、x * pgraph, Edge mst[]) {　　int i, j, min, vx, vy; 　　int weight, minweight; Edge edge;　　for (i = 0; i < pgraph->n-1; i++) {　　mst[i]

51、.start_vex = 0;　　mst[i].stop_vex = i+1;　　mst[i].weight = pgraph->arcs[0][i+1];　　}　　for (i = 0; i < pgraph->n

52、-1; i++) { /* 共n-1條邊 */　　minweight = MAX; min = i;　　for (j = i; j < pgraph->n-1; j++)/* 從所有邊(vx,vy)(vx∈U,vy∈V-U)中選出最短的邊 */　　if(mst[j].we

53、ight < minweight) {　　minweight = mst[j].weight; 　　min = j;　　}　　/* mst[min]是最短的邊(vx,vy)(vx∈U, vy

54、∈V-U)，將mst[min]加入最小生成樹 */　　edge = mst[min]; 　　mst[min] = mst[i]; 　　mst[i] = edge;　　vx = mst[i].stop_vex; /* vx為剛加入最小生成樹的頂點(diǎn)

55、的下標(biāo) */　　for(j = i+1; j < pgraph->n-1; j++) { /* 調(diào)整mst[i+1]到mst[n-1] */　　vy=mst[j].stop_vex; weight = pgraph->arcs[vx][vy];　　if (weight < mst[j].w

56、eight) {　　mst[j].weight = weight; 　　mst[j].start_vex = vx;　　}　　}　　}

57、　　}　　void out_edgeset(edgeset MST,int e)//顯示最小生成樹　　{ int k;　　printf("最小的消耗路線為\n");

58、　　for(k=0;k<e;k++)　　printf("(%d %d %d)\n",MST[k].fromvex,MST[k].endvex,MST[k].weight);　　}　　void prim(adjmatrix GA,ed

59、geset MST,int n)//利用prim算法從0點(diǎn)出發(fā)求圖的最小生成樹　　{ int i,j,t,k,w,min,m;　　struct edgeElem x;　　for(i=0;i<n;i++)　　if(i>0)//從0點(diǎn)連接其余頂點(diǎn)</p

60、>　　{ MST[i-1].fromvex=0;　　MST[i-1].endvex=i;　　MST[i-1].weight=GA[0][i];　　}　　for(k=1;k<n;k++)<

61、/p>　　{ min=MaxValue;　　m=k-1;　　for(j=k-1;j<n-1;j++)　　if(MST[j].weight<min) {min=MST[j].weight;m=j;}//選擇從0點(diǎn)出發(fā)權(quán)值最小

62、的邊　　x=MST[k-1];MST[k-1]=MST[m];MST[m]=x;//交換位置　　j=MST[k-1].endvex;//定位于權(quán)值最小邊的尾頂點(diǎn)　　for(i=k;i<n-1;i++)//選取輕邊　　{ t=MST[i].endvex;w=GA

63、[j][t];　　if(w<MST[i].weight)　　{ MST[i].weight=w;　　MST[i].fromvex=j;　　}　　}</b&g

64、t;　　}　　} 　　void main()　　{　　int n,e,i;

65、;　　int a;　　system("color 71");//改變屏幕顏色　　printf(" ┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");　　printf(" ┃㊣

66、必做題：最小生成樹㊣┃\n");　　printf(" ┃ 姓名：xxxx ┃\n");　　printf(" ┃ 學(xué)號(hào)：xxxxxxxxx

67、 ┃\n");　　printf(" ┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");　　vexlist GV;//頂點(diǎn)表　　adjmatrix GA;//邊表　　edgeset

68、 MST;//最小生成樹　　do{　　printf("輸入圖的頂點(diǎn)數(shù)n，我們將根據(jù)您輸入的數(shù)據(jù)大小選擇合適的算法。\n");　　scanf("%d",&n);　　if(n>=10)

69、//大于10用prim算法來實(shí)現(xiàn)，否則kruskal算法來實(shí)現(xiàn)　　{　　printf("用prim算法從0點(diǎn)出發(fā)求圖的最小生成樹為：\n");　　printf("請(qǐng)輸入圖的邊數(shù)。\n");　　c

70、anf("%d",&e);　　Creat_adjmatrix( GV, GA, n, e);//創(chuàng)建圖　　prim(GA,MST,n);//生成最小生成樹　　out_edgeset( MST, n-1);//輸出最小生成樹

71、}　　else{　　printf("用kcuskal算法的最小生成樹為：\n");　　GraphMatrix graph;//定義一個(gè)結(jié)構(gòu)體來表示存儲(chǔ)結(jié)構(gòu)　　Creat_adjmatrix2(G

72、V,GA,n,e,graph);//創(chuàng)建圖　　kruskal(&graph,mst);//生成最小生成樹　　rintf("最小的消耗路線為\n");　　for (i = 0; i < graph.n-1; i++)　　printf(&qu

73、ot;(%d %d %d)\n", mst[i].start_vex,　　mst[i].stop_vex, mst[i].weight);//輸出最小生成樹　　}　　printf("謝謝使用！\n");

74、　printf("繼續(xù)？輸入1繼續(xù)，輸入0退出。\n");//方便用戶重復(fù)使用　　scanf("%d",&a); 　　getchar();　　system("cls");//清屏語句 　　}while(a

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

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝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)下載