數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-最小通信網(wǎng).doc

課 程 設(shè) 計(jì) 報(bào) 告課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 題 目 最小通信網(wǎng) 指導(dǎo)教師 設(shè)計(jì)起始日期 5.25.9 學(xué) 院 計(jì)算機(jī)學(xué)院 系 別 計(jì)算機(jī)科學(xué)與工程 學(xué)生姓名 班級(jí)/學(xué)號(hào) 成 績(jī) 一、 需求分析 要在n個(gè)城市之間建立通信網(wǎng)，已知各個(gè)城市間的距離，建立的通信線路要使得這n個(gè)城市相連，而且建立的通信網(wǎng)絡(luò)代價(jià)最小。（1） 輸入：n個(gè)城市的距離關(guān)系圖，即圖的頂點(diǎn)和邊上的權(quán)值 （2） 輸出：含n個(gè)城市頂點(diǎn)的最小生成樹(shù)中的邊和代價(jià)（3） 功能：建立圖的最小生成樹(shù)（4） 測(cè)試數(shù)據(jù)：自選二、 概要設(shè)計(jì)1、 數(shù)據(jù)結(jié)構(gòu)用圖來(lái)描述n個(gè)城市之間的關(guān)系，頂點(diǎn)為城市，邊位兩個(gè)城市間的代價(jià)2、 使用算法：采用prim算法算法思想：假設(shè)G=(V,E)為待求圖，其中V為圖中所有頂點(diǎn)的集合，E為帶權(quán)圖中所有帶權(quán)邊的集合。設(shè)置兩個(gè)新的集合U和TE，其中集合U用于存放G的最小生成樹(shù)中的頂點(diǎn)，集合TE存放G的最先生成樹(shù)的邊。令集合U的初值U=u1（假設(shè)構(gòu)造最小生成樹(shù)時(shí)，頂點(diǎn)從u0出發(fā)），集合TE的初值為TE=。Prim算法的思想是，從所有uU，vV-U的邊中，選取具有最小權(quán)值的邊（u，v），將頂點(diǎn)v加入集合U中，將邊（u，v）加入集合TE中，如此不斷重復(fù)，直到U=V，最小生成樹(shù)樹(shù)構(gòu)造完畢，這時(shí)集合TE中包含了最小生成樹(shù)的所有邊 Prim算法可用下述過(guò)程描述，其中用wuv表示頂點(diǎn)u與頂點(diǎn)v邊上的權(quán)值。（1）Uu1,T=; （2）while (UV)do (u，v)minwuv；uU，vVU TT(u，v) UUv （3）結(jié)束三、 詳細(xì)設(shè)計(jì) 1、數(shù)據(jù)結(jié)構(gòu)詳細(xì)設(shè)計(jì) 圖的鄰接矩陣 typedef struct int Vnum;/*圖的頂點(diǎn)數(shù)*/ int ArcsMAXNMAXN;/*鄰接矩陣*/ Graph;/*圖的鄰接矩陣存儲(chǔ)法*/2、最小生成樹(shù)PRIM算法:在Prim算法中，應(yīng)當(dāng)考慮如何有效地找出滿足條件iU,jV-U，且權(quán)cij最小的邊(i,j)。實(shí)現(xiàn)這個(gè)目的的較簡(jiǎn)單的辦法是設(shè)置2個(gè)一維數(shù)組closest和lowcost。Lowcostj中存儲(chǔ)iU,jV-U且權(quán)最小的邊(i,j)的權(quán)值cij，而closestj中存儲(chǔ)的是最小邊（i，j）的另一個(gè)端點(diǎn)i。在Prim算法執(zhí)行過(guò)程中，先找出V-U中l(wèi)owcost值最小的頂點(diǎn)j，然后根據(jù)數(shù)組closest選取邊(j,closestj)，最后將j添加到U中，并對(duì)其他closest和lowcost作必要的修改。偽算法如下：int prim(Graph G, int u) 1. u0= 起始點(diǎn)u; 2. for 每個(gè)結(jié)點(diǎn)v 3. 初始化距離數(shù)組Closest()和Lowcost() 4. for V-U中的頂點(diǎn)i 5. for 所有頂點(diǎn)j 6 k使Lowcost()最小的頂點(diǎn) 7. 將頂點(diǎn)k及邊(k,closest(k)加入MST中 8. for 所有頂點(diǎn)j 9. if 原Lowcost(j)c(k,j) 10. Lowcost(j)= c(k,j) 11. Clostest(j)=k 12. return MST一、 調(diào)試分析a調(diào)試過(guò)程中遇到的問(wèn)題調(diào)試過(guò)程中出現(xiàn)了結(jié)果輸出錯(cuò)誤問(wèn)題，經(jīng)過(guò)跟蹤調(diào)試發(fā)現(xiàn)是在修正Lowcost數(shù)組和Closest數(shù)組過(guò)程中數(shù)據(jù)未被修正，經(jīng)改正后結(jié)果正確。b算法的時(shí)空分析算法中共四個(gè)for循環(huán)，第一個(gè)循環(huán)次數(shù)為n，第二個(gè)為n-1，第三個(gè)為n，第四個(gè)為n，并且第二個(gè)和第三、四個(gè)循環(huán)嵌套，所以循環(huán)次數(shù)為n的平方數(shù)量級(jí)。所以時(shí)間復(fù)雜度為O(n2)。算法中用到了兩個(gè)輔助一維數(shù)組closest和lowcost，數(shù)組的大小為n，即圖的頂點(diǎn)個(gè)數(shù)，所以算法的空間復(fù)雜度為O(n)。二、 程序清單1、圖的建立程序：作為圖的數(shù)據(jù)結(jié)構(gòu).#include#include#define MAXN 50#define INFINITY 32767 typedef struct int Vnum;/*圖的頂點(diǎn)數(shù)*/ int ArcsMAXNMAXN;/*鄰接矩陣*/ Graph;/*圖的鄰接矩陣存儲(chǔ)法*/ int create_graph(Graph *p)/*圖的創(chuàng)建,成功時(shí)返回非0值，失敗時(shí)返回0*/ int i,j,n; int v1,v2,w; char c; printf(nInput the vexnumber of graph:); scanf(%d,&n); if(nVnum=n; for(i=0;in;i+) for(j=0;jArcsij=0; else p-Arcsij=INFINITY; printf(nWill you input the weight of an edge?(y or n):); while(tolower(c=getchar()=y) printf(nedge(vertex1,vertex2,weight):); scanf(%d%d%d,&v1,&v2,&w); if(v1=0&v1=0&v2Arcsv1v2=p-Arcsv2v1=w; printf(nWill you continue to input the weight of an edge?(y or n):); return 1; 2、Prim算法：int prim(Graph G,int u0,int tree3)/*返回生成樹(shù)的代價(jià),v是指定的起始頂點(diǎn),生成樹(shù)的邊存放在數(shù)組tree中*/ int i,j,k,p,min,c; int lowcostMAXN,closestMAXN; for(i=0;iG.Vnum;i+) closesti=u0; /*初始時(shí)U中只有頂點(diǎn)v*/ lowcosti=G.Arcsu0i;/*U中頂點(diǎn)到V-U中頂點(diǎn)代價(jià)*/ c=0; /*記錄生成樹(shù)的代價(jià)*/ p=0; /*從序號(hào)為0的頂點(diǎn)出發(fā)求最小生成樹(shù)*/ for(i=0;iG.Vnum-1;i+)/*從圖中找出G.Vnum-1條邊，構(gòu)成最小生成樹(shù)*/ min=INFINITY; for(j=0;jG.Vnum;j+) /*查找U中頂點(diǎn)到V-U中頂點(diǎn)的邊中權(quán)值最小者*/ /*(closestk,k)為找到的最小權(quán)值的邊*/ if(lowcostj!=0&lowcostjmin) min=lowcostj; k=j; treep0=closestk;/*存放找到的最小權(quán)值的邊*/ treep1=k; treep2=min; p+; c+=min;/*計(jì)算當(dāng)前生成樹(shù)的代價(jià)*/ lowcostk=0;/*將k加入U(xiǎn)*/ for(j=0;jG.Vnum;j+)/*更新V-U中與k鄰接的頂點(diǎn)到U中頂點(diǎn)的代價(jià)*/ if(G.Arcskj!=0&G.Arcskjlowcostj) lowcostj=G.Arcskj; closestj=k; return c;/*返回最小生成樹(shù)的代價(jià)*/ 3、測(cè)試程序：void main() int i; int treeMAXN3; int cost; Graph G; create_graph(&G); cost=prim(G,0,tree); printf(nMinimum-Cost spanning tree(prim):n); printf(edget weighttn); for(i=0;iG.Vnum-1;i+) printf(v%d,v%d)t %dn,treei0,treei1,treei2); printf(Cost:%dn,cost); 六、 使用說(shuō)明和測(cè)試結(jié)果1、使用說(shuō)明：首先用戶輸入圖