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

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告---最小生成樹問題_第1頁

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

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

文檔簡介

1、　　二 ○ 一○ 屆課程設(shè) 計論文　　《算法與數(shù)據(jù)結(jié)構(gòu)》　　二〇一〇年六月　　目錄　　一、引言 …………………………………………

2、　　二、設(shè)計目的與任務(wù)………………………………　　1·課程設(shè)計的目的　　2·課程設(shè)計的任務(wù)　　三、設(shè)計方案………………………………………

3、;　　1·需求分析　　2·概要設(shè)計　　3·詳細(xì)設(shè)計　　4·程序清單　　四、調(diào)試分

4、析………………………………………　　五、測試結(jié)果………………………………………　　六、附錄……………………………………………　　七、工作環(huán)境………………………………………　　八、參考文獻……………………………　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)

5、計　　——最小生成樹問題　　一、引言　　《數(shù)據(jù)結(jié)構(gòu)》是計算機科學(xué)與技術(shù)專業(yè)和信息系統(tǒng)專業(yè)的必修課之一，是一門綜合的專業(yè)技術(shù)課。本課程較系統(tǒng)的介紹了軟件開發(fā)過程中常用的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)的實現(xiàn)算法。如線性表、棧、隊列、樹和二叉樹，圖、檢索和排列

6、等，并對性能進行分析和比較，內(nèi)容非常豐富。　　本課程設(shè)計我們要解決的是最小生成樹問題。要用到圖的相關(guān)數(shù)據(jù)結(jié)構(gòu)和最小生成樹的克魯斯卡爾算法，以及存儲圖的邊和點的鄰接矩陣。　　本課程設(shè)計要解決的問題是構(gòu)造連通圖的最小生成樹我們首先要做的是都造一個鄰接表，用以存儲圖，然后我們要想好怎樣利用克魯斯卡爾算法構(gòu)造最小生成樹，把這個算法寫入主程序，調(diào)試好程序，最后完成

7、報告。　　二、設(shè)計目的與任務(wù)　　1·課程設(shè)計的目的　　本課程設(shè)計是為了了解并掌握數(shù)據(jù)結(jié)構(gòu)及算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；初步掌握軟件開發(fā)過程的相關(guān)步驟；提高運用所學(xué)理論知識獨立分析和解決問題的能力；訓(xùn)練用系統(tǒng)的觀

8、點和軟件開發(fā)的一般規(guī)范進行軟件開發(fā)。　　2·課程設(shè)計的任務(wù)　　問題描述：若要在n個城市之間建設(shè)通信網(wǎng)絡(luò)，只需架設(shè)n—1條線路即可。如何以最低的經(jīng)濟代價建設(shè)這個通信網(wǎng)，是一個最小生成樹的問題。　　三、設(shè)計方案

9、　　1·需求分析　　利用克魯斯卡爾算法求最小生成樹；　　實現(xiàn)教科書6.5節(jié)中抽象數(shù)據(jù)類型MFSet。以此表示構(gòu)造生成樹過程中的連通分量。　　以文本形式輸出生成樹中各條邊以及它們的權(quán)值。

10、　2·概要設(shè)計　　抽象數(shù)據(jù)類型（ADT）如下：　　ADT GRAPH{　　數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，成為頂點集。　　數(shù)據(jù)關(guān)系R：<b&g

11、t;　　R={VR}　　VR={<v,w>|v,w∈V且P(v,w),<v,w>表示從v到w的弧，　　謂詞P（v，w）定義了弧<v,w>的意義或信息　　基本操作P：　　Creat

12、eGraph(&G,V,VR)　　初始條件：v是圖的頂點集，VR是圖中弧的集合。　　操作結(jié)果：按V和VR的定義構(gòu)造圖G。　　DestroyGraph(&G)　　初始條件：圖G存在。　　操作結(jié)果：銷毀圖G </

13、p>　　LocateVex(G,u)　　初始條件：圖G存在，u和G中定點有相同特征。　　操作結(jié)果：若圖G中存在頂點u，則返回頂點在圖中的位置；否則返回其他信息。　　GetVex(G,v)　　初始條件：圖G存在，v是G中某個頂點。</p&g

14、t;　　操作結(jié)果：返回v的值。　　PutVex(&G,v,value)...　　初始條件：圖G存在。　　操作結(jié)果：對v賦值value。　　}

15、存儲結(jié)構(gòu)　　typedef struct　　{　　int begin;　　int end;　　int weight;

16、;　　}edge;　　typedef struct　　{　　int adj;　　int weight;<p

17、>　　}AdjMatrix[MAX][MAX];　　typedef struct　　{　　AdjMatrix arc;　　int vexnum, arcnum;　　}M

18、Graph;　　流程圖　　3·詳細(xì)設(shè)計　　在該函數(shù)中主要有6段代碼塊，分別是圖的構(gòu)建代碼，對權(quán)值排序的代碼，交換權(quán)值代碼，最小生成樹代碼，找尾代碼，主函數(shù)代碼。6段代碼分別實現(xiàn)不同的功能，共同滿足了課題所需要

19、實現(xiàn)的功能。　　主函數(shù)代碼　　int main(void)//主函數(shù)　　{　　MGraph *G;　　G = (MGraph*)malloc(sizeof

20、(MGraph));　　if (G == NULL)　　{　　printf("memory allcation failed,goodbye");　　exit(1);</

21、p>　　}　　CreatGraph(G);　　MiniSpanTree(G);　　system("pause");　　return 0;</p

22、>　　}　　圖的構(gòu)建代碼　　void CreatGraph(MGraph *G)//構(gòu)件圖　　{　　int i, j,n, m;&

23、lt;/p>　　printf("請輸入邊數(shù)和頂點數(shù):");　　scanf("%d %d",&G->arcnum,&G->vexnum);　　for (i = 1; i <= G->vexnum; i++)//初始化圖<

24、p>　　{　　for ( j = 1; j <= G->vexnum; j++)　　{　　G->arc[i][j].adj = G->arc[j][i].adj = 0;<p&g

25、t;　　}　　}　　for ( i = 1; i <= G->arcnum; i++)//輸入邊和權(quán)值　　{　　printf("\n請輸

26、入有邊的2個頂點");　　scanf("%d %d",&n,&m);　　while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum)　　{<

27、;/p>　　printf("輸入的數(shù)字不符合要求請重新輸入:");　　scanf("%d%d",&n,&m);　　}　　G->arc[n][m].adj = G->arc[m][

28、n].adj = 1;　　getchar();　　printf("\n請輸入%d與%d之間的權(quán)值:", n, m);　　scanf("%d",&G->arc[n][m].weight);　　}<

29、/b>　　printf("鄰接矩陣為:\n");　　for ( i = 1; i <= G->vexnum; i++)　　{　　for ( j = 1; j <= G->vexnum;

30、 j++)　　{　　printf("%d ",G->arc[i][j].adj);　　}　　printf("\n");<

31、p>　　}　　}　　對權(quán)值排序的代碼　　void sort(edge edges[],MGraph *G)//對權(quán)值進行排序　　{&l

32、t;/b>　　int i, j;　　for ( i = 1; i < G->arcnum; i++)　　{　　for ( j = i + 1; j <= G->arc

33、num; j++)　　{　　if (edges[i].weight > edges[j].weight)　　{　　Swapn(edges, i, j);<p&g

34、t;　　}　　}　　}　　printf("權(quán)排序之后的為:\n");　　for (i = 1; i < G->arcnum;

35、i++)　　{　　printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);　　}</p&g

36、t;　　}　　交換權(quán)值代碼　　void Swapn(edge *edges,int i, int j)//交換權(quán)值以及頭和尾　　{&l

37、t;b>　　int temp;　　temp = edges[i].begin;　　edges[i].begin = edges[j].begin;　　edges[j].begin = temp;　　temp = edges[i].end;<

38、/p>　　edges[i].end = edges[j].end;　　edges[j].end = temp;　　temp = edges[i].weight;　　edges[i].weight = edges[j].weight;　　edge

39、s[j].weight = temp;　　}　　最小生成樹代碼　　void MiniSpanTree(MGraph *G)//生成最小生成樹　　{</p

40、>　　int i, j, n, m;　　int k = 1;　　int parent[M];　　edge edges[M];　　for ( i = 1; i < G->vexnum; i++)

41、;　　{　　for (j = i + 1; j <= G->vexnum; j++)　　{　　if (G->arc[i][j].adj == 1)　　{<

42、/b>　　edges[k].begin = i;　　edges[k].end = j;　　edges[k].weight = G->arc[i][j].weight;　　k++;&

43、lt;b>　　}　　}　　}　　sort(edges, G);　　for (i = 1; i <= G->arcnum; i++)&l

44、t;p>　　{　　parent[i] = 0;　　}　　printf("最小生成樹為:\n");　　for (i = 1; i <= G->arcnum; i

45、++)//核心部分　　{　　n = Find(parent, edges[i].begin);　　m = Find(parent, edges[i].end);　　if (n != m)<

46、;b>　　{　　parent[n] = m;　　printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);　　}

47、;　　}　　}　　6）找尾代碼　　int Find(int *parent, int f)//找尾

48、　　{　　while ( parent[f] > 0)　　{　　f = parent[f];　　}　　retu

49、rn f;　　}　　4·程序清單　　/*Name:最小生成樹kruskal算法　　Author:Song Changzhi

50、　Description:生成最小生成樹 　　Date: 2010-06-15 20:07　　Copyright:Song Changzhi　　*/　　#include<stdio.h><p&

51、gt;　　#include<stdlib.h>　　#define M 20　　#define MAX 20　　typedef struct　　{　　int begin;</p

52、>　　int end;　　int weight;　　}edge;　　typedef struct　　{&l

53、t;p>　　int adj;　　int weight;　　}AdjMatrix[MAX][MAX];　　typedef struct　　{　　Adj

54、Matrix arc;　　int vexnum, arcnum;　　}MGraph;　　void CreatGraph(MGraph *);//函數(shù)申明　　void sort(edge* ,MGraph *);

55、　　void MiniSpanTree(MGraph *);　　int Find(int *, int );　　void Swapn(edge *, int, int);　　void CreatGraph(MGraph *G)//構(gòu)件圖

56、;　　{　　int i, j,n, m;　　printf("請輸入邊數(shù)和頂點數(shù):");　　scanf("%d %d",&G->arcnum,&G->vexnum);　　for (i =

57、 1; i <= G->vexnum; i++)//初始化圖　　{　　for ( j = 1; j <= G->vexnum; j++)　　{　　G->arc[i][

58、j].adj = G->arc[j][i].adj = 0;　　}　　}　　for ( i = 1; i <= G->arcnum; i++)//輸入邊和權(quán)值

59、　{　　printf("\n請輸入有邊的2個頂點");　　scanf("%d %d",&n,&m);　　while(n < 0 || n > G->vexnum || m < 0 || n > G->v

60、exnum)　　{　　printf("輸入的數(shù)字不符合要求請重新輸入:");　　scanf("%d%d",&n,&m);　　}</p

61、>　　G->arc[n][m].adj = G->arc[m][n].adj = 1;　　getchar();　　printf("\n請輸入%d與%d之間的權(quán)值:", n, m);　　scanf("%d",&G->arc

62、[n][m].weight);　　}　　printf("鄰接矩陣為:\n");　　for ( i = 1; i <= G->vexnum; i++)　　{</

63、p>　　for ( j = 1; j <= G->vexnum; j++)　　{　　printf("%d ",G->arc[i][j].adj);　　}

64、　　printf("\n");　　}　　}　　void sort(edge edges[],MGraph *G)//對權(quán)值進行排序　　{

65、　　int i, j;　　for ( i = 1; i < G->arcnum; i++)　　{　　for ( j = i + 1; j <= G->a

66、rcnum; j++)　　{　　if (edges[i].weight > edges[j].weight)　　{　　Swapn(edges, i, j);<p

67、>　　}　　}　　}　　printf("權(quán)排序之后的為:\n");　　for (i = 1; i < G->arcnum

68、; i++)　　{　　printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);　　}</p

69、>　　}　　void Swapn(edge *edges,int i, int j)//交換權(quán)值以及頭和尾　　{　　int temp;<p&

70、gt;　　temp = edges[i].begin;　　edges[i].begin = edges[j].begin;　　edges[j].begin = temp;　　temp = edges[i].end;　　edges[i].end = edges[j].end

71、;　　edges[j].end = temp;　　temp = edges[i].weight;　　edges[i].weight = edges[j].weight;　　edges[j].weight = temp;<b&

72、gt;　　}　　void MiniSpanTree(MGraph *G)//生成最小生成樹　　{　　int i, j, n, m;　　int k = 1;　　int par

73、ent[M];　　edge edges[M];　　for ( i = 1; i < G->vexnum; i++)　　{　　for (j = i + 1; j <= G->vexnum; j++)</p&

74、gt;　　{　　if (G->arc[i][j].adj == 1)　　{　　edges[k].begin = i;　　edges[k].end = j;</p&

75、gt;　　edges[k].weight = G->arc[i][j].weight;　　k++;　　}　　}

76、　}　　sort(edges, G);　　for (i = 1; i <= G->arcnum; i++)　　{　　parent[i] = 0;

77、;　　}　　printf("最小生成樹為:\n");　　for (i = 1; i <= G->arcnum; i++)//核心部分　　{　　n = Find(parent, edg

78、es[i].begin);　　m = Find(parent, edges[i].end);　　if (n != m)　　{　　parent[n] = m;　　printf("<

79、;< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);　　}　　}　　}</p&g

80、t;　　int Find(int *parent, int f)//找尾　　{　　while ( parent[f] > 0)　　{　　f = parent[f];&l

81、t;/p>　　}　　return f;　　}　　int main(void)//主函數(shù)　　{

82、　　MGraph *G;　　G = (MGraph*)malloc(sizeof(MGraph));　　if (G == NULL)　　{　　printf("memory allca

83、tion failed,goodbye");　　exit(1);　　}　　CreatGraph(G);　　MiniSpanTree(G);　　s

84、ystem("pause");　　return 0;　　}　　四、調(diào)試分析　　終于，在老師的耐心指導(dǎo)和同學(xué)的幫助下，我的課設(shè)任務(wù)完成了。通

85、過這次課程設(shè)計中遇到的許多問題，我收獲頗多，下面就談一談我遇到的一個主要問題及相應(yīng)的產(chǎn)生原因。　　問題：頂點名的類型識別。　　現(xiàn)象：當(dāng)用字母表示頂點時，程序進入死循環(huán)。　　原因：頂點名稱與頂點數(shù)屬于同一數(shù)據(jù)類型即是int整形,當(dāng)出現(xiàn)類型沖突時，程序不能識別就會發(fā)生沖突。&

86、lt;b>　　五、測試結(jié)果　　當(dāng)運行程序時，進入每一步都會有相應(yīng)提示，這會對程序的使用者提供較大的便利。下面就是程序運行時的一些截圖。　　對給定的圖運行程序　　下面是給定的圖<p&g

87、t;　　運行程序　　輸入頂點數(shù)和邊數(shù)后　　輸入各邊及其權(quán)值后　　運行結(jié)果　　六、附錄

88、;　　由于添加了如下兩段代碼：　　printf("鄰接矩陣為:\n");　　for ( i = 1; i <= G->vexnum; i++)　　{　　for

89、( j = 1; j <= G->vexnum; j++)　　{　　printf("%d ",G->arc[i][j].adj);　　}　　printf(&q

90、uot;\n");　　}　　printf("權(quán)排序之后的為:\n");　　for (i = 1; i < G->arcnum; i++)　　{</p

91、>　　printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);　　}　　}<p&

92、gt;　　程序又可以將圖的鄰接矩陣和排序后的權(quán)值列出來，多實現(xiàn)了兩個附加功能。這對于程序的使用者而言將能更直觀更方便的理解有圖到最小生成樹的運算過程，有利于對克魯斯卡爾算法的理解和掌握。　　七、工作環(huán)境　　編譯環(huán)境：Dev-C++4.9.9.2　　文檔書寫工具:Microso

93、ft Office Word2003　　硬件環(huán)境：Intel(R) Core(TM)2 Duo CPU　　T5870 @2.00Hz　　2.00GB 內(nèi)存　　八、參考文獻&

眾賞文庫> 全部分類> 畢業(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)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載