數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告—管道鋪設(shè)問(wèn)題

1、計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 實(shí)驗(yàn)報(bào)告 I 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三 ：管道鋪設(shè)施工的最佳方案問(wèn)題一、問(wèn)題描述1. 實(shí)驗(yàn)題目 ：需要在某個(gè)城市 n 個(gè)居民小區(qū)之間鋪設(shè)煤氣管道 ， 則在這 n 個(gè)居民小區(qū)之間只需要鋪 設(shè) n-1 條管道即可 。假設(shè)任意兩個(gè)小區(qū)之間都可以鋪設(shè)管道 ， 但由于地理環(huán)境不同 ， 所需 要的費(fèi)用也不盡相同 。 選擇最優(yōu)的方案能使總投資盡可能小，這個(gè)問(wèn)題即為求無(wú)向網(wǎng)的最小生成樹(shù) 。2. 基本要求 ：在可能假設(shè)的 m 條管道中 ， 選取 n-1 條管道 ，使得既能連通 n 個(gè)小區(qū) ， 又能使總投資 最小 。每條管道的費(fèi)用以網(wǎng)中該邊的權(quán)值形式給出 ，網(wǎng)的存儲(chǔ)采用鄰接表的結(jié)構(gòu) 。3. 測(cè)試數(shù)據(jù) ：

2、使用下圖給出的無(wú)線(xiàn)網(wǎng)數(shù)據(jù)作為程序的輸入，求出最佳鋪設(shè)方案 。 右側(cè)是給出的參考解。圖 1 小區(qū)煤氣管道鋪設(shè)網(wǎng)及其參考解4.輸入輸出 :表示鋪設(shè)的管通過(guò)普利姆2. 輸入輸出形式及輸入值范圍 ：根據(jù)提示輸入總的邊數(shù) ，結(jié)點(diǎn)數(shù) 。再根據(jù)提示輸入各結(jié)點(diǎn)的信息即結(jié)點(diǎn)的名稱(chēng)， 輸入邊的信息 ，即邊的兩個(gè)端點(diǎn)和該邊的權(quán)值 。輸入后成功創(chuàng)建鄰接表 ， 自動(dòng)輸出所建立的鄰接 表和普利姆算法求出的最小生成樹(shù) 。3. 測(cè)試數(shù)據(jù)要求 ：解。使用下圖給出的無(wú)線(xiàn)網(wǎng)數(shù)據(jù)作為程序的輸入， 求出最佳鋪設(shè)方案 。 右側(cè)是給出的參考輸入邊的信息 ， 即兩個(gè)端點(diǎn)的名稱(chēng)及該邊的權(quán)值A(chǔ) B 32.8 )；B C 5.9);(C D 21

3、.3);(DE 67.3);(A C 44.6);(A H 12.1);(A I 18.2);(H I 8.7);(H G 52.5);(C G 56.4);(C E 41.1);(E F 85.6); (D F 98.7);(I F 79.2);(E G 10.5)輸入完畢直接輸出 “建立的圖鄰接表表示為 ：0-8-7-2-1-2-0-2-4-6-0-3-1-3-5-4-2-4-6-5-2-3-5-8- 3-4-6-4-2-7-7-6-8-0-8-5-7-0直接輸出應(yīng)用 prime 算法 ，得到的最小生成樹(shù)的結(jié)果 ，用結(jié)點(diǎn)字母表示、概要設(shè)計(jì)為了實(shí)現(xiàn)上述功能 ， 該程序以鄰接表存儲(chǔ)的無(wú)向圖模擬

4、居民住宅的分布和住宅之間的 管道 ，通過(guò)普利姆算法求最小生成樹(shù)來(lái)求解管道最小花費(fèi) 。因此需要鄰接表這一抽象數(shù)據(jù) 類(lèi)型來(lái)表示無(wú)向圖 。還需要普利姆算法求最小生成樹(shù) 。1. 鄰接表抽象數(shù)據(jù)類(lèi)型定義ADT ALGraph 數(shù)據(jù)對(duì)象 ： D=ai,bi,ci|ai AdjList, bi int,ci int),i =1,2.,n,n 0:數(shù)據(jù)關(guān)系 ：R=?基本操作 :create(ALGraph* G)/ 建立無(wú)向圖的鄰接表存儲(chǔ)void prime(ALGraph * G, int from)/ 用普利姆算法求最小生成 樹(shù)ADT ALGraph2. ADT 的 c 語(yǔ)言形式說(shuō)明 ：typedef s

5、tructAdjList adjlist;/ 鄰接表int n, e;/ 頂點(diǎn)數(shù)和邊數(shù)ALGraph; /ALGraph 是以鄰接表方式存儲(chǔ)的圖類(lèi)型void create(ALGraph* G)/ 建立無(wú)向圖的鄰接表存儲(chǔ)void prime(ALGraph * G, int from)/用普利姆算法求最小生成樹(shù)3. 本程序保護(hù)模塊 ：主函數(shù)模塊圖模塊4. 普利姆算法分析(1) 普利姆算法思想 ：普利姆算法的思想是 ： 在圖中人去一個(gè)定點(diǎn) k0 作為開(kāi)始點(diǎn) ，令 U=k0 ，W=V-U ， 其中 V 為圖中所有頂點(diǎn)集 ，然后找一個(gè)頂點(diǎn)在 U 中， 另一個(gè)頂點(diǎn)在 w 中的邊中最短的一條 ，找到后，

6、將該邊作為最小生成樹(shù)的樹(shù)邊保存起來(lái) ，并將該邊頂點(diǎn)全部加入 U 集合 中，并從 W中刪除這些頂點(diǎn) ，然后重新調(diào)整 U中頂點(diǎn)到 W中頂點(diǎn)的距離 ，使之保持最小 ， 再重復(fù)此過(guò)程 ， 直到 W 為空集 。（2）算法過(guò)程描述 ：在圖 G= （V，E）（ V是頂點(diǎn)，E是邊）中，從集合 V中任取一個(gè)頂點(diǎn) ，如 k0放入集 合 U中，這時(shí)， U=k0 ，集合 T（ E）為空。從 k0 出發(fā)尋找與 U 中頂點(diǎn)相鄰權(quán)值最小的邊的另一頂點(diǎn) k1 ，并使 k1 加入 U。 即U=k0 ， k1，同時(shí)將該邊加入集合 T（E）中 。重復(fù)（2），直到 U=V 為止 。這時(shí) T（E）中有 n-1 條邊，T= （U，T（E

7、）就是一一顆最小生成樹(shù)。各邊兩端名稱(chēng)和邊的權(quán)值創(chuàng)建鄰接表存儲(chǔ)無(wú)向圖并輸出這一鄰接表。 用普利姆算法求最小生成樹(shù) ：訪(fǎng)問(wèn)各節(jié)點(diǎn) ，從 已經(jīng)訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn)和未訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn)組成的所有邊中挑出權(quán)重最小的一條邊放入鄰接表EdgeNode * minEdge 中。 輸出這個(gè)最小權(quán)重的表 。(2)模塊調(diào)用關(guān)系主函數(shù)模塊鄰接表存儲(chǔ)模塊 create(ALGraph* G)普 利 姆 算 法求 最小 生成樹(shù)模塊 prime(ALGraph * G, int from)判斷是否訪(fǎng)問(wèn)過(guò) isExists(int*visited, int n, int vex)3)功能模塊圖6.主要算法流程圖create(ALGrap

8、h* G)開(kāi)始讀入節(jié)點(diǎn) 數(shù)和邊數(shù)i=0四、詳細(xì)設(shè)計(jì)1、元素類(lèi)型 、結(jié)點(diǎn)類(lèi)型 、 結(jié)點(diǎn)指針類(lèi)型 typedef struct node/ 邊表節(jié)點(diǎn)int src; / 邊端的序號(hào)char srcName;/ 邊端的名稱(chēng)int adjvex;/ 鄰接點(diǎn)域node* next;/ 指向下一個(gè)鄰接點(diǎn)的指針域char adjName;float cost;/ 邊的權(quán)值EdgeNode;typedef struct / 頂點(diǎn)表節(jié)點(diǎn)char vertex;/ 頂點(diǎn)域EdgeNode* firstedge;/ 邊表頭指針是鄰接表類(lèi)型VertexNode;typedef VertexNode AdjListMa

9、xVertexNum;/AdjListtypedef structAdjList adjlist;/ 鄰接表int n, e;/ 頂點(diǎn)數(shù)和邊數(shù)ALGraph; /ALGraph 是以鄰接表方式存儲(chǔ)的圖類(lèi)型2. 創(chuàng)建鄰接表 void create(ALGraph* G)/ 建立無(wú)向圖的鄰接表存儲(chǔ)int k, w, v;EdgeNode *s;cout 請(qǐng)輸入節(jié)點(diǎn)數(shù)和邊數(shù) (用空格隔開(kāi) ) G-n G-e;/ 讀入頂點(diǎn)數(shù)和邊數(shù)for (int i = 0;in;i+)/建立有 n 個(gè)頂點(diǎn)的頂點(diǎn)表cout c;/ 讀入頂點(diǎn)信息G-adjlisti.vertex = c;G-adjlisti.firs

10、tedge = NULL; /頂點(diǎn)表的邊表頭指針設(shè)為空printf( 建立邊表 n);for (k = 0;ke;k+)/ 建立邊表float cost;cout ci cj cost;/讀入邊 / 將輸入的節(jié)點(diǎn)名 (A,B,C.)轉(zhuǎn)化成內(nèi)部的下標(biāo)i = ci - A;j = cj - A;/ 將輸入的 vi-vj 這條邊插入到鄰接表頭部s = (EdgeNode*)malloc(sizeof(EdgeNode);s-src = i;s-srcName = G-adjlisti.vertex;s-adjvex = j;s-adjName = G-adjlistj.vertex;s-cost =

11、 cost;s-next = G-adjlisti.firstedge;/ 插入表頭G-adjlisti.firstedge = s;s = (EdgeNode*)malloc(sizeof(EdgeNode);s-src = j;s-srcName = G-adjlistj.vertex;s-adjvex = i;s-adjName = G-adjlisti.vertex;s-cost = cost;s-next = G-adjlist j.firstedge;G-adjlistj.firstedge = s;3. 用普利姆算法生成最小生成樹(shù)int isExists(int * visite

12、d, int n, int vex) / 判斷 vex 是否在 visited 數(shù)組里 int exists = 0;for (int i = 0; i n)/ 當(dāng)訪(fǎng)問(wèn)到所有的點(diǎn) ， 就表示整個(gè)過(guò)程結(jié)束EdgeNode * minEdge = NULL;float minCost = 9999;for (int i = 0;i adjlistvisitedNodesi.firstedge;while (p != NULL)if (isExists(visitedNodes, visitedIndex, p-adjvex) = 0 & p-cost cost;minEdge = p;p = p-

13、next;totalMinCost += minCost; chosenedgeIndex+ = *minEdge;輸出cout srcName adjName adjvex;4. 主函數(shù)int main()printf( 試驗(yàn)名稱(chēng) ： 管道鋪設(shè)施工的最佳方案問(wèn)題 n);printf( 學(xué)號(hào) ： 031350103n);printf( 姓名 ： n);printf(=n);time_t rawtime1;struct tm * timeinfo1;time (&rawtime1);timeinfo1 = localtime (&rawtime1);/ 時(shí)間函數(shù) ；printf ( 程序運(yùn)行開(kāi)始

14、 ,當(dāng)前日期和時(shí)間 : %s, asctime(timeinfo1);ALGraph* G = (ALGraph*)malloc(sizeof(ALGraph);create(G);cout 建立的圖鄰接表表示為 ： endl;for (int i = 0;in;i+)EdgeNode *p = G-adjlisti.firstedge;printf(%d-, i); / 輸出建立的鄰接表while (p != NULL)printf(%d-, p-adjvex);p = p-next;printf(n);printf( 應(yīng)用 prim 算法 ， 得到的最小生成樹(shù)是 ： );prime(G,

15、0);char kong;cin kong;/ 輸出最小生成樹(shù)return 0;time_t rawtime2;struct tm * timeinfo2;time (&rawtime2);timeinfo2 = localtime (&rawtime2);printf ( 程序運(yùn)行結(jié)束 ,當(dāng)前日期和時(shí)間 : %s, asctime(timeinfo2);五、調(diào)試分析， 每個(gè)節(jié)點(diǎn)與小區(qū)一一對(duì)應(yīng) ，權(quán)1、程序?qū)⑿^(qū)的相關(guān)信息輸入存儲(chǔ)在圖的鄰接表結(jié)構(gòu)中 值與小區(qū)之間的距離一一對(duì)應(yīng) ，只需要輸入節(jié)點(diǎn)符號(hào) ， 以及相應(yīng)的權(quán)值 ，程序會(huì)自動(dòng)輸出 相應(yīng)的最小生成樹(shù)即相應(yīng)的管道鋪設(shè)線(xiàn)路 。2、算法的時(shí)空分析

16、 ：(1)由于 create(ALGraph* G) 程序中讀入頂點(diǎn)的操作執(zhí)行了 n 次 ，讀入邊的操作執(zhí)行了 e 次 ， 故其時(shí)間復(fù)雜度為 O( n+2e )(2)prime(ALGraph * G, int from) 的時(shí)間復(fù)雜度為 O( n2 )，n 是頂點(diǎn)個(gè)數(shù) ；(3) 所有算法的空間復(fù)雜度都是 O(1).六、使用說(shuō)明用戶(hù)首先根據(jù)提示輸入節(jié)點(diǎn)數(shù) n和邊數(shù) e，應(yīng)輸入整數(shù) ，用空格隔開(kāi) ，如：9 15 ； 再根據(jù)提示輸入 n 個(gè)結(jié)點(diǎn)的名稱(chēng) ，分 n次輸入；再根據(jù)提示輸入邊的信息 ， 即兩個(gè)端點(diǎn)的名稱(chēng)及該邊的權(quán)值 ，名稱(chēng)為字符 ，權(quán)值為實(shí) 數(shù)，用空格隔開(kāi) ，如：A B 32.8 ，分 e

17、次輸入輸入完成后不需操作 ， 自動(dòng)輸出所建立的鄰接表及最小生成樹(shù)的結(jié)果七、調(diào)試結(jié)果輸入節(jié)點(diǎn)數(shù)邊數(shù) ：9 15輸入九個(gè)結(jié)點(diǎn)的名稱(chēng) ：A B C D E F G H I輸入邊的信息 ，即兩個(gè)端點(diǎn)的名稱(chēng)及該邊的權(quán)值 ：(A B 32.8 )；( B C 5.9 );(C D21.3);(D E 67.3);(A C 44.6);(A H 12.1);(A I 18.2);(H I 8.7);(H G 52.5);(C G 56.4);(C E 41.1);(E F 85.6);(D F 98.7);(I F 79.2);(E G 10.5)輸入完畢直接輸出 “建立的圖鄰接表表示為 ：0-8-7-2-

18、1-2-0-2-4-6-0-3-1-3-5-4-2-4-6-5-2-3-5-8-輸入數(shù)據(jù)時(shí)的界面(W5T0Z 9：6T = 0Z iT日1 ：fS.axa 活亠 jj 內(nèi)門(mén) q 各(JE LHPAjqsdopj ssqjoipj isiuivju p 冒石2 門(mén): 9.HH u u u fllHDJaDflo牙牙牙牙參牙牙牙牙 f LFF 11 f f Li f L f L f 匸 pl無(wú)克衣v-ta txL -w v- L4n /-Ta皿w+WT 皿w叫 叫7aaB一盾SI一一盾 一一 貿(mào)Enb嘗 冒置留哥目EBtE昌 TaUpm%ll 班血MM血址如址址血址 草學(xué)“鳳盡盡盡就民DnsDrT

19、fr9S s_zs“8 EflT TZT 9分羽ET?6-5 8_ZE3回Y8呼rH-tl 15 町 d a g昭日i S6 J d 9S8 J aTTt 3 DST0EAIR90s一 Y 7-0-尋f t-H型王口一 T T _ T 一 -尺二-=T幻J火3axalw59x8火蟲(chóng) xE87r_-li 為 -T華冒冒r宵霄 zx 業(yè)_址邇說(shuō)址逬3 T Tr Tr T TrT- 6 8 2 E s 0匕n E T - ZA -src = i;s-next = G-adjlisti.firstedge;/ 插入表頭G-adjlisti.firstedge = s;s-src = j;s-next

20、= G-adjlist j.firstedge;G-adjlistj.firstedge = s;3. 輸入所有的結(jié)點(diǎn)和邊的信息后程序運(yùn)行出錯(cuò)，如圖 ：后經(jīng)排查調(diào)試發(fā)現(xiàn)錯(cuò)誤原因是 ：在輸出圖 G的時(shí)候 ，直接用 G-adjlisti.firstedge 這 個(gè)指針 ， 并在輸出的過(guò)程中 ，不斷的修改 G-adjlisti.firstedge ， 導(dǎo)致 firstedge 最后被 修改成了 NULL ， 在后面的 Prime 算法中出現(xiàn)了空指針異常 。修改辦法是 ， 用指針 p 代替 G-adjlisti.firstedge 做遍歷 ， 防止了G-adjlisti.firstedge 被隨意修改

21、 。 經(jīng)再測(cè)試發(fā)現(xiàn)運(yùn)行正常 ， 錯(cuò)誤得到解決九 、實(shí)驗(yàn)收獲和感想 ：這次的計(jì)算機(jī)實(shí)踐題目是要求用鄰接表存儲(chǔ)無(wú)向圖再求出最小生成樹(shù)， 完成以后感覺(jué)這一次的程序是本學(xué)期計(jì)算機(jī)實(shí)踐數(shù)據(jù)結(jié)構(gòu)部分相對(duì)較難的一個(gè)題目 。 我們?cè)谡n本上給出 的程序語(yǔ)句樣例是建立有向圖 ，建立無(wú)向圖時(shí)只需要做以修改 ， 在邊表結(jié)點(diǎn)中設(shè)置兩組變 量分別存儲(chǔ)兩端的節(jié)點(diǎn) 。 這個(gè)程序只需要求最小生成樹(shù) ， 而且題目說(shuō)明了要用鄰接表存儲(chǔ) 即需求明確且不復(fù)雜 ，所以設(shè)計(jì)程序成思路明確 ，先建立鄰接表再求最小生成樹(shù) 。 再求最 小生成樹(shù)時(shí) ，有普里姆算法和克里斯卡爾算法兩種選擇， 我選擇了自己更為理解的普里姆。 寫(xiě)過(guò)調(diào)試過(guò)才對(duì)算法的算法

22、 。這也是第一次運(yùn)用這些只理解理論的算法來(lái)寫(xiě)實(shí)際的程序 精髓有了深入的理解 。完成整個(gè)程序設(shè)計(jì)使得對(duì)數(shù)據(jù)結(jié)構(gòu) 、算法的使用更加熟練 。 同時(shí)通過(guò)直接對(duì)圖的操作 ，加深了對(duì)數(shù)據(jù)結(jié)構(gòu)的理解和認(rèn)識(shí) 。 感覺(jué)自己編寫(xiě)程序的能力在一次次 實(shí)踐中有著顯著的進(jìn)步 ，要想真正理解并記住一個(gè)算法 ， 親自的編寫(xiě)程序比其他任何方法 都更加有效果 。 比如本次編程前我對(duì)于普里姆算法完全不懂 ，只知道它是用來(lái)求解最小生 成樹(shù)的 ， 卻沒(méi)有想過(guò)它的邏輯思路 ， 知道這次要用到才去查找資料學(xué)習(xí)普里姆算法， 最終在運(yùn)用中實(shí)現(xiàn)了從不會(huì)到熟練運(yùn)用的轉(zhuǎn)型 。 感覺(jué)收獲非常大 。 以后即使這門(mén)實(shí)踐課結(jié)束了 我也要經(jīng)常聯(lián)系編寫(xiě)程序

23、， 在實(shí)踐運(yùn)用中學(xué)習(xí)算法 。十、源程序#include#include#include #include#include #define MaxVertexNum 50#define MaxEdgeNum 1000/ 邊的最大值typedef struct node / 邊表節(jié)點(diǎn)int src; / 邊端的序號(hào)char srcName;/ 邊端的名稱(chēng)int adjvex;/ 鄰接點(diǎn)域node* next;/ 指向下一個(gè)鄰接點(diǎn)的指針域char adjName;float cost;/ 邊的權(quán)值EdgeNode;typedef struct/ 頂點(diǎn)表節(jié)點(diǎn)char vertex;/ 頂點(diǎn)域EdgeN

24、ode* firstedge;/ 邊表頭指針是鄰接表類(lèi)型VertexNode;typedef VertexNode AdjListMaxVertexNum;/AdjListtypedef structAdjList adjlist;/ 鄰接表int n, e;/ 頂點(diǎn)數(shù)和邊數(shù)ALGraph; /ALGraph 是以鄰接表方式存儲(chǔ)的圖類(lèi)型void create(ALGraph* G)/ 建立無(wú)向圖的鄰接表存儲(chǔ)int k, w, v;EdgeNode *s;cout 請(qǐng)輸入節(jié)點(diǎn)數(shù)和邊數(shù) (用空格隔開(kāi) ) G-n G-e;/ 讀入頂點(diǎn)數(shù)和邊數(shù)for (int i = 0;in;i+)/建立有 n 個(gè)

25、頂點(diǎn)的頂點(diǎn)表cout c; / 讀入頂點(diǎn)信息G-adjlisti.vertex = c;G-adjlisti.firstedge = NULL; /頂點(diǎn)表的邊表頭指針設(shè)為空printf( 建立邊表 n);for (k = 0;ke;k+) / 建立邊表float cost;cout ci cj cost;/讀入邊 i = ci - A;/ 將輸入的節(jié)點(diǎn)名 (A,B,C.)轉(zhuǎn)化成內(nèi)部的下標(biāo)j = cj - A;s = (EdgeNode*)malloc(sizeof(EdgeNode);/ 將輸入的 vi-vj 這條邊插入到鄰接表頭部s-src = i;s-srcName = G-adjlist

26、i.vertex;s-adjvex = j;s-adjName = G-adjlist j.vertex;s-cost = cost;s-next = G-adjlisti.firstedge;/ 插入表頭G-adjlisti.firstedge = s;s = (EdgeNode*)malloc(sizeof(EdgeNode);s-src = j;s-srcName = G-adjlist j.vertex;s-adjvex = i;s-adjName = G-adjlisti.vertex;s-cost = cost;s-next = G-adjlist j.firstedge;G-adjlistj.firstedge = s;int isExists(int * visited, int n, int vex) /判斷 vex 是否在 visited 數(shù)組里int exists = 0;for (int i = 0; i n)/ 當(dāng)訪(fǎng)問(wèn)到所有的點(diǎn) ， 就表示整個(gè)過(guò)程結(jié)束 EdgeNode * minEdge = NULL;float minCost = 9999;for (int i = 0;i adjlistvi