構(gòu)造使n個(gè)城市連接的最小生成樹(shù)課程設(shè)計(jì)報(bào)告

1、構(gòu)造可以使N個(gè)城市連接的最小生成樹(shù)一、課程設(shè)計(jì)目的及基本要求本課程設(shè)計(jì)是為了配合計(jì)算機(jī)軟件基礎(chǔ)課程的開(kāi)設(shè)，通過(guò)設(shè)計(jì)一完整的程序使學(xué)生能達(dá)到如下要求，了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力，使學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的應(yīng)用、算法的編寫(xiě)、類C語(yǔ)言的算法轉(zhuǎn)換成C程序并用上機(jī)調(diào)試的基本方法?；疽螅?. 城市間的道路網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義采用課本中給出的定義，若兩個(gè)城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無(wú)窮大值。2. 顯示出城市間道路網(wǎng)的鄰接矩陣。3. 最小生成樹(shù)中包括的邊及其權(quán)值，并顯示得到的最小生成樹(shù)的總代價(jià)。二、課程設(shè)計(jì)的主要任務(wù) 1. 設(shè)計(jì)的

2、任務(wù)給定一個(gè)地區(qū)的n個(gè)城市間的距離網(wǎng)，用Prim算法或Kruskal算法建立最小生成樹(shù)，并計(jì)算得到的最小生成樹(shù)的代價(jià)。2. 程序執(zhí)行命令輸入城市數(shù)、道路數(shù)輸入城市名輸入道路信息執(zhí)行Kruskal 算法執(zhí)行 Prim 算法輸出最小生成樹(shù)3、 概要設(shè)計(jì) 1. 抽象數(shù)據(jù)類型結(jié)構(gòu)體數(shù)組的定義：#ifndef ADJACENCYMATRIXED/防止該頭文件被重復(fù)引用#define ADJACENCYMATRIXED/而引起的數(shù)據(jù)重復(fù)定義#define INFINITY32767/最大值#define MAX_VERTEX_NUM20/最大頂點(diǎn)個(gè)數(shù)typedef intVRType;/權(quán)值，即邊的值ty

3、pedef charInfoType;/附加信息的類型，后面使用時(shí)會(huì)定義成一個(gè)指針typedef charVertexTypeMAX_VERTEX_NUM;/頂點(diǎn)類型typedef enum DG=1, DN, UDG, UDN GraphKind;/有向圖，有向網(wǎng)，無(wú)向圖，無(wú)向網(wǎng)typedef struct ArcCellVRTypeadj;/VRType 是頂點(diǎn)關(guān)系類型。對(duì)無(wú)權(quán)圖，用 1 或 0 表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型。InfoType*info;/該弧關(guān)系信息的指針ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef s

4、tructVertexTypevexsMAX_VERTEX_NUM;/頂點(diǎn)向量AdjMatrixarcs;/鄰接矩陣intvexnum, arcnum;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)GraphKindkind;/圖的種類標(biāo)志MGraph;typedef struct/普里姆算法輔助數(shù)組的定義VertexTypeadjvex;VRTypelowcost;closedgeMAX_VERTEX_NUM;#endif/結(jié)束if 2. 程序模塊MGraph G;/網(wǎng) G，唯一的全局變量int main(int argc, char * argv);/主函數(shù)Status LocateVex(MGraph G, V

5、ertexType v);/判斷城市 v 在網(wǎng) G 中的位置Status CreateUDN(MGraph &G);/創(chuàng)建網(wǎng) G 的鄰接矩陣void DisplayNet(MGraph G);/以鄰接矩陣的形式顯示網(wǎng) Gvoid MiniSpanTree_KRUSKAL(MGraph G);/最小生成樹(shù)的 Kruskal 算法void MiniSpanTree_PRIM(MGraph G, VertexType u);/最小生成樹(shù)的 Prim 算法Status Minimum(closedge closeEdge, int n); /Prim 算法中求下一個(gè)城市的函數(shù)void Dele

6、teInfo(MGraph &G);/釋放堆內(nèi)存上動(dòng)態(tài)申請(qǐng)的空間 3. 流程圖創(chuàng)建用鄰接矩陣表示的城市道路網(wǎng)輸入城市數(shù)G.vexnum、道路數(shù)G.arcnum輸入城市名G.vexsi輸入表示道路的兩個(gè)城市及道路值G.arcsij.adj返回 OK圖3-1 創(chuàng)建鄰接矩陣的流程圖(N-S圖)Prim算法化輔助數(shù)組closeEdgefor (i=1; i<G.vexnum; +i)求下一個(gè)城市k = Minimum(closeEdge, G.vexnum)輸出找到的道路標(biāo)記城市，避免重復(fù)輸出總耗費(fèi)圖3-2 Prim算法流程圖（N-S圖）4、 詳細(xì)設(shè)計(jì)1. 數(shù)據(jù)類型定義為了用鄰接矩陣表示

7、圖 G ，先是定義二維數(shù)組的每一個(gè)元素含道路值然后在圖的定義中定義一個(gè)此二維數(shù)組的結(jié)構(gòu)成員。并且在圖中還定義一個(gè)用來(lái)存放城市的一維數(shù)組及int 型的城市數(shù)級(jí)道路數(shù)。用二維數(shù)組的兩個(gè)下標(biāo)表示道路，這兩個(gè)下標(biāo)又在一位數(shù)組中對(duì)應(yīng)兩個(gè)城市。這樣就建立起了一個(gè)城市到城市之間的道路網(wǎng)。2. 程序主要模塊說(shuō)明：該程序共含5個(gè)模塊，本人負(fù)責(zé)其中2個(gè)模塊構(gòu)造：如圖3-1創(chuàng)建鄰接矩陣的流程圖(N-S圖) ，初始化圖G*LocateVex(MGraph G, VertexType v)*Status LocateVex(MGraph G, VertexType v);while (strcmp(G.vexsi, v

8、) i+;返回 i；* CreateUDN*輸入城市數(shù)、道路數(shù)；for (i=0; i<城市數(shù); +i) 輸入城市名；for (i=0; i<城市數(shù); +i)for(j=0; j<城市數(shù); +j)初始化鄰接矩陣：道路值= INFINITY;for (i=0; i<城市數(shù); +i)for(j=0; j<城市數(shù); +j)輸入兩個(gè)城市表示道路，輸入道路值；圖3-2 Prim算法* MiniSpanTree_PRIM*void MiniSpanTree_PRIM(MGraph G, VertexType u)定義輔助數(shù)組：closedge closeEdge;初始化：st

9、rcpy(closeEdgej.adjvex, u);closeEdgej.lowcost = G.arcskj.adj;for (i=1; i<G.vexnum; +i)在其余G.vexnum-1個(gè)城市中找到離輔助數(shù)組中標(biāo)記的道路最小值；顯示找到的道路；標(biāo)記新找到的城市；* Minimum*Status Minimum(closedge closeEdge, int n)在輔助數(shù)組中找到道路值最小的道路的兩點(diǎn)城市：if (closeEdgei.lowcost != 0) && (minTemp > closeEdgei.lowcost)返回該城市在 G 中的位置5

10、、 調(diào)試分析和測(cè)試結(jié)果 1. 調(diào)試分析 （1）鄰接矩陣初始化本函數(shù)的主要功能是對(duì)無(wú)向網(wǎng)進(jìn)行鄰接矩陣的初始化。構(gòu)造這種具有n個(gè)頂點(diǎn)和e條邊的無(wú)向網(wǎng)時(shí)，關(guān)鍵需要考慮其時(shí)間復(fù)雜度O（n+e*n）,其中對(duì)鄰接矩陣G.arcs的初始化花費(fèi)了O（n）的時(shí)間。 （2）Prim 算法Prim 算法的思路是逐步將城市納入生成樹(shù)中，這里面的關(guān)鍵步驟是要找到下一個(gè)城市。于是通過(guò)討教別人，寫(xiě)了Status Minimum(closedge closeEdge, int n)函數(shù)，這樣就可以在輔助數(shù)組中找到道路值最小的道路的兩點(diǎn)城市了。2. 測(cè)試結(jié)果圖5-1 鄰接矩陣初始化運(yùn)行顯示界面圖5-2 Prim算法運(yùn)行顯示界面

11、六、總結(jié)通過(guò)課程設(shè)計(jì)，終于圓滿完成了課程設(shè)計(jì)的任務(wù)，我也有不少收獲。既鞏固和加深了對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，認(rèn)識(shí)到計(jì)算機(jī)軟件基礎(chǔ)課程是計(jì)算機(jī)專業(yè)一門重要的專業(yè)技術(shù)基礎(chǔ)課程，還提高了我綜合運(yùn)用本課程所學(xué)知識(shí)的能力。而且，并不是單純的看看教材就能解決我們的實(shí)際問(wèn)題，所以還要去查找各種我們所需要的資料，所以這次課程設(shè)計(jì)也培養(yǎng)了我選用參考書(shū)，查閱手冊(cè)及文獻(xiàn)資料的能力。要完成一個(gè)課程設(shè)計(jì)的課題并不是一次就能編譯成功的，中間會(huì)出現(xiàn)很多的大問(wèn)題小問(wèn)題，改錯(cuò)是個(gè)很繁瑣的問(wèn)題。通過(guò)這次課程設(shè)計(jì)培養(yǎng)了我獨(dú)立思考，深入研究，分析問(wèn)題，解決問(wèn)題的能力。在以后的學(xué)習(xí)過(guò)程中我將要注意以下幾點(diǎn)：1、認(rèn)真上好專業(yè)實(shí)驗(yàn)課，多在實(shí)踐中鍛

12、煉自己。2、寫(xiě)程序的過(guò)程要考慮周到，嚴(yán)密。3、在做設(shè)計(jì)的時(shí)候要有信心，有耐心，切勿浮躁。4、認(rèn)真的學(xué)習(xí)課本知識(shí)，掌握課本中的知識(shí)點(diǎn)，并在此基礎(chǔ)上學(xué)會(huì)靈活運(yùn)用。5、在課余時(shí)間里多寫(xiě)程序，熟練掌握在調(diào)試程序的過(guò)程中所遇到的常見(jiàn)錯(cuò)誤，以便能節(jié)省調(diào)試程序的時(shí)間。七、附錄/main#include <iostream.h>#include <stdio.h>#include <string.h>#include <windows.h>#include "TypeDefine.h"#include "AdjacencyMatri

13、x.h"#include "InitializeFunction.h"#include "MiniSpanTree_KRUSKAL.h"#include "MiniSpanTree_PRIM.h"#include "DisplayNet.h"#include "DeleteInfo.h"MGraph G;/全局變量Gint main(int argc, char * argv);/主函數(shù)Status LocateVex(MGraph G, VertexType v);/判斷城市 v 在

14、網(wǎng) G 中的位置Status CreateUDN(MGraph &G);/創(chuàng)建網(wǎng) G 的鄰接矩陣void DisplayNet(MGraph G);/以鄰接矩陣的形式顯示網(wǎng) Gvoid MiniSpanTree_KRUSKAL(MGraph G);/最小生成樹(shù)的 Kruskal 算法void MiniSpanTree_PRIM(MGraph G, VertexType u);/最小生成樹(shù)的 Prim 算法Status Minimum(closedge closeEdge, int n);/Prim 算法中求下一個(gè)城市的函數(shù)void DeleteInfo(MGraph &G);/

15、釋放堆內(nèi)存上動(dòng)態(tài)申請(qǐng)的空間int main(int argc, char * argv)CreateGraph(G);DisplayNet(G);MiniSpanTree_KRUSKAL(G);MiniSpanTree_PRIM(G, G.vexs0);DeleteInfo(G);cout<<endl<<endl;system("pause");return 0;/intializeFunction.hStatus CreateDG(MGraph &G)return 0;Status CreateDN(MGraph &G)return

16、 0;Status CreateUDG(MGraph &G)return 0;Status CreateUDN(MGraph &G);Status LocateVex(MGraph G, VertexType v)/判斷輸入的頂點(diǎn)v在G中的位置。/根據(jù)頂點(diǎn)的類型，可重載此函數(shù)。目前為charint i=0;while (strcmp(G.vexsi, v) i+;return i;Status CreateGraph(MGraph &G)/采用數(shù)組（鄰接矩陣）表示法，構(gòu)造圖G.G.kind = UDN;/默認(rèn)構(gòu)造無(wú)向網(wǎng)/*printf("+n");p

17、rintf("|1:有向圖 2:無(wú)向圖 3:有向網(wǎng) 4:無(wú)向網(wǎng)n");printf("|請(qǐng)選擇: bb");scanf("%d", &G.kind);printf("+n");*/switch (G.kind)case DG: return CreateDG(G);/構(gòu)造有向圖Gcase DN: return CreateDN(G);/構(gòu)造有向網(wǎng)Gcase UDG: return CreateUDG(G);/構(gòu)造無(wú)向圖Gcase UDN: return CreateUDN(G);/構(gòu)造無(wú)向網(wǎng)Gdefault

18、 : return ERROR;/CreateGraphStatus CreateUDN(MGraph &G)/采用數(shù)組（鄰接矩陣）表示法，構(gòu)造圖G.int i, j, k;VertexType v1, v2;VRType w;printf(" 構(gòu)造可以使N個(gè)城市連接的最小生成樹(shù)n");printf("請(qǐng)輸入城市數(shù)、道路數(shù)(至少6個(gè)城市，10條道路)：");cin>>G.vexnum>>G.arcnum;for (i=0; i<G.vexnum; +i)/構(gòu)造頂點(diǎn)向量printf("請(qǐng)輸入第 %d 個(gè)城市名

19、（共 %d 個(gè)）:", i+1, G.vexnum);cin>>G.vexsi;for (i=0; i<G.vexnum; +i)/初始化鄰接矩陣for (j=0; j<G.vexnum; +j)G.arcsij.adj = INFINITY;/G. = NULL;printf("請(qǐng)輸入一條道路連接的兩個(gè)城市名及權(quán)值:n");for (k=0; k<G.arcnum; +k)/構(gòu)造鄰接矩陣printf("共%3d條道路，第%3d條道路：", G.arcnum,k+1);cin>>v

20、1>>v2>>w;/輸入一條邊依附的頂點(diǎn)及權(quán)值i = LocateVex(G, v1);/確定v1、v2在G中的位置j = LocateVex(G, v2);G.arcsij.adj = w;/弧<v1,v2>的權(quán)值G.arcsji = G.arcsij;/置<v1,v2>的對(duì)稱弧<v2,v1>return OK;/CreateUDN/MiniSpan Tree PRIM.hStatus Minimum(closedge closeEdge, int n)int i, flag, minTemp = INFINITY;for (i=0

21、; i<n; +i)if (closeEdgei.lowcost != 0) && (minTemp > closeEdgei.lowcost)minTemp = closeEdgei.lowcost;flag = i;return flag;void MiniSpanTree_PRIM(MGraph G, VertexType u)/用普里姆算法從第 u 個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng) G 的最小生成樹(shù) T，輸出 T 的各條邊。/記錄從頂點(diǎn)集 U 到 V-U 的代價(jià)最小的邊的輔助數(shù)組定義見(jiàn) "AdjacencyMatrix.h"int i, j, k, totalCost=0;closedge closeEdge;k = LocateVex(G, u);for (j=0; j<G.vexnum; +j)/輔助數(shù)組初始化if (j != k)strcpy(closeEdgej.adjvex, u);closeEdgej.lowcost = G.arcskj.adj;cout<&l