地铁课设报告

.z.-----总结资料阳工程学院课程设计设计题目：地铁问题系别班级学生****指导教师职称讲师、讲师起止日期：2015年6月15日起——至2015年6月26日止阳工程学院课程设计任务书课程设计题目：地铁问题课程设计的原始资料及依据地铁建立问题描述：*城市要在其各个辖区之间修建地铁来加快经济的开展，但由于建立地铁的费用昂贵，因此需合理安排地铁的建立路线，使乘客可以沿地铁到达各个辖区，并使总的建立费用最小。二、课程设计主要内容及要求地铁建立内容及要求〔1〕从包含各辖区的地图文件中读入名称和各辖区间的直接距离。〔2〕根据读入的各辖区间距离信息，计算应该建立哪些辖区建的地铁线路。〔3〕输出应该建立的地铁路线及所需建立的总里程信息。三、对课程设计说明书撰写内容、格式、字数的要求1．课程设计说明书是表达和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。一般不应少于3000字。2．在适当位置配合相应的实验原理图、数据通路图、微程序流程图、实验接线图、微指令代码表等图表进展说明。应做到文理通顺，内容正确完整，书写工整，装订整齐。3．设计总结局部主要写本人完成工作简介以及自己的设计体会，包括通过课程设计学到了什么，哪里遇到了困难，解决的方法以及今后的目标。4．课程设计说明书手写或打印均可。手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时采用A4纸，页边距均为20mm，正文采用宋体小四号字，行间距18磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5．课程设计说明书装订顺序为：封面、任务书、任务分工表、成绩评定表、目录、正文、参考文献。磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5．课程设计说明书装订顺序为：封面、任务书、任务分工表、成绩评定表、目录、正文、参考文献。四、设计完成后应提交成果的种类、数量、质量等方面的要求1．完成"任务书〞中指定的操作功能，运行稳定。2．课程设计说明书。五、时间进度安排顺序阶段日期计划完成容备注1第1天阅读资料2第2—3天系统分析设计3第4—7天程序编制、调试及运行4第8—9天成绩评定5第10天撰写课程设计说明书六、主要参考资料〔文献〕[1]滕国文.数据构造课程设计.:清华大学.2010.09[2]MarkAllenWeiss编著.数据构造与算法分析.:人民邮电.2007[3]李春葆.数据构造〔C语言版〕习题与解析.:清华大学.2002..04[4]熊锡义主编C语言程序设计案例教程**理工大学09年3月版[5]严蔚敏吴伟民.数据构造〔C语言版〕.:清华大学.2007[6]谭浩强.C程序设计.:清华大学.1999.12阳工程学院程序设计根底课程设计成绩评定表系〔部〕：计算机科学与技术系班级：计算机B143学生**：王世杰指导教师评审意见评价内容具体要求权重评分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15432工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作，0.25432工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整标准。0.55432指导教师评审成绩〔加权分合计乘以8〕分加权分合计指导教师签名：年月日评阅教师评审意见评价内容具体要求权重评分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25432工作量工作量饱满，难度适中。0.55432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整标准。0.35432评阅教师评审成绩〔加权分合计乘以4〕分加权分合计评阅教师签名：年月日答辩小组评审意见评价内容具体要求权重评分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，根本上反映了所完成任务的全部内容；时间符合要求。0.55432辩论思路清晰；答复下列问题有理论依据，根本概念清楚；主要问题答复准确，深入，有说服力。0.55432辩论小组评审成绩〔加权分合计乘以8〕分加权分合计辩论小组教师签名：年月日课程设计总评成绩分阳工程学院程序设计根底课程设计成绩评定表系〔部〕：计算机科学与技术系班级：计算机B143学生**：张云朗指导教师评审意见评价内容具体要求权重评分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15432工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作，0.25432工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整标准。0.55432指导教师评审成绩〔加权分合计乘以8〕分加权分合计指导教师签名：年月日评阅教师评审意见评价内容具体要求权重评分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25432工作量工作量饱满，难度适中。0.55432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整标准。0.35432评阅教师评审成绩〔加权分合计乘以4〕分加权分合计评阅教师签名：年月日答辩小组评审意见评价内容具体要求权重评分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，根本上反映了所完成任务的全部内容；时间符合要求。0.55432答辩思路清晰；答复下列问题有理论依据，根本概念清楚；主要问题答复准确，深入，有说服力。0.55432辩论小组评审成绩〔加权分合计乘以8〕分加权分合计辩论小组教师签名：年月日课程设计总评成绩分阳工程学院程序设计根底课程设计成绩评定表系〔部〕：计算机科学与技术系班级：计算机B143学生**：王丛伍指导教师评审意见评价内容具体要求权重评分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15432工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作，0.25432工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整标准。0.55432指导教师评审成绩〔加权分合计乘以8〕分加权分合计指导教师签名：年月日评阅教师评审意见评价内容具体要求权重评分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25432工作量工作量饱满，难度适中。0.55432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整标准。0.35432评阅教师评审成绩〔加权分合计乘以4〕分加权分合计评阅教师签名：年月日答辩小组评审意见评价内容具体要求权重评分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，根本上反映了所完成任务的全部内容；时间符合要求。0.55432辩论思路清晰；答复下列问题有理论依据，根本概念清楚；主要问题答复准确，深入，有说服力。0.55432辩论小组评审成绩〔加权分合计乘以8〕分加权分合计辩论小组教师签名：年月日课程设计总评成绩分-.z.摘要*城市要在其各个辖区之间修建地铁来加快经济的开展，但由于建立地铁的费用昂贵，因此需合理安排地铁的建立路线，使乘客可以沿地铁到达各个辖区，并使总的建立费用最小。地铁建立可以缓解城市交通压力。城市交通问题，已经成为现代人无法面对的通病。经济开展，汽车数量增长速度，远远快于城市道路的扩张速度。地铁这个交通的特点就是到达的快捷性和可靠性，运载能力强，能够在很短的时间运输大量的人群。运行中不塞车，是城市中最具可靠性的交通工具。第二、增加地铁交通体系，可以使城市规划更加科学和合理。可以节约能源。缓解对石油、天然气消耗的压力。可以减少污染。地铁这种交通工具污染少。可以节省时间。因为不塞车，速度快，节省上班族上下班的在途时间。因此我们小组利用数据构造输入各条线路起点、终点和直接距离，建立无向图，邻接矩阵存储输出邻接矩阵中的普利姆算法计算最小生成树输出最有线路。关键词数据构造最小生成树地铁邻接矩阵-.z.目录摘要I第一章问题分析11.1引言11.2背景11.3分析11.3.1调试过程中的问题1第二章原理与运行环境22.1数据理论22.1.1地铁问题的数据理论22.2运行环境22.2.1翻开方法22.2.2翻开Microsoftvisualstdio6.0运行环境32.2.3源程序的建立与编辑、连接4第三章系统分析与设计63.1地铁建立问题分析与设计63.1.1系统的功能6第四章系统功能实现74.1地铁建立问题的系统功能实现74.1.1定义主函数74.1.2创立构造体数组，存储辖区名84.1.3创立无向图，邻接矩阵存储94.1.4输出邻接矩阵10普利姆算法求最小生成树，输出最优路线11结论14致谢15参考文献16-.z.第一章问题分析1.1引言数据构造是计算机存储、组织数据的方式。数据构造是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据构造可以带来更高的运行或者存储效率。数据构造往往同高效的检索算法和索引技术有关。一般认为，一个数据构造是由数据元素依据*种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑构造；数据必须在计算机内存储，数据的存储构造是数据构造的实现形式，是其在计算机内的表示；此外讨论一个数据构造必须同时讨论在该类数据上执行的运算才有意义。一个逻辑数据构造可以有多种存储构造，且各种存储构造影响数据处理的效率。在许多类型的程序的设计中，数据构造的选择是一个根本的设计考虑因素。许多大型系统的构造经历说明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据构造。许多时候，确定了数据构造后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据构造与之适应。不管哪种情况，选择适宜的数据构造都是非常重要的。选择了数据构造，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。本次课程设计主要利用数据构造中最小生成树实现地铁最优线路问题。1.2背景随着经济的迅速开展，城市交通"外拥内堵〞，情况严峻，压力巨大。我们为了缓解城市交通拥堵，改变过去以地上交通为主的单一格局，构建地上地下立体交通体系，并通过与其他交通方式的有机衔接，将极大地缓解城市交通拥堵状况，解决人民群众出行难的问题，于是我们建立了地铁建立工程。1.3分析1.3.1调试过程中的问题1.调试过程中遇到的问题是如何解决的以及对设计与实现的回忆讨论和分析：=1\*GB3①开场准备将辖区名和相应距离同存储在邻接矩阵中，但因为数据类型不同，这个想法难以实现；而且就算实现了，在后面的程序中操作也非常麻烦。所以我创立了一个构造体数组用来存储辖区名，这样辖区名和数组下标一一对应，简明、易懂、清晰。以后只要看数字所对应的下标存储的是哪个辖区，就可以将其引用。=2\*GB3②运行程序时，我要输出最优路线对应的辖区，所以在输出时要直接引用构造体数组，但怎么都不行，我就分模块来调试，最后发现，原来是没有将构造体数组的地址传过来。修改后，程序运行正常。=3\*GB3③没有使用指针，防止了指针指向错误存储区而造成的错误。2.算法的时间复杂度和空间复杂度的分析，改良设想：本程序的时间复杂度为o〔n^2〕，主要是for循环的作用。-.z.第二章原理与运行环境2.1数据理论2.1.1地铁问题的数据理论1．程序所能到达的功能：⑴creatve〔〕创立构造体数组，存储辖区名=2\*GB2⑵CreateGraph〔〕建立辖区间直接距离的无向图，用邻接矩阵存储⑶pri〔〕输出无向图的邻接矩阵⑷prim〔〕普利姆算法计算无向图的最小生成树，输出最优路线2．输入的形式和输入值的范围：输入数字和字母，字母为辖区名，数字为直接距离，名称个数n，线路个数e，0<e<n(n-1),直接距离weigth，0<weigth<999993．输出的形式：最正确建立路径为：〔辖区名辖区名〕直接路径2.2运行环境数据构造程序的运行环境为Microsoftvisualc++6.02.2.1翻开方法开场→程序→Microsoftvisualstdio6.0→MicrosoftVisualC++6.0，如图2-1所示。图2-1翻开VisualC++的方法2.2.2翻开Microsoftvisualstdio6.0运行环境其工作环境如图2-2所示。图2-2VisualC++工作环境2.2.3源程序的建立与编辑、连接⑴建立C语言源程序文件。建立方法：选择菜单命令"File〞→"New〞或直接点击对话框中的"New〞，如图2-3所示。图2-3建立C语言源程序文件⑵程序的编辑与编译。编辑完成后，选择菜单栏中的"组建〞→"调试程序〞，或者直接点击工具栏中"箭头〞按钮，即可对程序进展编译。当输出区显示"0errors，0warnings〞时表示没有错误和警告，反之，则会按序号列出错误和警告。双击错误或警告，编辑标志会出现在源文件可能出错的位置，我们可以在此对源程序中的错误进展更改。当然有时提示位置不一定很准确。程序的编辑于编译操作，如图2-4所示。图2-4程序的编辑与编译⑶程序的执行。单击工具栏上的"深红色感慨号〞按钮，即可执行刚编写的程序。假设程序完全正确，即可弹出运行框。如图2-5所示。图2-5程序的执行-.z.第三章系统分析与设计3.1地铁建立问题分析与设计3.1.1系统的功能此系统为：*城市要在各个辖区之间修建地铁，由于地铁建立费用昂贵，因此需要合理安排地铁建立线路，使市民可以沿地铁到达各个辖区，并使总费用最小。其主功能模块的流程图如图3-1所示。开场开场输入辖区个数和辖区名输入辖区个数和辖区名输入线路个数输入线路个数判断0<e<n(n-1)判断0<e<n(n-1)Y输入各条线路起点、终点和直接距离输入各条线路起点、终点和直接距离建立无向图，邻接矩阵存储建立无向图，邻接矩阵存储输出邻接矩阵输出邻接矩阵普利姆算法计算最小生成树普利姆算法计算最小生成树输出最优线路和总里程输出最优线路和总里程完毕完毕-.z.第四章系统功能实现4.1地铁建立问题的系统功能实现4.1.1定义主函数主函数是程序的入口，采用模块化设计，首先声明一些必要的变量函数如下：⑴creatve〔〕创立构造体数组，存储辖区名=2\*GB2⑵CreateGraph〔〕建立辖区间直接距离的无向图，用邻接矩阵存储⑶pri〔〕输出无向图的邻接矩阵⑷prim〔〕普利姆算法计算无向图的最小生成树，输出最优路线主函数调用各模块的关系如下：⑴主函数main〔〕调用intcreatve(cityve*[ma*])创立构造体数组存储辖区名；=2\*GB2⑵主函数main〔〕调用intCreateGraph(intg[][ma*],intn,voidpri(intg[][ma*],intn))建立无向图，用邻接矩阵存储；⑶intCreateGraph(intg[][ma*],intn,voidpri(intg[][ma*],intn))调用voidpri(intg[][ma*],intn)输出邻接矩阵；⑷主函数main〔〕调用voidprim(intg[][ma*],intn,cityve*[ma*])计算最小生成树，输出最优线路和总里程。源代码如下：voidmain()/*主函数*/{intg[ma*][ma*],n;cityve*[ma*];n=creatve(ve*);CreateGraph(g,n,pri);printf("\n\n最正确建立路线为:\n");printf("(辖区名辖区名)直接距离\n\n");prim(g,n,ve*);}功能实现图如图4-1所示。图4-1初始化界面创立构造体数组，存储辖区名进入主程序页面后，应输入各个辖区名，并调用函数对输入的辖区名进展存储。源代码如下：intcreatve(cityve*[ma*])//创立辖区名数组{ inti,n;printf("设置辖区的个数:");//城市中辖区的个数scanf("%d",&n); for(i=1;i<n+1;i++)//建立城市辖区名数组 { printf("第%d个城市辖区名称为:",i); scanf("%s",ve*[i].name); } return(n);}功能实现图4-2所示。图4-2创立无向图，邻接矩阵存储按照地铁建立问题的要求，要将各个辖区为顶点作为图，并用邻接矩阵将其存储。其源代码如下：intCreateGraph(intg[][ma*],intn,voidpri(intg[][ma*],intn))/*建立无向图*/{inte,i,j,k,v1=0,v2=0,weight=0;printf("输入可建地铁线线路个数:");scanf("%d",&e);while(e<=0||e>=n*(n-1)||n>=ma*){error();printf("输入可建地铁线线路个数:");scanf("%d",&e);}for(i=1;i<=n;i++)for(j=1;j<=n;j++)g[i][j]=inf;/*初始化矩阵，全部元素设为无穷大*/for(k=1;k<=e;k++){printf("输入第%d条线路的起始辖区,终点辖区,直接距离:",k);scanf("%d%d%d",&v1,&v2,&weight);while(v1==v2||v1>n||v2>n||v1<1||v2<1){error();printf("输入第%d条线路的起始辖区,终点辖区,直接距离:",k);scanf("%d%d%d",&v1,&v2,&weight);}g[v1][v2]=weight;g[v2][v1]=weight;}printf("\n输出存储矩阵:\n");pri(g,n);returnOK;}功能实现图如图4-3所示图4-3输出邻接矩阵此时将邻接矩阵存储的结果显示一下，以便检查下一步中结果的正确性。其源代码如下：voidpri(intg[][ma*],intn)/*输出无向图的邻接矩阵*/{inti,j;for(i=0;i<=n;i++)printf("%d\t",i);for(i=1;i<=n;i++){printf("\n%d\t",i);for(j=1;j<=n;j++)/*输出边的权值*/{if(g[i][j]==inf)printf("∞\t",'\354');elseprintf("%d\t",g[i][j]);}}printf("\n");}功能实现如图4-4所示图4-4普利姆算法求最小生成树，输出最优路线用普利姆算法求出最短路程，则为地铁建立的最优路线。其源代码如下：voidprim(intg[][ma*],intn,cityve*[ma*])/*prim的函数*/{intlowcost[ma*],closest[ma*];inti,j,k,min,s=0;for(i=2;i<=n;i++)/*n个顶点，n-1条边*/{lowcost[i]=g[1][i];/*初始化*/closest[i]=1;/*顶点未参加到最小生成树中*/}lowcost[1]=0;/*标志顶点1参加U集合*/for(i=2;i<=n;i++)/*形成n-1条边的生成树*/{min=inf;k=0;for(j=2;j<=n;j++)/*寻找满足边的一个顶点在U,另一个顶点在V的最小边*/if((lowcost[j]<min)&&(lowcost[j]!=0)){min=lowcost[j];k=j;s+=min;}printf("(%s%s)%d\t",ve*[closest[k]].name,ve*[k].name,min);lowcost[k]=0;/*顶点k参加U*/for(j=2;j<=n;j++)/*修改由顶点k到其他顶点边的权值*/if(g[k][j]<lowcost[j]){lowcost[j]=g[k][j];closest[j]=k;}printf("\n");}printf("\n修建地铁最短总里程为:");printf("%d",s);}功能实现如图4-5所示图4-5-.z.结论刚开场拿到题目的时候，没有什么思路，就翻书看了普利姆算法，然后也在网上搜索了相关的资料。找到有相似的程序，但不符合我的题目的要求，不是邻接矩阵存储，输入输出也不行。于是，我们小组就仔细的看了程序，弄懂之后我们就开场编我