搜索
课程设计报告课程名称数据结构课题名称交通咨询系统专业通信工程班级通信0902班学号姓名指导教师田娟秀、李杰君、张鏖烽2011年07月01日湖南工程学院课程设计任务书课程名称数据结构课题交通咨询系统专业班级通信工程0902学生姓名肖彬学号200903020205指导老师田娟秀、李杰君、张鏖烽审批任务书下达日期2011年06月27日任务完成日期2011年07月01日1设计内容与设计要求1.1设计内容课题六：交通咨询系统在交通网络非常发达的今天，人们出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需时间等问题也很感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示城市，边表示城市之间的交通关系。设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到达另外一个城市顶点之间的最短路径（里程）的问题。要求完成以下功能：（a）．根据实际情况，先建立交通网络图的存储结构。（b）．求某个城市到达其余各城市的最短路径。（c）．任一输入两个城市，要求求出他们之间的最短路径。1.2设计要求：1.2.1课程设计报告规范（1）需求分析a.程序的功能。b.输入输出的要求。（2）概要设计a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。（3）详细设计a.采用C语言定义相关的数据类型。b．写出各模块的类C码算法。c.画出各函数的调用关系图、主要函数的流程图。（4）调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。b.程序调试中遇到的问题以及解决问题的方法。c.课程设计过程经验教训、心得体会。（5）使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。（6）书写格式a.设计报告要求用A4纸打印成册：b.一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。（7）附录源程序清单（带注释）1.2.2考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：（1）平时出勤（占10%）（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）（3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）（4）设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。（5）独立完成情况（占10%）。1.2.3课程验收要求（1）运行所设计的系统。（2）回答有关问题。（3）提交课程设计报告。（4）提交软盘（源程序、设计报告文档）。（5）依内容的创新程度，完善程序情况及对程序讲解情况打分。2进度安排第19周：星期一8：00——12：00上课星期一14：30——18：30上机星期二14：30——18：30上机星期四8：00——12：00上机目录一、需求分析............................................................................................................................11.1.程序的功能...................................................................................................................11.2输入输出的要求。.......................................................................................................1二、概要设计............................................................................................................................12.1系统功能模块划分......................................................................................................12.1各模块数据类型...........................................................................................................42.21用邻接矩阵构造图结构函数CreateMGraph().................................................42.22费洛伊德Floyd()................................................................................................52.23狄克斯特拉Dijkstra().........................................................................................6三、详细设计............................................................................................................................73.1各模块流程图及其函数调用.......................................................................................73.11主要函数流程图:.................................................................................................73.12一个城市到其他城市的路径调用.....................................................................83.13任意两个城市之间路径调用.............................................................................83.2各模块C类算法..........................................................................................................93.21创建交通网络的邻接矩阵算法.........................................................................93.22查询某一城市至其他所有城市的最短路径算法..............................................93.23查询任意两个城市之间路径的算法...............................................................11四、调试分析以及设计体会..................................................................................................124.1测试数据：.................................................................................................................124.2程序调试中遇到的问题以及解决问题的方法。.....................................................134.3课程设计过程经验教训、心得体会。.....................................................................14五、使用说明..........................................................................................................................15六、附录..................................................................................................................................166.1源程序清单（带注释）.............................................................................................161一、需求分析1.1.程序的功能（1）．用户自己可以建立不同的路径之间的关系网（2）．可以查询某个城市到达其余各城市的最短路径。（3）．可以任一查询两个城市之间的最短路径。1.2输入输出的要求。在刚进入主界面后系统提示输入建立交通网络储存结构，输入顶点个数和和边数为整数不能输入其他字符，随后系统提示输入边与边之间的关系分别为i，j，w表示边之间的距离。然后进入查询页面，输入整数1，2，0分别表示你所要查询的功能：一个城市至其他所有城市的最短路径查询、任意两个城市之间的最短路径查询、退出程序。不能输入其他字符否则不能执行操作。在整个操作都是用整数表示城市。二、概要设计2.1系统功能模块划分用邻接矩阵建立交通网络模块图1：建立邻接矩阵注解：用户构建交通网络时，输入顶点个数n，边数e。然后在分别输入每个顶点i和j之间的距离w。程序将自动根本用户所输入的构建邻接矩阵。开始输入n,e输入i,j,wke,k+++结束YN2查询任意两个顶点之间的最短路径图3:弗洛伊德算法注解：用户输入他所需要查询的城市的起点v和终点w，程序利用弗洛伊德算法依次输出起点v到终点w所经过的顶点。开始输入起点v，终点w调用弗洛伊德算法k=p[v][w]保存最短路径长度k是否为0输出经过的顶点结束NY3查询一个城市到其他所有城市的最短路径图4:狄克斯特拉算法注解：用户输入他所需要查询的城市的起点v，程序将会调用狄克斯特拉算法，用S保存经过的顶点，最终会输出用户所需要查询的顶点v到其他所有顶点的最短路径。开始输入顶点v，路径初始化将原定编号放入S中判断输出路径结束修改顶点放入S中4整个函数流程模块图5：主程序2.1各模块数据类型2.21用邻接矩阵构造图结构函数CreateMGraph()其中vexs[MAX]保存顶点信息，arcs[MAX][MAX]用于保存边与边之间的信息。在构建时通过输入的边数i，j作为矩阵的行、列确定顶点的出度和入度。用邻接矩阵方法存储图，很容易确定图的任意两个顶点是否是有边相连，因此用邻接矩阵对有利于后面费洛伊德算法和狄克斯特拉算法。数据类型定义：typedefstruct{VertexTypevexs[MAX];Adjmatrixarcs[MAX][MAX];}MGraph;交通咨询系统构建交通网络1查询一个城市到所有城市的最短路径