数据结构全国交通咨询模拟系统实习报告

数据结构课程设计报告全国交通咨询模拟管理系统学院：计算机学院姓名： 班级：学号：指导老师日期:1. 需求分析 出于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。要求：（1）提供对城市信息进行编辑（如添加或删除）的功能。（2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。（3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。（4）旅途中耗费的总时间应该包括中转站的等候时间。（5）咨询以用户和计算机的对话方式进行。2设计2.1 设计思想（1）数据结构设计该系统存储结构运用到数组和结构体。该结构分别存储火车列次，航班，出发点与目的地以及所需要走的路程和所用费用。主要用到的数据结构有图中的交通网的各种信息的邻接矩阵的存储。最短路径使用迪杰斯特拉算法编程求算得出最近或最便宜路径。火车列次，航班的存储结构：struct Tvaval /火车或飞机的存储结构/char id20; /火车或飞机航班的代码/char start20; /出发地/char end20; /目的地/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 citytable20, char* city, int number) /在城市数中查找某个城市2. 寻找最优路线模块void the_best_path(struct Tvaval* timetable, char* start, char* end, char city20, 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 citytable20, char* city, int number) /在城市数中查找某个城市/int i;for (i = 0; inumber; i+)if (strcmp(citytablei, city) = 0)return i;return -1;（2）最优路径算法模块void the_best_path(struct Tvaval* timetable, char* start, char* end, char city20, int times, int number, int choice)/最优路线/start表示出发地，end表示目的地，times表示表示航班或车次的总次数，number表示城市的总数/choice=0表示求最短时间路线，choice=1表示求最少花费路线/int i, j, k, st, et;float min, t;char pcity1020;float edge1515, dist15;/15*15的数组储存的是权值/int path15, s15;for (i = 0; inumber; i+)for (j = 0; jnumber; j+)edgeij = max;for (i = 0; itimes; i+)/dijkstra算法/j = search(city, timetablei.start, number);/寻找出发地/k = search(city, timetablei.end, number);/寻找目的地/if (choice = 0)/最短时间/t = timetablei.time;if (tedgejk)edgejk = t;else/最少花费/t = timetablei.price;if (tedgejk)edgejk = t;st = search(city, start, number);et = search(city, end, number);for (i = 0; inumber; i+)disti = edgesti;si = 0;if (i != st&distimax) pathi = st;else pathi = -1;sst = 1; distst = 0;for (i = 0; inumber - 1; i+)min = max;k = st;for (j = 0; jnumber; j+)if (!sj & distjmin)k = j;min = distj;sk = 1;for (j = 0; jnumber; j+)if (!sj & edgekjmax&distk + edgekj= 0; j-)printf(%s , pcityj);printf(n);if (choice = 0)printf(tt所需总时间为:%5.1f小时n, distet);elseprintf(tt所需的总费用为:%7.2f元n, distet);printf(n);（3）主函数模块void main()int i, j, k, m, n, number = 5, train_number = 6, fly_number = 6;printf(tt*n);printf(tt* 欢迎使用全国交通查询系统 *n);printf(tt*n);char city1520 = 北京, 昆明, 曲靖, 重庆, 武汉 ;/现有城市，最多15个城市/struct Tvaval train20 = T1, 北京, 武汉, 10, 90 , T2, 北京, 昆明, 8, 70 , T3, 昆明, 曲靖, 3, 30 , T4, 昆明, 重庆, 25, 200 , T5, 武汉, 重庆, 14, 120 , T6, 昆明, 武汉, 8, 80 ;struct Tvaval flight20 = F1, 北京, 武汉, 3, 500 , F2, 北京, 昆明, 2.5, 400 , F3, 昆明, 曲靖, 1, 200 , F4, 昆明, 重庆, 6, 1400 , F5, 武汉, 重庆, 5, 700 , F6, 昆明, 武汉, 3, 450 ;printf(tt现有城市); /输出现有地图上的城市,便于后面的输入和修改/for (j = 0; jnumber; j+)printf(%d.%st, j + 1, cityj);printf(nn);loop1:printf(t请选择所需功能：ntt1:修改地图 ntt2:编辑火车时刻表 ntt3:编辑飞机航班表 ntt4:选择出游路线 ntt5:退出);printf(nt请选择:);scanf(%d, &i);while (i != 1 & i != 2 & i != 3 & i != 4 & i != 5)printf(tt输入有误，请重新输入:);scanf(%d, &i); /避免按错而导致程序错误/switch (i) /switch语句/case 1: /第一种情况，修改地图*/ loop2: printf(t现有城市：ntt); for (j = 0; jnumber | k1) printf(tt输入有误，请重新输入:); scanf(%d, &k); /避免按错而导致程序错误/ if (k = number) number-; else for (m = k - 1; mnumber - 1; m+) strcpy(citym, citym + 1); number-; /城市总数减少一个/ /else goto loop2; /查看修改后的地图，便于判断或是再次修改/ /if else goto loop1; /回到主菜单/ case 1 ，修改地图/case 2: /修改火车时间表/ loop3: printf(ntt现有火车时刻表：n); printf(tt 车次 起点站 终点站 路途时间(h) 票价(元)n); /输出各火车时刻表/ for (j = 0; jtrain_number; j+) printf(tt%d: %st%st%st%5.1ftt%5.2ftn, j + 1, trainj.id, trainj.start, trainj.end, trainj.time, trainj.price); printf(nn); printf(t功能：1.添加t2.删除t3.返回n); printf(t请选择：); scanf(%d, &j); while (j != 1 & j != 2 & j != 3) printf(tt输入有误，请重新输入:); scanf(%d, &j); /避免按错而导致程序错误/ printf(n); if (j = 1) printf(现有城市：n); for (k = 0; ktrain_number | k1) printf(tt输入有误，请重新输入:); scanf(%d, &k); /避免按错而导致程序错误/ if (k = train_number) train_number-; /火车车次减一/ else for (m = k - 1; mtrain_number - 1; m+) trainm = trainm + 1; train_number-; goto loop3; /回到loop3，查看修改后的列车信息/ else goto loop1; /回到主菜单/case 2 ,修改火车时刻表/case 3:/修改飞机航班表，和列车相似/ loop4: printf(tt现有飞机航班表：n); printf(tt 班次t起点t终点t路途时间t票价n); for (j = 0; jfly_number; j+)printf(tt%d: %st%st%st%5.1ftt%5.2ftn, j + 1, flightj.id, flightj.start, flightj.end, flightj.time, flightj.price); printf(nn); printf(tt功能：1.添加t2.删除t3.返回n); printf(tt请选择：); scanf(%d, &j); while (j != 1 & j != 2 & j != 3) printf(tt输入有误，请重新输入:); scanf(%d, &j); /避免按错而导致程序错误/ printf(n); if (j = 1) printf(现有城市：n); for (k = 0; kfly_number | k1) printf(tt输入有误，请重新输入:); scanf(%d, &k); /避免按错而导致程序错误/ if (k = fly_number) fly_number-; else for (m = k - 1; mfly_number - 1; m+) flightm = flightm + 1; fly_number-; /else goto loop4; /else if else goto loop1;/case 3,修改飞机航班表/case 4: printf(tt请选择交通工具(1.火车 2.飞机):); scanf(%d, &j); while (j != 1 & j != 2) printf(tt输入有误，请重新输入:); scanf(%d, &j); /避免按错而导致程序错误/ printf(tt请选择决策方案(1.最短时间 2.最少花费):); scanf(%d, &k); while (k != 1 & k != 2) printf(tt输入有误，请重新输入:); scanf(%d, &k); /避免按错而导致程序错误/ printf(t现有城市：n); for (i = 0; inumber | mnumber | n1) /number为现有城市数目/ printf(tt输入有误，请重新输入:); scanf(%d, &n); /避免按错而导致程序错误/ printf(n); if (j = 1 & k = 1) the_best_path(train, citym - 1, cityn - 1, city, 6, 5, 0); if (j = 1 & k = 2) the_best_path(train, citym - 1, cityn - 1, city, 6, 5, 1); if (j = 2 & k = 1) the_best_path(flight, citym - 1, cityn - 1, city, 6, 5, 0); if (j = 2 & k = 2) the_best_path(flight, citym - 1, cityn - 1, city, 6, 5, 1); goto loop1;/回到主菜单/case 5: return;/退出系统/switch 语句/void main()/3调试分析在调试的过程中，经常会出现输入错误，然后程序发生错误。所以在后来的改善中，在需要输入的地方加入了错误判断代码，以便防止输入错误带来的程序错误。在设计最优路径的代码时，总会出现好多错误，说明了自己对课本还不熟悉，对图的知识还要多写多练。这次使用了结构主干设计的方法，由列出主干再到细节分析使编程工作更有步骤，编程思路清晰，很有效率，以后要多用这种方法。4 用户手册（1）用户运行程序后，从主界面进入选择；（2） 选择1，用户可以修改地图，包括查看已有城市，增加和删除城市及返回；（3）选择2，用户可以编辑火车时刻表，包括查看以有火车线路，增加和删除火车线路及回；（4）选择3，用户可以编辑飞机航班表，包括查看以有飞机航班，增加和删除飞机航班及返回；（5）选择4，用户可以根据交通工具和决策方案选择出游路线；（6）退出运用。5测试数据及测试结果（1）主界面（2）修改地图中的增加城市和删除城市（3）火车时刻表中的编辑与删除 添加新的火车班次删除火车车次（3） 飞机时刻表中的编辑与删除添加航班和删除航班（4） 最优路线的选取乘坐火车并且最短时间的最优路线 乘坐飞机并且最短时间的最优路线测试结果：程序主要功能已经实现，细节方面仍要处理。