数据结构课程设计报告3440130.docx
《数据结构课程设计报告3440130.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告3440130.docx（36页珍藏版）》请在冰点文库上搜索。
数据结构课程设计报告3440130
（此文档为word格式，下载后您可任意编辑修改！
）
第15小组课程设计报告
题目：
全国铁路运输网最佳经由问题
组员：
幸慧（）、彭西（）、韩向檀（）、夏权（）、杨洁（）、张磊（）
班级：
指导教师：
高永平
2015年01月08日
目录
一、需求分析
1.问题描述
2.基本要求
二、总体设计
1.程序流程图
2.数据结构设计
三、详细设计
1.程序设计思想
2.软件模块结构图
3.源程序
四、调试分析
1.测试数据
2.时间复杂度分析
3.上机遇到的问题及解决方案
4.算法的改进设想
五、用户使用手册
六、心得体会
一、需求分析
1.问题描述
该题目采用我国铁路运输网的数据进行编程和运行验证。
详细可在网上搜索《全国铁路局管辖线路示意图》，只要全国的主干线就可以了。
铁路运输网络中由铁路线和火车站的两个主要概念，譬如：
1号铁路线表示京广线，2号铁路线表示京沪线等。
铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志（00B客货运禁行,01B货运通行专线，10B客运通行专线，11B客货运通行）。
火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离该铁路线起点站路程及终点站路程。
2.基本要求
（1）查询某站所属的铁路线
（2）要求具备新增铁路线的管理功能
（3）要求具备新增车站的管理功能
（4）针对客运，货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。
并且要求能够显示出该最短路径的各个火车站的经由顺序
二、总体设计
1.程序流程图
2.数据结构设计
存储结构：
本程序部分函数采用的是文件进行数据的存储，所以采用的是顺序存储结构，如要添加数据，直接在文件里面进行操作就行了。
弗洛伊德算法中采用的存储结构是图的邻接矩阵。
A.如下为抽象数据类型定义的模板以及抽象数据类型线性表的定义：
ADTList{
数据对象：
D={ai|ai∈ElemSet,i=1,2,3„„,n,n≥0}
数据关系：
R1={|ai-1,ai∈D,i=1,2,3,„„,n}
基本操作：
voidreadways（）
初始条件:
views.txt已经存在。
操作结果:
将views.txt里面的数据一次存入数组views[SIZE_view]里，并将数组里面的存储数据的个数赋值给全局变量view_count；
voidreadways（）
初始条件:
ways.txt已经存在。
操作结果:
将ways.txt里面的数据一次存入数组ways[SIZE_way]里，并将数组里面的存储数据的个数赋值给全局变量way_count；
voidreadlines（）
初始条件：
lines.txt已经存在。
操作结果:
将lines.txt里面的数据一次存入数组lines[SIZE_line]里，并将数组里面的存储数据的个数赋值给全局变量line_count；
voidsearch（）;
初始条件：
views[SIZE_view]存在，且里面放有相关信息。
操作结果：
根据用户输入的车站名查找该车站的相关信息并输出；
voidaddview（）
初始条件:
views.txt已经存在。
操作结果:
将views.txt里面的数据一次存入数组views[SIZE_view]里，并将数组里面的存储数据的个数赋值给全局变量view_count；
voidaddway（）
初始条件:
ways.txt已经存在。
操作结果:
将ways.txt里面的数据一次存入数组ways[SIZE_way]里，并将数组里面的存储数据的个数赋值给全局变量way_count；
voidaddline（）
初始条件：
lines.txt已经存在。
操作结果:
将lines.txt里面的数据一次存入数组lines[SIZE_line]里，并将数组里面的存储数据的个数赋值给全局变量line_count；
voidfloyed（）
初始条件:
views[SIZE_view]、ways[SIZE_way]、lines[SIZE_line]已经存在并且存有相关信息。
操作结果：
把每个车站到各个车站的最短经由路径及此路径的距离存储在path_info、path_list[SIZE_view][SIZE_view]数组里；
voidshortest_path（）
初始条件：
path_info、path_list[SIZE_view][SIZE_view]存储相关的数据；操作结果：
输出输入的两个站的最短距离及经过的所有站；
voidaddadta（intmenu）
初始条件：
views.txt、ways.txt、lines.txt已经存在。
操作结果：
如果menu=1，则添加车站数据，如果menu=2，则添加路线数据；
B.弗洛伊德算法中，数据结构所用到的思想为图的思想，所以数据结构的设计主要的目的为便于图的操作的设计。
因此我们用了下面这些数据定义。
structview_info*城市信息结构*
{
intid;charname[20];intcode;charshortname[20];charLName[100];经过此站的铁路线名称
}views[SIZE_view];
structline_info铁路线信息结构
{
intLid;charLName[20];intstart_id;始发站intend_id;终点站intdist;铁路线长charsign[5];通行标志
}lines[SIZE_line];
structway_info铁路度的信息结构
{
intstation1;intstation2;intdist;
}ways[SIZE_way];
structpath_info用于最短路径的查询
{
};
三、详细设计
1.程序设计思想
设计思路:
核心问题：
求最短路径（弗洛伊德算法）
数据模型（逻辑结构）：
带权有向图
输入输出：
初始数据是从views.txt、lines.txt、way.txt三个文件中读入，在读入数据后，用户可以根据选项选择相应的功能，不同的功能有不同的数据输入输出，比如：
查询的功能是要求输入要查询的站的名称，然后输出是该站的相关信息；查询最intcount;intpath[SIZE_view];
短路径的功能则是输入起点站、终点站的名称，输出则是该段路线距离和经由站等。
程序的输入：
（1）铁路线信息的输入：
依次输入“铁路线代码,铁路线名称，起始站代码,终点站代码，该铁路线长度、通行标志”，并且中间以空格隔开。
（2）火车站信息的输入：
依次输入“车站代码，车站名，车站编号、车站简称，所属铁路线编号”，并且中间以空格隔开。
程序的输出格式：
（1）当显示铁路线或者火车站的信息时，与输入时的格式完全一致；
（2）输出最短路径的长度，以及最短路径的经由顺序；
按照程序功能要求，设计了一下各个功能模块：
（1）、文件读取模块
文件读取模块包括读取车站信息模块readviews、路段权值信息读取模块readlines、铁路线信息读取模块readlines。
这些模块的主要功能为从文件中读取所需的信息。
（2）、添加信息模块adddata
添加信息模块又包括以下子功能模块：
A、添加站点信息模块addview。
B、添加路段权值模块addway。
C、添加铁路线信息模块addline。
（3）查询模块
根据用户需求，查询站点信息
（4）最短路径查询模块
该模块为本软件设计的核心部分。
根据该模块可以很方便的找出两个城市的最短路径。
该最短路径的算法为常用的弗洛伊德算法。
（5）操作菜单模块
该模块主要用于与用户的交互，一个界面友好的菜单可以提高软件的人机交互体验。
2.软件模块结构图
（1）主程序模块，其中主函数为：
voidmain（）{新增火车站；新增铁路线；查询火车站的信息；针对客运、货运情况，求两站之间的最短路径及其经由顺寻；退出界面}
（2）文件模块为:
voidreadways（）；voidreadviews（）；voidreadlines（）（3）图模块为：
Voidshort_path（）；voidfloyed（）（4）查询函数和添加函数
voidsearch（）；voidadddata（inmenu）；voidaddway（）；voidaddline（）；voidaddview（）函数的调用：
进入主函数，调用文件模块各函数以读取数据；选择1或2，则调用voidadddata（inmenu）,其中若选择1，则调用voidaddview（）函数，若选择2，则调用voidaddline（）和voidaddway（）函数；选择3，调用voidsearch（）函数进行查询；选择4，调用voidshort_path（）和voidfloyed（）函数以得到最短路径。
3.源程序（见附录）四、调试分析
1.测试数据
数据读取如下：
功能测试截图：
输入1，增加车站信息如下：
输入2，增加铁路线信息如下：
输入3，查询车站信息如下：
输入4，查询最短路径如下：
输入5，退出界面如下;
2.时间复杂度分析
程序中图的存储结构为带权邻接矩阵，其中对邻接矩阵的初始化的时间复杂度为O（n*n）;在求最短路径的时候，用的是弗洛伊德算法，时间复杂度主要在于求每一站到任意站的最短路径由是的for循环，那有三个for循环，所以时间复杂度为O（n3）。
3.上机过程中出现的问题及其解决方案
（1）刚刚看到题目要求的时候就想到了弗洛伊德算法，但是不知道如何去做，在网站搜索到类似代码，经过修改后，最终得出了源程序。
（2）源程序可以运行的时候，忘记添加相关文本文件，所以运行文件的时候会提示文件打开失败，无法进行接下来的功能使用，这时候才想起来要自行添加相关的文本文档，接着问题就解决了。
（3）在way.text文本文档中添加各站权值的时候，一开始不知道如何添加，经过思考和查询课本后，明白了添加权值时是以各站编码代表各站，由于是有向图，所以需要添加两站往返权值。
（4）在输入信息时，由于是输入汉字，系统不稳定，容易出现刷屏，这个问题，
我是向学长寻求帮助并得以解决的。
4.算法的改进设想
1.程序界面不够美观，需要改进，作为人机交互的界面，应尽量美观舒适，提高人机交互体验。
2.铁路交通网的管理还有很多方面，例如删除某些铁路线或火车站
五、用户使用手册
首先运行可执行文件，执行文件为：
test.exe。
根据需要选择相应的数字代码：
【1】选择1，增加车站信息。
首先输入新车站的id，输入为数字（必须大于所
给提示信息），其次输入新车站名称，输入为文字，接着输入新车站的编号，输入为数字（必须大于所给信息），然后输入新车站的简称，输入为英文字母（一般为新车站拼音首字母），接着输入新车站经过的路线，输入为文字。
最后选择是否继续，输入为n（不）或y（是）。
【2】选择2，增加铁路线信息。
首先输入新铁路线信息的Lid，输入为数字（必
须大于所给提示信息），其次输入新铁路线名称，输入为文字，接着分别输入新铁路线的起始站id和终点站id，输入为数字，然后输入距离，输入为数字，通行标志：
00B客货运禁行,01B货运通行专线，10B客运通行专线，11B客货运通行，接着输入权值信息,前一站和后一站的编码，输入为数字，两站的距离，输入为数字。
最后选择是否继续，输入为n（不）或y（是）。
【3】选择3，查询车站信息。
输入需要查询的车站名称，输入为文字。
最后选
择是否继续，输入为n（不）或y（是）。
【4】选择4，查询最短路径。
分别输入需要查询最短路径的起始站和终点站的
名称。
最后选择是否继续，输入为n（不）或y（是）。
【5】选择5，退出程序。
六、心得体会
本次课程设计我们做的是全国铁路网最经经由问题，功能都实现了，运行顺畅。
对于这次的数据结构设计我觉得我们还是挺成功的。
以下是我在这次数据结构中的体会。
我觉得相比大一做的C语言程序设计而言，这次的程序难了很多，但同时教会了我更多的知识，最重要的就是让我明白了数据结构这门课程的使用价值。
以前，在课堂上老师一遍遍的讲到数据结构和编程语言的关系，自从完成了课程设计以后我突然恍然大悟，明白了数据结构和C语言等编程语言的关系。
简单的说，它就是一个程序所采用的逻辑结构（有集合，线性表，树和图等）和存储结构（顺序和链表）。
只有确定了这些，再加上算法才能写出一个程序。
在写本次程序时，遇到了不少的问题。
主要还是对编程语言的不熟悉，虽然
总体思路可以明确，但是真的写起来却漏洞百出。
因此，我们上网搜索相关资料，找到了类似的源程序，参考源程序之后，我们进行了一系列的改错和完善。
遇到不明白的部分，马上询问学长或者优秀的同学，让他们为我们指点迷津。
最终把他们都解决了。
虽然这次花的时间比较多，但是收获也是很大啊。
最重要的收获就是：
当遇到问题时，要很高兴的面对它。
相信自己一定能解决这个问题。
接下来，要沉住气，不断地尝试，不断地调试，最终会把问题给解决的。
我认为编程遇到问题是一件很高兴的事情。
只有遇到问题，才能有问题解决。
解决问题也是一件很开心的事情。
通过本次课程设计，增强了我的调试程序的能力，以及分析程序，分析算法的能力。
巩固了我数据结构的知识，对与去年学习的一门学科的温习，让我更了解了弗洛伊德算法，熟练掌握了函数的定义，函数的调用等编程能力。
我相信只有自己的能力不断地提高，才能编写出高质量的程序来。
课程设计期间，不得不提的是合作。
因为合作我们才能又快又好的完成任
务。
当今社会，需要一个会思考会设计的人，但是更需要的是一个懂合作，会合作的搭档。
只有两个人默契配合，合理分工才能顺利的完成任务。
我很开心能和我的搭档一组，我们分工合作，在整个课程设计中遇到问题一起商量，一起解决，让我感受到了合作的快乐。
最后我想说，数据结构是一门很复杂的学科，难懂。
但是只要你利用学习
到的理论知识去实践，结合实践去分析和理解它，最终你会发现它也不过如此。
在实践的过程中互相帮助很重要，它能让你在困境中体会到快乐，在苦涩的学
习中体会友情带来的快乐！
附录：
#include
#include
#include
#include
#include
#include
#defineSIZE_view50
#defineSIZE_line100
#defineSIZE_way300
#defineMAXNODE30
定义最多节点数
#defineMAXCOST10000
usingnamespacestd;
structview_info
*城市信息结构*{
intid;
intcode;
charname[20];
charshortname[20];
charLName[100];
经过此站的铁路线名称
}views[SIZE_view];
structline_info
铁路线信息结构
{
intLid;
charLName[20];
intstart_id;
始发站
intend_id;
终点站
intdist;
铁路线长
charsign[5];
通行标志
}lines[SIZE_line];
structway_info
铁路度的信息结构
{
intstation1;
intstation2;
intdist;
}ways[SIZE_way];
structpath_info
用于最短路径的查询
{
intcount;
intpath[SIZE_view];
};
intview_count,line_count,way_count;
用来存储文件中有多少条记录
intdist_list[SIZE_view][SIZE_view];
定义一个数组
structpath_infopath_list[SIZE_view][SIZE_view];
定义一个path_info结构体变量..
voidreadviews（）;彭西
voidreadways（）;彭西
voidreadlines（）;幸慧
voidsearch（）;幸慧
voidaddview（）;韩向檀
voidaddway（）;韩向檀
voidaddline（）;杨洁
voidshortest_path（）;杨洁
voidfloyed（）;夏权
voidadddata（intmenu）;夏权
voidmain（）张磊外加敲代码
{
readviews（）;
cout<readlines（）;
cout<readways（）;
while
（1）
{
intmenu;
cout<cout<<"全国铁路运输网经由系统"<cout<<"**************************************"<cout<<"2、增加铁路线信息"<cout<<"3、查询车站信息"<cout<<"4、查询最短路径"<cout<<"5、退出界面"<cout<<"**************************************"<"<cin>>menu;
while（menu<1||menu>5）
{
cout<<"error!
pleaseenteragain:
";cout<<"错误!
请再次输入:
";
cin>>menu;
}
switch（menu）
{
case1:
case2:
adddata（menu）;
break;
case3:
while
（1）
{
search（）;
cout<<"doyouwanttocontinue?
（yn）"<（yn）"<charcon;
cin>>con;
if（con=='y'）;
else
break;
}
break;
case4:
while
（1）
{
shortest_path（）;
cout<<"doyouwanttocontinue?
（yn）"<cout<（yn）"<charcon;
cin>>con;
if（con=='y'）;
*addline（）;*
else
break;
}
break;
case5:
cout<<"谢谢使用..再会.."<getchar（）;
getchar（）;
exit
（1）;
break;
}
}
}
彭西
voidreadviews（）
{
inti;
ifstreaminfile（"views.txt",ios:
:
in）;
打开文件
把文件中的个数付给view_count
*infile>>view_count;*
if（!
infile）
打开文件失败
{
cerr<<"can'topenviews.txt!
"<cerr<<"不能打开views.txt!
"<exit
（1）;
}
infile>>view_count;
先读入文件个数
for（i=0;;i++）
{
infile>>views[i].id>>views[i].name>>views[i].code>>views[i].shortname>>views[i].LName;
if（i!
=0&&views[i].id==0）break;
}
view_count=i;
view_count=i;
给出源文件中车站的个数
infile.close（）;
下面是测试用的代码
cout<:
left）;
cout<<"城市信息结构"<cout<cout<for（i=0;i{
cout<cout<}
cout<:
left）;
}
彭西
voidreadways（）
读文件ways.txt
{
inti;
ifstreaminfile（"ways.txt",ios:
:
in）;
打开文件
*infile>>way_count;*
把文件中的记录付给way_count
if（!
infile）
打开文件失败
{
cerr<<"can'topenways.txt!
"<cerr<<"不能打开ways.txt!
"<exit
（1）;
}
for（i=0;;i++）
{
infile>>ways[i].station1>>ways[i].station2>>ways[i].dist;
if（i!
=0&&ways[i].station1==0）break;
}
way_count=i;
infile.close（）;
测试用..输入路段的信息
cout<:
left）;
cout<for（i=0;i{
cout<cout<}
cout<:
left）;
}
幸慧
voidreadlines（）
读文件lines.txt
{
inti;
ifstreaminfile（"lines
升级会员 