数据结构课程设计-地铁建设问题

软件学院课程设计报告书课程名称数据结构设计题目地铁建设问题专业班级学号姓名指导教师2013年1月1目录1设计时间................................................22设计目的................................................23设计任务................................................24设计内容................................................24.1需求分析...............................................24.1.1程序所能达到的功能...................................24.1.2输入、输出的形式和输入值的范围........................24.1.3测试数据.............................................34.2总体设计...............................................34.2.1抽象数据类型定义.....................................34.2.2主程序的流程、模块之间的调用关系......................44.3详细设计...............................................54.3.1数据类型、函数的伪码算法.............................54.3.2函数的调用关系图.....................................94.4测试与分析............................................104.4.1测试................................................104.4.2分析................................................114.5附录.................................................115总结与展望.............................................16参考文献.................................................17成绩评定.................................................1721设计时间2012年1月21日——2012年1月25日2设计目的1.通过这次设计，在数据结构的逻辑结构和存储结构、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解2.训练程序设计方法以及上机操作等基本技能，积累编程经验3.培养用计算机解决实际问题的能力3设计任务某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。4设计内容4.1需求分析4.1.1程序所能达到的功能城市要在各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要编写程序合理安排地铁的建设路线，使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。（1）使用结构体数组，存储辖区名称（2）建立辖区间直接距离的无向图，用邻接矩阵存储辖区间直接距离信息（2）根据读入的辖区距离信息，计算出应该建设哪些辖区的地铁路线（3）输出应该建设的路线，以及所需建设的总里程信息4.1.2输入、输出的形式和输入值的范围①输出的形式和输入值的范围输入数字和字母，字母为辖区名，数字为辖区间直接距离，名称个数o，0线路个数o(o-1),直接距离m，0m10000②输出的形式1：辖区名辖区名路程2：辖区名辖区名路程33：辖区名辖区名路程总费用为：路程的和4.1.3测试数据①正确输入：辖区个数：4名称abcd线路起止辖区及直接距离：ab3、ac5、ad4、bc2、bd3、cd2、000开始辖区：a输出为：1：ab32：bc23：cd2总费用：7②错误输入：辖区个数：4名称abcd线路及之间距离：asb3输出为：没有as这个辖区4.2总体设计4.2.1抽象数据类型定义1．抽象数据类型图的定义ADTGraph{数据对象v：v是具有相同特性的数据元素的集合，成为顶点集。数据关系R：R={VR}VR={v,w|v,w∈V且P（v，w），v,w表示从v到w的弧，4谓词P（v,w）定义了弧v,w的意义或信息}基本操作P：CreateGraph（&G,V,VR）；初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。}ADTGraph4.2.2主程序的流程、模块之间的调用关系①主程序的流程②模块之间的调用关系（1）主函数main（）调用intcreatgraph(Graph*g)建立无向图，用邻接矩阵存储；（2）voidMiniSpanTree_PRIM(Graphg,chara[10])调用intminimun(structtree*a,Graphg)和intlocatevex(Graph*g,chara[10])生成树，判断辖区名称输入是否正确；（3）主函数main（）调用voidMiniSpanTree_PRIM(Graphg,chara[10])计算最小开始输入辖区个数和辖区名称输入各辖区之间路程判断输入是否正确NY建立无向图，邻接矩阵存储普利姆算法计算最小生成树输出路线和总费用结束5生成树，输出最优线路和总里程。4.3详细设计4.3.1数据类型、函数的伪码算法1．结构体类型typedefstruct{charV[M][10];intR[M][M];intvexnum;}Graph;2．函数算法①创建无向图intlocatevex(Graph*g,chara[10]){inti;for(i=0;ig-vexnum;i++){if(strcmp(a,g-V[i])==0)returni;}if(i==g-vexnum)return-1;}intcreatgraph(Graph*g){inti=0,j,m,k,p,o,e;chara[10],b[10];6printf(设置辖区的个数:);//城市中辖区的个数scanf(%d,&o);for(i=0;io;i++)//建立城市辖区名数组{printf(第%d个城市辖区名称为:,i+1);scanf(%s,g-V[i]);}g-vexnum=o;for(i=0;ig-vexnum;i++)for(j=0;jg-vexnum;j++)g-R[i][j]=INFINITY;printf(辖区之间的路程，以000为结束标志\n);scanf(%s%s%d,a,b,&m);while(strcmp(0,a)!=0||strcmp(0,b)!=0||m!=0){k=locatevex(g,a);p=locatevex(g,b);if(k==-1){printf(没有%s这个辖区\n,a);return0;}if(p==-1){printf(没有%s这个辖区\n,b);return0;}g-R[k][p]=g-R[p][k]=m;scanf(%s%s%d,a,b,&m);7}return1;}structtree{intweizhi;intlowcost;};intminimun(structtree*a,Graphg){inti,k,m=0;for(i=0;ig.vexnum;i++){if(m==0&&a[i].lowcost!=0){m=1;k=i;}if(m==1&&a[i].lowcost!=0){if(a[i].lowcosta[k].lowcost)k=i;}}returnk;}8④普利姆算法求最小生成树，输出最优线路及费用voidMiniSpanTree_PRIM(Graphg,chara[10]){structtreeclosedge[M];inti,j,k,money=0;k=locatevex(&g,a);for(i=0;ig.vexnum;i++){if(i!=k){closedge[i].lowcost=g.R[k][i];closedge[i].weizhi=k;}}closedge[k].lowcost=0;for(i=1;ig.vexnum;i++){k=minimun(closedge,g);money+=closedge[k].lowcost;printf(%d:%s%s%d\n,i,g.V[closedge[k].weizhi],g.V[k],closedge[k].lowcost);closedge[k].lowcost=0;for(j=0;jg.vexnum;j++){if(g.R[k][j]closedge[j].lowcost){closedge[j].weizhi=k;closedge[j].lowcost=g.R[k][j];}9}}printf(总费用为：%d\n,money);}4.3.2函数的调用关系图locatevexminimuncreatgraphmainMiniSpanTree_PRIM结束104.4测试与分析4.4.1测试1．正确的输入2．错误的输入114.4.2分析调试过程中遇到的问题及其解决方法（1）问题:用for循环语句控制输入辖区名称及输出辖区名称时候的个数名不对应解决方法:数组下标时从零开始的，并且在for循环语句中,循环变量的执行次数总是比循环体的执行次数多一次，所以应该注意修改使其相对应（2）问题：用循环控制各辖区及其之间的距离没有考虑清楚解决方法：用输入000判定辖区及其直接距离数据输入完毕（3）问题：普利姆算法理解不透彻，用其计算最小生成树输出结果的时候出现问题解决方法：上网查阅资料及阅读课本询问同学，并在以前程序上加以修改，最终得以运行。4.5附录#includestdio.h#defineINF32767typedefintInfoType;#defineMAXV100typedefstruct{intadj;InfoType*info;}ArcCell,AdjMatrix[MAXV][MAXV];typedefstruct{intedges[MAXV][MAXV];intn,e;intvexs[MAXV];}MGraph;typedefstructANode{intadjvex;12structANode*nextarc;InfoTypeinfo;}ArcNode;typedefintVertex;typedefstructVnode{Vertexdata;ArcNode*firstarc;}VNode;typedefVNodeAdjList[MAXV];typedefstruct{AdjListadjlist;intn,e;}ALGraph;intsum=0;intLocatevex(MGraphg,intA){inti;for(i=0;ig.n;i++){if(A==g.vexs[i])returni;}if(i==g.n)return-1;}intCreateMgraph(MGraph&g){13inti,j,k,w,v1,v2;printf(请输入辖区个数和单个路径的个数:\n);scanf(%d%d,&g.n,&g.e);printf(输入各个辖区编号:\n);for(i=0;ig.n;++i)scanf(%d,&g.vexs[i]);for(i=0;ig.n;i++)for(j=0;jg.n;j++)g.edges[i][j]=INF;printf(输入各辖区编号间的