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

X X 学 院 计 算 机 系数据结构课程设计报告书全国交通咨询模拟系统的设计与实现 学生姓名： 学 号： 年级专业及班级： 指导老师及职称： 讲师 专 业：计算机科学与技术专业 提交日期：2011年6月 全国交通咨询模拟系统的设计与实现 学 生：指导老师：(怀化学院计算机系，怀化 418008) 摘 要：该课程设计主要实现了对全国火车及飞机信息的修改和查询，其中主要包括：管理员对火车、飞机信息的操作，其中又包含对两种交通方式的增加和删除操作。旅客用户对两种交通信息的查询，其中飞机信息和火车信息都包含了对两个站点间最短路径方式的查询、最少花费方式的查询以及城市中所有的交通信息的查询。 关键词：全国交通咨询；1 前言 为了完成数据结构的课程设计，为了巩固自己数据结构的知识，也是为了提高自己的编程能力和逻辑思维能力，我选了这道全国交通咨询模拟系统的设计与实现一题。在对其需求进行分析之后，按照需求分析，逐步完成其各部分的功能实现。对于总的方面来讲，管理员功能实现并不难，而难点在于用户功能中的算法及数据结构中的知识以及编程的细微方面，下面将详细介绍本课程设计的内容。2 需求分析 2.1 范围1.1 标识文件状态：【】草稿【 】正式发布【 】正在修改文件标识：需求分析报告当前版本：V1.0作 者：完成日期：2011-6-1221.2 系统概述1软件名称：全国交通咨询系统V1.02软件功能：主要的功能有：管理员增删和修改城市站点信息、飞机路线信息、火车路线信息。3用户：查询最小耗费路线、查询最短时间路线、查询城市所有路线。4开发者：21.3 文档概述需求分析采用在面向对象的方法，主要使用结构体struct的方法来进行实际的编程，在文档中主要采E-R图和对功能的简单描述的方法来表述系统的需求。本需求分析的审查者是老师，所以主要是写给老师看的，用来说明我对这个系统的分析情况。22 引用文件 无23 需求概述23.1 系统目标本系统的总体目标是通过使用该系统，管理员可以对飞机或者火车的信息的简单管理，也方便外出旅客在不同的需求下（如：最少的花费和最短的路程），快速浏览到所要的信息。本系统设计的特点主要有以下几个方面：1. 具有较高的可靠性和可用性；2. 系统易于管理维护；3 简单、便捷；23.2 运行环境1. 系统硬件需求Pentium4 800MHz或更高主频CPU 256MB以上内存。2. 系统软件需求Visual C+ 6.0或者visual studio 6.0等编程软件。23.3 用户的特点机场工作人员或火车站工作人员以及其他具备基本的电脑操作技能和一定的管理权限的用户；旅客需具备基础的计算机操作技能。24功能需求通过对本设计的信息综合分析，得到交通信息的主要组成部分之后，我觉得本系统功能主要分为以下两个部分：1管理员操作：可以对站点的增设和删除，对火车车次的添加与删除以及对飞机航班的添加及删除操作。2. 旅客用户操作：对最小耗费路线的查看、最短时间路线的查看和城市所有的路线信息的查看。24.1 操作流程图增删城市信息 管理员增删飞机信息增删交通路线信息增删火车信息增删交通路线信息退出系统增删交通路线信息旅客用户增删交通路线信息24.2 系统各项功能描述1） 用例1用例名：管理员操作行为者：信息管理员目的：完成对站点信息、飞机航班信息、火车列次信息的增加和删减管理过程描述：a) 选择管理员入口。b) 输出正确的密码登入系统。c) 可以添加城市。d) 可以删除城市。e) 添加交通路线。f) 删除交通路线。g) 退出系统异常处理：无。2） 用例2用例名：旅客及其它人操作行为者：非管理员目的：查看交通信息过程描述：a) 选择旅客入口。b) 可以查询最小耗费路线。c) 可以查询最短时间路线。d) 可以查询城市所有路线。e）退出系统异常处理：无25数据下面仅列出主要实体。通过对学生管理系统的需求分析，我画出五个实体的E-R图：（1）城市信息实体城市信息实体包括城市名，如下图所示： 城市名城市信息（2）火车信息实体火车信息实体包括火车车次、起始站点、终止站点、耗费时间、费用，如下图所示：起始站点终止站点费用火车车次火车信息耗费时间（3）飞机信息实体飞机信息实体包括飞机航班、起始站点、终止站点、耗费时间、费用，如下图所示：终止站点起始站点飞机信息飞机航班费用耗费时间26 采用的技术采用的技术主要包括对文件存取、数据结构和迪杰斯特拉算法等技术。3 详细设计根据题目要求及本次课程设计的目的，按着原来的需求分析的要求，我采用结构体来存储每组数据，其中对每组数据进行相应的操作使用后将他们建立领结矩阵，然后采用迪杰斯特拉算法，在读取文件和保存文件的功能中使用了文件流的相关操作。现把相应的设计思路及各个函数解析如下。3.1 数据结构设计分析3.1.1 存储城市信息的结构体 城市信息包含城市名，具体结构如下：typedef short int CityType; char CityNameMAX_VERTEX_NUMMAX_STRING_NUM; 3.1.2 存储列车次信息的结构体typedef struct TrafficNode char nameMAX_STRING_NUM; int Time;/int EndCity /火车到达城市的编号int Cost;/票价 TrafficNodeDat; typedef struct VNode CityType city; /城市编号int TrainNum; /标记下面Train数组里元素个数 TrafficNodeDat TrainMAX_TRAFFIC_NUM; /数组成员为结构体，记录了到达城市、起止时间、票价和班次 VNodeDat; 3.1.3 存储航班的构体typedef struct TrafficNode char nameMAX_STRING_NUM; /班次 int Time;int EndCity; /火车到达城市的编号int Cost; /票价 TrafficNodeDat; typedef struct VNode CityType city; /城市编号int FlightNum; /标记下面Train数组和Flight数组里元素个数 TrafficNodeDat FlightMAX_TRAFFIC_NUM; VNodeDat;3.2 各个函数分析3.2.1 主函数和功能界面菜单函数 函数原型：int main()main()函数主要是控制整个系统，主要功能是控制整个程序的运行。从主函数开始调用各相关函数来达到相应的功能。由于有多个不同的选项，用switch()语句控制每个函数调用。关键代码如下： switch(Command) case 0: return 0; case 1: Administrators();/管理员操作界面函数 break; case 2: User();/用户操作界面函数 break; default: coutt选择序号错误!请重新选择!n;3.2.2 读文件函数本系统要读入3个文件. 函数原型：int InitSystem()3.2.3 系统主界面函数函数原型： int main()在主函数中，展示整个系统可供用户选择的选项，也使不同的用户进入不同的操作界面。3.2.4 显示函数显示函数要三个，按不用的排序方式进行排序和显示，如下：函数原型：void User()void Administrators()3.2.5 删除函数函数原型：int DelCity(char *Name) /删除城市/删除城市int city,i,j;city=SeekCity(Name);for(i=city;iCityNum-1;i+)strcpy(CityNamei,CityNamei+1);AdjListi.FlightNum=AdjListi+1.FlightNum;AdjListi.TrainNum=AdjListi+1.TrainNum;for(j=0;jAdjListi.FlightNum;j+)AdjListi.Flightj.Cost=AdjListi+1.Flightj.Cost;AdjListi.Flightj.EndCity=AdjListi+1.Flightj.EndCity;strcpy(AdjListi.F,AdjListi+1.F);AdjListi.Flightj.Time=AdjListi+1.Flightj.Time;CityNum-;return 1;int DelPath(char *name) /删除路线/删除路线int i,j,flag=0;for(i=0;iCityNum;i+)for(j=0;jAdjListi.FlightNum;j+)if(strcmp(AdjListi.F,name)=0)flag=1;break;/找到要删除的路线，找到跳出for循环if(flag)for(;jAdjListi.FlightNum-1;j+)AdjListi.Flightj.Cost=AdjListi.Flightj+1.Cost;AdjListi.Flightj.EndCity=AdjListi.Flightj+1.EndCity;strcpy(AdjListi.F,AdjListi.Flightj+1.name);AdjListi.Flightj.Time=AdjListi.Flightj+1.Time;AdjListi.FlightNum-;/将要删除路线后面的路线全部向前移，并将总数减1break;for(j=0;jAdjListi.TrainNum;j+)if(strcmp(AdjListi.T,name)=0)flag=1;break;if(flag)for(;jAdjListi.TrainNum-1;j+)AdjListi.Trainj.Cost=AdjListi.Trainj+1.Cost;AdjListi.Trainj.EndCity=AdjListi.Trainj+1.EndCity;strcpy(AdjListi.T,AdjListi.Trainj+1.name);AdjListi.Trainj.Time=AdjListi.Trainj+1.Time;AdjListi.TrainNum-;break;return 1;通过调用上面这些函数，可以删除某个城市、某航班或者某列车次的信息。3.2.6 添加函数函数原型：int InsertCity(char *Name) /添加某个城市/添加城市strcpy(CityNameCityNum,Name);AdjListCityNum.city=CityNum;/设置城市编号AdjListCityNum.FlightNum=0;AdjListCityNum.TrainNum=0;/新增城市火车数和飞机数初始为零CityNum+;/城市总数加1return 1;int InsertFlight(char *flight,char *StartCity,char *EndCity,int Time,int cost) /添加某架航班/添加飞机路线int i,j;i=SeekCity(StartCity);j=SeekCity(EndCity);AdjListi.FlightAdjListi.FlightNum.Cost=cost;AdjListi.FlightAdjListi.FlightNum.EndCity=j;AdjListi.FlightAdjListi.FlightNum.Time=Time;strcpy(AdjListi.FlightAdjListi.FlightN,flight);AdjListi.FlightNum+;return 1;int InsertTrain(char *train,char *StartCity,char *EndCity,int Time,int cost) /添加某次列车/添加火车路线int i,j;i=SeekCity(StartCity);j=SeekCity(EndCity);AdjListi.TrainAdjListi.TrainNum.Cost=cost;AdjListi.TrainAdjListi.TrainNum.EndCity=j;AdjListi.TrainAdjListi.TrainNum.Time=Time;strcpy(AdjListi.TrainAdjListi.TrainN,train);AdjListi.TrainNum+;return 1;3.2.7迪杰斯特拉函数void Dijkstra(int s3030,int p_start,int p_end,int TravelType) int PreCity30; int i,j,min,pre,pos;for(i=0;iCityNum;i+) PreCityi=-1;PreCityp_start=-2;while(PreCityp_end=-1)min=-1;for(i=0;iCityNum;i+)if(PreCityi!=-1)/i为起始站for(j=0;j0&(min0|sijmin)pre=i;pos=j;/j为起始站中花费最小的到达站的城市编号min=sij;PreCitypos=pre;Dijkstra_Output(s,PreCity,p_end,TravelType);3.2.8查询最小耗费函数int CalcMinCost(int StartCity,int EndCity,int TravelType)/查询最小耗费路线int s3030;int i,j,min,end,flag1,flag2;flag1=0;flag2=0;for(i=0;iCityNum;i+)for(j=0;jCityNum;j+)sij=-1;/设空路径if(TravelType=0)/判断初始城市和终点城市是否在火车交通路线中for(i=0;iCityNum;i+)for(j=0;jAdjListi.TrainNum;j+)if(AdjListi.Trainj.EndCity=StartCity) flag1=1;if(AdjListi.Trainj.EndCity=EndCity) flag2=1;else if(TravelType=1)/判断初始和终点城市是否在飞机交通路线中for(i=0;iCityNum;i+)for(j=0;jAdjListi.FlightNum;j+)if(AdjListi.Flightj.EndCity=StartCity) flag1=1;if(AdjListi.Flightj.EndCity=EndCity) flag2=1;if(flag1!=1&flag2!=1)printf(nt抱歉!没有您要查找的路线!);return 0;if(TravelType=0)for(i=0;iCityNum;i+)min=32767;j=0;while(jAdjListi.TrainNum)min=32767;end=AdjListi.Trainj.EndCity;while(end=AdjListi.Trainj.EndCity&jAdjListi.TrainNum)if(AdjListi.Trainj.Costmin) min=AdjListi.Trainj.Cost;j+;/min为i城市中的最小花费，end为其路线终点站siend=min;elsefor(i=0;iCityNum;i+)min=32767;j=0;while(jAdjListi.FlightNum)min=32767;end=AdjListi.Flightj.EndCity;while(end=AdjListi.Flightj.EndCity&jAdjListi.FlightNum)if(AdjListi.Flightj.Costmin) min=AdjListi.Flightj.Cost;j+;siend=min;Dijkstra(s,StartCity,EndCity,TravelType);return 1;3.2.9存储数据函数int SaveFile()/将火车飞机交通信息写入文件FILE *fp;int i,j,total;if(fp=fopen(city.txt,wb)=NULL)coutnt无法打开文件!n; return -1;fprintf(fp,%dn,CityNum);/在city文件中输入城市总数for(i=0;iCityNum;i+)fprintf(fp,%sn,CityNamei);/再输入城市名fclose(fp);total=0;if(fp=fopen(train.txt,wb)=NULL)coutnt无法打开文件!n; return -1;for(i=0;iCityNum;i+)total+=AdjListi.TrainNum;fprintf(fp,%dn,total);/在train文件中输入火车总数for(i=0;iCityNum;i+)for(j=0;jAdjListi.TrainNum;j+)fprintf(fp,%s %s %s ,AdjListi.T,CityNamei, CityNameAdjListi.Trainj.EndCity);/输入火车车次，始发站和终点站fprintf(fp,%d %dn,AdjListi.Trainj.Time,AdjListi.Trainj.Cost);/输入发车时间和到站时间和费用fclose(fp);total=0;if(fp=fopen(flight.txt,wb)=NULL)coutnt无法打开文件!n;return -1;for(i=0;iCityNum;i+)total+=AdjListi.FlightNum;fprintf(fp,%dn,total);/在flight文件中输入飞机总数for(i=0;iCityNum;i+)for(j=0;jAdjListi.FlightNum;j+)fprintf(fp,%s %s %s ,AdjListi.F,CityNamei, CityNameAdjListi.Flightj.EndCity);/输入飞机航班号，始发站和终点站fprintf(fp,%d %dn,AdjListi.Flightj.Time,AdjListi.Flightj.Cost);/输入起飞时间，到达时间和费用fclose(fp);return 1;3.3 算法及平台分析 本系统用到的算法主要有数据结构中的排序、和文件流的操作等基本算法和迪杰斯特拉求取最短路径算法。本系统是在Microsoft Visual C+ 6.0上设计及运行的，所有的信息显示均是在dos界面中显示出来，利用system(color sf)操作使主界面以绿色为背景，前景色为白色。并且在每一步操作后，都利用system(cls)对dos界面进行清屏，使显示器显示的信息清晰、整齐。4 实现方法 通过对设计题目的深入分析，及题目的要求，在设计时，主要实现的大功能模块，大致满足一个全国交通咨询系统的需要，主要的流程及实现方法请看下面的报告。4.1 学生信息管理系统框架及流程如下图 主界面学生用户界面管理员界面查询城市所有路线查询最短时间路线查询最小耗费路线删除交通路线添加交通路线删除城市添加城市结束退出5 调试问题在编程中遇到不少问题，起初因为对题目理解不足，使得将程序的功能不足，未能实现全部的意思。后来经过查阅相关资料后，发现其中系统在对最短路径问题上实现困难。一番努力后，了解了迪杰斯特拉算法，并实现了最短时间到达的问题进行了解决，后来因为老师对问题的简化，发现在最少费用上同样可以用次算法，经过一番编译调试后，基本实现了功能。还有显示方面问题。起初，对库函数的调用并不在意，但系统完成初期才发现，在DOS界面下，在界面的美观上大大受影响。后来发现调用system(“cls”)时，就会清除屏幕信息。system(“pause”)，它会使数据显示后暂停一下，用记按键后再继续。Sleep(100)可以将界面冻结一段时间后在跳转，这使得使得整个系统的界面看起来整齐而又不失丰富。当然，在编写代码调试程序的时候，还碰到很多的问题，但在自己一遍又一遍的调试中改正了，从而使系统的功能更加完善，使系统的功能更从人性化，容错能力更加强大。但是系统仍然存在很多不足之处，这与自己的经验和知识范围有关，在老师的指导下，相信自己以后能作出更完善、更人性化的系统。6 系统的使用说明书 对于整个系统的使用及每一次你所作出选择和操作之后会出现什么样的界面及操作结果，在下面的说明中作出详细的说明及展示，具体如下所示。5.1 主界面说明当运行系统时，首先进入的是主界面，显示了用户类型的选项，选择正确的类型进入，在最后一行有提示让您输入你