《数据结构课程设计_____全国交通咨询系统》由会员分享，可在线阅读，更多相关《数据结构课程设计_____全国交通咨询系统（16页珍藏版）》请在金锄头文库上搜索。
1、太原工业学院计算机工程系计算机工程系数据结构课程设计数据结构课程设计设计题目：设计题目：全国交通网络咨询系统全国交通网络咨询系统1班班级：级：计算机科学与技术学学号：号：132054103姓姓名：名：陈敏指导教师：指导教师：刘海静年月日目录目录一、一、课程设计题目课程设计题目1 1二、二、需求分析需求分析1 1三、三、测试数据测试数据2 2四、四、概要设计概要设计2 2五、五、调用关系图调用关系图3 3六、六、程序代码程序代码3 3七、七、测试结果测试结果1 14 4八、八、心得体会及总结心得体会及总结1 14 41数据结构课程设计一、课程设计题目 全国交通网络咨询系统二、需求分析1、实现功能
2、对城市信息(城市名、城市间的里程)进行编辑：具备添加、修改、删除功能；对城市间的交通工具：火车。对列车时刻表进行编辑：里程、和列车班次的添加、修改、删除；提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具，可以不考虑回程；咨询以用户和计算机对话方式进行，要注意人机交互的屏幕界面。由用户选择最优决策原则和交通工具，输入起始站、终点站、出发时间，输出信息：最快需要多长时间才能到达及旅费， 或者最少需要多少旅费才能到达及时间， 并详细说明依次于何时何地乘坐哪一趟列车何时到达何地。2、设计思路（1) 数据存储。城市信息(城市名、代码)、交通信息(城市间的里程、各航班和列车时刻)存储于磁盘文
3、件磁盘文件。在实验中本想用文本储存数据，但操作不熟悉，而是改用图的邻接矩阵改用图的邻接矩阵储存原始信息，而后用数组进行添加删改(2) 数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构图结构，可看作为无向图，图的顶点是城市，边是城市之间所耗费的时间（要包括中转站的时间）或旅费。(3) 数据的存储结构。 采用邻接表和邻接矩阵都可作为数据的存储结构， 这里建议采用邻接邻接矩阵矩阵作为数据的存储结构。(4) 用不同的功能模块对城市信息和交通信息进行编辑编辑。添加添加、修改修改、删除删除功能可用菜单方式或命令提示方式。 只要能方便的对城市信息和交通信息进行管理即可， 但要注意人
4、机界面，具体实现由学生自行设计， 也可参考有关程序(届时在网上提供)。 这些工作有不小的工作量。(5) 最优决策功能模块 读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放城市名及对方城市到达该元素所代表城市的所有信息； 表头数组中的元素所对应的单链表存放与该元素所代表的城市有交通联系的城市(代码、里程、列车车次)。 根据具体最优决策的要求， 用 floydfloyd 算法算法求出出发城市到其它各城市的最优值(最短时间2或最小的费用)，搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。其目的城市所代表的元素中就保存了所需的最优决策结果。 其相应的初始值可为， 并在表
5、头数组对应的城市元素中保存响应的信息。 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。三、测试数据：7046513491579138523688125112553北京徐州西安成都郑州广州上海四、概要设计 本程序运用了关于图这种数据结构。它的抽象数据类型定义如下：typedef struct unDiGraphint numVerts; /结点costAdj cost; /邻接矩阵 unDiGraph,*UNG; 基本操作：基本操作：unDiGraph* CreateCostG()操作结果：操作结果：构造带权(费用)图。unDiGraph*
6、CreateTimeG()操作结果：操作结果：构造带权（时间）图。构造飞机带权(费用)图。PathMat *Floyed(unDiGraph *D) 操作结果：操作结果：Floyed 函数 求任意两点的最短路径。3五、调用关系图六、程序代码 #include #include #include #include #include #include #define INF 10000/定义一个最大数定为无穷值 #define MAX 7 static int cnumber=7; static int k=0; static int v=0,z=0;/定义静态变量 typedef struct
7、zhu/定义结构体 zhu int ccost;/定义结构变量 int ctime; zhu; zhu m20,x20,n20;/定义数组为 struct zhu 类型数组，且三个数组分别 储存添加后的数据，且表示花费 m，起点 n，和终点 x typedef int costAdjMAX+1MAX+1;/定义图的邻接矩阵，并从 1 开始 int PathMAX+1MAX+1;/路程矩阵，表示经过存放的点 k typedef struct unDiGraph int numV;/结点 costAdj cost;/邻接矩阵 unDiGraph,*UNG;unDiGraph （图）CreateCo
8、stG （构造带权费用）CreateTimeG（构造带权时间）Floyed 函数 求任意两点的最短路径4typedef struct cedit char a10; cedit; cedit add10; costAdj B,L; /功能一 输出相应的城市信息 int pr(int i,int j)/pr 函数表输出功能 int h=0; if (j=0) h=i; else if (j=1) cinaddi.a; switch (h) case(0) : coutcostij=INF;/初始化矩阵 cost 每一项，使其无穷大 G-numV=cnumber; G-cost16=G-cost6
9、1=90; G-cost12=G-cost21=84; G-cost23=G-cost32=51; G-cost25=G-cost52=67; G-cost34=G-cost43=53; G-cost45=G-cost54=40; G-cost47=G-cost74=88; G-cost56=G-cost65=90; G-cost57=G-cost75=67; G-cost67=G-cost76=60; if (o) while(h=1)/h 初始值为 1 v=v+1;/V 为全局静态变量， 初始值为 0 ,v 表示编辑的火车花费的组数， 三个编辑数组中的存放代码6pri(); couta;
10、coutb; coutmv.ccost; nv.ccost=a; xv.ccost=b; couth; switch(h) case 1: h=1; break; case 0: h=0; break; default: coutcostnv.ccostxv.ccost=mv.ccost; v=f; return(G); /构造 TimeG 图，表示其花费时间 unDiGraph *CreateTimeG(int o)/火车的时间的存贮和编辑功能7 unDiGraph *G; int i,j;/循环变量 int a=0,b=0,f,h=1;/a,b 表增加城市的代码 if(!(G=(unDiG
11、raph *)malloc(sizeof(unDiGraph)/为 G 分配存储空 间。 return(NULL); for(i=1;icostij=INF;/初始化使 G-costij为无穷。 G-numV=cnumber; G-cost16=G-cost61=9; G-cost12=G-cost21=8; G-cost23=G-cost32=5; G-cost25=G-cost52=3; G-cost34=G-cost43=5; G-cost45=G-cost54=4; G-cost47=G-cost75=6; G-cost56=G-cost65=9; G-cost57=G-cost75=
12、6; G-cost67=G-cost76=6; if (o) while(h=1) z=z+1;/全局静态变量，初始值为 0.即 1=0+1 pri(); couta; coutb; coutmz.ctime; nz.ctime=a; xz.ctime=b; couth; switch(h) case 1: h=1; break; case 0: h=0; break; default: coutcostnz.ctimexz.ctime=mz.ctime; z=f; return(G); /Floyed 函数 求任意两点的最短路径： void Floyed(unDiGraph *D,unDiG
13、raph *M)/图 D M int i,j,k,n;/i,j 为循环变量,k 表中间节点的变量 costAdj A,C;/A C 为图，临时表示两种最佳路线组成的矩阵，定义 costAdj B L n=cnumber; for(i=1;icostij;/初始化矩阵 A,C。 Cij=M-costij; Pathij=-1;/初始化权矩阵 p for(k=1;kBcity; cinEcity;/输入起始城市和终点城市的代码。10if (!(08000|LBcityEcity8000) coutBcity; cinEcity;/输入起始城市和终点城市的代码。 if (!(08000|BBcity
14、Ecity8000) coutj; for (i=1;ih; if (h=1) money(); else time(); void edit_line()/增加编辑火车的费用12 CreateCostG(1); void edit_hour()/增加编辑火车的时间 CreateTimeG(1); void administrator()/管理员功能 int h=1; while (h) couth; switch(h) case 1 :add_city(); break; case 2:edit_line(); break; case 3:edit_hour(); break; case 0: h=0; break; d
