《資料結構課程設計》報告
題目： 管道鋪設設計
專業： 軟體072
學號： 04號
姓名指導老師
時間： 6.29～7.8
目錄摘要3
一、問題重述、需求分析及研究意義3
1.1 問題重述3
1.2 需求分析3
1.3 研究意義3
二、資料結構的邏輯設計和物理儲存設計4
2.1 資料結構的邏輯設計4
2.2 資料的物理儲存結構設計4
三、詳細設計5
3.1 普里姆演算法分析5
3.1.1 普里姆演算法思想5
3.1.2 演算法過程描述5
3.2 各功能模組的劃分6
3.3 資料結構7
3.4 流程描述7
3.4.1 資訊輸入模組7
3.4.2 建立最小生成樹並輸出結果8
3.5 演算法時間複雜度分析及流程圖8
3.5.1 時間複雜度8
3.5.2 流程圖9
3.6 源程式**9
3.7 程式最終實現結果12
四、小結14
參考文獻14
摘要：n(n>10)個居民區之間需要鋪設煤氣管道。假設任意兩個居民區之間都可以鋪設煤氣管道，但代價不同。
一、問題重述、分析及研究意義
1.1 問題重述
n(n>10)個居民區之間需要鋪設煤氣管道。假設任意兩個居民區之間都可以鋪設煤氣管道，但代價不同。問題的實質就是編寫相應程式求解最小生成樹問題。程式要求：
事先任意兩居民區之間鋪設煤氣管道的代價存入磁碟檔案中。設計乙個最佳方案使得這n個居民區之間鋪設煤氣管道所需代價最小，並將結果以圖形方式在螢幕上輸出。
1.2 需求分析
在n(n>10)個居民區之間鋪設煤氣管道所需代價最小，即求最小生成樹問題。在我們的課程中介紹了兩種求解方法：普里姆（prim）演算法和克魯斯卡爾（kruskal）演算法。
普里姆演算法與網的變數無關，時間複雜度為o（n2),適宜求解邊稠密的網的最小生成樹。而克魯斯卡爾演算法正好相反，時間複雜度為o（eloge）（e為網中邊的數目），故而該演算法適宜求邊稀疏的最小生成樹。
由於在實際應用中，居民區數量一般很有限，而任何兩個居民區間都可能有連線，即這樣的圖應該是邊較為稠密的。因此，我們選擇普里姆演算法對問題進行求解。
1、 建立乙個帶權無向圖的鄰接矩陣，然後進行深度和廣度優先搜尋遍歷，並輸出遍歷的結果序列。最後若此圖是連通圖，輸出該網的一顆最小生成樹。
2、 網中頂點的編號從0開始頂點的資訊為字元。
3、 按照網的鄰接矩陣定義輸出該矩陣。
4、 在非連通圖的情況下要能夠按深度和廣度優先搜尋遍歷整個網。
5、 用普里姆法構造最小生成樹。在最小生成樹演算法中，應判斷該網是否連通，如果非連通，則需輸出提示資訊並退出程式。
1.3 研究意義
實際生活中最小生成樹的問題具有很大的意義。例如，本文所討論的構架居民區之間鋪設煤氣管道代價最小，還有在若干的地區見鋪設光纜，等等。最小生成樹讓許多諸如求造價最小、最短路徑等最優化的現實問題找到了理論依據，並提供了有效的解決方法。
二、資料結構的邏輯設計和物理儲存設計
2.1 資料結構的邏輯設計
每個居民區可能與其他任何乙個居民區相連，也即居民區與居民區之間是一種多對多的關係。把乙個城市抽象成為乙個頂點，居民區之間的連線抽象為圖中頂點之間的邊，路程作為邊的權值。那麼，結構中的每個資料元素（頂點）都可能有任意多個直接前驅和直接後繼，即是一種圖結構。
當然，從居民區0到居民區1應和從居民區1到居民區0是等價的。因此，我們把該資料的邏輯結構定義為無向圖結構。圖示如下：
2.2 資料的物理儲存結構設計
為了方便圖的各種操作，如該演算法當中需要判斷某頂點間是否有邊、比較邊的權值、求頂點的位置等問題，而且這是個邊較為稠密的圖。鑑於此，我們採取鄰接矩陣表示法來儲存圖結構。如對上圖採用鄰接矩陣儲存可表示為：
b=用鄰接矩陣建立無向圖的演算法：
//鄰接矩陣資料型別描述
#define max 30 /*最大定點數*/
typedef struct
adjmatrix;
//求頂點位置函式
int locatevertex (adjmatrix *g,vertexdata v)
return(j);
}//建立乙個無向圖
#define infinity 9999 //infinity代表乙個無窮大的數
int creatudn(adjmtrix *g)
reurn （ok）；
}三、詳細設計
3.1 普里姆演算法分析
3.1.1普里姆演算法思想
普里姆方法的思想是：在圖中任取乙個頂點k0作為開始點，令u=，w=v-u，其中v為圖中所有頂點集，然後找乙個頂點在u中，另乙個頂點在w中的邊中最短的一條，找到後，將該邊作為最小生成樹的樹邊儲存起來，並將該邊頂點全部加入u集合中，並從w中刪去這些頂點，然後重新調整u中頂點到w中頂點的距離, 使之保持最小，再重複此過程，直到w為空集止。
3.1.2該演算法過程描述
(1)在圖g=(v, e) （v表示頂點 ，e表示邊）中，從集合v中任取乙個頂點（例如取頂點k0）放入集合 u中，這時 u=，集合t(e)為空。
(2) 從k0出發尋找與u中頂點相鄰（另一頂點在v中）權值最小的邊的另一頂點k1，並使k1加入u。即u=，同時將該邊加入集合t(e)中。
(3) 重複(2)，直到u = v為止。
(4)這時t(e)中有n-1條邊，t = (u, t(e))就是一棵最小生成樹。
prim演算法示意圖
3.2 各功能模組的劃分
根據對模型的功能分析，該管道鋪設設計可以具有以下功能：
1 管道鋪設資訊的輸入；
2 最小生成樹資訊的輸出；
下面我們給出相應的功能模組圖：
3.3 資料結構
areanum 居民區總數（頂點總數）；
edgenum 邊的總數；
date[20] 鄰接矩陣儲存圖結構；
s邊的權值；
short_way[i] 居民區i到到目前生成樹中所有點集u中某個居民區的路程最小值
near_area[i] u中能使其最小的居民區
3.4 流程描述
3.4.1資訊輸入模組
//讀入圖的資訊，並將鄰接矩陣輸出
管道鋪設問題資料結構課程設計
資料結構課程設計報告 管道設計問題 二維陣列的運用 班級姓名 指導教師 成績2010年 1 月 20日 目錄一 摘要 3 二 引言 3 三 需求分析 3 四 概要設計 4 1.普里姆演算法分析 4 2.模組分析 5 3.抽象資料型別分析 5 5.全部流程 6 五 詳細設計 7 1.演算法分析 7 資...
資料結構課程設計報告
交通諮詢系統設計 不用輸入程式語句，也不用那個截圖 不用太著急，報告周五之前給我就行了 列印和壓縮包都要哈！對了，這段文字記得刪掉啊嘿嘿 題目名稱交通諮詢系統設計 院 系 管理學院 課程名稱資料結構課程設計 班級資訊 10 2 學生姓名呂德麗 指導教師李長雲 目錄一 需求分析及選題要求 3 1 問題...
資料結構課程設計報告
課程設計報告 課程名稱資料結構 課題名稱生死者遊戲 專業資訊管理與資訊系統 班級學號 姓名指導教師 2011 年 1 月 20 日 湖南工程學院 課程設計任務書 課程名稱資料結構 課題生死者遊戲 專業班級 學生姓名 學號指導老師 審批任務書下達日期 2011 年 1 月 3 日 任務完成日期 201...