首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构全国交通咨询模拟系统实习报告


数 据结构课程设计报告
全国交通咨询模拟管理系统
学院:计算机学院 姓名: 班级: 学号: 指导老师 日期:

1. 需求分析
出于不同目的的旅客对交通工具有不同的要求。例如,因公出差的旅客希望在旅途中 的时间尽可能短,出门旅游的游客则期望旅费尽可能省,而老年旅客则要求中转次数最少。 编制一个全国城市间的交通咨询程序,为旅客提供两种或三种最优决策的交通咨询。 要求: (1)提供对城市信息进行编辑(如添加或删除)的功能。 (2)城市之间有两种交通工具:火车和飞机。提供对列车时刻表和飞机航班进行编辑 (增设或删除)的功能。 (3)提供两种最优决策:最快到达或最省钱到达。全程只考虑一种交通工具。 (4)旅途中耗费的总时间应该包括中转站的等候时间。 (5)咨询以用户和计算机的对话方式进行。

2.设计 2.1 设计思想

(1)数据结构设计 该系统存储结构运用到数组和结构体。该结构分别存储火车列次,航班,出发点与目的 地以及所需要走的路程和所用费用。 主要用到的数据结构有图中的交通网的各种信息的邻接 矩阵的存储。最短路径使用迪杰斯特拉算法编程求算得出最近或最便宜路径。 火车列次,航班的存储结构: structTvaval{ char id[20]; char start[20]; char end[20]; float time; float price;
};

//火车或飞机的存储结构// //火车或飞机航班的代码// //出发地// //目的地// //路途时间// //价钱//

(2)算法设计 在求最短路径使用到的算法是迪杰斯特拉算法,算法步骤如下: 1、起始点(V0)与其相邻点的权值(即当前最短路径) 。 2、求出当前最短路径中的最小值即是该起始点(V0)与另一点(Vi)的最短路径。 3、V0 到 Vi 的距离加上 Vi 到 Vj 的距离小于 V0 到 Vj 则将 V0 到 Vi 的距离加上 Vi 到 Vj 的距离记为 V0 到 Vj 当前最短路径,循环第二、三步。如此得到 V0 到各点 的最短路径,进而可以得到想要的一条。 系统主干功能的实现是用一个 swich 语句来实现多功能的选取以及程序的退出; 主要有: 1:修改地图, 2:编辑火车时刻表,3:编辑飞机航班表,4:选择出游路线,5:退出;继而通过 选中其中的数字来实现自己的目的;然后再引用程序再用一个 switch case 语句来实现 1 2 3 选项中的添加删除以及退出功能,然后在 4 中再用 if 语句来实现自己的需求考虑。可以随 时退出程序。最后再经调用函数再来输出结果。 系统设计中包括的函数模块:

1. 查找模块 int search(char citytable[][20], char* city, int number) //在城市数中查找某个城市 2.寻找最优路线模块 void the_best_path(struct Tvaval* timetable, char* start, char* end, char city[][20], int times, int number, int choice) //寻找最优路线 先得到存储最少花费或最短时间信息的邻接矩阵,接着得到起始点与相邻的点的权值 (即当前最短路径)并记录点,再求出当前最短路径中的最小值即是该起始点(V0)与另一点 (Vi)的最短路径, V0 到 Vi 的距离加上 Vi 到 Vj 的距离小于 V0 到 Vj 则将 V0 到 Vi 的距离加 上 Vi 到 Vj 的距离记为 V0 到 Vj 当前最短路径并且记录前一个点。然后重复(4) , (5)步 得到所有点最短路径。最后以终点开始逐步向前赋值得到所需路径并输出该路径的权值。 3.主函数模块 void main()//主函数 本设计采用的是在界面上通过输入相应的字符表示的要求来实现对于不同目的不同函 数的调用, 主要用到的数据结构有图中的交通网的各种信息的邻接矩阵的存储。 通过顾客输 入不同的字符来实现不同的功能, 主界面上注释着这个程序的系统名称, 组员以及指导老师 等基本学生信息,用星号来加以修饰;然后就是用一个 swich 语句来实现多功能的选取以及 程序的退出;主要有一:1:修改地图 2:编辑火车时刻表 t3:编辑飞机航班表 t4:选择出 游路线 t5:退出;继而通过选中其中的数字来实现自己的目的;然后再引用程序再用一个 switch case 语句来实现 1 2 3 选项中的添加删除以及退出功能,然后在 4 中再用 if 语句来实 现自己的需求考虑。可以随时退出程序。

2.2

设计表示

(1)函数调用关系图
主函数

修改地图

编辑火车时刻表

编辑飞机航班表

选择出游路线

退出

增 加

删 除

退 出

增 加

删 除

退 出

退 出

增 加

删 除

火车

飞机

最 短 时 间

最 少 花 费

最 少 花 费

最 短 时 间

2.3

详细设计

(1)查找模块 int search(char citytable[][20], char* city, int number) //在城市数中查找某 个城市// { int i; for (i = 0; i<number; i++) { if (strcmp(citytable[i], city) == 0) return i; } return -1; } (2)最优路径算法模块 void the_best_path(struct Tvaval* timetable, char* start, char* end, char city[][20], int times, int number, int choice) {//最优路线// //start 表示出发地,end 表示目的地,times 表示表示航班或车次的总次数,number 表示城市的总数// //choice=0 表示求最短时间路线,choice=1 表示求最少花费路线// int i, j, k, st, et; float min, t; char pcity[10][20]; float edge[15][15], dist[15];//15*15 的数组储存的是权值// int path[15], s[15]; for (i = 0; i<number; i++) for (j = 0; j<number; j++) { edge[i][j] = max; } for (i = 0; i<times; i++)//dijkstra 算法// { j = search(city, timetable[i].start, number);//寻找出发地// k = search(city, timetable[i].end, number);//寻找目的地// if (choice == 0) {//最短时间// t = timetable[i].time; if (t<edge[j][k]) edge[j][k] = t; } else {//最少花费// t = timetable[i].price; if (t<edge[j][k]) edge[j][k] = t;

} } st = search(city, start, number); et = search(city, end, number); for (i = 0; i<number; i++) { dist[i] = edge[st][i]; s[i] = 0; if (i != st&&dist[i]<max) path[i] = st; else path[i] = -1; } s[st] = 1; dist[st] = 0; for (i = 0; i<number - 1; i++) { min = max; k = st; for (j = 0; j<number; j++) if (!s[j] && dist[j]<min) { k = j; min = dist[j]; } s[k] = 1; for (j = 0; j<number; j++) if (!s[j] && edge[k][j]<max&&dist[k] + edge[k][j]<dist[j]) { dist[j] = dist[k] + edge[k][j]; path[j] = k; } } k = et; i = 0; if (path[k] == -1) { printf("tt 对不起,不存在从 %s 到 %s 的路线nn", start, end); return; } while (path[k] != -1) { strcpy(pcity[i++], city[k]); k = path[k]; } strcpy(pcity[i++], city[st]); printf("tt 最佳路线为:ntt"); for (j = i - 1; j >= 0; j--)

123

 


 

  【Top

最新搜索

 

数据结构全国交通咨询模拟系统实习报告 - 用C语言写的全国交通咨询模拟系统,实现了基于费用和时间消耗的最佳路径的选择功能,还有路线添加,删除等基本功能


 

热点推荐