数据结构实验大作业报告专业：物流1001 班级： 1001 学号： 18姓名：金渐指导教师：庄毅2011年12月8日一、问题描述处于对不同目的的旅客对交通工具有不同的要求。

例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则希望旅费尽可能省，而老年旅客则要求中转次数最少。

编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。

【基本要求】（1）提供对城市信息进行编辑（如：添加或删除）的功能。

（2）城市之间有两种交通工具：火车和飞机。

提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。

（3）提供两种最优决策：最快到达或最省钱到达。

全程只考虑一种交通工具。

（4）旅途中耗费的总时间应该包括中转站的等候时间。

（5）咨询以用户和计算机的对话方式进行。

由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。

二、系统设计系统框图：模块说明：本系统共分15个模块1、主函数2、添加城市3、查找城市并返回序号4、删除城市5、添加列车6、添加航班7、删除列车或航班8、找出最小费用路线9、打印出最小费用路线10、初始化系统数据（读入内存）11、找出最快路线12、计算最快路线耗费的时间并打印13、计算最小费用路线14、主界面15、存储信息到文件16、退出下面是系统总流程图：下面是各模块示意图：三、系统测试1、主界面2、添加城市模块：输入命令 1 后，将提示输入城市名，而后返回主界面3、删除城市：输入命令2后，提示输入城市名，而后返回主界面4、添加交通路线：输入命令3，提示输入起点站和重点站，并提示选择火车或飞机，而后输入班次、出发时间、到达时间、票价，而后返回主界面原train文件：添加路线后：5、删除路线：输入命令4，输入班次，而后返回主界面原train文件：删除后ttrain文件：6、查询最小费用路线：输入命令5，并输入起点站和重点站，然后选择交通工具结果正确！7、查询时间最短路线：输入命令6，并输入起点站和重点站，然后选择交通工具四、小结从小学家里买了电脑起，我对计算机就相当感兴趣，有事没事就喜欢捣鼓捣鼓。

六年级的时候，我的第一台台式电脑就这样被我折腾坏了。

高中，我迷上了硬件，一放假就泡论坛，研究攒机。

大学，我买了一台真正的属于自己的智能手机——魅族M8。

买时已经上市超过两年的M8使用的是被微软抛弃的windows CE系统。

系统的落后导致了应用程序的匮乏，虽然日常应用勉强可以应付，但是看着android丰富有趣的app不免让人心痒。

于是在大一的寒假里我第一次萌生了学习编程的念头。

现在，经过了C语言和数据结构的学习之后，编写一个相对大型的程序的机会终于来了，我也憋足了劲想要写出一个优秀的程序，并且选择了一个具有实际价值的模型——全国交通咨询系统。

第一天，我花了周六10个小时的时间写出了寻找相邻城市旅行时间最短的一个函数，然而这只是系统其中的一个简单的功能。

至此，我也就做好了在编写过程中遇到相当大困难的准备。

但是，后来的一个星期里，虽然利用了所有的课外时间来思考文件的存储格式以及所有城市间的转车、最低费用、最短时间函数，事情却依然毫无进展。

由于期末临近，时间紧迫，我只好求助于网上的资料。

查阅之后发现求图的最短路径使用的是我还未学会的迪杰斯特拉算法。

在认真研究之后，终于将迪杰斯特拉算法加到了自己的程序之中，完成了最最关键的功能。

两个星期后的今天，终于完成了系统的全部功能以及测试。

这一次的编程经验，我最大的体会是：代码的编写、调试并不是最困难的部分。

最困难的部分在于如何构思出一个巧妙的软件框架、统一的数据输入输出格式以形成一个完整的体系。

包括各种全局变量的设定、模块的划分都是需要很长的时间去考虑完善的。

五、附录cpp : Defines the entry point for the console application.int Cityity/*int类型*/=NumofCity;CityInfo[NumofCity].FlightNum=0;CityInfo[NumofCity].TrainNum=0;NumofCity++; lightNum=CityInfo[i+1].FlightNum; rainNum=CityInfo[i+1].TrainNum; lightNum;j++){CityInfo[i].Flight[j].Price=CityInfo[i+1].Flight[j].Price;CityInfo[i].Flight[j].DesCity=CityInfo[i+1].Flight[j].DesCity;strcpy(CityInfo[i].Flight[j].name,CityInfo[i+1].Flight[j].name);CityInfo[i].Flight[j].DepTime=CityInfo[i+1].Flight[j].DepTime;CityInfo[i].Flight[j].ArriveTime=CityInfo[i+1].Flight[j].ArriveTime;} rain[CityInfo[i].TrainNum].Price=cost;CityInfo[i].Train[CityInfo[i].TrainNum].DesCity=j;CityInfo[i].Train[CityInfo[i].TrainNum].DepTime=DepTime;CityInfo[i].Train[CityInfo[i].TrainNum].ArriveTime=EndTime;strcpy(CityInfo[i].Train[CityInfo[i].TrainNum].name,train);CityInfo[i].TrainNum++;light[CityInfo[i].FlightNum].Price=cost;CityInfo[i].Flight[CityInfo[i].FlightNum].DesCity=j;CityInfo[i].Flight[CityInfo[i].FlightNum].DepTime=DepTime;CityInfo[i].Flight[CityInfo[i].FlightNum].ArriveTime=EndTime;strcpy(CityInfo[i].Train[CityInfo[i].FlightNum].name,flight);CityInfo[i].FlightNum++;return 1;}lightNum;j++)if (strcmp(CityInfo[i].Flight[j].name,name)==0) lightNum-1;j++){CityInfo[i].Flight[j].Price=CityInfo[i].Flight[j+1].Price;CityInfo[i].Flight[j].DesCity=CityInfo[i].Flight[j+1].DesCity;strcpy(CityInfo[i].Flight[j].name,CityInfo[i].Flight[j+1].name);CityInfo[i].Flight[j].DepTime=CityInfo[i].Flight[j+1].DepTime;CityInfo[i].Flight[j].ArriveTime=CityInfo[i].Flight[j+1].ArriveTime;} lightNum--;break; rainNum;j++)if (strcmp(CityInfo[i].Train[j].name,name)==0) rainNum-1;j++){CityInfo[i].Train[j].Price=CityInfo[i].Train[j+1].Price;CityInfo[i].Train[j].DesCity=CityInfo[i].Train[j+1].DesCity;strcpy(CityInfo[i].Train[j].name,CityInfo[i].Train[j+1].name);CityInfo[i].Train[j].DepTime=CityInfo[i].Train[j+1].DepTime;CityInfo[i].Train[j].ArriveTime=CityInfo[i].Train[j+1].ArriveTime;} rainNum--;break;}}return 1;}int PreCityrainNum;k++)if(CityInfo[track[i]].Train[k].DesCity==end&&min>CityInfo[track[i]].Train[k].Price){min=CityInfo[track[i]].Train[k].Price;tmp=k;}printf("请乘坐%s次列车起止时间：",CityInfo[track[i]].Train[tmp].name);printf("%02d:%02d-%02d:%02d",CityInfo[track[i]].Train[t mp].DepTime/60,CityInfo[track[i]].Train[tmp].DepTime%60,CityInfo[track[i]].Train[tmp].ArriveTime/60,CityInfo[track[i]].Train[tmp].ArriveTime%60);}}else{for(i--;i>0;i--){printf("\n%s:",CityName[track[i]]);end=track[i-1];min=32767;for (k=0;k<CityInfo[track[i]].FlightNum;k++)if(CityInfo[track[i]].Train[k].DesCity==end&&min>CityInfo[track[i]].Flight[k].Price){min=CityInfo[track[i]].Flight[k].Price;tmp=k;}printf("请乘坐%s次航班起止时间：",CityInfo[track[i]].Flight[tmp].name);printf("%02d:%02d-%02d:%02d",CityInfo[track[i]].Flight[tmp] .DepTime/60,CityInfo[track[i]].Flight[tmp].DepTime%60,CityInfo[track[i]].Flight[tmp].ArriveTime/60,CityInfo[track[i]].Flight[tmp].ArriveTime%60);}}printf("\n%s: 已到达目的地",CityName[track[0]]);printf("\n最低价格 : %d\n",cost);}ity=i;CityInfo[i].TrainNum=0; lightNum=0;rain[CityInfo[j].TrainNum].DesCity=FindNumofCity(TempString3);rain[CityInfo[j].TrainNum].name,TempString1);rain[CityInfo[j].TrainNum].DepTime=hour*60+minute;rain[CityInfo[j].TrainNum].ArriveTime=hour*60+minute;rain[CityInfo[j].TrainNum].Price=cost; rainNum++;}fclose(fp);fp=fopen(FlightFile,"r");if (!fp){printf("\n文件打开错误！\n请先初始化系统数据！");return -1;}fscanf(fp,"%d",&num);for (i=0;i<num;i++){fscanf(fp,"%s",&TempString1);fscanf(fp,"%s",&TempString2);fscanf(fp,"%s",&TempString3);j=FindNumofCity(TempString2);CityInfo[j].Flight[CityInfo[j].FlightNum].DesCity=FindNumofCity(Tem pString3);strcpy(CityInfo[j].Flight[CityInfo[j].FlightNum].name,TempString1);fscanf(fp,"%d:%d",&hour,&minute);CityInfo[j].Flight[CityInfo[j].FlightNum].DepTime=hour*60+minute;fscanf(fp,"%d:%d",&hour,&minute);CityInfo[j].Flight[CityInfo[j].FlightNum].ArriveTime=hour*60+minute ;fscanf(fp,"%d",&cost);CityInfo[j].Flight[CityInfo[j].FlightNum].Price=cost;CityInfo[j].FlightNum++; ity=TemPath[i].City;MinPath[i].FlainNo=TemPath[i].FlainNo;curPath=curPathNo;}ity=City; rainNum;i++) rain[i].DepTime>=(CurTime%1440))&&(CityInfo[City].Train[i].ArriveTime+(CurTime/1440)*1440-DepTime<MinTime))lainNo=i;rain[i].DesCity/*（后来调用）现在到达城市可以去的城市*/,DesCity,CityInfo[City].Train[i].ArriveTime+(CurTime/1440)*1440,curPathNo,ByTorByP);rain[i].DepTime<(CurTime%1440))&&(CityInfo[City].Train[i].ArriveTime+(CurTime/1440)*1440-DepTime<MinTime)) lainNo=i;rain[i].DesCity,DesCity,CityInfo[City].Train[i].ArriveTime+(CurTime/1440+1/*等一天*/)*1440,curPathNo,ByTorByP);}}}else lightNum;i++){if((CityInfo[City].Flight[i].DepTime>=CurTime)&&(CityInfo[City].Flight[i].ArriveTime+(CurTime/1440)*1440-DepTime<MinTime)){TemPath[curPathNo].FlainNo=i;SearchMinTime(CityInfo[City].Flight[i].DesCity,DesCity,City Info[City].Flight[i].ArriveTime+(CurTime/1440)*1440,curPathNo,ByTorByP);}if((CityInfo[City].Flight[i].DepTime<CurTime)&&(CityInfo[City].Flight[i].ArriveTime+(CurTime/1440)*1440-DepTime<MinTime)){TemPath[curPathNo].FlainNo=i;SearchMinTime(CityInfo[City].Flight[i].DesCity,DesCity,City Info[City].Flight[i].ArriveTime+(CurTime/1440+1)*1440,curPathNo,ByTorByP);}}}}return 1;}ity=DepCity; rainNum;i++) lainNo=i;rain[i].DepTime;rain[i].DesCity,DesCity,CityInfo[DepCity].Train[i].ArriveTime,0,ByTorByP);}}else lightNum;i++){TemPath[0].FlainNo=i;DepTime=CityInfo[DepCity].Flight[i].DepTime;SearchMinTime(CityInfo[DepCity].Flight[i].DesCity,DesCity,CityI nfo[DepCity].Flight[i].ArriveTime,0,ByTorByP);}}if (MinTime==32767) ity],CityInfo[MinPath[i].City].Train[MinPath[i].FlainNo].name);ity],CityInfo[MinPath[i].City].Flight[MinPath[i].FlainNo].name);ity].Train[MinPath[i].FlainNo].DepTime/60,CityInfo[MinPath[i].City].Tra in[MinPath[i].FlainNo].DepTime%60,CityInfo[MinPath[i].City].Train[MinPa th[i].FlainNo].ArriveTime/60,CityInfo[MinPath[i].City].Train[MinPath[i] .FlainNo].ArriveTime%60);}printf("%s: 已到达目的地",CityName[DesCity]);printf("\n旅途耗费时间: %02d:%02d",MinTime/60,MinTime%60);return 1;}rainNum){ rain[j].DesCity;while (end==CityInfo[i].Train[j].DesCity&&j<CityInfo[i].TrainNum) rain[j].Price<min) rain[j].Price;lightNum){min=32767;end=CityInfo[i].Flight[j].DesCity;while(end==CityInfo[i].Flight[j].DesCity&&j<CityInfo[i].FlightNum) {if (CityInfo[i].Flight[j].Price<min){min=CityInfo[i].Flight[j].Price;}j++;}ma[i][end]=min;}}} rainNum; rainNum;j++){fprintf(fp,"%s %s %s ", CityInfo[i].Train[j].name,CityName[i],CityName[CityInfo[i].Train[j].DesCity]); rain[j].DepTime/60,CityInfo[i].Train[j].DepTime%60,CityInfo[i].Train[j].ArriveTime/60,CityInfo[i].Train[j].ArriveTime%60,CityInfo[i].Train[j].Price); lightNum; lightNum;j++){fprintf(fp,"%s %s %s ", CityInfo[i].Flight[j].name,CityName[i],CityName[CityInfo[i].Flight[j].DesCity]); light[j].DepTime/60,CityInfo[i].Flight[j].DepTime%60,CityInfo[i].Flight[j].ArriveTime/60,CityInfo[i].Flight[j].ArriveTime%60,CityInfo[i].Flight[j].Price); //起止时间和价格输到文件中}}fclose(fp);return 1;}//////////////////////////////////////////////////主函数//////////////////////////////////////////////int main(){char name[15];char s_city[15];char e_city[15];int Command,cost;int DepCity,endcity,ByTorByP;int s_hour,s_minute,e_hour,e_minute;while (1){StartUI();scanf("%d",&Command);switch (Command){case 0: //退出return 0;case 1: //添加城市InitSysData(); //读入所有文档到内存，初始化系统printf("\n输入城市名:");scanf("%s",&name);AddCity(name);//插入城市SaveSysInfo();//保存到文件printf("系统数据保存完毕!\n");break;case 2: //删除城市InitSysData(); //读入内存printf("\n输入城市名:");scanf("%s",&name); //找到该城市DelCity(name); //删除城市SaveSysInfo(); //保存到文件printf("系统数据保存完毕!\n");break;case 3: //添加交通路线InitSysData(); //读入内存printf("起始站城市名:");scanf("%s",&s_city);printf("终点站城市名:");scanf("%s",&e_city);printf("类型（列车0，飞机1）:");scanf("%d",&ByTorByP);printf("输入列车/飞机班次:");scanf("%s",&name);printf("起始时刻(00:00，24小时制):");scanf("%2d:%2d",&s_hour,&s_minute);printf("到达时刻(00:00，24小时制):");scanf("%2d:%2d",&e_hour,&e_minute);printf("票价:");scanf("%d",&cost);if (ByTorByP){AddFlight(name,s_city,e_city,s_hour*60+s_minute,e_hour*60+e_min ute,cost);}else{AddTrain(name,s_city,e_city,s_hour*60+s_minute,e_hour*60+e_minu te,cost);}SaveSysInfo();printf("系统数据保存完毕!\n");break;case 4: //删除路线InitSysData();printf("输入输入列车车次或航班班次:");scanf("%s",&name);DelPath(name);SaveSysInfo();printf("系统数据保存完毕!\n");break;case 5: //最小耗费InitSysData();printf("\n起始城市:");scanf("%s",&name);DepCity=FindNumofCity(name);if (DepCity<0){printf("系统中无该城市数据!\n");break;}printf("终点城市:");scanf("%s",&name);endcity=FindNumofCity(name);if (endcity<0){printf("系统中无该城市数据!\n");break;}printf("乘坐列车请输入0，乘坐飞机请输入1:"); scanf("%d",&ByTorByP);if (ByTorByP!=0&&ByTorByP!=1){printf("输入错误！");break;}CalcMinPrice(DepCity,endcity,ByTorByP);printf("\n");break;case 6: //最短时间路线InitSysData();printf("\n起始城市:");scanf("%s",&name);DepCity=FindNumofCity(name);if (DepCity<0){printf("系统中无此城市数据!\n");break;}printf("终点城市:");scanf("%s",&name);endcity=FindNumofCity(name);if (endcity<0){printf("系统中无此城市数据!\n");break;}printf("乘坐列车请输入0，乘坐飞机请输入1 :");scanf("%d",&ByTorByP);if (ByTorByP!=0&&ByTorByP!=1){printf("输入错误！");break;}CalcMinTime(DepCity,endcity,ByTorByP);printf("\n");break;}}}。