1、精選文檔計算機軟件技術基礎 實驗報告I數據結構實驗三：管道鋪設施工的最佳方案問題一、問題描述1.實驗題目：需要在某個城市n個居民小區之間鋪設煤氣管道，則在這n個居民小區之間只需要鋪設n-1條管道即可。假設任意兩個小區之間都可以鋪設管道，但由于地理環境不同，所需要的費用也不盡相同。選擇最優的方案能使總投資盡可能小，這個問題即為求無向網的最小生成樹。2.基本要求：在可能假設的m條管道中，選取n-1條管道，使得既能連通n個小區，又能使總投資最小。每條管道的費用以網中該邊的權值形式給出，網的存儲采用鄰接表的結構。3.測試數據：使用下圖給出的無線網數據作為程序的輸入，求出最佳鋪設方案。右側是給出的參考解

2、。圖1 小區煤氣管道鋪設網及其參考解4.輸入輸出:從鍵盤或文件讀入上圖中的無向網，以頂點對（i, j）的形式輸出最小生成樹的邊。2、 需求分析1. 本程序所能達到的基本可能： 本程序用無向網表示各小區之間的管道鋪設情況，結點表示小區位置，邊表示鋪設的管道，邊的權值表示各段的費用。采用鄰接表存儲,輸入無向網數據創建鄰接表，通過普利姆算法求出最小生成樹，即是最佳鋪設方案。2. 輸入輸出形式及輸入值范圍： 根據提示輸入總的邊數，結點數。再根據提示輸入各結點的信息即結點的名稱，輸入邊的信息，即邊的兩個端點和該邊的權值。輸入后成功創建鄰接表，自動輸出所建立的鄰接表和普利姆算法求出的最小生成樹。3. 測試

3、數據要求： 使用下圖給出的無線網數據作為程序的輸入，求出最佳鋪設方案。右側是給出的參考解。輸入結點數和邊數：9 15根據提示分別輸入九個結點的名稱：A B C D E F G H I輸入邊的信息，即兩個端點的名稱及該邊的權值：（A B 32.8）；（B C 5.9）;(C D 21.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->

4、;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”直接輸出應用prime算法，得到的最小生成樹的結果，用結點字母表示三、概要設計 為了實現上述功能，該程序以鄰接表存儲的無向圖模擬居民住宅的分布和住宅之間的管道，通

5、過普利姆算法求最小生成樹來求解管道最小花費。因此需要鄰接表這一抽象數據類型來表示無向圖。還需要普利姆算法求最小生成樹。1. 鄰接表抽象數據類型定義 ADT ALGraph  數據對象：D=ai,bi,ci|aiAdjList, biint,ciint),i =1,2.,n,n0: 數據關系：R= 基本操作:create(ALGraph* G)/建立無向圖的鄰接表存儲 void prime(ALGraph * G, int from)/用普利姆算法求最小生成樹ADT ALGraph2. ADT的c語言形式說明：typedef structAdjList adjlis

6、t;/鄰接表int n, e;/頂點數和邊數ALGraph; /ALGraph是以鄰接表方式存儲的圖類型void create(ALGraph* G)/建立無向圖的鄰接表存儲void prime(ALGraph * G, int from)/用普利姆算法求最小生成樹3.本程序保護模塊： 主函數模塊 圖模塊4. 普利姆算法分析（1）普利姆算法思想： 普利姆算法的思想是：在圖中人去一個定點k0作為開始點，令U=k0，W=V-U，其中V為圖中所有頂點集，然后找一個頂點在U中，另一個頂點在w中的邊中最短的一條，找到后，將該邊作為最小生成樹的樹邊保存起來，并將該邊頂點全部加入U集合中，并從W中刪除這些頂

7、點，然后重新調整U中頂點到W中頂點的距離，使之保持最小，再重復此過程，直到W為空集。（2）算法過程描述： 在圖G=（V，E）（V是頂點，E是邊）中，從集合V中任取一個頂點，如k0放入集合U中，這時，U=k0，集合T（E）為空。 從k0出發尋找與U中頂點相鄰權值最小的邊的另一頂點k1 ，并使k1加入U。即U=k0，k1，同時將該邊加入集合T（E）中。 重復（2），直到U=V為止。 這時T（E）中有n-1條邊，T=（U，T（E）就是一一顆最小生成樹。 5.主程序流程及其模塊調用關系: (1) 主程序流程：先提示用戶輸入相關數據：節點數，邊數，各結點名稱，各邊兩端名稱和邊的權值。創建鄰接表存儲無向圖

8、并輸出這一鄰接表。用普利姆算法求最小生成樹：訪問各節點，從已經訪問過的節點和未訪問過的節點組成的所有邊中挑出權重最小的一條邊放入鄰接表EdgeNode * minEdge 中。輸出這個最小權重的表。（2） 模塊調用關系主函數模塊判斷是否訪問過isExists(int*visited, int n, int vex) 普利姆算法求最小 生成樹模塊prime(ALGraph * G, int from)鄰接表存儲模塊create(ALGraph* G)（3） 功能模塊圖建立最小生成樹問題題信息輸入模塊最小生成樹問題管道鋪設設計問題 6.主要算法流程圖 create(ALGraph* G)開始讀入節

9、點數和邊數i=0 in讀入頂點信息結束k=k+1將新邊表結點插入到vi和vj鄰接表頭部讀入邊<v1,v2>兩個對應頂點名及權值KeK=0i=i+1四、詳細設計1、元素類型、結點類型、結點指針類型：typedef struct node /邊表節點 int src; /邊端的序號char srcName;/邊端的名稱int adjvex;/鄰接點域node* next;/指向下一個鄰接點的指針域char adjName;float cost;/邊的權值EdgeNode;typedef struct /頂點表節點 char vertex;/頂點域EdgeNode* firstedge;

10、/邊表頭指針VertexNode;typedef VertexNode AdjListMaxVertexNum;/AdjList是鄰接表類型typedef structAdjList adjlist;/鄰接表int n, e;/頂點數和邊數ALGraph; /ALGraph是以鄰接表方式存儲的圖類型2. 創建鄰接表void create(ALGraph* G)/建立無向圖的鄰接表存儲int k, w, v;EdgeNode *s;cout << "請輸入節點數和邊數（用空格隔開）" << endl;cin >> G->n >&

11、gt; G->e;/讀入頂點數和邊數for (int i = 0;i<G->n;i+)/建立有n個頂點的頂點表cout << "請輸入頂點名稱："char c;cin >> c; /讀入頂點信息G->adjlisti.vertex = c;G->adjlisti.firstedge = NULL; /頂點表的邊表頭指針設為空printf("建立邊表n");for (k = 0;k<G->e;k+) /建立邊表float cost;cout << "請輸入邊的信息（頂點

12、1 頂點2 權值）"char ci, cj;int i=-1, j=-1;cin >> ci >> cj >> cost;/讀入邊<vi,vj的頂點對應名稱> /將輸入的節點名(A,B,C.)轉化成內部的下標i = ci - 'A'j = cj - 'A' /將輸入的vi-vj這條邊插入到鄰接表頭部s = (EdgeNode*)malloc(sizeof(EdgeNode);s->src = i;s->srcName = G->adjlisti.vertex;s->adjvex =

13、 j;s->adjName = G->adjlistj.vertex;s->cost = 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-&

14、gt;next = G->adjlistj.firstedge;G->adjlistj.firstedge = s;3. 用普利姆算法生成最小生成樹int isExists(int * visited, int n, int vex) /判斷vex是否在visited數組里int exists = 0;for (int i = 0; i < n; i+)if (visitedi = vex)exists = 1;return exists;void prime(ALGraph * G, int from)/用普利姆算法求最小生成樹int visitedNodesMaxVert

15、exNum;int visitedIndex = 0;visitedNodesvisitedIndex+ = from;EdgeNode chosenMaxEdgeNum;int edgeIndex = 0;float totalMinCost = 0; while (visitedIndex != G->n)/當訪問到所有的點，就表示整個過程結束EdgeNode * minEdge = NULL;float minCost = 9999; for (int i = 0;i < visitedIndex;i+) /從已經訪問過的節點和未訪問過的節點組成的所有邊中挑出權重最小的一條邊

16、EdgeNode * p = G->adjlistvisitedNodesi.firstedge;while (p != NULL)if (isExists(visitedNodes, visitedIndex, p->adjvex) = 0 && p->cost < minCost)minCost = p->cost;minEdge = p;p = p->next;totalMinCost += minCost;chosenedgeIndex+ = *minEdge; cout << minEdge->srcName &l

17、t;< "->" << minEdge->adjName <<endl;/輸出這條最小權重的表visitedNodesvisitedIndex+ = minEdge->adjvex;4. 主函數int main()printf("試驗名稱：管道鋪設施工的最佳方案問題n"); printf("學號：031350103n"); printf("姓名：n"); printf("=n"); time_t rawtime1; struct tm * time

18、info1; time (&rawtime1); timeinfo1 = localtime (&rawtime1); /時間函數；printf ("程序運行開始,當前日期和時間: %s", asctime(timeinfo1);ALGraph* G = (ALGraph*)malloc(sizeof(ALGraph);create(G);cout << "建立的圖鄰接表表示為："<<endl;for (int i = 0;i< G->n;i+)EdgeNode *p = G->adjlisti.

19、firstedge;printf("%d->", i); /輸出建立的鄰接表while (p != NULL)printf("%d->", p->adjvex);p = p->next;printf("n");printf("應用prim算法，得到的最小生成樹是：");prime(G, 0);char kong;cin >> kong;/輸出最小生成樹 return 0; time_t rawtime2; struct tm * timeinfo2; time (&raw

20、time2); timeinfo2 = localtime (&rawtime2); printf ("程序運行結束,當前日期和時間: %s", asctime(timeinfo2); 五、調試分析 1、程序將小區的相關信息輸入存儲在圖的鄰接表結構中，每個節點與小區一一對應，權值與小區之間的距離一一對應，只需要輸入節點符號，以及相應的權值，程序會自動輸出相應的最小生成樹即相應的管道鋪設線路。2、算法的時空分析：(1)由于 create(ALGraph* G)程序中讀入頂點的操作執行了n次，讀入邊的操作執行了e次，故其時間復雜度為O（n+2e）（2）prime(ALG

21、raph * G, int from)的時間復雜度為O（n2），n是頂點個數；（3）所有算法的空間復雜度都是O(1).六、使用說明 用戶首先根據提示輸入節點數n和邊數e，應輸入整數，用空格隔開，如：9 15；再根據提示輸入n個結點的名稱，分n次輸入； 再根據提示輸入邊的信息，即兩個端點的名稱及該邊的權值，名稱為字符，權值為實數，用空格隔開，如：A B 32.8，分e次輸入 輸入完成后不需操作，自動輸出所建立的鄰接表及最小生成樹的結果七、調試結果 輸入節點數邊數：9 15 輸入九個結點的名稱：A B C D E F G H I 輸入邊的信息，即兩個端點的名稱及該邊的權值：（A B 32.8）；（

22、B C 5.9）;(C D 21.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->1->2->0->2->4->6->0->3->1->3->5->4->2->4->6->5->2->3-&

23、gt;5->8->3->4->6->4->2->7->7->6->8->0->8->5->7->0” 輸出“應用prim算法，得到的最小生成樹是：A->H H->I A->B B->C C->D C->E E->G I->F”初始界面為：輸入數據時的界面：輸出界面：八、遇到的問題和解決方法：1最初拿到這個題目時還不會普利姆算法的具體內容，只知道求最小生成樹的兩個方法叫普利姆算法和克里斯卡爾算法，但不理解也不會寫代碼。于是我上網查閱了相關資料，還請教了上機時給

24、我們輔導的研究生學長，學會了prim算法。2.開始建立鄰接表的時候我是照著軟件技術基礎教程課本上給的鄰接表存儲有向圖的代碼修改的，想讓它存儲無向圖，但開始只是在創建邊表結點時設置了兩個char型變量存放兩個名稱和兩個int型變量存儲序號，后面不知道怎么改，后經助教學長指點知create(ALGraph* G)中對應改動，將新表結點插入到vi的邊表頭部這里的操作是雙向的才能保證圖是無向的，即，插入到vi后一次，插入到vj后一次，如這段代碼所示s->src = i;s->next = G->adjlisti.firstedge; /插入表頭 G->adjlisti.firs

25、tedge = s;s->src = j;s->next = G->adjlistj.firstedge;G->adjlistj.firstedge = s;3. 輸入所有的結點和邊的信息后程序運行出錯，如圖： 后經排查調試發現錯誤原因是：在輸出圖G的時候，直接用G->adjlisti.firstedge 這個指針， 并在輸出的過程中，不斷的修改G->adjlisti.firstedge ，導致firstedge最后被修改成了NULL， 在后面的Prime算法中出現了空指針異常。 修改辦法是，用指針p代替G->adjlisti.firstedge做遍歷

26、，防止了G->adjlisti.firstedge被隨意修改。經再測試發現運行正常，錯誤得到解決。9、 實驗收獲和感想： 這次的計算機實踐題目是要求用鄰接表存儲無向圖再求出最小生成樹，完成以后感覺這一次的程序是本學期計算機實踐數據結構部分相對較難的一個題目。我們在課本上給出的程序語句樣例是建立有向圖，建立無向圖時只需要做以修改，在邊表結點中設置兩組變量分別存儲兩端的節點。這個程序只需要求最小生成樹，而且題目說明了要用鄰接表存儲，即需求明確且不復雜，所以設計程序成思路明確，先建立鄰接表再求最小生成樹。再求最小生成樹時，有普里姆算法和克里斯卡爾算法兩種選擇，我選擇了自己更為理解的普里姆算法。

27、這也是第一次運用這些只理解理論的算法來寫實際的程序。寫過調試過才對算法的精髓有了深入的理解。完成整個程序設計使得對數據結構、算法的使用更加熟練。同時通過直接對圖的操作，加深了對數據結構的理解和認識。感覺自己編寫程序的能力在一次次實踐中有著顯著的進步，要想真正理解并記住一個算法，親自的編寫程序比其他任何方法都更加有效果。比如本次編程前我對于普里姆算法完全不懂，只知道它是用來求解最小生成樹的，卻沒有想過它的邏輯思路，知道這次要用到才去查找資料學習普里姆算法，最終在運用中實現了從不會到熟練運用的轉型。感覺收獲非常大。以后即使這門實踐課結束了，我也要經常聯系編寫程序，在實踐運用中學習算法。十、源程序#

28、include<stdio.h>#include<iostream.h>#include <malloc.h>#include<string.h>#include <time.h>#define MaxVertexNum 50 #define MaxEdgeNum 1000/邊的最大值typedef struct node /邊表節點 int src; /邊端的序號char srcName;/邊端的名稱int adjvex;/鄰接點域node* next;/指向下一個鄰接點的指針域char adjName;float cost;/邊的

29、權值EdgeNode;typedef struct /頂點表節點 char vertex;/頂點域EdgeNode* firstedge;/邊表頭指針VertexNode;typedef VertexNode AdjListMaxVertexNum;/AdjList是鄰接表類型typedef structAdjList adjlist;/鄰接表int n, e;/頂點數和邊數ALGraph; /ALGraph是以鄰接表方式存儲的圖類型void create(ALGraph* G)/建立無向圖的鄰接表存儲int k, w, v;EdgeNode *s;cout << "請輸

30、入節點數和邊數（用空格隔開）" << endl;cin >> G->n >> G->e;/讀入頂點數和邊數for (int i = 0;i<G->n;i+)/建立有n個頂點的頂點表cout << "請輸入頂點名稱："char c;cin >> c; /讀入頂點信息G->adjlisti.vertex = c;G->adjlisti.firstedge = NULL; /頂點表的邊表頭指針設為空printf("建立邊表n");for (k = 0;k&

31、lt;G->e;k+) /建立邊表float cost;cout << "請輸入邊的信息（頂點1 頂點2 權值）"char ci, cj;int i=-1, j=-1;cin >> ci >> cj >> cost;/讀入邊<vi,vj的頂點對應名稱>i = ci - 'A'/將輸入的節點名(A,B,C.)轉化成內部的下標j = cj - 'A' s = (EdgeNode*)malloc(sizeof(EdgeNode); /將輸入的vi-vj這條邊插入到鄰接表頭部s->

32、;src = i;s->srcName = G->adjlisti.vertex;s->adjvex = j;s->adjName = G->adjlistj.vertex;s->cost = 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 =

33、i;s->adjName = G->adjlisti.vertex;s->cost = cost;s->next = G->adjlistj.firstedge;G->adjlistj.firstedge = s; int isExists(int * visited, int n, int vex) /判斷vex是否在visited數組里int exists = 0;for (int i = 0; i < n; i+)if (visitedi = vex)exists = 1;return exists;void prime(ALGraph * G,

34、 int from)/用普利姆算法求最小生成樹int visitedNodesMaxVertexNum;int visitedIndex = 0;visitedNodesvisitedIndex+ = from;EdgeNode chosenMaxEdgeNum;int edgeIndex = 0;float totalMinCost = 0; while (visitedIndex != G->n)/當訪問到所有的點，就表示整個過程結束EdgeNode * minEdge = NULL;float minCost = 9999; for (int i = 0;i < visitedIndex;i+) /從已經訪問過的節點和未訪問過的節點組成的所有邊中挑出權重最小的一條邊EdgeNode * p = G->adjlistvisitedNodesi.firstedge;while (p != NULL)if (isExists(visitedNodes, visitedIndex, p->adjvex) = 0 && p