数据结构课程设计说明书最短路径.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结构定义

图4邻接矩阵
图3无向带权图

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语句查找，查询所在地到其他各站点的所有最短路径，根据迪杰斯特拉算法计算，然后输出最短路长和需用的时间，并输出相应的路线过程。
2.2.4函数流程图
（1）查询所有地点最短路径

图4查询所有地点最短路径

（2）修改功能

2.2.5代码（见附录）
2.3程序测试结果
（1） 主菜单结果

图6主界面

（2）录入函数结果

图7录入函数

（3）添加函数结果

图8添加函数

（4)修改函数结果

图9修改函数

（5）删除函数结果

图10删除函数

（6）查询两地最短路程结果
图11查询两地最短路程函数

（7）查询所有站点最短路程结果

图12查询所有站点最短路程

3、课程设计总结
通过此次课程设计，我也学到了很多，比如团队的力量永远大于个人的力量，细节决定成败等等。通过这次系统的编写，我明白了编程要细心，有耐心。有些程序看起来很多很难，但只要抽丝剥茧的慢慢分析，就能明白它是怎么运行的。其实，只要踏踏实实一步一步来，你会发觉原来编程难度也不过如此。
通过这一次的编写程序不但重新温习了以前学到的知识，还学习到许多的新的知识，也认识到了自己的许多的不足。例如耐心不够，在调试程序时，发现了一个错误，但是总是解决不了，心里就会感到厌烦，不想继续做下去。还有不够细心，每一次改写完程序后，检查了一遍，自己认为没有错了，结果调试发现又有错误等等。不过也发现了自己的一些优点，比如善于听取他人意见，虚心求教等。
通过这次次实验我们收获了很多，对数据结构这门课有更深的了解.让我们对链表、队列和图的应用更娴熟，加强了对图的最短路径的认识与应用，巩固了迪杰斯特拉算法为我们更好的了解课本内容，改进不足提供了件。
通过这次课程设计，我对用算法计算最短路径有了更深刻的认识，加强了我对数据结构的了解。我知道如果要想在C++语言有成就，必须多想多练习。现在我还是缺少练习，看程序可能看得懂。而当真正的编写程序起来就遇到困难了。同时，我懂得了要多思考，遇到问题或不解时不能不懂装懂，要尽量去想其缘由，要懂得查阅有用的资料。
最后，通过全组人的齐心协力，最终将程序编写了出来，并且使之得到实现我们的预期目的。通过此次课程设计，从一定成度上提高了我们对数据结构的熟悉度，也提高了我们独立编程的能力，同时也体会到在程序设计过程中团体合作，共同解决问题的重要性。
我知道在这次的课程设计中，还有许多的欠缺，在以后的日子中，我一定得更加严格要求自己，改正缺点，不断努力，不断进步。
4、参考文献
[1] 严蔚敏等.数据结构[M](C语言版).清华大学出版社,1997.4.
[2] 张乃孝主编.算法与数据结构[M](C语言版).高等教育出版社, 2002.
[3] 李廉治，姜文清，郭福顺.数据结构[M].大连理工大学出版社，1989.
[4] 徐孝凯，魏荣.数据结构[M].机械工程出版社,2007.
[5] 谭浩强.C++程序设计[M].清华大学出版社,2011.
[6] 杨路明.C++语言程序设计教程[M].京邮电大学出版社，2003.
答辩记录
答辩小组教师：
提问与答辩情况记录如下：
1、 为什么选择邻接矩阵存储结构？、
答：邻接矩阵存储结构容易实现图的操作，如：求某顶点的度，判断顶点间是否有弧，找顶点的邻接点。又因为站点作为图的顶点，线路作为图的边，边上的权值作为站点间的距离。此结构便于完成任务的各种操作。
2、程序的亮点在哪？
答：查询最短路径部分分为两部分，一是分两地查询，这部分功能是输入起点，在输入终点然后查询最短路径，输出其最短路程和相应的路径；二是该地到其他地方的最短路径，这部分的功能是输入用户的所在地，让后查询该所在地到其他各地的最短路程，并输出其所有的最短路程和相应的路径。
3、怎样对这个题目进行分析设计的？
答: 首先给定了图的邻接矩阵储存结构，然后在根据题目要求进行最短路路径相关的编写，此系统要完成对火车站点信息的储存、修改、删除、添加和查询最短路线，因为涉及到最短路线问题，所以数据结构优先考虑采用图的邻接矩阵储存结构，站点和行车线路可以构成图状结构。