数据结构课程设计交通咨询系统

1、课 程 设 计 报 告 课程名称课程名称 数据结构课程设计数据结构课程设计 课题名称课题名称 交通咨询系统交通咨询系统 专专 业业 通信工程通信工程 班班 级级 通信通信 1001 班班 学学 号号 姓姓 名名 指导教师指导教师 田娟秀田娟秀 胡瑛胡瑛 曹燚曹燚 2012 年年 7 月月 6 日日 2 湖南工程学院 课 程 设 计 任 务 书 课程名称 数据结构 课 题 交通咨询系统 专业班级 通信 1001 班 学生姓名 学 号 指导老师 田娟秀 胡瑛 曹燚 审 批 田娟秀 任务书下达日期 2012 年 7 月 1 日 任务完成日期 2012 年 7 月 6 日 3 1.11.1 任务书任务

2、书 课题六：交通咨询系统： 在交通网络非常发达的今天，人们出差、旅游或做其他出行时，不仅关心节省交通 费用，而且对里程和所需时间等问题也很感兴趣。对于这样一个人们关心的问题，可 用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表 示城市，边表示城市之间的交通关系。设计一个交通咨询系统，能让旅客咨询从任一 个城市顶点到达另外一个城市顶点之间的最短路径（里程）的问题。 要求完成以下功能： (a) 以图中顶点表示湖南省各市(至少包括 8 个以上的城市)，存放城市名称、代 号、简介等信息，以边表示路径，存放路径长度等有关信息，先建立交通网络图的存 储结构； (b) 为用户提供图

3、中任何城市有关信息的查询； (c) 为用户提供任意城市的交通查询,即查询任意两个城市之间的一条最短路径。 (d) 为用户提供指定城市的交通查询，即查询指定城市到其他城市之间的最短路 径。 选做内容： （1）提供图的编辑功能：增、删城市；增删路径；修改已有信息等； （2）交通图的仿真界面。 1.21.2 选题方案：选题方案： 所选题目根据学号确定，学号模 6 加 1，即（学号%6+1） 。如你的学号为 9，则 所选题目号为：9%6+1（题目 4） 。注意，所有的课题都要求用图形方式演示步骤 和结果。同学们可以自己针对数据结构课程中所讲算法来设计一个演示过程的算法。 1.31.3 设计要求：设计要

4、求： 1.3.11.3.1 课程设计报告规范课程设计报告规范 （1）需求分析 a.程序的功能。 b.输入输出的要求。 （2）概要设计 4 a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个 模块的功能。 b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么 样的结构，它们之间有什么关系等。 （3）详细设计 a.采用 c 语言定义相关的数据类型。 b写出各模块的类 c 码算法。 c.画出各函数的调用关系图、主要函数的流程图。 （4）调试分析以及设计体会 a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果 和含有错误的输入及输出结果。 b.程序调

5、试中遇到的问题以及解决问题的方法。 c.课程设计过程经验教训、心得体会。 （5）使用说明 用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。 （6）书写格式 a.设计报告要求用 a4 纸打印成册： b.一级标题用 3 号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为 22。 （7）附录 源程序清单（带注释） 1.3.21.3.2 考核方式考核方式 指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创 新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级 给出每位同学的课程设计成绩。具体考核标准包含以下几个部分： （1）平时出勤 （

6、占 10%） （2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占 10%） （3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占 40%） （4）设计报告（占 30%） 注意：不得抄袭他人的报告（或给他人抄袭） ，一旦发现，成绩为零分。 5 （5）独立完成情况（占 10%） 。 1.3.31.3.3 课程验收要求课程验收要求 （1）运行所设计的系统。 （2）回答有关问题。 （3）提交课程设计报告。 （4）提交软盘（源程序、设计报告文档） 。 （5）依内容的创新程度，完善程序情况及对程序讲解情况打分。 2 2 进度安排进度安排 第 20 周：星期一 8：0012：0

7、0 上课 星期一 14：3018：30 上机 星期二 14：3018：30 上机 星期三 8：0012：00 上机 附： 课程设计报告装订顺序：封面、任务书、目录、正文、评分表、附件（a4 大小的图纸及程序清单） 。 正文的格式:一级标题用 3 号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为 22。 正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图） ；三、主要功能 的实现（至少要有一个主要模块的流程图） ；四、程序调试；五、总结；六、附件（所有程序的原 代码，要求对程序写出必要的注释） 。 正文总字数要求在 5000 字以上（不含程序原代码） 。 6 目 录

8、 一一 需求分析需求分析.7 1.1 程序的功能.7 1.2 输入输出的要求.7 二概要设计二概要设计.8 2.1 程序的模块组成.8 2.2 每个模块的功能.8 2.3 存储数据及其关系.10 三详细设计三详细设计.10 3.1 采用 c 语言定义相关类型.10 3.2 写出各模块的类 c 码算法.11 3.3 调用关系图.14 四调试分析以及心得体会四调试分析以及心得体会.15 4.1 测试数据.15 4.2 心得体会 .17 五五 使用说明使用说明.18 六六 附录附录.19 七评分表七评分表.24 7 一 需求分析 1.11.1 程序的功能程序的功能 在交通网络非常发达的今天，人们出差

9、、旅游或做其他出行时，不仅关心节省交通 费用，而且对里程和所需时间等问题也很感兴趣。对于这样一个人们关心的问题，可 用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表 示城市，边表示城市之间的交通关系。设计一个交通咨询系统，能让旅客咨询从任一 个城市顶点到达另外一个城市顶点之间的最短路径（里程）的问题。 要求完成以下功能 (a) 以图中顶点表示湖南省各市(至少包括 8 个以上的城市)，存放城市名称、代 号、简介等信息，以边表示路径，存放路径长度等有关信息，先建立交通网络图的存 储结构； (b) 为用户提供图中任何城市有关信息的查询； (c) 为用户提供任意城市的交通查询

10、,即查询任意两个城市之间的一条最短路径。 (d) 为用户提供指定城市的交通查询，即查询指定城市到其他城市之间的最短路 径。 选做内容： （1）提供图的编辑功能：增、删城市；增删路径；修改已有信息等； （2）交通图的仿真界面。 1.21.2 输入输出的要求输入输出的要求 在用户刚进入主界面后，系统就会提示输入建立交通网络的储存结构，输入顶点 个数和和边数，随后会有系统进行提示输入顶点信息以及他们的权值，即 i,j 和 w，依 次根据边的信息个数进行输入。随之进行的是查询页面，输入选择按钮进行功能查询 选择。如，选择 1：表示的是查询任意两个城市之间的一条最短路径，选择 2：表示的 是查询指定城市

11、到其他城市之间的最短路径，选择 0：表示你将要退出程序查询系统。 二概要设计 2.12.1 程序的模块组成程序的模块组成 本程序主要有三个模块组成，他们分别是：邻接矩阵建立有向图，查询任意 8 两个城市之间的一条最短路径，查询指定城市到其他城市之间的最短路径。 三个模块的概图： 任意两个城市的 最短距离查询 两个指定城市的 最短距离查询 图 2.1 2.22.2 每个模块的功能每个模块的功能 邻接矩阵建立交通网络 y 用户进入系统 交通网络构建 结果，退出系统 开始 输入 n,e 输入 i,j,w k=e,k+ + 结束 n 9 图 2.2.1 查询指定城市到其他城市之间的最短路径 图 2.2

12、.2 查询任意两个城市之间的一条最短路径： 开始 输入顶点 v 狄克斯特拉算法 输出路径,距离 结束 开始 输入起点 v， 终点 w 输出路径,距离 结束 10 图 2.2.3 2.32.3 存储数据及其关系存储数据及其关系 比如下列五个数据之间的存储及其关系 12 4 53 图 2.3 上图说明：上图各个节点之间会有一条或者两条边，当输入他们的信息时根据 他们的方向进行有向图的存储。并且每两个顶点之间（单向）都会有一个值 w，即 权值。如顶点 1 和 2 之间可以设置他的权值是 2，顶点 2 到顶点 5 的权值可以是 3，顶点 5 到顶点 2 的权值可以是 4，等等。 三详细设计 3.13.

13、1 采用采用 c c 语言定义相关类型语言定义相关类型 1定义一个，用来存储顶点信息。 typedef struct vertextype vexsmax; adjmatrix arcsmaxmax; mgraph; . 2定义一个 dijkstra 函数 void dijkstra(mgraph *g,int v,int n); 2定义一个 floyd 函数 调用弗洛伊德 算法 11 void floyd(mgraph *g,int n); 3.23.2 写出各模块的类写出各模块的类 c c 码算法码算法 邻接矩阵构造图结构函数 数据类型定义： typedef struct vertexty

14、pe vexsmax; adjmatrix arcsmaxmax; mgraph; void createmgraph(mgraph *g,int n,int e)/邻接矩阵构成有向图 int i,j,k,w; for(i=1;ivexsi=(char)i; for(i=1;i=n;i+) for(j=1;jarcsij=idf; printf(输入%d 条边的 i,j 及 w: n,e); for(k=1;karcsij=w; printf(有向图的存储结构建立完毕!n); 其中 vexsmax保存顶点信息，arcsmaxmax用于保存边与边之间的信 息。在构建时通过输入的边数 i，j 作为

15、矩阵的行、列确定顶点的出度和入度。 用邻接矩阵方法存储图。 12 dijkstra 算法； 基本思想：设 g（v,e）是一个带权有向图，把图中的顶点集合 v 分成两组， 第一组为已经求出的最短路径的顶点集合（用 s 表示，初始时 s 中只有一个原 点，以后每求得一条最短路径就加入的集合 s 中，知道全部顶点都加入到集合 中） ，第二组，为其余未确定最短路径的顶点集合（用 u 表示） ，按最短路径长 度的递增次序依次把第二组的顶点就如 s 中。如果两个顶点之间有权值，并且 各个路径的权值不同，就把最小的作为顶点与顶点的最短距离。 y x z 图 3.3.1 如图所示 若 x+yk=u。同理若 x

16、+yu， d v1=0;sv1=1; /原点编号放入 s 中 for(i=2;in;i+) min=idf; for(w=1;w=n;w+) if(!swmin=d w; sv=1; /修改顶点 u 放入 s 中 for(w=1;warcsvwarcsvw; p w=v; 弗洛伊德算法： k vu 13 用邻接矩阵保存图存储后，另外需要存一个二维数组 a 存放当前顶点之间的最 短路径长度。分量 aij表示当前顶点 i 到 j 的最短路径长度。弗洛伊德算法的基 本思维是递推产生一个矩阵序列 a0，a1，a2，.ak， an，其中 akij表示从顶 点到 vi 到顶点 vj 的路径上所经过的顶点编

17、号不大于 k 的最短路径长度。 aij=costij a(k+1)ij=minakij,aki+1k+1+akk+1j 弗洛伊德主要算法，若 akij已求出，顶点 i 到顶点 k+1 的路径长度为 akik+1， 顶点路径长度为 akij，顶点 k+1 到顶点 j 的路径长度为 akk+1j，如果此时 akik+1+akk+1j akij,则将原来的顶点 i 到顶点 j 的路径改为顶点，否则不 需要修改顶点 i 到 j 的路径。 aki,k+1 akk+1,j aki,j 图 3.3.2 若 akik+1+akk+1 j akij,修改路径 过程： for(k=1;k=n;k+) for(i=

18、1;i=n;i+) for(j=1;j=n;j+) if(dik+dkj1 长度=0，1=2 长度=3，1=3 长度=3+3=8，1=4 长度=3+6=9；和下图完 全一致 图 4.4.3 3为保证结果正确换一个顶点进行：如图 4.4.4，计算可知结果正确。 图 4.4.4 4查询一个顶点到另一个顶点的最短路径：如图 4.4.5，经计算：可知结 果正确。 图 4.4.5 5选择 0 进行 退出程序的操作。如下图 4.4.6 图 4.4.6 17 4.24.2 心得体会心得体会 “平时不好干，遇事只能看” ，经过这几天的数据结构的课程设计对这句话这 真的别有一番的体会。 “成功只属于有准备的人”

19、 ，真的，这几天的课程设计让你不得 不想起这句话。俗话说“厚积薄发” ，前期的积累，说不定什么时候就能够用上。这次 就是这样，前期没有积累足够的知识储备，以至于拿到课程设计的任务书时感觉无所 适从，不知道从何下手，真是老虎吃刺猬，无从下口。所以，在第一次上课时就 什么都没有做，就那样在实验室里干看着别人在热热火火的搞自己的课程设计。于是 乎自己只能看书，把自己以前丢失的都补回来。 因为自己的不学习，导致这次的课设变得如此的艰难。当别人都已经快答辩了， 我的程序还只有那可怜的几行，无独有偶，也就是这样，我一度准备放弃，心想就直 接从网上拷贝一个就行了。可是，许三多的一句话敲醒了我，不抛弃，不放弃

20、，对， 不能放弃。就这样。我坚持了下去，开始从各个方面入手，查书，查资料，一句一句 的敲，一点一点的写，不会的问老师，请教同学。终于功夫不负有心人。临到答辩结 束的我赶上了末班车。顺利的通过了答辩，抹掉分数的高低吧。还是有小小的成就感 的。 通过这次的课程设计我有懂得了好多数据结构的知识，以前上课没有听的，不知 道的，这次都有所了解了，像有向图的构建，弗洛伊德算法，迪克斯特拉算法。这些 知识从曾经的听说到现在的了解，进了一大步。不但如此，这次的课设也是我感觉到 了数据结构的强大与神奇。渐渐的爱上他了。不仅让我了解了数据结构更加深了对它 与 c 语言的联系的理解。 课设已经结束了。真心的感谢我们

21、的田老师，这么大热的天，当其他老师都在空 调房里舒服时，她还是冒着火烈的太阳，赶过来给我们指导。想让我们学到更多的知 识。在这里，深情的说一句：老师，您辛苦了，谢谢您。同样感谢另外两个老师的知 道。谢谢你们。 18 5使用说明 第一步：运行程序。进入主界面。进一步提示输入图中的顶点，边数。 第二步：输入边之后按回车，进入图的构建。依次输入各个边的的信息，i, j, w 根据自 己所设的图的不同进行设置。 第三步：进入程序查询区域。有选择 1 或 2 或 0 分别表示你所选择的查询不同方式。 （1）选择 1 表示查询一个顶点至其他所有顶点的最短路径。会提示用户进行查 询定点的选择。系统将会显示你

22、要查询的最短路径。 （2）选择 2 表示查询任意两个点之间的最短路径，输入用户所要查询的起点和 终点就会显示你要查询的最短路径。 19 （3）选择 0 表示用户将要退出系统。 6附录 #include #include #define max 100 #define idf 32767 /最大顶点数 typedef char vertextype; typedef int adjmatrix; typedef struct /设置数组保存顶点信息 vertextype vexsmax; adjmatrix arcsmaxmax; mgraph; int d1max,p1max; int dma

23、xmax,pmaxmax; void createmgraph(mgraph *g,int n,int e); /建立图的存储结构 void dijkstra(mgraph *g,int v1,int n); /狄克特求最短路径 void floyd(mgraph *g,int n); /弗洛伊德算法 void main() 20 mgraph *g; int m,n,e,v,w,k; int xz=1; g=(mgraph *)malloc(sizeof(mgraph); printf( *欢迎进入交通咨询系统*n); printf(交通网络图的存储结构n); printf(输入图中顶点,边

24、数 n，e: ); scanf(%d %d, createmgraph(g,n,e); while(xz!=0) printf( *下一步*n); printf( *查询城市之间的路径*n); printf( 1.查询一个城市到所有城市的最短路径n); printf( 2.查询任意的两个城市之间的最短路径n); printf(请选择: 1 or 2:n ); printf( 选择:0 退出: ); scanf(%d, if(xz=2) floyd(g,n); /调用费洛伊德算法 printf(输入起点,终点：v,w: ); scanf(%d %d, k=pvw;/k 保存最短路径长度 if(k

25、=0) printf(顶点%d 到 %d 无路径!n,v,w); else printf(从顶点%d 到%d 的最短路径是: %d,v,w,v); while(k!=w) printf(-%d,k);/输入后继结点继续找下一个顶点 k=pkw; 21 printf(-%d,w); /输出终点 printf(路径长度: %dn,dvw); else if(xz=1) printf(输入顶点 v: ); scanf(%d, dijkstra(g,v,n);/调用狄克斯特拉算法 printf(结束求最短路径,再见! n); void createmgraph(mgraph *g,int n,int e)/邻接矩阵构成有向图 int i,j,k,w; for(i=1;ivexsi=(char)i; for(i=1;i=n;i+) for(j=1;jarcsij=idf; printf(输入%d 条边的 i,j 及 w: n,e); for(k=1;karcsij=w; prin