(圖論編程題3參考)構(gòu)成可以使n個城市連接的最小生成樹.doc

目錄一需求分析21.1 設(shè)計(jì)的任務(wù)21.2 程序所能達(dá)到的功能21.3 程序執(zhí)行命令2二概要設(shè)計(jì)32.1 抽象數(shù)據(jù)類型結(jié)構(gòu)體數(shù)組的定義：32.2 程序模塊42.3流程圖4三詳細(xì)設(shè)計(jì)53.1 數(shù)據(jù)類型定義53.2 程序主要模塊5四調(diào)試分析和測試結(jié)果84.1 調(diào)試分析84.2測試結(jié)果9五總結(jié)10六參考文獻(xiàn)10七致謝11八附錄11構(gòu)造可以使N個城市連接的最小生成樹一需求分析1.1 設(shè)計(jì)的任務(wù)給定一個地區(qū)的n個城市間的距離網(wǎng)，用Prim算法或Kruskal算法建立最小生成樹，并計(jì)算得到的最小生成樹的代價(jià)。1.2 程序所能達(dá)到的功能1.2.1 城市間的道路網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲結(jié)構(gòu)定義采用課本中給出的定義，若兩個城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無窮大值。1.2.2 顯示出城市間道路網(wǎng)的鄰接矩陣。1.2.3 最小生成樹中包括的邊及其權(quán)值，并顯示得到的最小生成樹的總代價(jià)。1.3 程序執(zhí)行命令輸入城市數(shù)、道路數(shù)輸入城市名輸入道路信息執(zhí)行Kruskal 算法執(zhí)行 Prim 算法輸出最小生成樹二概要設(shè)計(jì) 2.1 抽象數(shù)據(jù)類型結(jié)構(gòu)體數(shù)組的定義：#ifndef ADJACENCYMATRIXED/防止該頭文件被重復(fù)引用#define ADJACENCYMATRIXED/而引起的數(shù)據(jù)重復(fù)定義#define INFINITY32767/最大值#define MAX_VERTEX_NUM20/最大頂點(diǎn)個數(shù)typedef intVRType;/權(quán)值，即邊的值typedef charInfoType;/附加信息的類型，后面使用時會定義成一個指針typedef charVertexTypeMAX_VERTEX_NUM;/頂點(diǎn)類型typedef enum DG=1, DN, UDG, UDN GraphKind;/有向圖，有向網(wǎng)，無向圖，無向網(wǎng)typedef struct ArcCellVRTypeadj;/VRType 是頂點(diǎn)關(guān)系類型。對無權(quán)圖，用 1 或 0 表示相鄰否；對帶權(quán)圖，則為權(quán)值類型。InfoType*info;/該弧關(guān)系信息的指針ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexTypevexsMAX_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é)束if2.2 程序模塊MGraph G;/網(wǎng) G，唯一的全局變量int main(int argc, char * argv);/主函數(shù)Status LocateVex(MGraph G, VertexType 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);/最小生成樹的 Kruskal 算法void MiniSpanTree_PRIM(MGraph G, VertexType u);/最小生成樹的 Prim 算法Status Minimum(closedge closeEdge, int n); /Prim 算法中求下一個城市的函數(shù)void DeleteInfo(MGraph &G);/釋放堆內(nèi)存上動態(tài)申請的空間2.3流程圖創(chuàng)建用鄰接矩陣表示的城市道路網(wǎng)輸入城市數(shù)G.vexnum、道路數(shù)G.arcnum輸入城市名G.vexsi輸入表示道路的兩個城市及道路值G.arcsij.adj返回 OK2.3.1創(chuàng)建鄰接矩陣的流程圖(N-S圖)Prim算法化輔助數(shù)組closeEdgefor (i=1; iG.vexnum; +i)求下一個城市k = Minimum(closeEdge, G.vexnum)輸出找到的道路標(biāo)記城市，避免重復(fù)輸出總耗費(fèi)圖2.3.2Prim算法流程圖（N-S圖）三詳細(xì)設(shè)計(jì)3.1 數(shù)據(jù)類型定義為了用鄰接矩陣表示圖 G ，先是定義二維數(shù)組的每一個元素含道路值然后在圖的定義中定義一個此二維數(shù)組的結(jié)構(gòu)成員。并且在圖中還定義一個用來存放城市的一維數(shù)組及int 型的城市數(shù)級道路數(shù)。用二維數(shù)組的兩個下標(biāo)表示道路，這兩個下標(biāo)又在一位數(shù)組中對應(yīng)兩個城市。這樣就建立起了一個城市到城市之間的道路網(wǎng)。3.2 程序主要模塊說明：該程序共含5個模塊，本人負(fù)責(zé)其中2個模塊構(gòu)造：3.2.1 初始化圖G*LocateVex(MGraph G, VertexType v)*Status LocateVex(MGraph G, VertexType v);while (strcmp(G.vexsi, v) 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)輸入兩個城市表示道路，輸入道路值；3.2.2PRIM算法* MiniSpanTree_PRIM*void MiniSpanTree_PRIM(MGraph G, VertexType u)定義輔助數(shù)組：closedge closeEdge;初始化：strcpy(closeEdgej.adjvex, u);closeEdgej.lowcost = G.arcskj.adj;for (i=1; i closeEdgei.lowcost)返回該城市在 G 中的位置四調(diào)試分析和測試結(jié)果4.1 調(diào)試分析4.1.1鄰接矩陣初始化本函數(shù)的主要功能是對無向網(wǎng)進(jìn)行鄰接矩陣的初始化。構(gòu)造這種具有n個頂點(diǎn)和e條邊的無向網(wǎng)時，關(guān)鍵需要考慮其時間復(fù)雜度O（n+e*n）,其中對鄰接矩陣G.arcs的初始化花費(fèi)了O（n）的時間。4.1.2 Prim 算法Prim 算法的思路是逐步將城市納入生成樹中，這里面的關(guān)鍵步驟是要找到下一個城市。于是通過討教別人，寫了Status Minimum(closedge closeEdge, int n)函數(shù)，這樣就可以在輔助數(shù)組中找到道路值最小的道路的兩點(diǎn)城市了。4.2測試結(jié)果圖4.2.1鄰接矩陣初始化運(yùn)行顯示界面圖4.2.2Prim算法運(yùn)行顯示界面五總結(jié)通過本周的課程設(shè)計(jì)，我們小組終于圓滿完成了課程設(shè)計(jì)的任務(wù)，我也有不少收獲。既鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解，認(rèn)識到數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)一門重要的專業(yè)技術(shù)基礎(chǔ)課程，還提高了我綜合運(yùn)用本課程所學(xué)知識的能力。而且，并不是單純的看看教材就能解決我們的實(shí)際問題，所以還要去查找各種我們所需要的資料，所以這次課程設(shè)計(jì)也培養(yǎng)了我選用參考書，查閱手冊及文獻(xiàn)資料的能力。要完成一個課程設(shè)計(jì)的課題并不是一次就能編譯成功的，中間會出現(xiàn)很多的大問題小問題，改錯是個很繁瑣的問題。通過這次課程設(shè)計(jì)培養(yǎng)了我獨(dú)立思考，深入研究，分析問題，解決問題的能力。在以后的學(xué)習(xí)過程中我將要注意以下幾點(diǎn)：1、認(rèn)真上好專業(yè)實(shí)驗(yàn)課，多在實(shí)踐中鍛煉自己。2、寫程序的過程要考慮周到，嚴(yán)密。3、在做設(shè)計(jì)的時候要有信心，有耐心，切勿浮躁。4、認(rèn)真的學(xué)習(xí)課本知識，掌握課本中的知識點(diǎn)，并在此基礎(chǔ)上學(xué)會靈活運(yùn)用。5、在課余時間里多寫程序，熟練掌握在調(diào)試程序的過程中所遇到的常見錯誤，以便能節(jié)省調(diào)試程序的時間。六參考文獻(xiàn)1.嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）. 清華大學(xué)出版社，20072.譚浩強(qiáng)，張基溫. C語言程序設(shè)計(jì)教程（第三版）北京：高等教育出版社，20063.陳維新，林小茶. C+面向?qū)ο蟪绦蛟O(shè)計(jì)教程. 北京：清華大學(xué)出版社，20044.蘇仕華等.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì). 北京： 機(jī)械工業(yè)出版社，2005七致謝感謝梁英老師對我們數(shù)據(jù)結(jié)構(gòu)課程及其實(shí)驗(yàn)的悉心指導(dǎo)，正是因?yàn)槔蠋熢趯?shí)驗(yàn)課上的指導(dǎo)，讓我能夠把書本上的知識化成自己的知識，并運(yùn)用在編程的過程中。感謝同學(xué)在我的設(shè)計(jì)過程中提出的寶貴意見，如果沒有他們的幫助，我在設(shè)計(jì)過程中出現(xiàn)的一些錯誤可能無法迅速查出解決，你們的幫助為我節(jié)省了寶貴的時間。 衷心感謝！八附錄/main#include #include #include #include #include TypeDefine.h#include AdjacencyMatrix.h#include InitializeFunction.h#include MiniSpanTree_KRUSKAL.h#include MiniSpanTree_PRIM.h#include DisplayNet.h#include DeleteInfo.hMGraph G;/全局變量Gint main(int argc, char * argv);/主函數(shù)Status LocateVex(MGraph G, VertexType 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);/最小生成樹的 Kruskal 算法void MiniSpanTree_PRIM(MGraph G, VertexType u);/最小生成樹的 Prim 算法Status Minimum(closedge closeEdge, int n);/Prim 算法中求下一個城市的函數(shù)void DeleteInfo(MGraph &G);/釋放堆內(nèi)存上動態(tài)申請的空間int main(int argc, char * argv)CreateGraph(G);DisplayNet(G);MiniSpanTree_KRUSKAL(G);MiniSpanTree_PRIM(G, G.vexs0);DeleteInfo(G);coutendlG.vexnumG.arcnum;for (i=0; iG.vexsi;for (i=0; iG.vexnum; +i)/初始化鄰接矩陣for (j=0; jG.vexnum; +j)G.arcsij.adj = INFINITY;/G. = NULL;printf(請輸入一條道路連接的兩個城市名及權(quán)值:n);for (k=0; kv1v2w;/輸入一條邊依附的頂點(diǎn)及權(quán)值i = LocateVex(G, v1);/確定v1、v2在G中的位置j = LocateVex(G, v2);G.arcsij.adj = w;/弧的權(quán)值G.arcsji = G.arcsij;/置的對稱弧return OK;/CreateUDN/MiniSpan Tree PRIM.hStatus Minimum(closedge closeEdge, int n)int i, flag, minTemp = INFINITY;for (i=0; i closeEdgei.lowcost)minTemp = closeEdgei.lowcost;flag = i;return flag;void MiniSpanTree_PRIM(MGraph G, VertexType u)/用普里姆算法從第 u 個頂點(diǎn)出發(fā)構(gòu)造網(wǎng) G 的最小生成樹 T，輸出 T 的各條邊。/記錄從頂點(diǎn)集 U 到 V-U 的代價(jià)最小的邊的輔助數(shù)組定義見 AdjacencyMatrix.hint i, j, k, totalCost=0;closedge closeEdge;k = LocateVex(G, u);for (j=0; jG.vexnum; +j)/輔助數(shù)組初始化if (j != k)strcpy(closeEdgej.adjvex, u);closeEdgej.lowcost = G.arcskj.adj;coutnn+n;cout|用Prim算法求最小生成樹的各條邊依次為：n-;closeEdgek.lowcost = 0;/初始，U=u;for (i=1; i 0, viV-UcoutcloseEdgek.adjvex,G.v