《交通咨询系统数据结构c语言word文档良心出品》由会员分享，可在线阅读，更多相关《交通咨询系统数据结构c语言word文档良心出品(22页珍藏版)》请在人人文库网上搜索。
1、数据结构课程设t 交通咨询系统设十 生姓名: 导教师: 成日期: 设计任务书 1.1题目与要求 1.2知识点 1.3输入输出分析 1.4实现的功能 概要设计 2.1结构体类型及函数声明 2.2主程序流程 详细设计 3.1数据类型实现 3.2程序代码 调试分析 4.1 问题分析与回顾 4.2 算法时空分析 4.3 算法改进 4.4 经验和体会 2. 2. 2. 3. 3. .3. 10 10 11 1.1 11 12 1.3 测试结果 参考文献 设计任务书 1.1 题目与要求 3 建立交通网络网的存储结构; 总体设计要画流程图； 提供程序测试方案； 界面友好。 1.2 知识点 题目：编写程序实现。
2、交通咨询系统设计的模拟。 要求：(1) (2) (3) (4) 本次课程设计应用到了图的创建、邻接矩阵、迪杰斯特拉算法、弗洛伊德算法、结 构体、宏定义、自定义类型、函数的声明与调用等知识点。 1.3输入输出分析 (1)普通输入 对于图的存储，我采用的是邻接矩阵的方法，借助于邻接矩阵容易判定任意两个顶 点之间是否有弧相连，也容易求得各段弧的权值。 (2)对话式输入 在用户选择系统功能时，我采用的是对话式输入，让用户输入系统功能的代号，利 用switch语句判断用户输入的指令并调用相应的函数实现具体功能。 (3)程序输出 对于用户查询结果的展示，考虑美观以及方便用户的因素，我写了一个pri()函数。
3、输 出各个城市的代码城市名字对照表，用户可以更方便的使用。对于用户查询一个城市到 所有城市的最短路径时，考虑到显示结果较多，我采用表格的形式进行显示，使界面更 美观。 1.4 实现的功能 在交通网络越来越发达的今天，人们出去旅行、出差更多的会考虑选择最短路径或 最小花费等问题，因此我设计了一个交通咨询系统。这个系统可以根据用户的选择实现 3种功能：求一个城市到所有城市的最短路径；求两个城市间的最短路径；求两个城市 间的最小花费。 2概要设计 2.1结构体类型及函数声明 (1) 结构体 MGra ph HGraph 路径图结构体类型 花费图结构体类型 (2) 函数声明 void pri() 输出。
4、城市代号对照表函数。 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) /弗洛伊德求两点间最小花费函数，n表示。
5、城市个数， 这个图存放于H中。 2.2主程序流程 2-1所示。 (1) 主程序调用模块图 主程序利用switchO语句实现各个模块的调用，主函数调用如图 图2-1主程序调用模块图 详细设计 3.1 数据类型实现 II 4 (1)路径图结构体类型 Vertextype vexsMVNum;顶点数组，顶点表示城市代号 Adjmatrix arcsMVNum MVNum;/邻接矩阵定义路径图 MGra ph; (2)花费图结构体类型 typedef struct II顶点数组，顶点表示城市代号 II邻接矩阵定义花费图 Vertextype vexsMVNum; Adjmatrix arcsMVNum。
6、 MVNum; HGra ph; 3.2 程序代码 #in clude #i nclude 最大顶点数 II定义一个最大数，其意义为无穷大 enum boolea nFALSE,TRUE; typ edef typ edef typ edef #defi ne MVNum 100 #defi ne Maxi nt 65535 char Vertext ype; int Adjmatrix; struct vexsMVNum; arcsMVNum MVNum; Vertext ype Adjmatrix MGra ph; typ edef struct Vertext ype Adjmatrix。
7、 HGra ph; int D1MVNum, p 1MVNum; int DMVNumMVNum, pMVNumMVNum; void pr(int i) II顶点数组 / 类型假定为char型 邻接矩阵假定为int型 vexsMVNum; arcsMVNum MVNum; II顶点数组 类型假定为char型 邻接矩阵假定为int型 switch(i) case 1:prin tf(北京 );break; case 2:pnntf(” 天津 );break; case 3: prin tf(郑州 );break; case 4: prin tf(徐州 );break; case 5:print。
8、f(西安 );break; case 6:printf(成都 );break; case 7:pnntf(” 武汉 );break; case 8:printf(上海 );break; case 9: prin tf(福州 );break; case 1O:printf(” 南昌 );break; case 11: printf(株洲 );break; case 12: printf(贵阳 );break; case 13:printf(” 昆明 );break; case 14: printf(广州 );break; void p ri() int i; n); printf(城市代号对照表。
9、 prin tf(* for(i=1;i=14;i+) prin tf(%d.,i); pr(i)； pr(i); prin tf(n); prin tf(* ); void CreateMGra ph(MGra ph *G) /采用邻接矩阵表示法构造有向图G,此图为带权距离图 int i,j; for(i=1;ivexsi=(char)i; for(i=1;i=14;i+) 7 forQ=1;jarcsij=Maxint; / 初始化邻接矩阵 G-arcs12=G-arcs21=137; G-arcs24=G-arcs42=674; G-arcs13=G-arcs31=695; G-arcs。
10、34=G-arcs43=349; G-arcs35=G-arcs53=511; G-arcs56=G-arcs 6 5=842; G-arcs37=G-arcs73=534; G-arcs48=G-arcs84=651; G-arcs613=G-arcs13 6=1100; G-arcs612=G-arcs12 6=967; G-arcs711=G-arcs117=409; G-arcs810=G-arcs108=825; G-arcs910=G-arcs109=622; G-arcs1011=G-arcs1110=367; G-arcs1112=G-arcs1211=902; G-arcs1。
11、213=G-arcs1312=639; G-arcs1114=G-arcs1411=675; void CreateHGra ph(HGra ph *H) II采用邻接矩阵表示法构造有向图H,此图为带权花费图 int i,j; for(i=1;ivexsi=(char)i; for(i=1;i=14;i+) for(j=1;jarcsij=Maxint;II 初始化邻接矩阵 H-arcs12=H-arcs21=20; H-arcs24=H-arcs42=93; H-arcs13=H-arcs31=93; H-arcs34=H-arcs43=51; H-arcs35=H-arcs53=72; H。
12、-arcs56=H-arcs 65=112; H-arcs37=H-arcs73=75; H-arcs48=H-arcs84=91; H-arcs 6 13=H-arcs136=141; H-arcs 6 12=H-arcs126=128; H-arcs711=H-arcs117=62; H-arcs810=H-arcs108=105; H-arcs910=H-arcs109=86; H-arcs1011=H-arcs1110=53; H-arcs1112=H-arcs1211=115; H-arcs1213=H-arcs1312=86; H-arcs1114=H-arcs1411=91; 以。
13、下是迪杰斯特拉算法 void Dijkstra(MGra ph *G, i nt v1,i nt n) /用Dijkstra算法求有向网 G的v1顶点到其他顶点 v的最短路径Pv及其权Dv 设G是有向图的邻接矩阵，若边不存在则Gij=Maxint /Sv为真当且仅当v属于S,即已经求得从 v1到v的最短路径 int DMVNum, P 2MVNum; int v,i,w,mi n; enum boolean SMVNum; for(v=1;varcsv1v; /v1是前趋双亲 if(Dv Maxi nt) P 2v=v1; /v无前趋 P 2v=0; / En d_for Dv1=0;Sv1=。
14、TRUE; 开始循环緩每次求的 for(i=2;i=n;i+)/ 其余 mi n=Max int; else /S集初始时只有源点源点到源点的距离为 0 V1至U某个V顶点的最短路径陵并加V到S集中 n-1个顶点 /当前所知离v1顶点的最近距离 復设初值为8 for(w=1;w=n;w+)对所有顶点检查 if(!Sw min=Dw; /在 S集之外的离v1最近的顶点序号 最近的距离 /W顶点距离V1顶点更近 Sv=TRUE;/将 v 并入 S 集 for(w=1;warcsvw;/更新 D2w P2w=v; /End if if(!Sw for(i=1;i=n ;i+) printf (%10。
15、d, Di); printf (%13d, i);v= P2i; while(v!=0) printf (-%d, v); v=P 2v; prin tf(n); prin tf(nn); /以下是弗洛伊德求最短路径算法 void Floyd(MGra ph *G, i nt n) 用Floyd算法求有向网G中各对顶点i和j之间的最短路径 int i, j, k; for(i=1;i=n ;i+) for(j=1;jarcsij!=Maxi nt) Pij=j；/j 是 i 的后继 else pij=0; Dij=G-arcsij; for(k=1;k=n;k+) for(i=1;i=n ;i。
16、+) for(j=1;j=n;j+) if(Dik+DkjDij) 9 /修改长度 Dij=Dik+Dkj; Pij=P ik； 18 void Floyd1(HGra ph *H, i nt n) /用Floyd算法求有向网 int i, j, k; for(i=1;i=n ;i+) for(j=1;jarcsij!=Maxi nt) pij=j;/j 是 i 的后继 else pij=0; Dij=H-arcsij; for(k=1;k=n;k+) for(i=1;i=n ;i+) for(j=1;j=n;j+) if(Dik+Dkj%d,k); / 输出后继顶点 k=p kw;继续找下一。
17、个后继顶点 printf(-%d,w);/ 输出终点 w printf(”路径长度：dnnn,Dvw); break; case 3: pri(); Floyd1(H,14);调用费洛伊德求最小花费算法 printf(”输入城市起点代号和终点代号：”)； scan f(%d%d， 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=p kw;继续找下一个后继顶点 printf(-%d。
18、,w);/ 输出终点 w printf(n 最小花费(单位：元)：dnnn,Dvw); break; 4调试分析 4.1问题分析与回顾 问题1：求单源最短路径时，两点间无路径时程序出错。 分析对于边的初始化出错，我在程序开始的地方定义了一个最大数 Maxi nt =65535 表示无穷大，初始化邻接矩阵时，添加了一句“G-arcsij=Maxint; ”。 问题2：求两点间最短路径时，程序运行时不能给出最短路径。 分析：Floyd函数里修改长度时少写了一层循环，加上之后就好了。 问题3：输出城市代码对照表时出错。 分析：pri函数中调用pr函数时，pr函数应写到循环里边，我写到了循环外边。 4。
19、.2算法时空分析 (1) 对于 复杂度是 (2) 对于 迪杰斯特拉求单源最短路径的算法： n个顶点，每次求的V1到某个V顶点的最短路径时，第一个for循环的时间 0(n),内层for循环的时间复杂度是0(n),所以总的时间复杂度是0 (n2)。 弗洛伊德求两点间最短路径的算法： n个顶点，循环求最短路径是，第一个 for循环时间复杂度是0 (n),内层 (n3)。 O( n3)。 又有两个for循环，其时间复杂度是 0 (n2),所以总的时间复杂度是 0 (3) 弗洛伊德求两点间最小花费的算法： 对于n个顶点，此算法和求两点间最短路径算法时间复杂度一样，也是 4.3算法改进 赋予了一定 在这个。
20、交通咨询系统中，创建图时，我是在程序里对图进行了初始化， 的权值，这样不利于图的更新和再创建，系统功能还不是很完善。 求两点间最短路径和最小花费都用到了弗洛伊德算法，由于我编程的经验不足，对 函数参数传递理解的还不够透彻，所以用了两次弗洛伊德算法，这一点上还有待改进。 4.4经验和体会 经过这些天的设计，这个交通咨询系统已经实现。这个设计可以实现用户输入指令， 系统进行相应的查询功能。 因为运用数据结构可以编出 学习数据结构对我后继学习其它课程也有很大的帮助， 更“好”的程序。以前学习C语言时，只会编写简单的小程序，对于那些大点的程序， 如果不用数据结构，程序就会显得臃肿、杂乱无章。以前只是一。
21、味的编程，学了数据结 构之后，我明白了程序中的各个部分在计算机中是怎么存储的，明白了怎么编写程序可 以降低程序的时空复杂度让程序看起来更有条理。 此次课程设计，给我提供了一个既动手又动脑，独立实践的机会。我回顾了 C语言 编程的方法和编程的思想，并运用数据结构的知识使程序的时空复杂度都有所降低。 次课程设计让我更深刻地理解了迪杰斯特拉算法和弗洛伊德算法求最短路径的问题， 而 且在编程的过程中，更加锻炼了我的思维模式，让自己的思维更有条理，写出的程序也更简单明了。课程设计中，我将学到的知识融会贯通，同时提高调试程序的能力，养成 良好的编程习惯，并增强对程序整体设计的把握，理论与实践相结合。通过此。
22、次课程设 计，让我明白了数据结构的重要性，同时也提高了我分析问题、解决问题的能力。我会 再接再厉，编写出更好的程序。 5测试结果 (1)系统运行首页面如图5-1所示: 图5-1系统首页图 (2)选择“ 1”，系统会给出城市代号对照表并提示用户输入城市起点代号，运 行截图如图5-2所示： 3k市代码对照 MKM.WWWWWKMKMMXWW WW WHMMMMMMW WWEilKMMMMtWWWHMKKMMItWWWWMMMMKKMUWWWWWMMMMXM.WWWWW 拭 北豆2.天津郑州 4-01吕西安 成都 7-武汉 鉄上海 趴福州 10-m昌11-株洲 12.贵阳13.昆明14.r州 H H。
23、 M M M W M W H H H M M M * H BM K M W M ITH H H M M M K M H H H 扈 M M M W H H H H H 请输入城市超点代- 图5-2选择“ 1”功能运行图 (3) 输入城市代号“ 1”，系统会给出“ 1”到所有城市的最短路径以及路径长度, 运行截图如图5-3所示： -*) 号伽 代- 点位 起单 、不 0 137 95 eii 13eb 2048 1229 1462 227 2313 最短路径 1 2-1 3-t 4-2-1 5-3-1 6-5 J3-1 7-3-1 8-4-2-1 9-10-11-7-3-1 图5-3求。
24、单源最短路径输出图 2 城市代码对無表 ，諜昌它知r翌肘徐!1譎吨&谓都g (4)选择功能“ 2”，并输入城市起点和终点代号“ 1”和“ 4”，系统会给出最 短路径和最短路径长度，运行截图如图 5-4所示： 踏織ast詐 求两点间最小花费输出图 图5-5 图5-4求两点间最短路径输出图 (5)选择功能“ 3”，并输入城市起点和终点代号“ 3”和“ 7”，系统会给出最 小花费和相应的路径，运行截图如图5-5所示： 参考文献 1 2 3 4 6 7 严蔚敏，吴伟民.数据结构(C语言版)M.北京：清华大学出版社，. 蒋清明，向德生.C语言程序设计M.北京：人民邮电出版社， 尹德淳，龙脉工作室。
25、.C函数速查手册M.北京：人民邮电出版社， 李玲玲.C程序设计M.北京：清华大学出版社，. 陈雁.数据结构M.北京：高等教育出版社，. 张磊.C程序设计教程M.北京：中国铁道出版社，. 严蔚敏，米宁.数据结构习题集M.北京：清华大学出版社， 黄同成，黄俊民，董建寅.数据结构M.北京：中国电力出版社， 谭浩强.C程序设计M.北京：清华大学出版社，. . . 年. 8 9 10 刘振鹏，张晓莉，郝杰.数据结构M.北京：中国铁道出版社, 年. 年. 数据结构课程设计评分标准 学号1姓名 得分 程序运行情况 (占总成绩20%。
26、) 能正确运行 基本能正确运行 能运行但结果不完善 程序功能的完善程度 (占总成绩15%) .、 Z 完善 基本完善 不兀善 程序结构的合理性 (占总成绩15%) 合理 基本合理 不太合理 数据结构的合理性 (占总成绩25%) 正确应用并有创新 正确应用 基本正确应用 学生的工作态度与 独立工作能力 (占总成绩10%) 工作态度认真能独立完成任务 工作态度认真但独立性较差 工作态度基本认真但缺乏独立性 设计报告的规范性 (占总成绩15%) 符合规范 基本符合规范 规范性较差 成绩等级 总分 指导老师签字 时间 优秀：90分100分良好：80分89分 中等：7079分及格：6069分 不及格0分59分。
如果觉得《店铺咨询系统c语言 交通咨询系统数据结构c语言word文档良心出品》对你有帮助，请点赞、收藏，并留下你的观点哦！
