地铁课设报告.docx

沈阳工程学院课程设计设计题目：地铁问题系别蟀学生姓名学号_指导教师职称讲师、讲师起止日期：2022年6月15日起至2022年6月26日止沈阳工程学院课程设计任务书课程设计题目：地铁问题一、课程设计的原始资料及依据地铁建设问题描述：某城市要在其各个辖区之间修筑地铁来加快经济的发展，但由于建设地铁的费用昂贵，因此需合理安排地铁的建设路线，使乘客可以沿地铁到达各个辖区,并使总的建设费用最小。二、课程设计主要内容及要求地铁建设内容及要求(1)从包含各辖区的地图文件中读入名称和各辖区间的直接距离。(2)根据读入的各辖区间距离信息，计算应该建设哪些辖区建的地铁路线。(3)输出应该建设的地铁路线及所需建设的总里程信息。三、对课程设计说明书撰写内容、格式、字数的要求1 .课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。普通不应少于3000字。2 .在适当位置配合相应的实验原理图、数据通路图、微程序流程图、实验接线图、微指令代码表等图表进行说明。应做到文理通顺，内容正确完整，书写工整，装订整齐。3 .设计总结部份主要写本人完成工作简介以及自己的设计体味，包括通过课程设计学到了什么，哪里遇到了艰难，解决的办法以及今后的目标。4 .课程设计说明书手写或者打印均可。手写要用学校统一的课程设计用纸，用黑或者蓝黑墨水工整书写；打印时采用A4纸，页边距均为20,正文彩用宋体小四号字，行间距18磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5 .课程设计说明书装订顺序为：封面、任务书、任务分工表、成绩评定表、目录、正文、参考文献。磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5.课程设计说明书装订顺序为：封面、任务书、任务分工表、成绩评定表、目录、正文、参考文献。四、设计完成后应提交成果的种类、数量、质量等方面的要求1 .完成“任务书”中指定的操作功能，运行稳定。2 .课程设计说明书。五、时间进度安排顺序阶段日期计划完成内容备注1第1天阅读资料2第23天系统分析设计3第4一7天程序编制、调试及运行4第89天成绩评定5第10天撰写课程设计说明书六、主要参考资料（文献）1滕国文.数据结构课程设计.北京:清华大学出版社.2022.092MarkAlienWeiss编著.数据结构与算法分析.北京：人民邮电出版社.20223李春葆.数据结构（C语言版）习题与解析.北京:清华大学出版社.2002.044熊锡义主编C语言程序设计案例教程大连理工大学出版社09年3月版5严蔚敏吴伟民.数据结构（C语言版）.北京:清华大学出版社.20226谭浩强.C程序设计.北京:清华大学出版社.1999.12沈阳工程学院程序设计基础课程设计成绩评定表系（部）：计算机科学与技术系班级：计算机B143学生姓名：王世杰指导教师评审意见评价内容具体要求权重评分加权分调研论证能独立查阅文献,采集资料；能制定课程设计方案和日程安排。0.15432工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作，0.25432工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55432指导教师评审成绩办（加权分合计乘以8）K加权分合计指导教师签名：年月日评阅教师评审意见评价内容具体要求权重评分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25432工作量工作量饱满，难度适中。0.55432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35432评阅教师评审成绩（加权分合计乘以4）分加权分合计评阅教师签名：年月日答辩小组评审意见评价内容具体要求权重评分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清晰，论点正确，有层次，有重点，基本上反了所完成任务的全部内容；时间符合要求。映0.55432答辩思路清晰；回答问题有理论依据，基本概念清晰：主要问题回答准确，深入，有说服力。0.55432答辩小组评审成绩（加权分合计乘以8）分加权分合计答辩小组教师签名：年月日课程设计总评成绩分沈阳工程学院程序设计基础课程设计成绩评定表系（部）：计算机科学与技术系班级：计算机B143学生姓名：张云朗指导教师评审意见评价内容具体 要 求权重评分加权分调研论证能独立查阅文献,采集资料；能制定课程设计方 案和日程安排。0. 15432工作能力 态度工作态度认真，遵守纪律，出勤情况是否良好， 能够独立完成设计工作，0.25432工作量按期圆满完成规定的设计任务，工作量饱满，难 度适宜。0.25432说明书的 质量说明书立论正确，论述充分，结论严谨合理，文 字通顺，技术用语准确，符号统一，编号齐全， 图表完备，书写工整规范。0.55432指导教师评审成绩A（加权分合计乘以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）分加权分合计答辩小组教师签名：年月日课程设计总评成绩分摘要某城市要在其各个辖区之间修筑地铁来加快经济的发展，但由于建设地铁的费用昂贵，因此需合理安排地铁的建设路线，使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。地铁建设可以缓解城市交通压力。城市交通问题，已经成为现代人无法面对的通病。经济发展，汽车数量增长速度，远远快于城市道路的扩张速度。地铁这个交通的特点就是到达的快捷性和可靠性，运载能力强，能够在很短的时间运输大量的人群。运行中不塞车，是城市中最具可靠性的交通工具。第二、增加地铁交通体系，可以使城市规划更加科学和合理。可以节约能源。缓解对石油、天然气消耗的压力。可以减少污染。地铁这种交通工具污染少。可以节省时间。因为不塞车，速度快，节省上班族上下班的在途时间。因此我们小组利用数据结构输入各条路线起点、终点和直接距离，建立无向图，邻接矩阵存储输出邻接矩阵中的普利姆算法计算最小生成树输出最有路线。关键词数据结构最小生成树地铁邻接矩阵摘要I第一章问题分析11.1 弓I言112背景11.3 分析11.3.1 调试过程中的问题1第二章原理与运行环境32.1 S理论32.1.1 地铁问题的数据理论32.2 运行环境32.2.1 打开方法32.2.2 打开McRoSOFTVlSUALSTDIo6.0运行环境42.2.3 源程序的建立与编辑、连接5第三章系统分析与设计73.1 地铁建设问题分析与设计73.1.1 系统的功能7第四章系统功能实现84.1 地铁建设问题的系统功能实现84.1.1 定义主函数84.1.2 创建结构体数组，存储辖区名94.1.3 创建无向图，邻接矩阵存储104.1.4 输出邻接矩阵114.1.5 普利姆算法求最小生成树，输出最优路线12结论15致谢15第婀16第一章问题分析1.1 引言数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或者多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。普通认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才故意义。一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率。在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的艰难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的浮现，面向对象的程序设计语言就是其中之一。本次课程.计主要利用数据结构中最小生成树实现地铁最优路线问题。1.2 背景随着经济的迅速发展，城市交通“外拥内堵”，情况严峻，压力巨大。我们为了缓解城市交通拥堵，改变过去以地上交通为主的单一格局，构建地上地下立体交通体系，并通过与其他交通方式的有机衔接，将极大地缓解城市交通拥堵状况，解决人民群众出行难的问题，于是我们建立了地铁建设项目。1.3 分析1.3.1 调试过程中的问题1 .调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析：开始准备将辖区名和相应距离同存储在邻接矩阵中，但因为数据类型不同，这个想法难以实现；而且就算实现了，在后面的程序中操作也非常麻烦。所以我创建了一个结构体数组用来存储辖区名，这样辖区名和数组下标一一对应，简明、易懂、清晰。以后只要看数字所对应的下标存储的是哪个辖区，就可以将其引用。运行程序时，我要输出最优路线对应的辖区，所以在输出时要直接引用结构体数组，但怎么都不行，我就分模块来调试，最后发现，原来是没有将结构体数组的地址传过来。修改后，程序运行正常。没有使用指针，避免了指针指向错误存储区而造成的错误。2 .算法的时间复杂度和空间复杂度的分析，改进设想：本程序的时间复杂度为。(n2),主要是for循环的作用。第二章原理与运行环境2.1 数据理论2.1.1 地铁问题的数据理论1 .程序所能达到的功能：CreatVe()创建结构体数组，存储辖区名CrCateGraPh()-建立辖区间直接距离的无向图，用邻接矩阵存储pri()-一输出无向图的邻接矩阵(4)prim()-一普利姆算法计算无向图的最小生成树，输出最优路线2 .输入的形式和输入值的范围：输入数字和字母，字母为辖区名，数字为直接距离，名称个数n,路线个数e,O<e<n(n-1),直接距离weigth,0<weigth<999993 .输出的形式：最佳建设路径为：(辖区名一一辖区名)-一直接路径4 .2运行环境数据结构程序的运行环境为Microsoftvisualc+6.02.2.1打开方法开始-*程序fMicrOSoftvisualstdio6.0-*MicrosoftVisualC+6.0,如图2-1所示。"MT!W生加IitM<U*MtUK<WAjvC440wfi<mu(MBiw.*<.ittyaC*)JfWK0血z!fZZ建©(4lIug.lfJrQCgTtgWSMMCt4Cr<r¾r22MHtaiBfOlAl9tdWX4MW¼HIm*4.<aMkw«“fUMO1“58CV1»e6才hmfi»Mlrttf<9*o<t*r<M«*v<M*rfsS.,tAT4MMEMer*fr5MZHOrVzW(Qi>H0"fOC0B52CC”.Cjn*vaj*I54<4Otv>*¼OlKM*MUNuJQ0BrZ<tFr«>iOZWnN:焚rwrtrLLIM£-KilaL3aN(C<Rr.TPWFF图2-1打开ViSUalC+的方法2.2.2打开Microsoftvisualstdio6.0运行环境其工作环境如图2-2所示。图2-2ViSlIaIC+工作环境2.2.3源程序的建立与编辑、连接建立C语言源程叙文件。建立方法：选择菜单命令“File”一“New”或者直接点击对话框中的“New”，如图2-3所示。图2-3建立C语言源程叙文件程序的编辑与编译。编辑完成后，选择菜单栏中的“组建”一“调试程序”，或者直接点击工具栏中“箭头”按钮，即可对程序进行编译。当输出区显示“Oerrors,Owarnings”时表示没有错误和警告，反之，则会按序号列出错误和警告。双击错误或者警告，编辑标志会浮现在源文件可能出错的位置，我们可以在此对源程序中的错误进行更改。固然有时提示位置不一定很准确。程序的编辑于编译操作，如图2-4所示。图2-4程序的编辑与编译程序的执行。单击工具栏上的“深红色感叹号”按钮，即可执行刚编写的程序。若程序彻底正确，即可弹出运行框。如图2-5所示。图2-5程序的执行第三章系统分析与设计3.1 地铁建设问题分析与设计3.1.1 系统的功能因此需要合理此系统为：某城市要在各个辖区之间修筑地铁，由于地铁建设费用昂贵,安排地铁建设路线，使市民可以沿地铁到达各个辖区，并使总费用最小。其主功能模块的流程图如图3-1所示。第四章系统功能实现4.1 地铁建设问题的系统功能实现4.1.1 定义主函数主函数是程序的入口，采用模块化设计，首先声明一些必要的变量函数如下：CreatVe()创建结构体数组，存储辖区名CreateGraPh()-建立辖区间直接距离的无向图，用邻接矩阵存储pri()-一输出无向图的邻接矩阵(4)prim()-普利姆算法计算无向图的最小生成树，输出最优路线主函数调用各模块的关系如下：主函数main()调用intcreatve(cityvexmax)创建结构体数组存储辖区名；主函数mainO调用intCreateGraph(intgmax,intn,voidpri(intgmax,intn)建立无向图，用邻接矩阵存储；(3) intCreateGraph(intgmax,intn,voidpri(intgmax,intn)调用voidpri(intgmax,intn)输出邻接矩阵；主函数main()调用VOidPrim(intgmax,intn,cityvexmax)计算最小生成树,输出最优路线和总里程。源代码如下：voidmain()/*主函数*/(intgmaxmax,n;cityvexmax;n=creatve(vex);CreateGraph(g,n,pri);Printf(nn最佳建设路线为:n)；Printf(辖区名一一辖区名)-直接距离nn");prim(g,n,vex);)功能实现图如图4-1所示。4.1.2 创建结构体数组，存储辖区名进入主程序页面后，应输入各个辖区名，并调用函数对输入的辖区名进行存储。源代码如下：intcreatve(cityvexmax)创建辖区名数组(inti,n;Printf(设置辖区的个数：)；城市中辖区的个数SCanf("%d",&n);for(i=l;i<n+l;i+)建立城市辖区名数组(Printf(等d个城市辖区名称为：,i);scanf(z,%szz,vexi.name);)return(n);)功能实现图4-2所示。"C:DocumentsandSettingF608Debugayw.exc'(帔置辖区的个数二厂塞斗城正辖区名林为：a富2个城壶卷区名拴为：b氨个城市转区名校为：C第4个藏市珞区名林为：d编入可建地铁线线路个数：5箫入第1条线路的起始辖区,终点辖区.直接距离:图4-24.1.3 创建无向图,邻接矩阵存储按照地铁建设问题的要求，要将各个辖区为顶点作为图，并用邻接矩阵将其存储。其源代码如下：intCreateGraph(intgmax,intn,voidpri(intgmax,intn)/*建立无向图*/(inte,i,j,k,vl=0,v2=0,weight=0;Printf(输入可建地铁线路线个数:)；scanf(zz%d,z,&e);while(e<=0e>=n*(nl)n>=max)(error();Printf(输入可建地铁线路线个数:);scanf(zz%dzz,&e);for(i=l;i<=n;i+)for(j=l;j<=n;j+)gij=inf;/*初始化矩阵，全部元素设为无穷大*/for(k=l;k<=e;k+)(Printf(输入第%d条路线的起始辖区,终点辖区,直接距离:,k);scanf(z,%d%d%d,&vl,&v2,&weight);WhiIe(Vl=V21vl>nv2>nvl<lv2<l)(error();Printf(输入第%d条路线的起始辖区,终点辖区,直接距离:,k);scanf("%d%d%d”,&vl,&v2,&weight);gvlv2=weight;gv2vl=weight;)Printf(n输出存储矩阵：n);pri(g,n);returnOK;功能实现图如图4-3所示,F608D ebugayw. exe名名名名区区区区 城城城城 j÷÷÷ 个 12 3 4茎1 2 3 4 5 入入入入入入辖辖落a点点点点点吏离先离 ；距离:! 能离 柜离：3325431C:DocumpntandSettings图4-34.1.4 输出邻接矩阵此时将邻接矩阵存储的结果显示一下，以便检查下一步中结果的正确性。其源代码如下：voidpri(intgmax,intn)/*输出无向图的邻接矩阵7(inti,j;for(i=0;i<=n;i+)printfC,%dt",i);for(i=1;i<=n;i+)printf("n%dt",i);for(j=1;j<=n;j+)/*输出边的权值*/(if(gij=inf)prihtrf(3"54,);elseprintf(,'%dt",gij);printf("n");功能实现如图4-4所示j图4-4点点点点点线茨坎茨燃5即见K,见见沙始始始始始为为为为到需需起X -XMM AMH专名名名的普路咯路厅区区区区始线线线线线 ATP- P- H- j 12345 必恋克克.克.国434 432 523 411123 :一 离离高S离 巨巨巨巨巨 Sn 直直直直直 ， ， " ， 4.1.5 普利姆算法求最小生成树，输出最优路线用普利姆算法求出最短路程，则为地铁建设的最优路线。其源代码如下：voidprim(intgmax,intn,cityvexmax)*Prim的函数*/(intlowcostmax,c1osestmax;inti,j,k,min,s=0;for(i=2;i<=n;i+)*n个顶点，nT条边*/lowcosti=gli;*初始化*/closesti=l;*顶点未加入到最小生成树中*/)1Owcost1=O;/*标志顶点1加入U集合*/for(i=2;i<=n;i+)/*形成nT条边的生成树*/(min=inf;k=0;for(j=2;j<=n;j+)/*寻觅满足边的一个顶点在U,另一个顶点在V的最小边*/if(lowcostj<min)&&(lowcostj!=0)(min=lowcostj;k=j;s+=min;Jprintf(%s%s)%dt，vexclosestk.name,vexk.name,min);lowcostk=0;*顶点k加入U*/for(j=2;j<=n;j+)*修改由顶点k到其他顶点边的权值*/if(gkj<lowcostj)(lowcostj=gkj;closestj=k;printf(z,nz,);Printf(n修筑地铁最短总里程为:)；printf(,z%dzz,s);)功能实现如图4-5所示图4-5刚开始拿到题目的时候，没有什么思路，就翻书看了普利姆算法，然后也在网上搜索了相关的资料。找到有相似的程序，但不符合我的题目的要求，不是邻接矩阵存储，输入输出也不行。于是，我们小组就子细的看了程序，弄懂之后我们就开始编我的程序。经过一个星期的奋斗，我们终于是把程序整出来了。这是一个坚苦而又漫长的过程。看着劳动成果，很欣慰！毕竟这是我们第一次自己动脑筋做课程设计。通过这次课程设计我们深刻的理解了普利姆算法，同时理解了数据结构中思想的严谨性和准确性，在这次设计过程中让我们各自找到了自己在设计过程中的缺点，我们大家意识到自己当时学明白并不代表自己就真正的会，自己在看书是看明白了不一定就能在计算机上运行，例如当输入为祝时候如果一个一个的输入程序会把回车也当做一个字符。再者就是在每次程序中浮现的老问题，在函数调用时如果传值和传址弄混那末在函数调用过程中就会浮现传不回地址或者传回的值为乱码。在以后的每一个程序中我们一定会尽自己最大努力，在每一个程序中我都细心地去敲入每一个字符，函数调用过程中先想明白在往上面写。我们一定会继续努力，不辜负父母和老师对我的期望！致谢本文是在曹福毅老师和李波老师的热情关心和指导下完成的。从课程设计的前期准备工作到最后的修改，还得到了老师提出的许多珍贵的意见和建议，使我们小组受益非浅。特殊是在最后的测试修改阶段，给我提了不少建议，使我能顺利的完成课程设计。在短暂的两周的相处时间里，老师赅博的知识、敏锐的思路和实事求是的工作作风给我留下了深刻的印象，这促使我们小组有了很大的进步，谨此向我的指导老师表示衷心的感谢和崇高的敬意。在论文完成过程中，我们还得到了不少同学的热心匡助，他们在我们做课程设计的这段时间，赋予我匡助与支持，这也是我能顺利完成课程设计的重要因素。本人向他们表示深深的谢意！我们也要感谢和我一起学习共同进步的其他同学，有不会的问题我也往往请教身边的同学。合作的学习模式我们间形成为了深厚的友谊以及合作精神。这对我们将来的学习生活和工作生活将产生积极的影响。惟独团结协作才干更好的完成任务目标。最后向在百忙之中评审本文的老师表示衷心的感谢！参考文献1范策等编著.算法与数据结构（C语言版）.北京：机械工业出版社，20042徐孝凯编著.数据结构实用教程（第二版）.北京：清华大学出版社，20223徐孝凯.数据结构辅导与提高实用教程（第二版）.北京：清华大学出版社，20034胡学刚.算法与数据结构算法设计指导.北京：清华大学出版社，19995张乃孝等.数据结构-C+÷与面向对象的途径.北京：高等教育出版社，20016耿国华等.数据结构一C语言描述.西安：西安电子科技大学出版社，20027殷人昆.数据结构用面向对象方法与C÷÷语言描述.北京：清华大学出版社，20228李春葆.数据结构（C语言）习题与解析.北京：清华大学出版社，20029邓俊辉.数据结构与算法（JaVa描述）.北京：机械工业出版社，202210张乃笑.数据结构与算法.电子工业出版社.2004.1011张乃孝等.数据结构-C+与面向对象的途径.北京：高等教育出版社，200112苏德富.计算机算法设计与分析.北京：电子工业出版社，2001