軟件學(xué)院課程設(shè)計(jì)報(bào)告書課程名稱 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)題目 地鐵建設(shè)問題專業(yè)班級(jí)學(xué) 號(hào)姓 名指導(dǎo)教師2014年1月17日目錄1設(shè)計(jì)時(shí)間...............................錯(cuò)誤!未定義書簽。2設(shè)計(jì)目的...............................錯(cuò)誤!未定義書簽。3設(shè)計(jì)任務(wù)...............................錯(cuò)誤!未定義書簽。4設(shè)計(jì)內(nèi)容...............................錯(cuò)誤!未定義書簽?？傮w設(shè)計(jì).................................錯(cuò)誤!未定義書簽。需求分析.................................錯(cuò)誤!未定義書簽。詳細(xì)設(shè)計(jì).................................錯(cuò)誤!未定義書簽。測(cè)試與分析...............................錯(cuò)誤!未定義書簽。測(cè)試.....................................錯(cuò)誤!未定義書簽。分析.....................................錯(cuò)誤!未定義書簽。附錄....................................錯(cuò)誤!未定義書簽。5總結(jié)與展望.............................錯(cuò)誤!未定義書簽。參考文獻(xiàn).................................錯(cuò)誤!未定義書簽。成績?cè)u(píng)定.................................錯(cuò)誤!未定義書簽。設(shè)計(jì)時(shí)間2014年1月15日設(shè)計(jì)目的設(shè)計(jì)各轄區(qū)之間最短地鐵，使修建費(fèi)用最少設(shè)計(jì)任務(wù)某城市要在各個(gè)轄區(qū)之間修建地鐵，由于地鐵建設(shè)費(fèi)用昂貴，因此需要合理安排地鐵建設(shè)線路，使市民可以沿地鐵到達(dá)各個(gè)轄區(qū)，并使總費(fèi)用最小。設(shè)計(jì)內(nèi)容輸入各個(gè)轄區(qū)名稱和各轄區(qū)間直接距離（地鐵鋪設(shè)費(fèi)用與距離成正比）。根據(jù)轄區(qū)距離信息，計(jì)算出應(yīng)該在哪些轄區(qū)建立地鐵線路。輸出應(yīng)該建設(shè)的地鐵線路及所需建設(shè)總里程?？傮w設(shè)計(jì)圖4-1算法圖需求分析（1）本程序設(shè)計(jì)計(jì)算城市內(nèi)各轄區(qū)間修建地鐵的最短路程。（2）運(yùn)行時(shí)，輸入轄區(qū)的名稱，各轄區(qū)之間用空格鍵隔開，以 #輸入結(jié)束。（3）輸入各轄區(qū)間距離時(shí)，先輸入兩轄區(qū)名稱，再輸入距離。（4）最后計(jì)算最短距離來得出最少費(fèi)用。詳細(xì)設(shè)計(jì)采用鄰接矩陣存儲(chǔ)構(gòu)造無向圖int creatgraph(Graph*g){int i=0,j,m,k,p;chara[10],b[10];printf( "請(qǐng)輸入所有的轄區(qū)，以

#為輸入結(jié)束標(biāo)志

\n");scanf( "%s",g->V[i]);while(strcmp("#",g->V[i])!=0){i++;scanf( "%s",g->V[i]);}g->vexnum=i;for(i=0;i<g->vexnum;i++)for(j=0;j<g->vexnum;j++)g->R[i][j]=INFINITY;printf( "請(qǐng)輸入轄區(qū)和轄區(qū)之間的路程，以scanf( "%s%s%d",a,b,&m);

##為結(jié)束標(biāo)志\n");while(strcmp("##",a)!=0||strcmp( "##",b)!=0||m!=0){k=locatevex(g,a);p=locatevex(g,b);if(k==-1){printf(return

"沒有%s這個(gè)轄區(qū)\n",a);0;}if(p==-1){printf(return

"沒有%s這個(gè)轄區(qū)\n",b);0;}g->R[k][p]=g->R[p][k]=m;scanf("%s%s%d",a,b,&m);}return 1;}普利姆算法生成最小樹struct

tree

owcost!=0){m=1;k=i;}if(m==1&&a[i].lowcost!=0){if(a[i].lowcost<a[k].lowcost)k=i;}}return k;}測(cè)試與分析測(cè)試圖4-1正確測(cè)試結(jié)果圖4-2錯(cuò)誤測(cè)試結(jié)果分析調(diào)試時(shí)，在輸入數(shù)據(jù)時(shí)，再輸完數(shù)據(jù)后要再次按下空格鍵，再輸入結(jié)束符號(hào)才會(huì)結(jié)束本次輸入進(jìn)入下一個(gè)輸入。且不能輸入與本次輸入無關(guān)的數(shù)據(jù)或者超出本次輸入限制的數(shù)據(jù)，否則顯示錯(cuò)誤，將重新輸入。附錄#include<>#include<>#include<>#include<>#defineINFINITY10000#defineM20typedefstruct{charV[M][10];intR[M][M];intvexnum;}Graph;int locatevex(Graph *g,chara[10]){int i;for(i=0;i<g->vexnum;i++){if(strcmp(a,g ->V[i]) ==0)return i;}if(i==g->vexnum)return -1;}int creatgraph(Graph{

*g)int i=0,j,m,k,p;chara[10],b[10];printf( "請(qǐng)輸入所有的轄區(qū)，以#為輸入結(jié)束標(biāo)志scanf( "%s",g->V[i]);while(strcmp("#",g->V[i]) !=0){

\n");i++;scanf( "%s",g->V[i]);}g->vexnum=i;for(i=0;i<g->vexnum;i++)for(j=0;j<g->vexnum;j++)g->R[i][j] =INFINITY;printf( "請(qǐng)輸入轄區(qū)和轄區(qū)之間的路程，以 ##為結(jié)束標(biāo)志\n");scanf( "%s%s%d",a,b,&m);while(strcmp("##",a)!=0|| strcmp("##",b)!=0|| m!=0){k =locatevex(g,a);p =locatevex(g,b);if(k==-1){printf(return

"沒有%s這個(gè)轄區(qū)\n",a);0;}if(p==-1){printf(return

"沒有%s這個(gè)轄區(qū)\n",b);0;}g->R[k][p] =g->R[p][k] =m;scanf("%s%s%d",a,b,&m);}return 1;}struct tree owcost !=0){m=1;k=i;}if(m==1&&a[i] .lowcost!=0){if(a[i] .lowcost<a[k].lowcost)k=i;}}return k;}voidMiniSpanTree_PRIM(Graphg,{struct treeclosedge[M];int i,j,k,money =0;k=locatevex( &g,a);if(k==-1){

chara[10])printf(return

"沒有%s這個(gè)轄區(qū)，無法求解\n",a);0;}for(i=0;i<;i++){if(i!=k){closedge[i]closedge[i]}

.lowcost=[k][i];.weizhi=k;}closedge[k] .lowcost=0;for(i=1;i<;i++){=minimun(closedge,g);money+=closedge[k].lowcost;printf( "%d:%s%s%d\n",i,[closedge[k]

.weizhi],[k],closedge[k]

.lowcost);closedge[k] .lowcost=0;for(j=0;j<;j++){if[k][j] <closedge[j] .lowcost){closedge[j] .weizhi=k;closedge[j] .lowcost=[k][j];}}}printf( "總費(fèi)用為：%d\n",money);}voidmain(){int i,k;Graphg;chara[10];printf("請(qǐng)選擇功能：1（鐵路建設(shè)）0（退出）\n");scanf("%d",&k);while(k){=creatgraph(&g);if(i){printf("請(qǐng)輸入從哪里開始：");scanf( "%s",a);MiniSpanTree_PRIM(g,a);}printf( "請(qǐng)選擇功能：1（鐵路建設(shè)）scanf( "%d",&k);

0（退出）\n");}}總結(jié)與展望本程序，本次編譯涉及數(shù)據(jù)結(jié)構(gòu)最小生成樹以及圖的構(gòu)造等編譯。先要構(gòu)造結(jié)構(gòu)體，在定義時(shí)應(yīng)要注意盡量將賦值空間增大，以防止調(diào)試時(shí)輸入數(shù)據(jù)超出運(yùn)算范圍。再進(jìn)行函數(shù)的編譯調(diào)用，構(gòu)造無向圖用鄰接矩陣進(jìn)行存儲(chǔ)，這些編譯代碼，書上都有介紹，但不可盡抄，書上的只是一個(gè)模板，根據(jù)程序設(shè)計(jì)任務(wù)將變量進(jìn)行修改，構(gòu)造圖之后，運(yùn)用最小生成樹原理，用普利姆算法對(duì)整個(gè)程序變量進(jìn)行編譯，最后進(jìn)入主函數(shù)，就直接調(diào)用函數(shù)進(jìn)行運(yùn)算輸入的數(shù)據(jù)，輸出運(yùn)算結(jié)果。這次程序的編譯讓我對(duì)圖的遍歷理解的更加深入， 最小生成樹問題不僅可以運(yùn)算本次程序?qū)Φ罔F建造最少費(fèi)用問題，更可以運(yùn)用于一系列的最短距離等問題，解決甚多復(fù)雜問題！極其具有實(shí)用性！參考文獻(xiàn)[1]屈輝立,