数据结构课程设计—地铁建设问题.doc

《数据结构课程设计—地铁建设问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.软件学院课程设计报告书课程名称数据结构课程设计设计题目地铁建设问题专业班级学号姓名资料..指导教师2015年1月目录1设计时间32设计目的33设计任务34设计容34.1需求分析34.2总体设计44.3详细设计44.4测试与分析54.4.1测试54.4.2分析64.5附录75总结与展望11参考文献12成绩评定12资料..资料..1设计时间2015年1月19日—2012年1月23日2设计目的通过课程设计，加深对《数据结构》这一课程所学容的进一步理解与巩固，加深对结构化设计思想的理解，能对系统功能进行分析，并设计合理的模块化结构。提高程序开发功能，能运用合理的控制

2、流程编写清晰高效的程序。训练C程序调试能力，能将一个中小型各级组织系统联调通过。开发一个中小型系统，掌握系统研发全过程。培养分析问题、解决实际问题的能力。3设计任务某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。4设计容设计思路：(1)输入各个辖区名称和各辖区间直接距离（地铁铺设费用与距离成正比）。如:到的直接距离是100公里.(2)根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。(3)输出应该建设的地铁线路及所需建设总里程。本程序中用到的所有抽象数据类型的定义；typede

3、fcharInfoTypetypedefcharVertexType[MAX_NAME]typedefstruct资料..{VRTypeadj;InfoType*info;、}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;intvexnum,arcnum;}MGraph;typedefstruct{VertexTypeadjvex;VRTypelowcost;}minside[MAX_VER

4、TEX_NUM];4.1需求分析输出应该建设的地铁线路及所需建设总里程。要求输出建设地铁的最短路线，再利用其最短路线上的权值把总的里程计算出来，已达到最省的费用，实现该地铁的建设。4.2总体设计资料..1.首先要了解本题中的要求，要用已经学的邻接矩阵，根据输入的辖区信息，建立图模型，使用的数据结构是无向图，采用邻接矩阵存储。2.根据普利姆算法计算最小生成树。假设WN=(V,{E})是一个含有n个顶点的连通网，TV是WN上最小生成树中顶点的集合，TE是最小生成树中边的集合。显然，在算法执行结束时，TV=V，而TE是E的一个子集。在算法开始执行时，TE为空集，TV

5、中只有一个顶点，因此，按普里姆算法构造最小生成树的过程为：在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有n-1条边为止。3.了解了这些就可以实现它的基本操作，然后构建一个邻接矩阵，输入各个辖区构成一个无向连通图，并把直接距离当作权值来标记，之后，进行普里姆的算法，使其生成最小生成树，并带有权值了，把这些辖区输出，并把最小路径和最少的费用输出，这样就完成了操作。本题出现的调用函数是：i=creatgraph(&g);MiniSpanTree_PRIM(g,a);k=locateve

6、x(&g,a);minimun(structtree*a,Graphg)；开始主程序流程图：主函数资料..建设界面普里姆的构建及使用邻接矩阵的建立及存储MiniSpanTree_PRIMcreatgraphminimunlocatevex主函数结束图14.3详细设计typedefstruct{charV[M][10];intR[M][M];intvexnum;}Graph;intlocatevex(Graph*g,chara[10]){inti;for(i=0;ivexnum;i++){if(strcmp(a,g->V[i])==0)资料..retur

7、ni;}if(i==g->vexnum)return-1;}intcreatgraph(Graph*g){inti=0,j,m,k,p;chara[10],b[10];printf("所有的辖区，以0为结束");scanf("%s",g->V[i]);while(strcmp("0",g->V[i])!=0){i++;scanf("%s",g->V[i]);}g->vexnum=i;for(i=0;ivexnum;i++)for(j=0;jvexnum;j++)g->R[i][j]=INFINITY;printf("辖区之间的路程，以000

8、为结束标志");scanf("%s