数据结构课程设计报告(公交换乘)

1、课程设计报告题目:武昌地区公交查询与换乘推荐课程名称：数据结构课程设计 专业班级: 学 号: 姓 名: 指导教师: 报告日期:计算机科学与技术学院任务书设计内容掌握图、查找、排序等数据结构的物理存储结构与基本算法，通过解决较复 杂的基于图模型的实际问题，提高学生对数据结构知识综合运用的技能与实践能 力。设计要求（1）从互联网或相关资料获取可靠的武汉公交线路及其地理数据，通过线性结 构与图模型对其进行表示，且以文件保存。（2）图形方式显示上述图模型与求解结果。（3）界面友好，实现的功能包括：录入与修改公交线路信息；查询所有线路信 息（线路名号、起点、终点、首末车时间、票价规则），按线路名或起点站

2、名排 序；查询指定线路的详情（沿途站点、首末车时间、票价规则、站间距离等）； 查询某一位置途经的所有公交线路、指定起点与终点，推荐乘车方案（如要求换 乘次数最少、路线最短或无要求条件等）。参考文献1 严蔚敏，吴伟民.数据结构（c语言版）.北京：清华大学出版社,19972 严蔚敏，吴伟民，米宁.数据结构题集（c语言版）.北京：清华大学出 版社，19993 博客园，华山大师兄的博客，最短路径di jkstra算法和floyd算法http:/www. cnblogs. com/biyeymyhjob/archive/2012/07/31/2615833. html#33 39167目录1引言31.1

3、课题背景与意义31公交出行31.2国内外研究现状41.3课程设计的主要研究工作42系统需求分析与总体设计62系统需求分析62.2系统总体设计63系统详细设计73有关数据结构的定义73.2主要算法设计84系统实现与测试134系统实现134.2系统测试145总结与展望205全文总结205工作展望216.附录211引言1.1课题背景与意义1丄1公交出行公交出行是现在城市生活中必不可少的一种出行方式。但往往由于线路四通 八达，车次繁多，乘客众多，乘公交成了一件麻烦事。公交查询与换乘推荐系统 正是为了解决乘公交的诸多不便而产生的。1.1.2图模型图类型是一种重要的数据结构，而公交换查询与换乘推荐系统是图

4、模型的典 型应用。在此系统屮，将会模拟图屮遍历，查找，最短路径搜索等重要操作，巩 固图模型的各种操作。1.2国内外研究现状如今，公交出行方式已经较为成熟。随着互联网吋代的到来，各种查询系 统也是一应俱全。例如武汉市公交查询网站：、上均有非常方便的查询服务提供。国内外情况均是如此。1.3课程设计的主要研究工作主要内容：首先要搜集武汉数武昌区公交线路站点信息。住由于十分复杂， 使用完整的线路站点信息会导致数据料过于庞大且没有必耍，故采用在武汉市地 铁交通图上选取一些具有代表性的线路的站点信息代替。)其然后是进行系统总 体设计如下：1. 线路信息查询：线路信息查询屮要将所有线路的票价、首班时间、末班

5、时间、途径所有站点 等信息显示出来。故需要根据已经初始化好的线路信息打印在屏幕上，按照邻接 列表的存储顺序遍历图，一次打印途经站点的名字。2. 站点信息查询：站点信息查询中，为了方便输入，提高效率，故先对所有站点编号显示在屏 幕上供使用者查阅，根据编号输入需要查询的站点。对每一个站点需要了解所在 的所有线路，并分别显示该站点在该线路上的上一站和下一站，以及该线路的起 点和终点。如果该站点为起点或终点，则另作提示。3. 距离最短路线查询：使用者对照站点名字与编号输入起点编号与终点编号，则通过程序得岀两点 间的最短距离以及沿途站点，并给岀线路推荐。当两站间有多条线路可以选择吋, 则给出提示。该部分

6、使用辿杰特拉斯最短路线算法，使用邻接矩阵的存储结构进行搜索。 dijkstra算法说明如下：1)算法思想:设g二(v,e)是一个带权有向图，把图中顶点集合v分成两组，第一组 为已求出最短路径的顶点集合（用s表示，初始时s中只有一个源点，以后每求得一条最短路径，就将加入到 集合s中，直到全部顶点都加入到s中，算法就结束了）， 第二组为其余未确定最短路径的顶点集合（用u表示），按最短路径长度的递增 次序依次把第二组的顶点加入s中。在加入的过程中，总保持从源点start到s中各顶点的最短路径长度不大于从源点start到u中任 何顶点的最短路径长度。此外，每个顶点对应一个距离，s中的顶点的距离就是从s

7、tart到此顶点的最短路径长度，u中的顶点的距离， 是从start到此顶点只包括s中的顶点为中间顶点的当前最短路径长度。2）算法步骤：a. 初始时，s只包含源点，即s = start, start的距离为0。u包含除v外的其他 顶点，即:u=其余顶点,若start与u中顶点u有边，则v u ,start 正常有权值,若u不是start的出边邻接点，贝0 u ,start 权值为fb. 从u中选取一个距离start最小的顶点k,把k加入s中（该选定的距离就 是start到k的最短路径长度）。c以k为新考虑的中间点，修改u中各顶点的距离；若从源点start到顶点u的 距离（经过顶点k）比原来距离（

8、不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。d重复步骤b和c直到所有顶点都包含在s屮。在执行完迪杰特拉斯算法后，通过访问最短距离数组中的相应元素打印出最 短距离。然后对前驱结点编号数组进行调整，再遍历调整后的数组，从而输岀途 径的各站点。最后根据两两站点间的抽彖同路（即弧的邻接矩阵存储结构）进行 搜索得出在哪条线路上，从而得出换乘推荐。4. 将数据写入磁盘：本次设计的系统面向使用者，故所有初始数据都己经一数组的形式给出，主 要包括：图的邻接数组、弧权值数组、站点信息数组、站点编号与名称数组。针 对这四个数组，只需要设置四个文件指针，遍历数组的同时分别写入文

9、件即可。函数调用关系如下图1：创建图模型函数2站点定位函数3. 最短路径查询函数4文件存盘函数图1 系统函数调用关系图2系统需求分析与总体设计2.1系统需求分析用户需要知道是所有线路的信息，包括票价、首班时间、末班时间、沿途经 过的所有站点；由于线路可能很多，客户只需要知道摸个具体站点的信息的话， 具体到每一个站点，则有站点所在的所有线路以及在相应线路上的上一站，下一 站，以及相应的线路的起点终点；客户需要的最重要的是乘车线路推荐，具体表 现为输入起点和终点的编号要能够通过程序求出最短距离以及线路推荐。2.2系统总体设计针对以上需求，系统需要有初始化保存所有信息的功能，在这一部分中，将 所有站

10、点的名称、编号；站点间的邻接关系、距离；车次信息（包括票价、首班 时间、末班时间等）等信息初始化并保存，以备后续使用。第二个是现实所有线 路信息，在这一部分中，要先建立抽象线路图，使用邻接列表的存储方式建立线 路图，遍历图打印信息。第三个是站点位置信息的获取，在这一部分总，主要是 对图进行遍历，并查找得岀所有位置信息。第四部分是最优化路线推荐，在这一部分中主要使用迪杰斯特拉算法得出。最后将所有的初始化信息写入磁盘即可。3系统详细设计3.1有关数据结构的定义1. 站点名称与编号结构：保存站点名称与编号，名称使用字符吊结构长度为 20 个字符：char station_name20;编号使用整型：

11、int station_num;typedef structchar staton_name20|;int station_num;)station_num;2. 图结点结构：有邻接点域，存放与改点相邻的顶点的编号，使用整型: int verj_num;抽象站点的名称，使用字符串：char station_name20；自引用 指针域，指向相邻的下一个节点：struct tablenode *next；typedef structint verj_num;char station_namef20;struct tablenode *next;tablenode;3. 头结点结构：抽象站点的名称

12、，使用字符串：charstation_name20；抽象 站点编号，整型：int station_num;头指针：struct tablenode *next；typedef structint station_num;char station_name20;struct tablenode *head;headnode;4. 图结构：包含一个头结点结构数组：struct headnodemax_line_num;typedef structstruct headnodemax_line_num;jmgraph;5. 线路信息结构：线路编号，整型：int line_num；票价，浮点型：flo

13、at price; 首班时间的小时部分，整型：int start_time_houi'；首班时间的分钟部分：整型: int start_time_minute；末班时间的小时部分，整型：int end_time_hour:末班 时间的分钟部分，整型：int end_time_minute；typedef structint line_num;int start_time_hour;int start_time_minute;int end_time_hour;int end_time_minute;line_info;3.2主要算法设计1创建图模型：在建立图模型时，按照线路的结构建立。

14、每一个起点作为一个头结点，每一 条单链表代表一条线路。故图的头结点数组长度为max_llne_numo此时耍使用 的辅助存储结构是线路的邻接数组。遍历邻接数组，根据数组数据判断是否有下-结点并读取结点所代表的站点编号。流程图如图2：j+ ii+图2：建立线路邻图接列表2. 打印线路信息遍历线路信息数组，依次输出每一条线路的票价、首班时间、末班时间等信 息；遍历图，每一条链表是一条线路，依次输岀站点名称，名称之间用箭头相连, 显示岀一天线路的感觉。流程图如图3：图3：打印新路信息3 .站点定位有用户输入需要的站点编号，然后程序遍历图模型，当站点编号匹配吋，记 录下该站点所在的线路编号、线路起点终

15、点、该站点在相应线路上的上一站、下 一站。流程图如下图4：输入站点编号计数变量i,指针变量p记录前驱为上一站，记录后继为下一站>p=p > next图4：站点定位4 最优化线路推荐使用者对照站点名字与编号输入起点编号与终点编号，则通过程序得出两点 间的最短距离以及沿途站点，并给岀线路推荐。当两站间有多条线路可以选择时, 则给出提示。该部分使用迪杰特拉斯最短路线算法，使用邻接矩阵的存储结构进行搜索。 dijkstra算法说明如下：1）算法思想:设g=（v,e）是一个带权有向图，把图中顶点集合v分成两组，第一组 为已求岀最短路径的顶点集合（用s表示，初始时s中只有一个源点，以后每求得一

16、条最短路径，就将加入到 集合s中，直到全部顶点都加入到s中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用u表示），按最短路径长度的递增 次序依次把第二组的顶点加入s中。在加入的过程中，总保持从源点start到s中各顶点的最短路径长度不大于从源点start到u中任 何顶点的最短路径长度。此外，每个顶点对应一个距离，s中的顶点的距离就是从start到此顶点的最短路径长度，u中的顶点的距离， 是从start到此顶点只包括s中的顶点为中间顶点的当前最短路径长度。2）算法步骤：a初始时,s只包含源点,即s = start, start的距离为0。u包含除v外的其他 顶点，即:u二其余顶点,若

17、start与u中顶点u有边,则vu,start 正常有权值，若u不是start的出边邻接点，贝j u ,start 权值为8。b. 从u中选取一个距离start最小的顶点k,把k加入s中（该选定的距离就 是start到k的最短路径长度）。c. 以k为新考虑的中间点，修改u中各顶点的距离；若从源点start到顶点u的 距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。d重复步骤b和c直到所有顶点都包含在s中。在执行完迪杰特拉斯算法后，通过访问最短距离数组屮的相应元素打印出最 短距离。然后对前驱结点编号数组进行调整，再遍历调整后的数组，

18、从而输出途 径的各站点。最后根据两两站点间的抽象同路（即弧的邻接矩阵存储结构）进行 搜索得出在哪条线路上，从而得出换乘推荐。流程图如下图5：输入起点编号建立前驱顶点编号数组，各点最短距离编号图5：迪杰特拉斯算法4系统实现与测试4.1系统实现使用c语言编写系统，完成上述功能。硬件环境：联想thinkpad e431 o具 体数据结构定义如下：1. 站点名称与编号结构：typedef structchar staton_name20;int station_num;station_num;2. 图结点结构：typedefstructint verj_num;char station_name20;

19、struct tablenode *next;tablenode3. 头结点结构：typedef structint station_num;char station_name20|;struct tablenode *head;jheadnode;4. 图结构： typedef structstruct headnodemax_line_num;jmgraph;5. 线路信息结构：typedef structint line_num;int start_time_hour;int start_time_minute;int end_t ime_hour;int end_time_minute

20、;line_info;从main函数进入系统之后，首先直接调用创建图函数将各种初始化的数据 建立成图结构；再进入选择菜单，根据不同的选择(1, 2, 3, 4)进入调用打印 线路信息函数、顶点定位函数、最优化路线推荐函数、保存文件函数。详细代码见附录。4.2系统测试使用微软开发的visual studio 2012作为运行系统和调试系统的环境。运行 情况如下：首先进入系统界面：此时现实的简易文本菜单栏，有提示语“请输入您的选择：”字样，直接从键盘输入数字并回车;我们首先选择1:线路信息如下所示:1号线：票价：2.0元苜班车时间：6： 30末班车时间：22： 30光谷广场-> 广埠屯-&g

21、t; 街道口-洪山广场-中南路->江汉路-> 循礼门-> 汉口火车站常青花园2号线：票价：5元首班车时间：7： 0末班车时间：23： 0武汉火车站-> 仁和路-中南路-> 武昌火车站-钟家村王冢湾-> 新汉阳站首班车时间:6： 30末班车时间:22： 30新汉阳站-王家湾-> 宗关-王家墩4号线：票价：2.0元春班车时间：7： 0末班车时间：23： 0k关-崇仁路- >循礼门- >大智路-汉口北大道5号线：票价：15元苜班车时间：6： 30末班车时间：22： 30王家湾-钟家村江汉路-大智路->汉口北大道这是三，四，五号线。我们可以从

22、屏幕获取到每一趟车次的票价、首班时 间、末班时间以及从起点到终点沿途经过的站点名称。然后我们选择2：各站点对应编号如下:站洁 场车晦 屯广费卩 埠山汉口 广洪江汉寿站道车大 汉天盲和口 暫蛋示武仁汉0 2 4 6 8 0 2468111112站 m各>礒村萨 翳曇琴汉智 光街中頤吊一王王；大13 5 7 91357911111请输入你要查询位置的站点编号:n=ll我们首先可以看到所有站点的编号以及名称，我们任意选择一个站点，比如11：“王家湾”在"2号线”上，上一站是“钟詔寸”： 一一“2号线”的起点皇“武汉火车站”,终点臭“新汉阳站”。【阳毡1亠下一站是“宗关”。 当墩” o

23、“王家湾” > “肯线”的起点,、下一站是“钟家村”。 “5号线”甬寒点整“汉北大道”。是否继续使用系统？选择v或者十我们可以看到11号站点“王家湾”在图中的所有位置信息：三条线路上的 所有信息均分别显示。由于公交车是往返行驶，故方向只取一个，故起点、终点、 上一站、下一站均是相对的。我们继续使用，选择3：各站点对应编号如下:诂 站道 盘站 车大 斧議很天盲和口 nmwwint 汉0 2 4 6 8 0 2468111112站 口各訂5毒村r 光街中殖吊王王钟武大13 5 7 91357911111请输入起点编号:start_nun=13请输入终点编号;end_nun=l?我们可以看到所

24、有站点的名称编号，然后我们任意选择两个站点比如13和最短距离为:1讦米最短距离的近线路为：13王家墩->12宗关->14崇仁路->?循礼门->6江汉路-5中南路->18仁和路->1?武汉火车站具体换乘建议如下：ma 家线 王号关线 宗号 > 2-恿 -穿 划叙 幺号南 3 hr 艳-tr < -茸敝蠢羈豎魏点礼门壘号线2江汉路乘是否继续使用系统？选择v或者於我们首先看到了两个站点间的最短距离，然后是最短线路，最后是每两个 站点间的线路选择，即换乘推荐。当两个站点间有多班车往返时，会提示用户“或” 表示均可选择。我们继续试试其他站点间的情况：比如1

25、至ij 18：各站点对应编号如下:13 5 7 91357911111站 口各门>嗥r 口道 'rr汉智 光街中鲁王王大2468101214161820咕 站道 为锂站车大 飪ijr議很天皆曰和口 皿制蜩如药果武仁汉请输入起点编号:start_num=l请输入终点编号;end_nun=18好,我们输入了 1到18：我们看到了完全不同的另一套乘车方案。对照之前录入的地图信息我们发现测试正确。最后我们将系统用到的初始化数据，包括图的邻接矩阵，弧权值矩阵，名 称与编号，线路信息等数据存入磁盘：我们在f盘中查看是否存盘成功:vrstationlinenodeline j nfoline2

26、016/2/13 16:16文本文栏2016/2/13 16:16文本文栏2016/2/13 16:16文本文栏2016/2/13 16:16文本文桂2016/1/31 15:18文本文栏我们看到了相应的文本文档。5总结与展望5.1全文总结对自己的工作做一个总结。主要工作如下：(1) 、搜集关于武昌区公交线路图的信息，最终确定使用截取武汉市地铁 轨道交通图作为系统的初始化数据；(2) 、分析系统需求，设计系统板块；(3) 、编写系统，调试系统直至通过；(4) 、撰写课程设计报告。吋间安排如下：(1) 、2016年02月5日之前：完成所有要用到的结构体的定义。(2) 、2016 年 02 月 5

27、 002 月 6 日：完成建立合适的图模型以及信息的初始化。(3) 、2016年02月7日前：将初始化的所有的信息与建立的图模型完全连接起来，写调整函数将每一条路线的车的信息存放到所有的节点里去。(4) 、2016年2月8日2010年2月10日: 完成按时间最优的方法选择路线。(5) 、2016 年 2 月 10 日2016 年 2 月 12 0：完成文件写入的程序。(6) 、2016年2月12日之前：调试完毕，系统可以投入使用。5.1工作展望在今后的研究中，围绕着如下几个方面开展工作：(1) 、使得系统更加人性化，给用户带来使用的畅快感;(2) 、使用更加高级的算法使得系统工作更高效；(3)

28、 、学习界面优化，编写岀让用户伤心悦目的界面。6.附录程序完整源代码如下:#include<stdio.h># include<stdlib.h> #include<string.h> #define ok 1#define error 0#define false 0#define true 1#define max_vertex_num 20#define max_distance 99#define max_line_num 5最大顶点个数定义一个最大距离抽象为表示无穷大定义线路数#define o max_vertex_num+1typedef ch

29、ar elemtype;图顶点数据类型typedef struct station_infochar station_name20;int station_num;station_info;typedef structtablenode(表结点结构iint verj_num; 的顶点vj的序号jchar station_name20; struct tablenode *next;邻接点域，存放与vi相邻接抽象站点的名字指针域，将邻接表的所有表结点链在一起jtablenode;图的数据类型定义typedef structheadn ode头结点结构char station_name20;int

30、 station_num;/vi的邻接表的头指针struct tablenode *head;jheadnode;typedef struct mgraphstruct headnode linemax_line_num;线路数组 mgraph;typedef struct line_infoint line_num;float line_price;int start_time_hour;int start_time_minute;int end_time_hour;int end_time_minute;line_infb;line_info linemax_line_num=线路信息1,

31、2,6,30,22,30,2,1.5,7,0,23,0,3,2.5,6,30,22,30,4,2,7,0,23,0,5,1.5,6,30,22,30；int vrmax_vertex_nummax_vertex_num=/012345678910111213141516 1718190,1, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99 ,/01, 0,1, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99,99,/i 99

32、,1, 0,1, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99,99,/2 99, 99,1, 0,1, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99,99,/3 99, 99, 99, i, 0, 2, 99, 99, 99, 99, 99, 99, 99, 99, 99, 4, 99, 2, 99,99,/4 99, 99, 99, 99, 2, 0, i, 99, 99, 99, 99, 99, 99, 99, 4, 99, 99, 99, 2,99,/

33、5 99, 99, 99, 99, 99,1, 0, 2, 99, 99, 99, 99, 99, 2, 99, 99, 99, 99, 2,99,/6 99, 99, 99, 99, 99, 99, 2, 0, 2, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99,/74, 99, 99, 2, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 2, 0, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99 ,/8 99, 99, 99, 99, 99, 99, 99, 99, 99

34、, 0, 1,99, 99, 99, 99, 99, 99, 99, 99, 99 ,/9 99, 99, 99, 99, 99, 99, 99, 99, 99, 1, 0,0,1, 2, 99, 99, 99, 99, 99,99,/10 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 4,1, 0, 99, 99, 99, 99, 99, 99,99,/ll 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99,2, 99, 0, 99, 99, 99, 99, 99,99,/12 99, 99, 99, 99, 99, 99

35、, 2, 99, 99, 99, 99,99,/13 99, 99, 99, 99, 99, 4, 99, 99, 99, 99, 2, 99, 99, 99, 0, 3, 99, 99, 99, 99,/l 4 99, 99, 99, 99, 4, 99, 99, 99, 99, 99, 99, 99, 99, 99, 3, 0, 99, 99, 99, 99,/15 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 0,1, 99,99,/16 99, 99, 99, 99, 2, 99, 99, 99, 99,

36、 99, 99, 99, 99, 99, 99, 99,1, 0, 99,99,/17 99, 99, 99, 99, 99, 2, 2, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 0, 4,/18 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 4, 0,/19；弧权值二维数组int line_nummax_line_numlmax_vertex_numl=/0/i/2/3/40,1,2,3,4,5,6,7,8,00,0,0,0,0,0,0,0,0,0

37、,16,17,4,15,14,10,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9,10,11,12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,station|max_vertex_num=11,13,6,18,19,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 10,14,5,18,19,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, ； station_info 诂点信息数组”光谷广场“,0,”广埠屯”,1,”街道口 ”,2,”洪山广场“,3,“中南路”,4,“江汉路”,5,”循礼门”,6,“汉口火车站”,7, “常青花园”

38、,8,”新汉阳站”,9,”王家湾”,10, 宗关”,11,”王家墩”,12,”崇仁路”,13,”钟家村”,14,”武昌火车站”,15,”武汉火车站”,16, ”仁和路”,17,”大智路”,18,”汉口北大道”,19；int save_infomation(void);int print_line_info(mgraph *g); mgraph* creatmgraph(mgraph *g); void dijkstra_time(int start,int end);int locatevex(mgraph *g,int n);函数名称：save_infomation();函数功能：根据点集和

39、点关系集创建一个图； 函数参数：点集基址，点关系矩阵基址，定点数n;函数返回：图的基址；/t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /tint save_infomation(void)file *pl,*p2,*p3,*p4; int

40、 i,j； int *p_vr,*p_line_node; station_info *p_station; line_info *p_line_info;if(pl =fopen(,f:vr.txt,；,wbh)=null)exit(-l);if(p2=fopen(',f:line_node.txt,'wb,)=null)exit(-l);if(p3=fopen(,f:station.txt','wb,)=null) exit(-l);if(p4=fopen(,f:line_info.txt,uwb")=null) exit(-l);for(i 二

41、o;ivmax_vertex_num;i+) for(j=0;j<max_vertex_num;j+)p_vr=&vrij； fwrite(p_vr,sizeof(int), 1 ,p 1); for(i=0;i<max_line_num;i+) for(j=0;j<max_vertex_num;j+)p_line_node=&line_numij; fwrite(p_line_node,sizeof(int),l ,p2); for(i=o;i<max_vertex_num;i+)p_station=&stationi; fwrite(p_st

42、ation,sizeof(station_info),l ,p3); for(i=0;ivmax_line_num;i+)p_line_info=&linei; fwrite(p_line_info,sizeof(line_info), 1 ,p4);fclose(pl);fclose(p2);fclose(p3);fclose(p4);return ok;函数名称：print_line_info(mgraph *g)； 函数功能：屏幕打印线路信息； 函数参数：点集基址；函数返回：若成功则返回0k；/%、tint print_line_info(mgraph *g) int i,n;t

43、ablenode *p; n=max_line_num; printf(nnn);for(i=0;i<n;i+)printf(nn=)；printf("%d 号线:",linei.line_num);printf("t 票价:%l.lf 元nn'f,linei.line_price);printfc*首班车时间：%d： %dm,linei.start_time_hour,linei.start_time_minute);printf("t末班车时间:%d： %dnn",linei.end_time_hour,linei.end_t

44、ime_minute);p=g > linei.head->next;while(p)if(p->next)printf("%s->",p->station_name);elseprintf(,%s',p->station_name);p=p > next;primf(”n=*)；printf(unh);return ok;/ *. *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *

45、八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八函数名称：creatmgraph(mgraph* g,int *vr,int n)；函数功能：根据点集和点关系集创建一个图； 函数参数：点集基址，点关系矩阵基址，定点数m 函数返回：图的基址；/%、tmgraph* creatmgraph(mgraph *g)int i,j,n,m;tablenode *p,*rear;n=max_line_num;m=max_vertex_num;建立图模

46、型时，是按照线路建立，存储结构为邻接列表；每一条链表表示 一条线路；for(i=0;i<n;i+)real-g->linei.head;for(j=0;j<m;j+)if(line_numi|j<=m)p=(tablenode *)malloc(sizeof(tablenode); 创建一个新的结 点p->ver_nu m=line_numij; strcpy(p->station_name,stationline_numij.station_name); p->next=null;rear->next=p;插入链尾rear=p;return g

47、;b j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” *l* x* x* x* x* rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw

48、 rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw函数名称：dijkstra_time(int startjnt end)；函数功能：根据起点编号和终点编号在图中计算最短距离；函数参数：起点编号，终点编号；函数返回：最短距离值；函数说明：dijkstra算法说明如下：1）算法思想:设g=（v,e）是一个带权有向图，把图屮顶点集合v分成两组，第一 组为已求出最短路径的顶点集合（用s表示，初始i寸s中只有一个源点，以后每求得一条最短路径，就将加入 到集合s中，直到全部顶

49、点都加入到s中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用u表示），按最短路径长度的递增 次序依次把第二组的顶点加入s中。在加入的过程中，总保持从源点start到s中各顶点的最短路径长度不大于从源点start到u中 任何顶点的最短路径长度。此外，每个顶点对应一个距离，s中的顶点的距离就是从start到此顶点的最短路径长度，u中的顶点的距离， 是从start到此顶点只包括s屮的顶点为屮间顶点的当前最短路径长度。2）算法步骤：a. 初始吋，s只包含源点，即s= start, start的距离为0。u包含除v外的其 他顶点，即:u=其余顶点,若start与u中顶点u有边，则v u ,s

50、tart正常有权值，若u不是start的出边邻接点，则vu,start权值为8。b. 从u中选取一个距离start最小的顶点k,把k加入s中（该选定的距离就 是start到k的最短路径长度）。c. 以k为新考虑的中间点，修改u中各顶点的距离；若从源点start到顶点u 的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。d. 重复步骤b和c直到所有顶点都包含在s中。判断点是否进入s集合的数距离数组前驱点编号数组void dijkstra_time(int start,int end)int s_flagmax_vertex_num;

51、 组int distancemax_vertex_num;int prior.ver| max_vertex.num ;intout 1| m ax_vertex_num |= 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;输出线路时的数组int out2|max_vertex_num=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;输出线路时的数组int i j,k,f,min_distance=max_distance,m,change;int* flag;动态分配一个数组，记录一条弧是否已经扫描for(i=0;i<m

52、ax_vertex_num;i+)s_flagi=o;distancei=vrstart i;的距离if(distancei=max_distance) prior_veri=-l;elseprior_veri=start;distancestart=o;s_flagstart=l;for(i=l ;i<max_vertex_num;i+) k=start;min_distance=max_distance;始化抽象无穷远为最短距离刚开始都没有进入s集合距离数组中储存的是从起点到改点起点到自身没有距离起点已经入s集合每一次进入循环均要初for(j=o;j<max_vertex_num;j+)if(!s_flagj)&&(distancej<min_distance)k=j；