資料結構課程設計報告
管道鋪設最佳方案
班級：姓名：指導教師：
成績： 2023年1月20 日
目錄一、 摘要3
二、 引言3
三、 需求分析3
四、 概要設計4
1. 普利姆演算法分析6
2. 模組分析6
3. 抽象資料型別分析6
4. 全部流程6
五、 詳細設計7
1. 演算法分析7
（一） 資訊輸入模組7
（二） 建立最小生成樹並輸出結果8
2. 源程式**9
六、 測試結果14
程式開始14
資訊輸入14
輸出結果14
七、 設計體會15
八、 結束語16
參考文獻16
一、 摘要
n(n>10)個居民區之間需要鋪設煤氣管道。假設任意兩個居民區之間都可以鋪設煤氣管道，但代價不同。問題的實質就是編寫相應程式求解最小生成樹問題。
程式要求：
事先任意兩個居民區之間鋪設煤氣管道的代價存入磁碟檔案中。設計乙個最佳方案使得這n個居民區之間鋪設煤氣管道所需代價最小，並將結果以圖形方式在螢幕上輸出。
二、 引言
c語言作為一門最通用的語言，從語言產生到現在，它已經成為最重要和最流行的程式語言之一。在各種流行程式語言中，都能看到c語言的影子。學習掌握c語言是每乙個計算機技術人員的基本功之一。
實際生活中最小生成樹的問題具有很大的意義。例如，本文所討論的構架居民區之間鋪設煤氣管道代價最小，還有在若干地區鋪設光纜等等。最小生成樹讓許多諸如求造價最小、最短路徑等最優化的現實問題找到了理論依據，並提供了有效的解決方法。
三需求分析
在n（n>10）個居民區之間鋪設煤氣管道所需代價最小，即求最小生成樹問題。在我們的課本中介紹了兩種求解方法：普利姆演算法和克魯斯卡爾演算法。
普利姆演算法與網的變數無關， 適宜求解邊稠密的網的最小生成樹。而克魯斯卡爾演算法正好相反，
適宜求解邊稀疏的最小生成樹。
由於在實際問題中，居民數量一般很有限，而任何兩個居民區都可能有連線，即這樣的圖應該是邊較為稠密的。因此，我們選擇了普利姆演算法對問題進行求解。
四概要設計
1. 普利姆演算法分析
普利姆演算法思想
普利姆演算法的思想是：在圖中人去乙個定點k0作為開始點，令u=，w=v-u，
其中v為圖中所有頂點集，然後找乙個頂點在u中，另乙個頂點在w中的邊中最短
的一條，找到後，將該邊作為最小生成樹的樹邊儲存起來，並將該邊頂點全部加入u集合中，並從w中刪除這些頂點，然後重新調整u中頂點到w中頂點的距離，使之保持最小，再重複此過程，直到w為空集。
演算法過程描述
1） 在圖g=（v，e）（v是頂點，e是邊）中，從集合v中任取乙個頂點，如k0放入集合u中，這時，u=，集合t（e）為空。
2） 從k0出發尋找與u中頂點相鄰權值最小的邊的另一頂點k1 ，並使k1加入u。即u=，同時將該邊加入集合t（e）中。
3） 重複（2），直到u=v為止。
4） 這時t（e）中有n-1條邊，t=（u，t（e））就是一一顆最小生成樹
2、模組分析
根據對模型的功能分析，該管道鋪設設計可以具有以下功能：
管道鋪設資訊的輸入；
最小生成樹資訊的輸出；
功能模組圖：
3.抽象資料型別分析
areanum 居民區總數（頂點總數）；
edgenum 邊的總數；
date[ ][20] 鄰接矩陣儲存圖結構；
s邊的權值；
short-way[i] 居民區i到目前生成樹中所有點集u中某個居民區的路程最小值
near-area[i] u中能使其最小的居民區
5. 全部流程
五、詳細設計
1.演算法分析
資訊輸入模組
//讀入圖的資訊，並將鄰接矩陣輸出
void read（）
//輸出鄰接矩陣
for(i=0;i
}建立最小生成樹並輸出結果
// 用普里姆演算法從第u個頂點出發構造網g的最小生成樹t,輸出t的各條邊
void minispantree_prim(mgraph g,vertextype u)
}closedge[k].lowcost=0; // 初始,u=
printf("最小代價生成樹的各條邊為:\n");
for(i=1;i
system("pause");
}2. 源程式**
#include
#include
#include
#include
管道鋪設資料結構課程設計報告
資料結構課程設計 報告 題目 管道鋪設設計 專業 軟體072 學號 04號 姓名指導老師 時間 6.29 7.8 目錄摘要3 一 問題重述 需求分析及研究意義3 1.1 問題重述3 1.2 需求分析3 1.3 研究意義3 二 資料結構的邏輯設計和物理儲存設計4 2.1 資料結構的邏輯設計4 2.2 ...
管道鋪設問題資料結構課程設計
資料結構課程設計報告 管道設計問題 二維陣列的運用 班級姓名 指導教師 成績2010年 1 月 20日 目錄一 摘要 3 二 引言 3 三 需求分析 3 四 概要設計 4 1.普里姆演算法分析 4 2.模組分析 5 3.抽象資料型別分析 5 5.全部流程 6 五 詳細設計 7 1.演算法分析 7 資...
球閥課程設計報告 ProE課程設計
一.課題名稱 球閥班級 12機自a1 小組成員 李軍帥 組長 李軍帥 二.球閥的功能和工作原理描述 1.球閥的工作原理 球閥的主要驅動原件是裝配於閥杆上端的扳手，球閥的啟閉元件是位於閥桿下端的球體。球閥的主要工作原理是 當給扳手施加某一轉矩，扳手驅動閥桿旋轉，閥桿將扳手的轉矩傳遞給位於閥桿下端的球體...