数据结构课程设计说明书最短路径.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语句查找，查询所在地到其他各站
显示全部