资源描述
沈 阳 工 程 学 院课 程 设 计设计题目：地铁问题系 别 班级 学生姓名 学号 指导教师 职称 讲师、讲师 起止日期：2015年6月15日起至2015年6月26日止 沈 阳 工 程 学 院课程设计任务书课程设计题目：地铁问题一、 课程设计的原始资料及依据地铁建设问题描述：某城市要在其各个辖区之间修建地铁来加快经济的发展，但由于建设地铁的费用昂贵，因此需合理安排地铁的建设路线，使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。二、课程设计主要内容及要求 地铁建设内容及要求（1）从包含各辖区的地图文件中读入名称和各辖区间的直接距离。（2）根据读入的各辖区间距离信息，计算应该建设哪些辖区建的地铁线路。（3）输出应该建设的地铁路线及所需建设的总里程信息。三、对课程设计说明书撰写内容、格式、字数的要求1课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。一般不应少于3000字。2在适当位置配合相应的实验原理图、数据通路图、微程序流程图、实验接线图、微指令代码表等图表进行说明。应做到文理通顺，内容正确完整，书写工整，装订整齐。3设计总结部分主要写本人完成工作简介以及自己的设计体会，包括通过课程设计学到了什么，哪里遇到了困难，解决的办法以及今后的目标。4课程设计说明书手写或打印均可。手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时采用A4纸，页边距均为20mm，正文采用宋体小四号字，行间距18磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5课程设计说明书装订顺序为：封面、任务书、任务分工表、成绩评定表、目录、正文、参考文献。磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5课程设计说明书装订顺序为：封面、任务书、任务分工表、成绩评定表、目录、正文、参考文献。四、设计完成后应提交成果的种类、数量、质量等方面的要求1完成“任务书”中指定的操作功能，运行稳定。2课程设计说明书。五、时间进度安排顺序阶段日期计 划 完 成 内 容备注1第1天阅读资料2第23天系统分析设计3第47天程序编制、调试及运行4第89天成绩评定5第10天撰写课程设计说明书六、主要参考资料（文献）1滕国文.数据结构课程设计.北京:清华大学出版社.2010.092 Mark Allen Weiss编著. 数据结构与算法分析. 北京: 人民邮电出版社.20073李春葆.数据结构（C语言版）习题与解析.北京:清华大学出版社.2002.044 熊锡义主编C语言程序设计案例教程 大连理工大学出版社 09年3月版5严蔚敏 吴伟民.数据结构（C语言版）. 北京:清华大学出版社.20076谭浩强.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）分加权分合计答辩小组教师签名： 年 月 日课 程 设 计 总 评 成 绩分沈阳工程学院课程设计报告 摘要摘 要某城市要在其各个辖区之间修建地铁来加快经济的发展，但由于建设地铁的费用昂贵，因此需合理安排地铁的建设路线，使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。地铁建设可以缓解城市交通压力。城市交通问题，已经成为现代人无法面对的通病。经济发展，汽车数量增长速度，远远快于城市道路的扩张速度。地铁这个交通的特点就是到达的快捷性和可靠性，运载能力强，能够在很短的时间运输大量的人群。运行中不塞车，是城市中最具可靠性的交通工具。第二、增加地铁交通体系，可以使城市规划更加科学和合理。可以节约能源。缓解对石油、天然气消耗的压力。可以减少污染。地铁这种交通工具污染少。可以节省时间。因为不塞车，速度快，节省上班族上下班的在途时间。 因此我们小组利用数据结构输入各条线路起点、终点和直接距离，建立无向图，邻接矩阵存储输出邻接矩阵中的普利姆算法计算最小生成树输出最有线路。关键词 数据结构 最小生成树 地铁 邻接矩阵I沈阳工程学院课程设计报告 目录目 录摘 要I第一章 问题分析11.1 引言11.2背景11.3 分析11.3.1 调试过程中的问题1第二章 原理与运行环境22.1 数据理论22.1.1 地铁问题的数据理论22.2 运行环境22.2.1打开方法22.2.2打开Microsoft visual stdio6.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输出邻接矩阵104.1.5普利姆算法求最小生成树，输出最优路线11结论14致谢15参考文献16沈阳工程学院课程设计报告 第一章 问题分析第一章 问题分析1.1 引言数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率。在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。本次课程设计主要利用数据结构中最小生成树实现地铁最优线路问题。1.2背景 随着经济的迅速发展，城市交通“外拥内堵”，情况严峻，压力巨大。我们为了缓解城市交通拥堵，改变过去以地上交通为主的单一格局，构建地上地下立体交通体系，并通过与其他交通方式的有机衔接，将极大地缓解城市交通拥堵状况，解决人民群众出行难的问题，于是我们建立了地铁建设项目。1.3 分析1.3.1 调试过程中的问题1.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析： 开始准备将辖区名和相应距离同存储在邻接矩阵中，但因为数据类型不同，这个想法难以实现；而且就算实现了，在后面的程序中操作也非常麻烦。所以我创建了一个结构体数组用来存储辖区名，这样辖区名和数组下标一一对应，简明、易懂、清晰。以后只要看数字所对应的下标存储的是哪个辖区，就可以将其引用。 运行程序时，我要输出最优路线对应的辖区，所以在输出时要直接引用结构体数组，但怎么都不行，我就分模块来调试，最后发现，原来是没有将结构体数组的地址传过来。修改后，程序运行正常。 没有使用指针，避免了指针指向错误存储区而造成的错误。2.算法的时间复杂度和空间复杂度的分析，改进设想：本程序的时间复杂度为o（n2），主要是for循环的作用。15沈阳工程学院课程设计报告 第二章 原理与运行环境第二章 原理与运行环境2.1 数据理论2.1.1 地铁问题的数据理论1程序所能达到的功能：creatve（）-创建结构体数组，存储辖区名CreateGraph（）-建立辖区间直接距离的无向图，用邻接矩阵存储pri（）-输出无向图的邻接矩阵prim（）-普利姆算法计算无向图的最小生成树，输出最优路线2输入的形式和输入值的范围：输入数字和字母，字母为辖区名，数字为直接距离，名称个数n，线路个数e，0en(n-1),直接距离weigth，0weigth999993输出的形式：最佳建设路径为：（辖区名-辖区名）-直接路径2.2 运行环境数据结构程序的运行环境为Microsoft visual c+ 6.02.2.1打开方法开始程序Microsoft visual stdio6.0Microsoft Visual C+ 6.0，如图2-1所示。图2-1打开Visual C+的方法2.2.2打开Microsoft visual stdio6.0运行环境其工作环境如图2-2所示。 图2-2 Visual C+工作环境2.2.3源程序的建立与编辑、连接建立C语言源程序文件。建立方法：选择菜单命令“File” “New”或直接点击对话框中的“New”，如图2-3所示。 图2-3建立C语言源程序文件程序的编辑与编译。编辑完成后，选择菜单栏中的“组建”“调试程序”， 或者直接点击工具栏中“箭头”按钮，即可对程序进行编译。当输出区显示“0 errors， 0 warnings ”时表示没有错误和警告，反之，则会按序号列出错误和警告。双击错误或警告，编辑标志会出现在源文件可能出错的位置，我们可以在此对源程序中的错误进行更改。当然有时提示位置不一定很准确。程序的编辑于编译操作，如图2-4所示。图2-4 程序的编辑与编译程序的执行。单击工具栏上的“深红色感叹号”按钮，即可执行刚编写的程序。若程序完全正确，即可弹出运行框。如图2-5所示。图2-5程序的执行沈阳工程学院课程设计报告 第三章 系统分析与设计第三章 系统分析与设计3.1地铁建设问题分析与设计3.1.1 系统的功能此系统为：某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。其主功能模块的流程图如图3-1所示。开始输入辖区个数和辖区名输入线路个数判断0en(n-1) N Y输入各条线路起点、终点和直接距离 建立无向图，邻接矩阵存储输出邻接矩阵普利姆算法计算最小生成树输出最优线路和总里程结束沈阳工程学院课程设计报告 第四章 系统功能实现第四章 系统功能实现4.1地铁建设问题的系统功能实现4.1.1 定义主函数主函数是程序的入口，采用模块化设计，首先声明一些必要的变量函数如下：creatve（）-创建结构体数组，存储辖区名CreateGraph（）-建立辖区间直接距离的无向图，用邻接矩阵存储pri（）-输出无向图的邻接矩阵prim（）-普利姆算法计算无向图的最小生成树，输出最优路线主函数调用各模块的关系如下：主函数main（）调用int creatve(city vexmax)创建结构体数组存储辖区名；主函数main（）调用int CreateGraph(int gmax,int n,void pri(int gmax,int n)建立无向图，用邻接矩阵存储； int CreateGraph(int gmax,int n,void pri(int gmax,int n)调用void pri(int gmax,int n)输出邻接矩阵； 主函数main（）调用void prim(int gmax,int n,city vexmax)计算最小生成树，输出最优线路和总里程。源代码如下：void main() /* 主函数 */ int gmaxmax,n; city vexmax; n=creatve(vex); CreateGraph(g,n,pri); printf(nn最佳建设路线为:n); printf(辖区名-辖区名)-直接距离nn); prim(g,n,vex);功能实现图如图4-1所示。图4-1初始化界面4.1.2创建结构体数组，存储辖区名进入主程序页面后，应输入各个辖区名，并调用函数对输入的辖区名进行存储。源代码如下： int creatve(city vexmax)/创建辖区名数组int i,n; printf(设置辖区的个数: );/城市中辖区的个数 scanf(%d,&n);for(i=1;in+1;i+)/建立城市辖区名数组 printf(第%d个城市辖区名称为: ,i); scanf(%s,vexi.name);return(n);功能实现图4-2所示。图4-24.1.3创建无向图，邻接矩阵存储按照地铁建设问题的要求，要将各个辖区为顶点作为图，并用邻接矩阵将其存储。其源代码如下： int CreateGraph(int gmax,int n,void pri(int gmax,int n) /* 建立无向图 */ int e,i,j,k,v1=0,v2=0,weight=0; printf(输入可建地铁线线路个数:); scanf(%d,&e); while(e=n*(n-1)|n=max) error(); printf(输入可建地铁线线路个数:); scanf(%d,&e); for(i=1;i=n;i+) for(j=1;j=n;j+) gij=inf; /* 初始化矩阵，全部元素设为无穷大 */ for(k=1;kn|v2n|v11|v21) error(); printf(输入第 %d 条线路的起始辖区,终点辖区,直接距离:,k); scanf(%d%d%d,&v1,&v2,&weight); gv1v2=weight; gv2v1=weight; printf(n输出存储矩阵:n); pri(g,n); return OK; 功能实现图如图4-3所示图4-3 4.1.4输出邻接矩阵此时将邻接矩阵存储的结果显示一下，以便检查下一步中结果的正确性。其源代码如下：void pri(int gmax,int n) /* 输出无向图的邻接矩阵 */ int i,j; for(i=0;i=n;i+) printf( %dt,i); for(i=1;i=n;i+) printf(n %dt,i); for(j=1;j=n;j+) /* 输出边的权值 */ if(gij=inf) printf( t,354); else printf( %dt,gij); printf(n);功能实现如图4-4所示图4-4 4.1.5普利姆算法求最小生成树，输出最优路线用普利姆算法求出最短路程，则为地铁建设的最优路线。其源代码如下：void prim(int gmax,int n,city vexmax) /* prim的函数 */ int lowcostmax,closestmax; int i,j,k,min,s=0; for(i=2;i=n;i+) /* n个顶点，n-1条边 */ lowcosti=g1i; /* 初始化 */ closesti=1; /* 顶点未加入到最小生成树中 */ lowcost1=0; /* 标志顶点1加入U集合 */ for(i=2;i=n;i+) /* 形成n-1条边的生成树 */ min=inf; k=0; for(j=2;j=n;j+) /* 寻找满足边的一个顶点在U,另一个顶点在V的最小边 */ if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; s+=min; printf(%s-%s)-%dt,vexclosestk.name,vexk.name,min); lowcostk=0; /* 顶点k加入U */ for(j=2;j=n;j+) /* 修改由顶点k到其他顶点边的权值 */ if(gkjlowcostj) lowcostj=gkj; closestj=k; printf(n); printf(n修建地铁最短总里程为:); printf(%d,s); 功能实现如图4-5所示图4-5 沈阳工程学院课程设计报告 结论结论 刚开始拿到题目的时候，没有什么思路，就翻书看了普利姆算法，然后也在网上搜索了相关的资料。找到有相似的程序，但不符合我的题目的要求，不是邻接矩阵存储，输入输出也不行。于是，我们小组就仔细的看了程序，弄懂之后我们就开始编我的程序。经过一个星期的奋斗，我们终于是把程序整出来了。这是一个坚苦而又漫长的过程。看着劳动成果，很欣慰！毕竟这是我们第一次自己动脑筋做课程设计。通过这次课程设计我们深刻的理解了普利姆算法，同时理解了数据结构中思想的严谨性和准确性，在这次设计过程中让我们各自找到了自己在设计过程中的缺点，我们大家意识到自己当时学明白并不代表自己就真正的会，自己在看书是看明白了不一定就能在计算机上运行，例如当输入为%c时候如果一个一个的输入程序会把回车也当做一个字符。再者就是在每次程序中出现的老问题，在函数调用时如果传值和传址弄混那么在函数调用过程中就会出现传不回地址或者传回的值为乱码。在以后的每个程序中我们一定会尽自己最大努力，在每个程序中我都细心地去敲入每个字符，函数调用过程中先想明白在往上面写。我们一定会继续努力，不辜负父母和老师对我的期望！沈阳工程学院课程设计报告 致谢致谢本文是在曹福毅老师和李波老师的热情关心和指导下完成的。从课程设计的前期准备工作到最后的修改，还得到了老师提出的许多宝贵的意见和建议，使我们小组受益非浅。特别是在最后的测试修改阶段，给我提了很多建议，使我能顺利的完成课程设计。在短暂的两周的相处时间里，老师渊博的知识、敏锐的思路和实事求是的工作作风给我留下了深刻的印象，这促使我们小组有了很大的进步，谨此向我的指导老师表示衷心的感谢和崇高的敬意。在论文完成过程中，我们还得到了很多同学的热心帮助，他们在我们做课程设计的这段时间，给予我帮助与支持，这也是我能顺利完成课程设计的重要因素。本人向他们表示深深的谢意！我们也要感谢和我一起学习共同进步的其他同学，有不会的问题我也常常请教身边的同学。合作的学习模式我们间形成了深厚的友谊以及合作精神。这对我们将来的学习生活和工作生活将产生积极的影响。只有团结协作才能更好的完成任务目标。最后向在百忙之中评审本文的老师表示衷心的感谢！15沈阳工程学院课程设计报告 参考文献参考文献1范策等编著.算法与数据结构（C语言版）.北京：机械工业出版社，20042徐孝凯编著.数据结构实用教程（第二版）.北京：清华大学出版社，2006 3徐孝凯.数据结构辅导与提高实用教程（第二版）.北京：清华大学出版社，20034胡学刚.算法与数据结构算法设计指导.北京：清华大学出版社，19995张乃孝等.数据结构C+与面向对象的途径.北京：高等教育出版社，2001 6耿国华等.数据结构C语言描述.西安：西安电子科技大学出版社，2002 7殷人昆.数据结构用面向对象方法与C+语言描述.北京：清华大学出版社，20078李春葆.数据结构（C语言）习题与解析.北京：清华大学出版社，2002 9邓俊辉.数据结构与算法（Java描述）.北京：机械工业出版社，2006 10张乃笑.数据结构与算法.电子工业出版社.2004.1011张乃孝等.数据结构C+与面向对象的途径.北京：高等教育出版社，2001 12苏德富.计算机算法设计与分析.北京：电子工业出版社，200116
展开阅读全文