数据结构课程设计_____全国交通咨询系统.docVIP

太原工业学院 计算机工程系 数据结构课程设计 设计题目：全国交通网络咨询系统 1 班 级： 计算机科学与技术 学 号： 132054103 姓 名： 陈敏 指导教师： 刘海静 年 月 日 目录 课程设计题目…………………………………………………1 需求分析………………………………………………………1 测试数据………………………………………………………2 概要设计………………………………………………………2 调用关系图……………………………………………………3 程序代码………………………………………………………3 测试结果………………………………………………………14 心得体会及总结………………………………………………14 PAGE \* MERGEFORMAT PAGE \* MERGEFORMAT 3 数据结构课程设计 一、课程设计题目 全国交通网络咨询系统 需求分析 1、实现功能 对城市信息(城市名、城市间的里程)进行编辑：具备添加、修改、删除功能； 对城市间的交通工具：火车。对列车时刻表进行编辑：里程、和列车班次的添加、修改、删除； 提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具，可以不考虑回程； 咨询以用户和计算机对话方式进行，要注意人机交互的屏幕界面。由用户选择最优决策原则和交通工具，输入起始站、终点站、出发时间，输出信息：最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间，并详细说明依次于何时何地乘坐哪一趟列车何时到达何地。 设计思路 （1) 数据存储。城市信息(城市名、代码)、交通信息(城市间的里程、各航班和列车时刻)存储于磁盘文件。在实验中本想用文本储存数据，但操作不熟悉，而是改用图的邻接矩阵储存原始信息，而后用数组进行添加删改 (2) 数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为无向图，图的顶点是城市，边是城市之间所耗费的时间（要包括中转站的时间）或旅费。 (3) 数据的存储结构。采用邻接表和邻接矩阵都可作为数据的存储结构，这里建议采用邻接矩阵作为数据的存储结构。 (4) 用不同的功能模块对城市信息和交通信息进行编辑。添加、修改、删除功能可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可，但要注意人机界面，具体实现由学生自行设计，也可参考有关程序(届时在网上提供)。这些工作有不小的工作量。 (5) 最优决策功能模块 ① 读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放城市名及对方城市到达该元素所代表城市的所有信息；表头数组中的元素所对应的单链表存放与该元素所代表的城市有交通联系的城市(代码、里程、列车车次)。 ② 根据具体最优决策的要求，用floyd算法求出出发城市到其它各城市的最优值(最短时间或最小的费用)，有哪些信誉好的足球投注网站过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。其目的城市所代表的元素中就保存了所需的最优决策结果。其相应的初始值可为∞，并在表头数组对应的城市元素中保存响应的信息。 ③ 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。 三、测试数据： 704 704 651 349 1579 1385 2368 812 511 2553 北京 徐州 西安 成都 郑州 广州 上海 四、概要设计 本程序运用了关于图这种数据结构。 它的抽象数据类型定义如下： typedef struct unDiGraph { int numVerts; //结点 costAdj cost; //邻接矩阵 }unDiGraph,*UNG; 基本操作： unDiGraph* CreateCostG() 操作结果：构造带权(费用)图。 unDiGraph* CreateTimeG() 操作结果：构造带权（时间）图。 构造飞机带权(费用)图。 PathMat *Floyed(unDiGraph *D) 操作结果：Floyed函数 求任意两点的最短路径。 五、调用关系图 unDiGraph unDiGraph（图） Floyed函数 求任意两点的最短路径 Floyed函数 求任意两点的最短路径 CreateTimeG（ CreateTimeG（构造带权时间） CreateCostG（构造带权 费用） 程序代码 #include windows.h #include stdio.h #include crtdbg.h #