交通咨询系统数据结构c语言.pdf

《交通咨询系统数据结构c语言.pdf》由会员分享，可在线阅读，更多相关《交通咨询系统数据结构c语言.pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数 据 结 构 课 程 设 计 交通咨询系统设计 学 生 姓 名:学 号:指 导 教 师:完 成 日 期:目 录 1 设计任务书.1 1.1 题目与要求.1 1。2 知识点.1 1。3 输入输出分析.1 1。4 实现的功能.1 2 概要设计.2 2.1 结构体类型及函数声明.2 2。2 主程序流程.2 3 详细设计.3 3。1 数据类型实现.3 3.2 程序代码.3 4 调试分析.11 4。1 问题分析与回顾.11 4.2 算法时空分析.11 4.3 算法改进.11 4。4 经验和体会.12 5 测试结果.12 参考文献.14 1 1 设计任务书 1。1 题目与要求 题目：编写程序实现交通咨

2、询系统设计的模拟。要求：(1）建立交通网络网的存储结构;（2）总体设计要画流程图；（3）提供程序测试方案；（4)界面友好。1.2 知识点 本次课程设计应用到了图的创建、邻接矩阵、迪杰斯特拉算法、弗洛伊德算法、结构体、宏定义、自定义类型、函数的声明与调用等知识点.1。3 输入输出分析(1）普通输入 对于图的存储，我采用的是邻接矩阵的方法，借助于邻接矩阵容易判定任意两个顶点之间是否有弧相连，也容易求得各段弧的权值。（2）对话式输入 在用户选择系统功能时，我采用的是对话式输入,让用户输入系统功能的代号，利用 switch语句判断用户输入的指令并调用相应的函数实现具体功能。(3）程序输出 对于用户查询

3、结果的展示，考虑美观以及方便用户的因素，我写了一个 pri（）函数输出各个城市的代码城市名字对照表，用户可以更方便的使用.对于用户查询一个城市到所有城市的最短路径时，考虑到显示结果较多，我采用表格的形式进行显示，使界面更美观.1.4 实现的功能 在交通网络越来越发达的今天，人们出去旅行、出差更多的会考虑选择最短路径或最小花费等问题，因此我设计了一个交通咨询系统。这个系统可以根据用户的选择实现3 种功能:求一个城市到所有城市的最短路径；求两个城市间的最短路径；求两个城市间的最小花费。2 2 概要设计 2。1 结构体类型及函数声明(1）结构体 路径图结构体类型 MGraph 花费图结构体类型 HG

4、raph （2)函数声明 void pri(）/输出城市代号对照表函数。void CreateMGraph(MGraph G）/创建路径图函数，路径图存放于 G 中。void CreateHGraph（HGraph H)/创建花费图函数，花费图存放于 H 中。void Dijkstra(MGraph G，int v1，int n)/迪杰斯特拉算法求单源最短路径函数,v1为源点，n 为城市个数,这个图存放于 G 中。void Floyd（MGraph G,int n)/弗洛伊德求两点间最短路径函数，n 表示城市个数，这个图存放于 G 中。void Floyd1（HGraph*H,int n）/弗

5、洛伊德求两点间最小花费函数，n 表示城市个数，这个图存放于 H 中。2.2 主程序流程（1）主程序调用模块图 主程序利用 switch()语句实现各个模块的调用，主函数调用如图 21 所示。图 2-1 主程序调用模块图 主程序根据不同值主调函数 0退出 1求单源最短路径 2求两点间最短路径 3求两点间最小花费 3 3 详细设计 3.1 数据类型实现 (1）路径图结构体类型 Vertextype vexsMVNum；/顶点数组，顶点表示城市代号 Adjmatrix arcsMVNum MVNum；/邻接矩阵定义路径图 MGraph；（2）花费图结构体类型 typedef struct Verte

6、xtype vexsMVNum;/顶点数组,顶点表示城市代号 Adjmatrix arcsMVNum MVNum;/邻接矩阵定义花费图 HGraph；3。2 程序代码#includevexsi=（char）i；for(i=1；i=14;i+）for（j=1;jarcs12=Garcs21=137；G-arcs24=Garcs42=674；Garcs13=G-arcs31=695；Garcs34=G-arcs43=349；Garcs35=G-arcs53=511；Garcs56=Garcs65=842;G-arcs37=G-arcs73=534;G-arcs48=G-arcs84=651；G-a

7、rcs613=G-arcs136=1100；G-arcs612=G-arcs126=967;Garcs711=G-arcs117=409；G-arcs810=G-arcs108=825；G-arcs910=Garcs109=622；Garcs1011=Garcs1110=367；Garcs1112=Garcs1211=902;G-arcs1213=Garcs1312=639;Garcs1114=G-arcs1411=675;void CreateHGraph（HGraph H)/采用邻接矩阵表示法构造有向图 H，此图为带权花费图 int i，j;for（i=1；i=14；i+）/输入顶点信息

8、H-vexsi=（char)i;for（i=1；iarcs24=Harcs42=93；H-arcs13=H-arcs31=93;H-arcs34=H-arcs43=51;Harcs35=H-arcs53=72;H-arcs56=H-arcs65=112;Harcs37=H-arcs73=75;H-arcs48=Harcs84=91；H-arcs613=Harcs136=141；Harcs612=H-arcs126=128;H-arcs711=Harcs117=62;Harcs810=H-arcs108=105;Harcs910=H-arcs109=86；H-arcs1011=H-arcs111

9、0=53；H-arcs1112=H-arcs1211=115;Harcs1213=Harcs1312=86;Harcs1114=Harcs1411=91；/以下是迪杰斯特拉算法 void Dijkstra（MGraph G，int v1,int n）/用 Dijkstra 算法求有向网 G 的 v1 顶点到其他顶点 v 的最短路径 Pv及其权 Dv /设 G 是有向图的邻接矩阵,若边i，j不存在则 Gij=Maxint /Sv为真当且仅当 v 属于 S,即已经求得从 v1 到 v 的最短路径 int DMVNum，P2MVNum；int v，i,w，min;enum boolean SMVNu

10、m;for(v=1;varcsv1v；/置初始的最短路径值 if(Dv Maxint)P2v=v1；/v1 是前趋双亲 else P2v=0；/v 无前趋 /End_for Dv1=0；Sv1=TRUE;/S 集初始时只有源点 源点到源点的距离为 0 /开始循环每次求的 V1 到某个 V 顶点的最短路径并加 V 到 S 集中 7 for(i=2；i=n；i+)/其余 n1 个顶点 min=Maxint;/当前所知离 v1 顶点的最近距离设初值为 for(w=1；w=n；w+)/对所有顶点检查 if(！Sw&Dwmin）/找离 v1 最近的顶点 w 并将其赋给 v 距离赋给 min v=w;/在

11、 S 集之外的离 v1 最近的顶点序号 min=Dw；/最近的距离 /W 顶点距离 V1 顶点更近 Sv=TRUE;/将 v 并入 S 集 for(w=1；w=n;w+）/更新当前最短路径及距离 if(!Sw(Dv+Garcsvwarcsvw;/更新 D2w P2w=v；/End_if /End_for printf(路径长度（单位：km）最短路径n）;for（i=1；i=n;i+)printf（10d,Di）；printf(”%13d,i）;v=P2i;while(v！=0）printf(arcsij!=Maxint)8 pij=j;/j 是 i 的后继 else pij=0；Dij=Gar

12、csij;for（k=1;k=n；k+)for（i=1；i=n；i+)for（j=1；j=n；j+）if(Dik+Dkjarcsij!=Maxint）pij=j；/j 是 i 的后继 else pij=0；Dij=Harcsij;for（k=1;k=n;k+）for（i=1；i=n;i+）for(j=1;j%d”,k）；/输出后继顶点 k=pkw;/继续找下一个后继顶点 printf（d，w);/输出终点 w printf(路径长度：%dnnn”,Dvw)；break；case 3:pri(）;Floyd1（H，14)；/调用费洛伊德求最小花费算法 printf（输入城市起点代号和终点代号：”

13、）;scanf(dd”,v,w）;k=pvw;/k 为起点 v 的后继顶点 if(k=0）printf（”顶点d 到%d 无路径！n,v,w)；else printf（”从顶点%d 到%d 的路径是：d,v，w，v）;while(k!=w）printf（-%d，k);/输出后继顶点 k=pkw;/继续找下一个后继顶点 1 1 printf（-d,w);/输出终点 w printf(n 最小花费（单位：元)：%dnnn，Dvw）；break;4 调试分析 4.1 问题分析与回顾 问题 1:求单源最短路径时，两点间无路径时程序出错.分析 对于边的初始化出错，我在程序开始的地方定义了一个最大数 Ma

14、xint=65535表示无穷大，初始化邻接矩阵时，添加了一句“Garcsij=Maxint;”.问题 2：求两点间最短路径时，程序运行时不能给出最短路径.分析：Floyd 函数里修改长度时少写了一层循环,加上之后就好了。问题 3：输出城市代码对照表时出错。分析：pri 函数中调用 pr 函数时，pr 函数应写到循环里边,我写到了循环外边。4。2 算法时空分析（1）迪杰斯特拉求单源最短路径的算法：对于 n 个顶点，每次求的 V1 到某个 V 顶点的最短路径时，第一个 for 循环的时间复杂度是 O（n),内层 for 循环的时间复杂度是 O（n）,所以总的时间复杂度是 O（n2）。（2）弗洛伊德

15、求两点间最短路径的算法：对于 n 个顶点，循环求最短路径是，第一个 for 循环时间复杂度是 O（n)，内层又有两个 for 循环，其时间复杂度是 O（n2）,所以总的时间复杂度是 O（n3)。(3）弗洛伊德求两点间最小花费的算法:对于 n 个顶点，此算法和求两点间最短路径算法时间复杂度一样，也是 O（n3）。4。3 算法改进 在这个交通咨询系统中，创建图时，我是在程序里对图进行了初始化，赋予了一定的权值,这样不利于图的更新和再创建，系统功能还不是很完善。1 2 求两点间最短路径和最小花费都用到了弗洛伊德算法，由于我编程的经验不足，对函数参数传递理解的还不够透彻，所以用了两次弗洛伊德算法,这一

16、点上还有待改进.4。4 经验和体会 经过这些天的设计,这个交通咨询系统已经实现.这个设计可以实现用户输入指令，系统进行相应的查询功能。学习数据结构对我后继学习其它课程也有很大的帮助，因为运用数据结构可以编出更“好的程序。以前学习 C 语言时，只会编写简单的小程序，对于那些大点的程序,如果不用数据结构，程序就会显得臃肿、杂乱无章。以前只是一味的编程，学了数据结构之后，我明白了程序中的各个部分在计算机中是怎么存储的，明白了怎么编写程序可以降低程序的时空复杂度让程序看起来更有条理。此次课程设计,给我提供了一个既动手又动脑,独立实践的机会。我回顾了 C 语言编程的方法和编程的思想，并运用数据结构的知识

17、使程序的时空复杂度都有所降低.这次课程设计让我更深刻地理解了迪杰斯特拉算法和弗洛伊德算法求最短路径的问题,而且在编程的过程中，更加锻炼了我的思维模式,让自己的思维更有条理，写出的程序也更简单明了。课程设计中,我将学到的知识融会贯通,同时提高调试程序的能力，养成良好的编程习惯，并增强对程序整体设计的把握，理论与实践相结合。通过此次课程设计，让我明白了数据结构的重要性,同时也提高了我分析问题、解决问题的能力。我会再接再厉,编写出更好的程序。5 测试结果（1）系统运行首页面如图 5-1 所示：图 51 系统首页图（2）选择“1,系统会给出城市代号对照表并提示用户输入城市起点代号，运行截图如图 5-2

18、 所示:1 3 图 52 选择“1”功能运行图（3）输入城市代号“1”，系统会给出“1到所有城市的最短路径以及路径长度，运行截图如图 5-3 所示：图 53 求单源最短路径输出图（4）选择功能“2”，并输入城市起点和终点代号“1”和“4”，系统会给出最短路径和最短路径长度，运行截图如图 5-4 所示:图 54 求两点间最短路径输出图（5）选择功能“3”，并输入城市起点和终点代号“3和“7”，系统会给出最小花费和相应的路径，运行截图如图 5-5 所示:图 5-5 求两点间最小花费输出图 1 4 参考文献 1 严蔚敏,吴伟民数据结构（C 语言版）M北京：清华大学出版社，2010 2 蒋清明,向德生

19、 C 语言程序设计M北京：人民邮电出版社，2008 3 尹德淳，龙脉工作室C 函数速查手册M北京：人民邮电出版社，2009 4 李玲玲C 程序设计M北京：清华大学出版社,2011 5 陈雁数据结构M北京：高等教育出版社，2004 6 张磊C 程序设计教程M北京:中国铁道出版社，2007 7 严蔚敏,米宁数据结构习题集M北京：清华大学出版社,2009 年 8 黄同成，黄俊民，董建寅数据结构M北京:中国电力出版社，2008 年 9 谭浩强C 程序设计M北京：清华大学出版社，2008 10 刘振鹏，张晓莉，郝杰数据结构M北京：中国铁道出版社,2003 年 数据结构课程设计评分标准 学号 姓名 得分

20、程序运行情况（占总成绩 20%)能正确运行 基本能正确运行 能运行但结果不完善 程序功能的完善程度（占总成绩 15)完善 基本完善 不完善 程序结构的合理性（占总成绩 15)合理 基本合理 不太合理 数据结构的合理性(占总成绩 25%）正确应用并有创新 正确应用 基本正确应用 学生的工作态度与 独立工作能力（占总成绩 10)工作态度认真能独立完成任务 工作态度认真但独立性较差 工作态度基本认真但缺乏独立性 设计报告的规范性（占总成绩 15%）符合规范 基本符合规范 规范性较差 成绩等级 总分 指导老师签字 时间 优秀：90 分100 分 良好：80 分89 分 中等:7079 分 及格：6069 分 不及格 0 分59 分