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

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

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

已閱讀1頁(yè)，還剩15頁(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、　　二 ○ 一○ 屆課程設(shè) 計(jì) 論文　　《算法與數(shù)據(jù)結(jié)構(gòu)》　　二〇一〇年六月　　目錄　　一、引言 …………………………………………

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

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

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

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

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

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

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

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

10、　2·概要設(shè)計(jì)　　抽象數(shù)據(jù)類型（ADT）如下：　　ADT GRAPH{　　數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，成為頂點(diǎn)集。　　數(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是圖的頂點(diǎn)集，VR是圖中弧的集合。　　操作結(jié)果：按V和VR的定義構(gòu)造圖G。　　DestroyGraph(&G)　　初始條件：圖G存在。　　操作結(jié)果：銷毀圖G </

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

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

15、存儲(chǔ)結(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è)計(jì)　　在該函數(shù)中主要有6段代碼塊，分別是圖的構(gòu)建代碼，對(duì)權(quán)值排序的代碼，交換權(quán)值代碼，最小生成樹(shù)代碼，找尾代碼，主函數(shù)代碼。6段代碼分別實(shí)現(xiàn)不同的功能，共同滿足了課題所需要

19、實(shí)現(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("請(qǐng)輸入邊數(shù)和頂點(diǎn)數(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請(qǐng)輸

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

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

28、n].adj = 1;　　getchar();　　printf("\n請(qǐng)輸入%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>　　}　　}　　對(duì)權(quán)值排序的代碼　　void sort(edge edges[],MGraph *G)//對(duì)權(quán)值進(jì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;　　}　　最小生成樹(shù)代碼　　void MiniSpanTree(MGraph *G)//生成最小生成樹(shù)　　{</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("最小生成樹(shù)為:\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:最小生成樹(shù)kruskal算法　　Author:Song Changzhi

50、　Description:生成最小生成樹(shù) 　　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("請(qǐng)輸入邊數(shù)和頂點(diǎn)數(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請(qǐng)輸入有邊的2個(gè)頂點(diǎn)");　　scanf("%d %d",&n,&m);　　while(n < 0 || n > G->vexnum || m < 0 || n > G->v

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

61、>　　G->arc[n][m].adj = G->arc[m][n].adj = 1;　　getchar();　　printf("\n請(qǐng)輸入%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)//對(duì)權(quán)值進(jì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)//生成最小生成樹(shù)　　{　　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("最小生成樹(shù)為:\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、過(guò)這次課程設(shè)計(jì)中遇到的許多問(wèn)題，我收獲頗多，下面就談一談我遇到的一個(gè)主要問(wèn)題及相應(yīng)的產(chǎn)生原因。　　問(wèn)題：頂點(diǎn)名的類型識(shí)別。　　現(xiàn)象：當(dāng)用字母表示頂點(diǎn)時(shí)，程序進(jìn)入死循環(huán)。　　原因：頂點(diǎn)名稱與頂點(diǎn)數(shù)屬于同一數(shù)據(jù)類型即是int整形,當(dāng)出現(xiàn)類型沖突時(shí)，程序不能識(shí)別就會(huì)發(fā)生沖突。&

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

87、t;　　運(yùn)行程序　　輸入頂點(diǎn)數(shù)和邊數(shù)后　　輸入各邊及其權(quán)值后　　運(yù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)值列出來(lái)，多實(shí)現(xiàn)了兩個(gè)附加功能。這對(duì)于程序的使用者而言將能更直觀更方便的理解有圖到最小生成樹(shù)的運(yùn)算過(guò)程，有利于對(duì)克魯斯卡爾算法的理解和掌握。　　七、工作環(huán)境　　編譯環(huán)境：Dev-C++4.9.9.2　　文檔書(shū)寫(xiě)工具:Microso

93、ft Office Word2003　　硬件環(huán)境：Intel(R) Core(TM)2 Duo CPU　　T5870 @2.00Hz　　2.00GB 內(nèi)存　　八、參考文獻(xià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ù)覽，若沒(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ù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---最小生成樹(shù)問(wèn)題

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載