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

#為輸入結束標志

\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( "請輸入轄區和轄區之間的路程，以scanf( "%s%s%d",a,b,&m);

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

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

"沒有%s這個轄區\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;}測試與分析測試圖4-1正確測試結果圖4-2錯誤測試結果分析調試時，在輸入數據時，再輸完數據后要再次按下空格鍵，再輸入結束符號才會結束本次輸入進入下一個輸入。且不能輸入與本次輸入無關的數據或者超出本次輸入限制的數據，否則顯示錯誤，將重新輸入。附錄#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( "請輸入所有的轄區，以#為輸入結束標志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( "請輸入轄區和轄區之間的路程，以 ##為結束標志\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這個轄區\n",a);0;}if(p==-1){printf(return

"沒有%s這個轄區\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這個轄區，無法求解\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( "總費用為：%d\n",money);}voidmain(){int i,k;Graphg;chara[10];printf("請選擇功能：1（鐵路建設）0（退出）\n");scanf("%d",&k);while(k){=creatgraph(&g);if(i){printf("請輸入從哪里開始：");scanf( "%s",a);MiniSpanTree_PRIM(g,a);}printf( "請選擇功能：1（鐵路建設）scanf( "%d",&k);

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