數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 (2)

1、<p><b>　　目 錄</b></p><p><b>　　前言2</b></p><p>　　1.1設(shè)計背景和意義2</p><p>　　1.1.1數(shù)據(jù)結(jié)構(gòu)簡介2</p><p>　　1.1.2選擇算法的原因2</p><p>　　1.2設(shè)計的原理和內(nèi)

2、容2</p><p><b>　　工程概況2</b></p><p>　　2.1 項目所用的時間2</p><p>　　2.2項目負(fù)責(zé)人2</p><p>　　2.3項目指導(dǎo)人2</p><p><b>　　正文3</b></p><p>

3、　　3.1 設(shè)計的目的和意義3</p><p>　　3.2 目標(biāo)和總體方案3</p><p>　　3.3 設(shè)計方法和內(nèi)容3</p><p>　　3.3.1 硬件環(huán)境4</p><p>　　3.3.2軟件環(huán)境4</p><p>　　3.3.3 設(shè)計流程圖4</p><p>　　3.4

4、程序的設(shè)計思想和內(nèi)容4</p><p>　　3.4.1程序設(shè)計最小生成樹的基本運行環(huán)境5</p><p>　　3.4.3運行分析及要求7</p><p>　　3.4.4測試結(jié)果及界面的截圖8</p><p><b>　　3.5 結(jié)論9</b></p><p><b>　　參考文

5、獻(xiàn)10</b></p><p><b>　　前 言</b></p><p>　　1.1設(shè)計背景和意義</p><p>　　1.1.1數(shù)據(jù)結(jié)構(gòu)簡介</p><p>　　數(shù)據(jù)結(jié)構(gòu)是計算機程序設(shè)計的重要理論設(shè)計基礎(chǔ)，它不僅是計算機學(xué)科的核心課程，而且成為其他理工專業(yè)的熱門選修課。數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方

6、式。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運行或者存儲效率的算法。</p><p>　　比如在計算機中央處理器中，CPU接到一個中斷請求便會停下當(dāng)前正在執(zhí)行的指令去處理這個中斷請求完成中斷操作，首先要做的就是保護(hù)現(xiàn)場。保護(hù)現(xiàn)場需要將下一條指令的地址指針和當(dāng)前指令返回地址等重要的數(shù)據(jù)進(jìn)行存儲。在眾多的數(shù)據(jù)結(jié)構(gòu)中，這些重要的數(shù)據(jù)被存儲到棧這個數(shù)據(jù)結(jié)構(gòu)中。</p><p>　　1.1.2選

7、擇算法的原因</p><p>　　在許多類型的程序的設(shè)計中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個基本的設(shè)計考慮因素。許多大型系統(tǒng)的構(gòu)造經(jīng)驗表明，系統(tǒng)實現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴(yán)重的依賴于是否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。許多時候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時候事情也會反過來，我們根據(jù)特定算法來選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。不論哪種情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)都是非常重要的。</p><p>　　1.2設(shè)計

8、的原理和內(nèi)容</p><p>　　本次程序設(shè)計采用C語作為描述和實現(xiàn)算法的程序語言，主要的設(shè)計思路就是完成對圖的操作，如圖的構(gòu)造、圖的最短路徑、圖的輸出等等，這些操作都是通過C語言程序來實現(xiàn)的。最后的結(jié)果就是運行程序時能夠完成對以上設(shè)計的操作。</p><p><b>　　工程概況</b></p><p>　　2.1 項目所用的時間</p

9、><p>　　從這個項目開始到結(jié)束總共歷時七天。完成于2011年12月18日。</p><p><b>　　2.2項目負(fù)責(zé)人</b></p><p>　　張振東，男，計算機科學(xué)與技術(shù)14-1，學(xué)生。</p><p><b>　　2.3項目指導(dǎo)人</b></p><p>　　吳剛，

10、男，信息工程學(xué)院教師，講師。</p><p><b>　　正 文</b></p><p>　　3.1 設(shè)計的目的和意義</p><p>　　在n個城市間建立通信網(wǎng)絡(luò)，需架設(shè)n-1條線路。求解如何以最低經(jīng)濟(jì)代價建設(shè)此通信網(wǎng)，這是一個最小生成樹問題。要求：（1）利用普利姆算法求通信網(wǎng)絡(luò)的最小生成樹；（2）輸出生成樹中各邊及權(quán)值。</p>

11、<p>　　3.2 目標(biāo)和總體方案 </p><p>　　(1)、如何選擇存儲結(jié)構(gòu)去建立一個帶權(quán)網(wǎng)絡(luò)。</p><p>　　(2)、如何在所選存儲結(jié)構(gòu)下輸出這個帶權(quán)網(wǎng)絡(luò)。</p><p>　　(3)、如何實現(xiàn)PRIM算法的功能。</p><p>　　(4)、如何從每個頂點開始找到所有的最小生成樹的頂點。</p>&

12、lt;p>　　(5)、如何輸出最小生成樹的邊及其權(quán)值。</p><p>　　此問題的關(guān)鍵在于如何實現(xiàn)PRIM算法，實現(xiàn)的過程中如何得到構(gòu)成最小生成樹的所有頂點，此外輸出也是一個關(guān)鍵問題所在，在此過程中經(jīng)過了多次調(diào)試。</p><p>　　首先我們對問題進(jìn)行大致的概要分析：</p><p>　　這個問題主要牽涉到通過PRIM的基本算法思想實現(xiàn)程序所要求的功能，該

13、算法的主要思想是：假設(shè)N=（V，{E}）是連通網(wǎng)，TE是N上最小生成樹中邊的集合。算法從U={u0}( u0∈V),TE={}開始，重復(fù)執(zhí)行下述操作：在所有u∈U,v∈V-U的邊（u,v）∈E中找一條代價最小的邊（u0,v0）并入集合TE，同時v0并入U，直至U=V為止。此時TE中必有n-1條邊，則T=（V，{E}）為N的最小生成樹。</p><p>　　問題的輸入數(shù)據(jù)的格式為：首先提示輸入帶權(quán)網(wǎng)絡(luò)的頂點邊數(shù)，我

14、定義的為整形數(shù)據(jù)型，然后輸入每一條邊的信息，即邊的兩個頂點以及權(quán)值，是十進(jìn)制整數(shù)類型，這樣我們就建立一個帶權(quán)網(wǎng)絡(luò)，并用鄰接矩陣來存儲，生成一個方陣顯示出來。</p><p>　　問題的輸出數(shù)據(jù)格式為：輸出是以鄰接矩陣存儲結(jié)構(gòu)下的方陣，以及從不同頂點開始省城的最小生成樹。</p><p>　　題目要求以及達(dá)到目標(biāo)：題目要求用普利姆算法實現(xiàn)任意給定的網(wǎng)和頂點的所有最小生成樹，并且輸出各邊的權(quán)值

15、。</p><p>　　由于時間只有七天，故做了如下的計劃安排，將這項工程分為兩大部分：程序的設(shè)計和程序的調(diào)試。</p><p>　　首先在程序的設(shè)計部分由分為幾個步驟：</p><p>　　第一步：查閱有關(guān)數(shù)據(jù)結(jié)構(gòu)棧操作的資料，用一到兩天的時間。</p><p>　　第二步：設(shè)計這個項目的整體架構(gòu)和算法，用一到兩天的時間。</p>

16、;<p>　　第三步：選擇一門程序設(shè)計語言進(jìn)行算法的描述，兩天的時間。</p><p>　　其次，進(jìn)行程序的調(diào)試，用一天。</p><p>　　3.3 設(shè)計方法和內(nèi)容</p><p>　　3.3.1 硬件環(huán)境</p><p>　　微型計算機：聯(lián)想臺式品牌機</p><p>　　中央處理器：Pentuim

17、4 主頻：3.0GHz</p><p>　　主存容量： 512M</p><p>　　硬盤容量： 80G</p><p><b>　　3.3.2軟件環(huán)境</b></p><p>　　Windows XP 操作系統(tǒng)</p><p>　　Microsoft NotePad 記事本程序</p

18、><p>　　Microsoft Visual C++編譯器</p><p>　　3.3.3 設(shè)計流程圖</p><p>　　圖3-1 程序流程圖</p><p>　　3.4 程序的設(shè)計思想和內(nèi)容</p><p>　　Prim算法求最小生成樹的主要思想。此算法是普利姆與1957年提出的一種構(gòu)造最小生成樹的算法，主要思想是：

19、假設(shè)N=（V，{E}）是連通網(wǎng)，TE是N上最小生成樹中邊的集合。算法從U={u0}( u0∈V),TE={}開始，重復(fù)執(zhí)行下述操作：在所有u∈U,v∈V-U的邊（u,v）∈E中找一條代價最小的邊（u0,v0）并入集合TE，同時v0并入U，直至U=V為止。此時TE中必有n-1條邊，則T=（V，{E}）為N的最小生成樹。</p><p><b>　　對于最小生成樹問題</b></p>

20、<p>　　最小生成樹是指在所有生成樹中，邊上權(quán)值之和最小的生成樹，另外最小生成樹也可能是多個，他們之間的權(quán)值之和相等。</p><p>　　3.4.1程序設(shè)計最小生成樹的基本運行環(huán)境</p><p><b>　?。?）預(yù)處理</b></p><p>　　#include <stdio.h></p>&l

21、t;p>　　#include <graphics.h></p><p>　　#define inf 9999</p><p>　　#define max 40</p><p>　　#define linelenght 77</p><p><b>　　（2）普里姆算法</b></p>&l

22、t;p>　　void prim(int g[][max],int n) /* prim的函數(shù) */</p><p><b>　　{</b></p><p>　　int lowcost[max],closest[max];</p><p>　　int i,j,k,min;</p><p&g

23、t;　　for(i=2;i<=n;i++) /* n個頂點，n-1條邊 */</p><p>　　{ lowcost[i]=g[1][i]; /* 初始化 */</p><p>　　closest[i]=1; /* 頂點未加入到最小生成樹中 */<

24、/p><p><b>　　}</b></p><p>　　lowcost[1]=0; /* 標(biāo)志頂點1加入U集合 */</p><p>　　for(i=2;i<=n;i++) /* 形成n-1條邊的生成樹 */</p><

25、;p><b>　　{</b></p><p><b>　　min=inf;</b></p><p><b>　　k=0;</b></p><p>　　for(j=2;j<=n;j++) /* 尋找滿足邊的一個頂點在U,另一個頂點在V的最小邊 */&

26、lt;/p><p>　　if((lowcost[j]<min)&&(lowcost[j]!=0))</p><p><b>　　{</b></p><p>　　min=lowcost[j];</p><p><b>　　k=j;</b></p><p>&l

27、t;b>　　}</b></p><p>　　printf("(%d,%d)%d\t",closest[k],k,min);</p><p>　　lowcost[k]=0; /* 頂點k加入U */</p><p>　　for(j=2;j<=n;j++)

28、 /* 修改由頂點k到其他頂點邊的權(quán)值 */</p><p>　　if(g[k][j]<lowcost[j])</p><p><b>　　{</b></p><p>　　lowcost[j]=g[k][j];</p><p>　　closest[j]=k;</p><p>

29、<b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　?。?）輸出分割線</b></p><

30、p>　　int priline(int h) /* 輸出一條分割線 */</p><p><b>　　{</b></p><p><b>　　int g;</b></p><p>　　printf("\n|");</p><p>　　

31、for(g=0;g<h;g++)</p><p>　　printf("*");</p><p>　　printf("|\n");</p><p><b>　　}</b></p><p><b>　?。?）提示錯誤信息</b></p><

32、;p>　　int error() /* 提示錯誤信息 */</p><p><b>　　{</b></p><p>　　printf("\n\n|************************E*R*R*O*R************************|\n");</p><p&

33、gt;　　printf("Input errors or Data overflow!!! please re-enter\n\n");</p><p>　　fflush(stdin); /* 清除緩存 */</p><p><b>　　}</b></p><p><

34、b>　?。?）建立無向圖</b></p><p>　　int adjg(int g[][max]) /* 建立無向圖 */</p><p><b>　　{</b></p><p>　　int n,e,i,j,k,v1=0,v2=0,weight=0;</p><p

35、>　　printf("Input the number of vertices, number of the edge:");</p><p>　　scanf("%d,%d",&n,&e);</p><p>　　while(e<=0||e>=n*(n-1)||n>=max)</p><p&g

36、t;<b>　　{</b></p><p><b>　　error();</b></p><p>　　printf("Input the number of vertices, number of the edge:");</p><p>　　scanf("%d,%d",&n

37、,&e);</p><p><b>　　}</b></p><p>　　for(i=1;i<=n;i++)</p><p>　　for(j=1;j<=n;j++)</p><p>　　g[i][j]=inf; /* 初始化矩陣，全部元素設(shè)為無窮大 */</

38、p><p>　　for(k=1;k<=e;k++)</p><p><b>　　{</b></p><p>　　printf("Input the %d on the edge of the starting point, terminal, weights:",k);</p><p>　　sca

39、nf("%d,%d,%d",&v1,&v2,&weight);</p><p>　　while(v1==v2||v1>n||v2>n||v1<1||v2<1)</p><p><b>　　{</b></p><p><b>　　error();</b>&l

40、t;/p><p>　　printf("Input the %d on the edge of the starting point, terminal, weights:",k);</p><p>　　scanf("%d,%d,%d",&v1,&v2,&weight);</p><p><b>

41、　　}</b></p><p>　　g[v1][v2]=weight;</p><p>　　g[v2][v1]=weight;</p><p><b>　　}</b></p><p>　　return(n);</p><p>　　}

42、 /* 返回節(jié)點個數(shù)n */</p><p>　?。?）輸出無向圖的鄰接矩陣</p><p>　　void pri(int g[][max],int n) /* 輸出無向圖的鄰接矩陣 */</p><p><b>　　{</b></p><p><b>　　i

43、nt i,j;</b></p><p>　　for(i=0;i<=n;i++)</p><p>　　printf("%d\t",i);</p><p>　　for(i=1;i<=n;i++)</p><p><b>　　{</b></p><p>　　p

44、rintf("\n%d\t",i);</p><p>　　for(j=1;j<=n;j++) /* 輸出邊的權(quán)值 */</p><p><b>　　{</b></p><p>　　if(g[i][j]==inf) printf("%c\t",'\354

45、');</p><p>　　else printf("%d\t",g[i][j]);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("\n");</p><p>

46、;<b>　　}</b></p><p><b>　?。?）主函數(shù)模塊</b></p><p>　　void main() /* 主函數(shù) */</p><p><b>　　{</b></p><p>　　int g[max][max

47、],n;priline(linelenght);</p><p>　　n=adjg(g);priline(linelenght);priline(linelenght);</p><p>　　printf("Input the adjacency matrix without directed graph:\n");</p><p><b&

48、gt;　　pri(g,n);</b></p><p>　　printf("\n");</p><p>　　printf("Minimum spanning tree structure:\n");</p><p>　　prim(g,n);</p><p><b>　　getch()

49、;</b></p><p><b>　　}</b></p><p>　　3.4.3運行分析及要求</p><p>　　對于任意給定的網(wǎng)和起點，用PRIM算法的基本思想求解出所有的最小生成樹并輸出這些邊的權(quán)值，所以如何實現(xiàn)輸出顯示所有的最小生成樹關(guān)鍵問題所在，經(jīng)過分析調(diào)試，用一個for語句就可以解決這個問題，從每個頂點出發(fā)，開始每一次

50、遍歷并輸出顯示出來。</p><p>　　算法的時間和空間性能分析。根據(jù)程序中算法的循環(huán)語句可以判斷出普利姆算法的時間復(fù)雜度為O（n2）算法和圖中的邊數(shù)無關(guān)。因此普利姆算法適合求稠密網(wǎng)的最小生成樹，因為在算法中用鄰接矩陣的存儲結(jié)構(gòu)，在無向圖中，鄰接矩陣是對稱的。所以僅需要存儲上三角或下三角的元素，因此需要n(n+1)的存儲空間。</p><p>　　3.4.4測試結(jié)果及界面的截圖</

51、p><p><b>　　輸入的情況的截圖</b></p><p><b>　　輸出結(jié)果的截圖</b></p><p><b>　　輸入錯誤的截圖</b></p><p><b>　　3.5 結(jié)論</b></p><p>　　我們設(shè)計的題

52、目是最小生成樹的構(gòu)造，在這次實踐中遇到了各種問題，碰到問題有時總是百思不得其解</p><p>　　最開始，程序要求輸入數(shù)值時，如果任意沒有按照程序給定的類型輸入，程序就會出現(xiàn)死循環(huán)，雖然加入了檢測程序段，但是當(dāng)我們不按個數(shù)輸入的時候程序也出現(xiàn)了不穩(wěn)定，又進(jìn)入死循環(huán)了。我們想了很多辦法，其中之一就是加入break這個函數(shù)。</p><p>　　不過，并沒有出項我們想要的結(jié)果，導(dǎo)致循環(huán)檢測輸

53、入的函數(shù)while無法繼續(xù)執(zhí)行，中途就中斷了。有點大失所望，但是我們沒有氣餒。記得以前老是老師又用過清空緩存這個函數(shù)，會不會失這個原因呢？</p><p>　　int error() /* 提示錯誤信息 */</p><p><b>　　{</b></p><p>　　printf("\n\n|**

54、**********************E*R*R*O*R************************|\n");</p><p>　　printf("Input errors or Data overflow!!! please re-enter\n\n");</p><p>　　fflush(stdin);

55、 /* 清除緩存 */</p><p><b>　　}</b></p><p>　　經(jīng)過我們反復(fù)測試，最終確定原因，正是出在這里，導(dǎo)致數(shù)據(jù)無法更新。</p><p>　　最小生成樹主要由PRIM算法完成，由于老師平時課上對普利姆算法的知識的透徹講解，通過整體構(gòu)思，，于是，我們先確立了基本步驟：1.建立一個具有n個定點的無向圖 2.接著

56、創(chuàng)建一個鄰接矩陣來存儲該圖，然后初始化該矩陣，最后根據(jù)普利姆算法，得到了最小生成樹以及各邊的權(quán)值 ；好的開頭是成功的一半，按照這個步驟，我們忙碌了3天，在大家的共同努力下，我們總算將此程序設(shè)計出來。盡管不是自己獨立完成，但仍然很欣慰，因為在設(shè)計的過程中，讓我們了解到要設(shè)計一個大型程序，查找資料是至關(guān)重要的，在他人的基礎(chǔ)上，再根據(jù)自己所學(xué)進(jìn)行修改與調(diào)試，最后設(shè)計出自己想要的程序，這過程艱辛，但只要你持之以恒，定可將問題解決。 通過本次實驗

57、鞏固了課本的基本知識，熟練運用課程知識。提高我們組織數(shù)據(jù)及編寫程序的能力，使我們能夠根據(jù)問題要求和數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)組織的方法，把現(xiàn)實世界中的問題在計算機內(nèi)部表示出來并用軟件解決問題，本次實驗大大提高了對編程的愛好，發(fā)現(xiàn)，只要認(rèn)認(rèn)真真的去思考，沒有辦不到的事情， 程序設(shè)計過程有</p><p>　　這個課程設(shè)計是一個簡單的設(shè)計，如果說有“設(shè)計創(chuàng)新與關(guān)鍵技術(shù)”的話，只能勉強說有設(shè)計創(chuàng)新，至于關(guān)鍵技術(shù)應(yīng)該談不上

58、。</p><p>　　談到設(shè)計創(chuàng)新，只能說在設(shè)計思路、設(shè)計方法和設(shè)計內(nèi)容上有別人沒有的東西。而所用的技術(shù)倒是沒有多少。主要是運用了C語言豐富的表達(dá)能力，將隊列的建立、出隊列、進(jìn)隊列和棧的建立、進(jìn)棧、出棧等操作形象的反應(yīng)出來。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]嚴(yán)蔚敏.吳偉民編著.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華

59、大學(xué)出版社.2007</p><p>　　[2]李春葆.編著.數(shù)據(jù)結(jié)構(gòu)教程.清華大學(xué)出版社.2006</p><p>　　[3]郭翠英等編著.C語言課程設(shè)計案例精編.中國水利水電出版社.2004</p><p>　　[4]譚浩強編著.C程序設(shè)計.清華大學(xué)出版社.2005</p><p>　　[5] 嚴(yán)蔚敏.吳偉民編著.數(shù)據(jù)結(jié)構(gòu)（C語言版）算法