交通咨询系统设计报告.doc

重庆科技学院数据结构课程设计报告 学 院:_电气与信息工程学院_ 专业班级: 计科2 学生姓名: 学 号: 设计地点（单位）_ _ 计算机基础自主学习中心 _ _ _设计题目:_ 交通咨询系统设计_ _ _ _ 完成日期：2012年 7 月 6 日 指导教师评语: _ _ _ _ 成绩（五级记分制）:_ _ 指导教师（签字）:_ _ 重庆科技学院课程设计任务书设计题目：交通咨询系统的设计学生姓名课程名称数据结构课程设计专业班级计地 点计算机基础自主学习中心起止时间2012.6.25-2012.7.6设计内容及要求人们在出差、旅游出行时，往往关心节省交通费用或节省所需要的时间等问题。可以用一个图结构来表示交通网络，图中顶点表示城市，边表示城市之间的交通情况，其权值可代表里程、交通费用或时间。设计一个交通咨询系统，能让旅客咨询从任一个城市到另一个城市之间的最短路径（里程）、最少交通费用或最少时间等问题。该设计的内容主要分两部分：一是建立交通网络图的存储结构；二是实现求两个城市顶点之间的最短路径算法。要求表示城市之间的交通关系的边的信息中包括里程、费用、时间三个值。程序可实现求任两个城市之间的最短里程、最少时间或最少费用的路线。建立图的存储结构时要求从文本文件中读入顶点和边的信息。设计参数 测试数据要求：交通图中顶点数不少于16个，边数不少于20，每条边有三个权值（里程、交通费用、时间）。进度要求2012.6.25 完成任务的讲解、并接受课程设计任务，选定课程设计的题目2012.6.26 了解任务的算法、并画出算法的程序流程图，对任务的关键技术进行验证、并确定解决办法2012.6.27-2012.6.29 程序设计及编码，上机调试2012.7.02 对程序进行调试，设计测试用例进行测试2012.7.03 整理课程设计的过程、并进行总结，完善程序功能2012.7.04 编写课程设计报告初稿2012.7.05 完善课程设计报告、并准备答辨2012.7.06 提交课程设计报告和程序，进行答辨参考资料1严蔚敏 吴伟民， 数据结构，清华大学出版社，2007.32程杰 ，大话数据结构，清华大学出版社，2011.63（美）Stephen Prata, C Primer Plus中文版（第五版），人民邮电出版社，2005.2其它说明1.本表应在每次实施前一周由负责教师填写二份，学院审批后交学院教务办备案，一份由负责教师留用。2.若填写内容较多可另纸附后。3.一题多名学生共用的，在设计内容、参数、要求等方面应有所区别。系主任：雷亮 指导教师：黄永文/王双明/熊茜/彭军/王成敏 2012年 6月 20日摘要在交通网络非常发达，人们在出差、旅游出行时，往往关心节省交通费用或节省所需要的时间等问题。对于这样一个人们关心的问题，可以用一个图结构来表示交通网络，利用计算机建立一个交通咨询系统。图中顶点表示城市，边表示城市之间的交通情况，其权值可代表里程、交通费用或时间。比如任意一个城市到其他城市的最短路径，任意两个城市之间的最短路径问题。本次设计的交通咨询系统主要是运用C语言的数据结构来完成交通图的存储、图中顶点的单源最短路径和任意一对顶点间的最短路径问题。关键词：数字结构C语言交通咨询最短路径目录1 设计内容和要求11.1 问题描述11.2需求分析12 课程需求分析22.1 算法思路22.2 数据结构体22.3 基本操作32.4 算法应用32.5 程序设计流程图43 功能模块详细设计53.1 测试数据53.2 程序调试54 课程总结与体会195参考文献206 致谢211 设计内容和要求1.1 问题描述：设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方案：（1）时间最短（2）费用最小（3）里程最少。1.2需求分析：该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。此程序规定：（1） 在程序中输入城市名称时，需输入20个字符以内的字符串；输入费用时需输入一个实型数据；输入时间时需输入一个整型数据；在选择功能时，应输入与所选功能对应的一个整型数据。 （2） 程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或两城市间需要走过的最短路程，并详细说明如何坐车才能最省。（3） 程序的功能包括：提供对城市信息的编辑，对两城市间时间、花费、还有路程的编辑，提供三种最优决策：最快到达、最省钱到达、最少路程到达。 2 课程需求分析2.1 算法思路(1) 数据存储。城市信息、交通信息(城市间的里程、旅费和时间)存储于磁盘文件。建议把城市信息、交通信息还有城市和交通信息数目分开存于三个文件中，用fread和fwrite函数操作。 (2) 数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间所耗费的时间、旅费、里程。 (3) 数据的存储结构。采用邻接矩阵作为数据的存储结构，提高空间的存储效率。(4) 用不同的功能模块对城市信息和交通信息进行编辑，可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可。 (6) 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。2.2 数据结构体typedef struct lu /* 交通信息数据类型 */ int distance; /*城市间里程*/ int cost; /*城市间旅费*/int time; /*城市间时间*/lu,lujinmaxmax;typedef struct city /*城市数据类型*/char name20;/*城市名称*/citysmax;typedef struct /*网络图的数据类型*/ citys clist; /*城市信息*/lujin arcs; /*边的信息*/int c_n,l_n; /*边和顶点数目*/Graph;typedef struct /*最短路径*/char adjvex;int mincost;/*最少旅费*/int mindistance;/*最短里程*/int mintime;/*最少时间*/closedge;2.3 基本操作void zairu(Graph *G);/*导入文件中的信息，能否是程序运行*/void Administer(Graph G);/*管理员操作界面，由主函数调用*/void show(Graph G);/*显示系统中的全部城市信息和交通信息*/int insertcity(Graph *G); /*增加城市信息*/int insertlu(Graph *G); /*增加交通信息*/int Located(Graph *G, char *p);/* 返回邻接矩阵的位置下标，系统中的关键*/void baocun(Graph G);/*将城市信息、交通信息保存在文件中*/int serchlu(Graph *G);/*搜索交通信息*/void mindistance(Graph *G, int v0, int v1);/*最少里程计算，迪杰斯特拉算法*/void mincost(Graph *G, int v0, int v1);/*最少旅费计算，迪杰斯特拉算法*/void mintime(Graph *G, int v0, int v1);/*最少时间计算，迪杰斯特拉算法*/2.4 算法应用在判断源点到其余各点的最短路径时运用迪杰斯特拉算法：一般情况下，假设S为以求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为x）或者是弧(v,k)，或者是中奖只经过S中的顶点而最后到达顶点x的路径。这可用反证法来证明，假设此路径上有一个顶点不在S中，则说明存在一条终点不在S而长度比此路径短的路径。但是，这是不可能的。因为我们是按照路径长度递增的次序来产生各最短路径的，故长度比此路径段的所有路径均已产生，它们的终点必定在S中，即假设不成立。因此，在一般情况下，下一条长度次短的最短路径的长度必是其中，Di或者是弧上的权值，或者是Dk和弧上的权值之和。（1）假设用带权的邻接矩阵arcs来表示带权有向图，arcsij表示弧上的权值。若存在，则置arcsij为(在计算机上可用允许的最大值代替)。S为已找到从v出发的最短路径的终点的集合，他的初始状态为空集。那么，从v出发到图上其余个顶点(终点)vi可能达到的最短路径长度的初值为： （2）选择，使得就是当前求得的一条从v出发的最短路径的终点。令(3)修改从v出发到集合V-S上任一顶点可达的最短路径长度。如果则修改为(4)重复操作(2)、(3)共n-1次。由此求得从v到图上其余各点的最短路径是依路径长度递增的序列。2.5 程序设计流程图：交通咨询系统管理员用户添加城市查询最少花费路线查询最短时间路线查询最短里程路线退出添加交通路线返回上一级菜单返回上一级菜单显示所有交通路线图2.1程序设计流程图3 功能模块详细设计3.1 测试数据表3.1城市信息北京天津石家庄济南重庆成都郑州徐州九江武汉广安无锡表3.2交通信息表起始目的旅费（元）时间（小时）里程（公里）重庆广安501300重庆成都1002500广安成都601100北京天津1001250济南天津2002300成都南京50020700浙江郑州300301000九江武汉20010500南京无锡1005200石家庄北京1005300浙江徐州300241500重庆南京500232000成都郑州400302400无锡北京700403500徐州上海20015895上海温州1008300济南重庆15015500天津武汉530282593广安济南300231842上海重庆5342814343.2 程序调试1.主界面包括四个选项：选项一：管理员管理界面，选择该项可进行城市交通系统的管理；选项 二：用户咨询界面，选择该项可进行最少费用、最少时间、最短里程的决策咨询；选项三：显示城市交通系统，选择该项可显示城市交通系统的所有信息，包括城市、交通路线信息；选项四：退出程序， 选择该项将退出程序。图3.1程序主界面在该系统运行的开始会从文件读取交通信息，如果文件不存在会导致程序运行错误！出现下图情况：图3.2文件不存在该函数代码如下：void zairu(Graph *G)/读取文本中的信息FILE *fpout, *fpin;int cnum, lnum;char Fromc20, Toc20;int t, i, j;for(i = 0; i max; i+)for(j = 0; j arcsij.distance = G-arcsji.distance = zuida;G-arcsij.cost = G-arcsji.cost = zuida;G-arcsij.time = G-arcsji.time = zuida;fpout = fopen(number.txt, r);assert(fpout);if(fscanf(fpout, %d %d, &cnum,&lnum)= 2)G-c_n = cnum;G-l_n = lnum;fclose(fpout);/读取城市顶点信息fpout = fopen(city.txt, r);for(t = 0; t c_n; t+)fscanf(fpout, %s, G-clistt.name);fclose(fpout);/读取边的信息.(起点、终点、距离(千米)、花费(元)、时间(分钟)fpout = fopen(lu.txt, r);for(t = 0; t l_n; t+)fscanf(fpout, %s %s, Fromc, Toc);i = Located(G, Fromc);j = Located(G, Toc);fscanf(fpout, %d %d %d, &G-arcsij.distance, &G-arcsij.cost, &G-arcsij.time);G-arcsji.distance = G-arcsij.distance;G-arcsji.cost = G-arcsij.cost;G-arcsji.time = G-arcsij.time;fclose(fpout);elsefpin = fopen(number.txt, w);assert(fpin);fprintf(fpin, 0 0);G-l_n = 0;G-c_n = 0;fclose(fpin); 2管理员管理 界面首先出现登陆界面，采用加密技术，初始密码为 admin， 菜单项包括 5 个选项： 选项一：增加城市信息；选项 二：增加交通路线信息；选项三：保存新增信息，返回上一级菜单，可返回主界面。图3.3管理员界面在该界面中调用了三个重要函数，对城市、交通信息进行编辑和保存。int insertcity(Graph *G)/增加城市char name20;printf(输入要增加的城市: );scanf(%s, name);getchar();if(G-c_n = 0)strcpy(G-clist0.name, name);G-c_n+;elsefor(int i = 0; i c_n; i+)if(strcmp(G-clisti.name, name) = 0)return -1;elsestrcpy(G-clistG-c_n.name, name);G-c_n+;return 1;图3.4增加城市int insertlu(Graph *G)/增加城市交通信息char Fromc20, Toc20;int i, j;int d, c, t;printf(输入增加路径的出发城市、目的城市、距离(公里)、花费(元)、时间(小时): n);scanf(%s %s %d %d %d, Fromc, Toc, &d, &c, &t);getchar();i = Located(G, Fromc);j = Located(G, Toc);if(i = -1 | j = -1)return -1;elseG-arcsij.distance = G-arcsji.distance = d;G-arcsij.cost = G-arcsji.cost = c;G-arcsij.time = G-arcsji.time = t;G-l_n+;return 1;图3.5增加交通信息void baocun(Graph G)/保存新增信息于文件中FILE *fpin;int i,m,k;/边和顶点的个数fpin = fopen(number.txt, w);assert(fpin);fprintf(fpin, %d %d, G.c_n, G.l_n);fclose(fpin);/顶点信息.fpin = fopen(city.txt, w);assert(fpin);for(i = 0; i G.c_n; i+)fprintf(fpin, %s , G.clisti.name);m=i%10; if(m=0)printf(n);fclose(fpin);/边的信息.fpin = fopen(lu.txt, w);assert(fpin);for(i = 0; i G.c_n; i+)for(k = i + 1; k c_n * sizeof(int);/判断顶点是否已求出最短路径d = (int *)malloc(G -c_n * sizeof(int);/储存起始点到各点的最短路径pred = (int *)malloc(G -c_n * sizeof(int);/最后用于输出最短路径for(v=0;v c_n; v+)finaldv =0 ;dv =G -arcsv0v.cost ;if(dv zuida)predv =v0;elsepredv =-1;dv0 = 0;/到起始点无路径finaldv0 =1;/v0放入到final数组里for(i=1;ic_n ;i+)/从1开始、因为起始点已经在final里面、剩下n - 1个顶点、循环n - 1次。mind = zuida;for(w=0;wc_n ;w+)if(!finaldw)/没有放进final里面的终点进行选择最短路径出来.if(dw vexsvfinaldvd =1;/放入final中for(w = 0; w c_n; w+)if(!finaldw & (mind + G-arcsvdw.distance arcsvdw.distance;predw = vd;if(predv1 != -1)printf(%s 到 %s , G-clistv0.name, G-clistv1.name);printf(最短路程为(公里): %dtt, dv1);printf(%s , G-clistv0.name);j = predv1;while(j != v0)printf(- %s, G-clistj.name);j = predj;printf(- %sn, G-clistv1.name);elseprintf(%s 到 %s 没有信息.n, G-clistv0.name, G-clistv1.name);该代码在系统中是核心算法！图3.7最短路径4.显示所有交通信息图3.8交通信息该函数代码如下：void show (Graph G)int i, k; system(cls);printf(nn目前交通系统中含有%d个城市，%d条旅游路径nnn, G.c_n, G.l_n);printf(各大城市: n);for(i = 0; i G.c_n; i+)printf(%s , G.clisti.name);if(i+1)%10=0)printf(n);printf(nn*nn);printf(城市tt城市tt距离(公里)t花费(元)t时间(小时) n);for(i = 0; i G.c_n; i+)for(k = i + 1; k G.c_n; k+)if(G.arcsik.distance != zuida)printf(%stt%stt %dtt %dtt%dn, G.clisti.name, G.clistk.name, G.arcsik.distance, G.arcsik.cost, G.arcsik.time);system(pause);该短代码中主要是读取三个文件，然后分别将信息输出在屏幕上！5.在该系统中还有一段代码，是该程序的核心内容，用于返回网络图结构中位置下标；代码如下：int Located(Graph *G, char *p)/返回数据位置int i;for(i = 0; i c_n; i+)if(strcmp(G-clisti.name, p) = 0)return i;return -1;4 课程总结与体会该系统虽然已满足此次任务要求，但是还有许多需要修改增加的地方：1. 在系统运行时，如无文件就不能运行。可以让系统自行创建文件。2. 在对城市和交通信息进行编辑时不能对其进行删除和修改3. 在对信息编辑时可同时进行保存在这次数据结构课程设计中，自己的 C 语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。同时也学会了解决问题的方法。总结起来，自己主要有以下几点体会： 1.必须牢固掌握基础知识。由于 C 语言知识，有所遗忘，且未掌握好这学期所学的数据结构这门课，所以在实习开始不知如何下手，但在后来的实习过程中自己通过看书和课外资料，并请教其他同学，慢慢地C语言和数据结构知识有所熟悉。这时才逐渐有了思路。 2.必须培养严谨的科学态度。自己在编程时经常因为一些类似于“少了分号” 的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十 分严谨的事情，不能有一点的粗心3.这次课程设计也让我充分认识到数据结构这门课的重要性。它给我们一个思想和大纲，让我们在编程时容易找到思路，不至于无章可循。同时它也有广泛的实际应用。 总之，在这次实习中，自己的 C 语言以及数据结构知识得到提高，编程能力 也得到了提高。5参考文献【1】严蔚敏，吴伟民，数据结构（C语言版），清华大学出版社，1997.4； 【2】周学毛，新编C语言程序设计教程，西安电子科技大学出版社，2005.7； 【3】苏仕华，数据结构课程设计，机械工业出版社，2005【4】滕国文，数据结构课程设计，清华大学出版社，2010年【5】Mark Allen Weiss，数据结构与算法分析：C语言描述，机械工业出版社，2004年6 致谢通过此次的课程设计，我不仅学会了很多有关数据结构的算法思路。此次课程设计要细心指导，以师所授的数据结构知识，还有一些同学和学长的帮助，由于他们的指导与帮助才完成了课程设计。谢谢！