數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-地鐵建設(shè)問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上軟 件 學(xué) 院課程設(shè)計報告書課程名稱 數(shù)據(jù)結(jié)構(gòu) 設(shè)計題目 地鐵建設(shè)問題 專業(yè)班級 學(xué) 號 姓 名 指導(dǎo)教師 2013年 1 月專心-專注-專業(yè)目錄1 設(shè)計時間.22 設(shè)計目的.23 設(shè)計任務(wù).24 設(shè)計內(nèi)容.24.1需求分析.24.1.1程序所能達到的功能.24.1.2輸入、輸出的形式和輸入值的范圍.24.1.3測試數(shù)據(jù).34.2總體設(shè)計.34.2.1抽象數(shù)據(jù)類型定義.34.2.2主程序的流程、模塊之間的調(diào)用關(guān)系.44.3詳細設(shè)計.54.3.1 數(shù)據(jù)類型、函數(shù)的偽碼算法.54.3.2函數(shù)的調(diào)用關(guān)系圖.94.4測試與分析.104.4.1測試.104.4.2分析.114.

2、5 附錄.115 總結(jié)與展望.16參考文獻.17成績評定.171 設(shè)計時間2012年1月21日2012年1月25日2 設(shè)計目的1.通過這次設(shè)計，在數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計及其實現(xiàn)等方面加深對課程基本內(nèi)容的理解2.訓(xùn)練程序設(shè)計方法以及上機操作等基本技能，積累編程經(jīng)驗3.培養(yǎng)用計算機解決實際問題的能力3 設(shè)計任務(wù)某城市要在各個轄區(qū)之間修建地鐵，由于地鐵建設(shè)費用昂貴，因此需要合理安排地鐵建設(shè)線路，使市民可以沿地鐵到達各個轄區(qū)，并使總費用最小。4 設(shè)計內(nèi)容 4.1需求分析 4.1.1程序所能達到的功能 城市要在各個轄區(qū)之間修建地鐵來加快經(jīng)濟發(fā)展，但由于建設(shè)地鐵的費用

3、昂貴，因此需要編寫程序合理安排地鐵的建設(shè)路線，使乘客可以沿地鐵到達各個轄區(qū)，并使總的建設(shè)費用最小。（1）使用結(jié)構(gòu)體數(shù)組，存儲轄區(qū)名稱（2）建立轄區(qū)間直接距離的無向圖，用鄰接矩陣存儲轄區(qū)間直接距離信息（2）根據(jù)讀入的轄區(qū)距離信息，計算出應(yīng)該建設(shè)哪些轄區(qū)的地鐵路線（3）輸出應(yīng)該建設(shè)的路線，以及所需建設(shè)的總里程信息4.1.2輸入、輸出的形式和輸入值的范圍輸出的形式和輸入值的范圍輸入數(shù)字和字母，字母為轄區(qū)名，數(shù)字為轄區(qū)間直接距離，名稱個數(shù)o， 0<線路個數(shù)<o(o-1),直接距離m，0<m<10000輸出的形式1：轄區(qū)名 轄區(qū)名 路程2：轄區(qū)名 轄區(qū)名 路程3：轄區(qū)名 轄區(qū)名

4、路程總費用為：路程的和4.1.3測試數(shù)據(jù)正確輸入：轄區(qū)個數(shù)：4名稱 a b c d 線路起止轄區(qū)及直接距離：a b 3、a c 5、a d 4、b c 2、b d 3、c d 2、0 0 0 開始轄區(qū)：a 輸出為：1：a b 32：b c 23：c d 2總費用：7錯誤輸入：轄區(qū)個數(shù)：4名稱 a b c d 線路及之間距離：as b 3輸出為：沒有as 這個轄區(qū)4.2總體設(shè)計4.2.1抽象數(shù)據(jù)類型定義1抽象數(shù)據(jù)類型圖的定義ADT Graph數(shù)據(jù)對象v：v是具有相同特性的數(shù)據(jù)元素的集合，成為頂點集。數(shù)據(jù)關(guān)系R： R=VR VR=<v,w>|v,wV且P（v，w），<v,w>

5、;表示從v到w的弧，謂詞P（v,w）定義了弧<v,w>的意義或信息 基本操作P： CreateGraph（&G,V,VR）； 初始條件：V是圖的頂點集，VR是圖中弧的集合。 操作結(jié)果：按V和VR的定義構(gòu)造圖G。 ADT Graph4.2.2主程序的流程、模塊之間的調(diào)用關(guān)系主程序的流程開始輸入轄區(qū)個數(shù)和轄區(qū)名稱輸入各轄區(qū)之間路程判斷輸入是否正確NY建立無向圖，鄰接矩陣存儲普利姆算法計算最小生成樹輸出路線和總費用結(jié)束模塊之間的調(diào)用關(guān)系（1）主函數(shù)main（）調(diào)用int creatgraph(Graph *g)建立無向圖，用鄰接矩陣存儲；（2）void MiniSpanTree_

6、PRIM(Graph g,char a10)調(diào)用int minimun(struct tree *a,Graph g)和int locatevex(Graph *g,char a10)生成樹，判斷轄區(qū)名稱輸入是否正確；（3）主函數(shù)main（）調(diào)用void MiniSpanTree_PRIM(Graph g,char a10) 計算最小生成樹，輸出最優(yōu)線路和總里程。4.3詳細設(shè)計4.3.1 數(shù)據(jù)類型、函數(shù)的偽碼算法1結(jié)構(gòu)體類型typedef struct char VM10; int RMM; int vexnum; Graph; 2函數(shù)算法創(chuàng)建無向圖int locatevex(Graph *g

7、,char a10) int i; for(i=0;i<g->vexnum;i+) if(strcmp(a,g->Vi)=0) return i; if(i=g->vexnum) return -1; int creatgraph(Graph *g) int i=0,j,m,k,p,o,e; char a10,b10; printf("設(shè)置轄區(qū)的個數(shù): ");/城市中轄區(qū)的個數(shù) scanf("%d",&o); for(i=0;i<o;i+)/建立城市轄區(qū)名數(shù)組 printf("第%d個城市轄區(qū)名稱為: &q

8、uot;,i+1);scanf("%s",g->Vi); g->vexnum=o;for(i=0;i<g->vexnum;i+) for(j=0;j<g->vexnum;j+) g->Rij=INFINITY; printf("轄區(qū)之間的路程，以0 0 0為結(jié)束標(biāo)志n"); scanf("%s%s%d",a,b,&m); while(strcmp("0",a)!=0 | strcmp("0",b)!=0 | m!=0) k=locatevex(g

9、,a); p=locatevex(g,b);if(k=-1) printf("沒有%s這個轄區(qū)n",a); return 0; if(p=-1) printf("沒有%s這個轄區(qū)n",b); return 0;g->Rkp=g->Rpk=m;scanf("%s%s%d",a,b,&m); return 1; struct tree int weizhi; int lowcost;int minimun(struct tree *a,Graph g) int i,k,m=0; for(i=0;i<g.vexnu

10、m;i+) if(m=0 && ai.lowcost!=0) m=1; k=i;if(m=1 && ai.lowcost!=0) if(ai.lowcost<ak.lowcost) k=i; return k;普利姆算法求最小生成樹，輸出最優(yōu)線路及費用void MiniSpanTree_PRIM(Graph g,char a10) struct tree closedgeM; int i,j,k,money=0; k=locatevex(&g,a); for(i=0;i<g.vexnum;i+) if(i!=k) closedgei.lowc

11、ost=g.Rki; closedgei.weizhi=k; closedgek.lowcost=0; for(i=1;i<g.vexnum;i+) k=minimun(closedge,g); money+=closedgek.lowcost; printf("%d:%s %s %dn",i,g.Vclosedgek.weizhi,g.Vk,closedgek.lowcost); closedgek.lowcost=0; for(j=0;j<g.vexnum;j+) if(g.Rkj<closedgej.lowcost) closedgej.weizhi

12、=k; closedgej.lowcost=g.Rkj; printf("總費用為：%dn",money);4.3.2函數(shù)的調(diào)用關(guān)系圖locatevexminimuncreatgraphmainMiniSpanTree_PRIM結(jié)束4.4測試與分析4.4.1測試1正確的輸入2錯誤的輸入4.4.2分析 調(diào)試過程中遇到的問題及其解決方法 （1）問題: 用for循環(huán)語句控制輸入轄區(qū)名稱及輸出轄區(qū)名稱時候的個數(shù)名不對應(yīng)解決方法: 數(shù)組下標(biāo)時從零開始的，并且在 for 循環(huán)語句中,循環(huán)變量的執(zhí)行次數(shù)總是比循環(huán)體的執(zhí)行次數(shù)多一次，所以應(yīng)該注意修改使其相對應(yīng) （2）問題：用循環(huán)控制各轄區(qū)

13、及其之間的距離沒有考慮清楚解決方法：用輸入0 0 0 判定轄區(qū)及其直接距離數(shù)據(jù)輸入完畢 （3）問題：普利姆算法理解不透徹，用其計算最小生成樹輸出結(jié)果的時候出現(xiàn)問題 解決方法：上網(wǎng)查閱資料及閱讀課本詢問同學(xué)，并在以前程序上加以修改，最終得以運行。4.5 附錄#include<stdio.h>#define INF 32767typedef int InfoType;#define MAXV 100typedef structint adj;InfoType *info;ArcCell,AdjMatrixMAXVMAXV;typedef structint edgesMAXVMAXV;

14、int n,e;int vexsMAXV;MGraph;typedef struct ANodeint adjvex;struct ANode *nextarc;InfoType info;ArcNode;typedef int Vertex;typedef struct VnodeVertex data;ArcNode *firstarc;VNode;typedef VNode AdjListMAXV;typedef structAdjList adjlist;int n,e;ALGraph;int sum=0;int Locatevex(MGraph g,int A)int i;for(i

15、=0;i<g.n;i+)if(A=g.vexsi)return i;if(i=g.n)return -1;int CreateMgraph(MGraph &g)int i,j,k,w,v1,v2;printf("請輸入轄區(qū)個數(shù)和單個路徑的個數(shù):n");scanf("%d%d",&g.n,&g.e);printf("輸入各個轄區(qū)編號:n"); for(i=0;i<g.n;+i)scanf("%d",&g.vexsi); for(i=0;i<g.n;i+)for(j=0

16、;j<g.n;j+)g.edgesij=INF;printf("輸入各轄區(qū)編號間的路徑長度:");for(k=0;k<g.e;+k)scanf("%d%d%d",&v1,&v2,&w); i=Locatevex(g,v1); j=Locatevex(g,v2); g.edgesij=g.edgesji=w;return 1;void DispMat(MGraph g)/輸出鄰接矩陣int i,j;for(i=0;i<g.n;i+)for(j=0;j<g.n;j+)if(g.edgesij=INF)print

17、f("%3s","");elseprintf("%3d",g.edgesij);printf("n");void Prim(MGraph g,int v)int lowcostMAXV,min,n=g.n;int closestMAXV,i,j,k;for(i=0;i<n;i+)lowcosti=g.edgesvi;closesti=v;for(i=1;i<n;i+)min=INF;for(j=0;j<n;j+)if(lowcostj!=0&&lowcostj<min)min

18、=lowcostj;k=j;printf("應(yīng)建設(shè)的轄區(qū)(%d,%d)轄區(qū)的花費為:%dn",closestk,k,min);if(min!=INF) sum+=min;lowcostk=0;for(j=0;j<n;j+)if(g.edgeskj!=0&&g.edgeskj<lowcostj)lowcostj=g.edgeskj;closestj=k;printf("建設(shè)鐵路線的最低費用為:%dn",sum);void main()int i,j;MGraph g;CreateMgraph(g);printf("n");printf("轄區(qū)圖的鄰接矩陣:n");DispMat(g);printf("n");printf("普里姆算法結(jié)果:n");Prim(g,0);printf("n");5 總結(jié)與展望這次課程設(shè)計任務(wù)是我在大學(xué)以來的遇到的第一次課程設(shè)計，剛開始看到題目的時候看起來不是很難，但是在實際編程操作中遇到了很多的問題，不過，在不斷地遇到和解決問題的過程中，學(xué)到了很多的知識。通過這一周的課程設(shè)計，加深了我對數(shù)據(jù)結(jié)構(gòu)這門課程所學(xué)內(nèi)