数据结构课程设计说明书最短路径.doc

计算机科学与技术教研室 课程设计说明书 （2014-2015学年 第1学期） 课程名称 算法与数据结构课程设计 设计题目 火车路径查询系统 学号 姓名 小组成员 起止时间： 2015年 1 月 7 日 至 2015 年 1 月 19 日 课程设计 评 语 在为期两周的课程设计中，该生课堂表现良好，参与了课程设计的整个过程，实现了火车路线查询的以下功能：录入，添加，修改，删除，查询最短路线和显示等功能。课程设计说明书填写正确，条理清楚，对于课程设计过程介绍详细，代码正确。作品演示熟练，能按照设计要求完成指定的功能。答辩过程中，回答问题正确，熟练，对自己的程序描述清楚，条理性强。 平时成绩 报告成绩 演示与答辩成绩 成绩总评 指导教师 （签字） 年 月 日 注：成绩均用百分制。总成绩=平时成绩*20%+报告成绩*40%+演示与答辩成绩*40%设计题目：火车路径查询系统 1、课程设计目的 （1）熟练掌握图的存储结构及其建立过程和常用操作。 （2）巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终能够熟练应用数据结构的知识写程序。 （3）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力，初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。 （4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力，培养我们的创新思维能力。 2、课程设计正文 2.1概要设计 2.1.1 系统分析 该系统主要功能包括：录入信息、添加信息、修改信息、删除信息、按最短路径查询信息等。 分析： 1.此系统要完成对火车站点信息的储存、修改、删除、添加和查询最短路线，因为涉及到最短路线问题，所以数据结构优先考虑采用图的邻接矩阵储存结构，站点和行车线路可以构成图状结构，站点作为图的顶点，行车路线作为图的边，边上的权值作为站点间的距离。此结构便于完成任务的各种操作。 2.录入信息：录入站点的名称，输入站点i到站点j的路长。 3.添加信息：添加站点的名称，输入站点i到站点j的路长。 4.修改信息：输入站点的名称，查询，如果有该站点，则输入新的站点名，新的从该站点到其他站点的路长。 5.删除信息：输入要删除站点前的序号，要删除路线的站点序号(vi,vj)，然后查找并删除。 6.最短路径查询：(1)输入起点，终点，输出最短路长和需用的时间，并输出相应的路线过程。(2)输入用户所在地，查询所在地到其他各站点的所有最短路径，输出最短路长和需用的时间，并输出相应的路线过程。 2.1.2系统结构图 2.2详细设计 2.2.1数据类型定义 const int MAXVertices = 20; const int MAXweight = 500; struct Vertex {string city;}; class Graph {public: Graph(); void input(); void add(); void change(); void del(); void show(); void select_path1(); void select_path2(); private: int Edge[MAXVertices][MAXVertices]; int numE,numV; Vertex Vertices[MAXVertices];}; 2.2.2 存储结构 2.2.3 函数声明 （1)录入函数 函数名：void Graph::input() 操作结果:录入站点信息。 分析:输入站点名,两站点距离,为图的顶点和边权值赋值。 （2）添加函数 函数名：void Graph::add() 操作结果：添加站点信息。 （3）修改函数 函数名：void Graph::change() 操作结果：修改其站点信息和两站点之间的距离值。 （4）删除函数 函数名：void Graph::del() 操作结果：删除站点信息和这个站点与其他站点的距离。 分析：输入要删除站点序号和路线条数，用for语句查找并删除。 （5）显示函数 函数名：void Graph::show() 操作结果：显示出所有的站点信息。 （6）查找两地最短距离函数 函数名：void Graph::select_path1() 操作结果：查找最短距离并输出。 分析：输入起点，终点，利用for语句查找，根据迪杰斯特拉算法计算，然后输出最短路长和需用的时间，并输出相应的路线过程。 （7）查找所有地点最短距离 函数名：void Graph::select_path2() 操作结果：查找最短距离并输出。 分析：输入用户所在地，利用for语句查找，查询所在地到其他各站