管道鋪設問題資料結構課程設計

資料結構課程設計報告

管道設計問題

——二維陣列的運用

班級姓名

指導教師

成績2023年 1 月 20日

目錄一、摘要 3

二、引言 3

三、需求分析 3

四、概要設計 4

1.普里姆演算法分析 4

2.模組分析 5

3.抽象資料型別分析 5

5.全部流程 6

五、詳細設計 7

1.演算法分析 7

①資訊輸入模組 7

②建立最小生成樹並輸出結果 8

2.源程式** 9

六、測試結果 14

程式開始 14

資訊輸入 14

輸出結果 15

七、設計體會 15

八、結束語 16

參考文獻 16

n(n>10)個居民區之間需要鋪設煤氣管道。假設任意兩個居民區之間都可以鋪設煤氣管道，但代價不同。問題的實質就是編寫相應程式求解最小生成樹問題。程式要求：

事先任意兩居民區之間鋪設煤氣管道的代價存入磁碟檔案中。設計乙個最佳方案使得這n個居民區之間鋪設煤氣管道所需代價最小，並將結果以圖形方式在螢幕上輸出。

c語言作為一門最通用的語言，在過去很流行，將來依然會如此。幾乎每乙個理工科或者其他專業的學生毫不例外地要學習它。

從c語言產生到現在，它已經成為最重要和最流行的程式語言之一。在各種流行程式語言中，都能看到c語言的影子。學習、掌握c語言是每乙個計算機技術人員的基本功之一。

c語言具有高階語言的強大功能，卻又有很多直接操作計算機硬體的功能，因此，c語言通常又被稱為中級語言。

實際生活中最小生成樹的問題具有很大的意義。例如，本文所討論的構架居民區之間鋪設煤氣管道代價最小，還有在若干的地區見鋪設光纜，等等。最小生成樹讓許多諸如求造價最小、最短路徑等最優化的現實問題找到了理論依據，並提供了有效的解決方法。

在n(n>10)個居民區之間鋪設煤氣管道所需代價最小，即求最小生成樹問題。在我們的課程中介紹了兩種求解方法：普里姆（prim）演算法和克魯斯卡爾（kruskal）演算法。

普里姆演算法與網的變數無關，時間複雜度為o（n2),適宜求解邊稠密的網的最小生成樹。而克魯斯卡爾演算法正好相反，時間複雜度為o（eloge）（e為網中邊的數目），故而該演算法適宜求邊稀疏的最小生成樹。

由於在實際應用中，居民區數量一般很有限，而任何兩個居民區間都可能有連線，即這樣的圖應該是邊較為稠密的。因此，我們選擇普里姆演算法對問題進行求解。

1、建立乙個帶權無向圖的鄰接矩陣，然後進行深度和廣度優先搜尋遍歷，並輸出遍歷的結果序列。最後若此圖是連通圖，輸出該網的一顆最小生成樹。

2、網中頂點的編號從0開始頂點的資訊為字元。

3、按照網的鄰接矩陣定義輸出該矩陣。

4、在非連通圖的情況下要能夠按深度和廣度優先搜尋遍歷整個網。

5、用普里姆法構造最小生成樹。在最小生成樹演算法中，應判斷該網是否連通，如果非連通，則需輸出提示資訊並退出程式。

①普里姆演算法思想

普里姆方法的思想是：在圖中任取乙個頂點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中頂點相鄰（另一頂點在v中）權值最小的邊的另一頂點k1，並使k1加入u。即u=，同時將該邊加入集合t(e)中。

(3) 重複(2)，直到u = v為止。

(4)這時t(e)中有n-1條邊，t = (u, t(e))就是一棵最小生成樹。

prim演算法示意圖

根據對模型的功能分析，該管道鋪設設計可以具有以下功能：

①管道鋪設資訊的輸入；

②最小生成樹資訊的輸出；

下面我們給出相應的功能模組圖：

areanum 居民區總數（頂點總數）；

edgenum 邊的總數；

date[20] 鄰接矩陣儲存圖結構；

s邊的權值；

short_way[i] 居民區i到到目前生成樹中所有點集u中某個居民區的路程最小值

near_area[i] u中能使其最小的居民區

//讀入圖的資訊，並將鄰接矩陣輸出

void read（）

//輸出鄰接矩陣

for(i = 0; i

printf("\n"); }}

void prim(int date[maxnode],int areanum,int near_area)

short_way[i]=0;

near_area[0] = 0;

for(i = 1; i < areanum; i++)//有n-1條邊要加入生成樹,所以只要迴圈n-1次即可

j++;

} printf("居民區序號為%d，居民區路程（邊的權值）為%d",k,min);

short_way[k]=0;

for(j=0;j

} }#include<>

#define infinity 9999

void main()

{int a1;

printf("%46s\n","管道鋪設方案選擇");

for(a1=0;a1<21;a1++)

printf(" ");

for(a1=0;a1<34;a1++)

printf("*");

printf("\n");

for(a1=0;a1<21;a1++)

printf(" ");

printf

printf("\n");

for(a1=0;a1<21;a1++)

printf(" ");

printf("*");

printf("歡迎使用本程式，本程式可以幫助您*");

printf("\n");

for(a1=0;a1<21;a1++)

printf(" ");

printf("*");

printf("選擇最佳管道鋪設方案

printf("\n");

for(a1=0;a1<21;a1++)

printf(" ");

printf

管道鋪設問題資料結構課程設計

管道鋪設資料結構課程設計報告

資料結構課程設計

資料結構課程設計

相關推薦