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

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

1、软件学院课程设计报告书课程名称数据结构课程设计设计题目地铁建设问题专业班级学号姓名指导教师2013年1月目录1设计时间12设计目的13设计任务14设计内容14.1需求分析14.2总体设计24.3详细设计44.4测试与分析114.4.1测试114.4.2分析134.5附录145总结与展望20参考文献22成绩评定22221设计时间2013年1月16日至2013年1月21日2设计目的数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础。数据结构是实践性很强的课程。课程设计是加强学生实践

2、能力的一个强有力手段。要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。3设计任务某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。1.输入各个辖区名称和各辖区间直接距离（地铁铺设费用与距离成正比）；2.根据辖区距离信息，

3、计算出应该在哪些辖区建立地铁线路；3.输出应该建设的地铁线路及所需建设总里程。4设计内容4.1需求分析1、程序所能达到的功能：(1)根据输入的辖区信息，建立图模型，使用的数据结构是无向图，采用邻接矩阵存储。(2)根据普利姆算法计算最小生成树。(3)输入各个辖区代号，名称和各辖区间直接距离（地铁铺设费用与距离成正比）。(4)根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。22(5)输出应该建设的地铁线路及所需建设总里程。2、输入的形式及内容：包括城市名称、城市间距离权值、起始地点，详见4.4.1测试部分

4、。3、输出的形式及内容：包括生成的邻接表、应建设铁路的辖区名称及权值、最终地铁的总里程，详见4.4.1测试部分。4、测试数据：四个城市abcd及其之间的距离权值，详见4.4.1测试部分。4.2总体设计4.2.1数据类型的定义1.图的邻接矩阵存储数据类型定义：typedefstruct{charV[M][10];intR[M][M];intvexnum;Graph;）2.辅助数组数据类型定义：typedefstruct{intadjvex;intlowcost;}closedge[MAX];4.2.2基本操

5、作：CreateCity(&G)操作结果：构造一个无向图G；22LocateDistri(Graphg,intu)操作结果：找出目标城市的位置；Min(Graphg,closedgeclosedge)操作结果：求出点与点之间的最短路径；Prim(G,G.distrinam[1])操作结果：用普里姆算法找到连接各辖区的最短路；4.2.3主程序的流程主程序的流程如图1所示：图1224.2.4各程序模块之间的层次（调用）关系各程序模块之间的层次（调用）关系如图2所示：图24.3详细设计4.3.1预处理#incl

6、ude#include#include#include#defineINFINITY10000#defineM20typedefstruct{//创建图的结构体charV[M][10];//顶点数组，用来存储辖区的值即辖区的名称intR[M][M];//邻接矩阵，邻接矩阵的元素值为辖区之间的距离22intvexnum;//辖区的个数}Graph;structtree{intweizhi;intlowcost;};4.3.2创建辖

7、区无向图的算法intcreatgraph(Graph*g)//创建辖区无向图，图中含有n个结点，创建辖区邻接矩阵{inti=0,j,m,k,p;chara[10],b[10];printf("*****欢迎使用本程序解决地铁建设问题*****");printf("*******请按照提示依次输入相关信息*******");printf("***请输入所有的辖区，以0作为结束标志****");scanf("%s",g->V[i]);//输入结点值while(strcmp("0",g->V[i])

8、!=0){i++;scanf("%s",g->V[i]);}g->vexnum=i;for(i=0;ivexnum;i++)for(j=0;jvexnum;j++)22g->R[i][j]=INFINITY;//初始化printf("*请输入辖区之间的路程，以000为结束标志*");scanf("%s%s%d",a,b,&m);//输入辖区结点及辖区之间的距离while(strcmp("0",a)!=0

9、

10、