实验报告C语言数据结构全国交通模拟咨询.doc

资源描述

浙江工商大学计算机与信息工程学院数据结构实验大作业报告专业：物流1001 班级： 1001 学号： 1012600118 姓名：金渐指导教师：庄毅 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. // #include "stdafx.h" #include <stdio.h> #include <string.h> #include<stdlib.h> /////////////////////////////////////结构体定义//////////////////////////////// typedef short int NumType; typedef struct TrafficWay //交通工具信息记录了班次起止时间目的地价格 { char name[15]; //班次 int DepTime; int ArriveTime; //起止时间，以分钟为单位 int DesCity; //目的地的编号 int Price; //票价 } TrafficWayDat; typedef struct CityNode //城市信息只记录序号通过的火车飞机数以及所有火车飞机的结构体 { NumType city; //城市的序号 int TrainNum,FlightNum; //标记火车列次和飞机航班数 TrafficWayDat Train[15]; //数组成员为结构体，记录了到达城市、起止时间、票价和班次 TrafficWayDat Flight[15]; } CityNodeDat; //节点数据类型 typedef struct PathNode //存储路径的路点 { int City; int FlainNo; //此地应乘的火车或飞机航班的次号 } PathNodeDat; /////////////////////////////////////////变量定义////////////////////////////////////// CityNodeDat CityInfo[33]; //System Info ，记录城市信息 char CityName[33][15]; //用来记录城市名，第一下标为该城市编号 int NumofCity; //城市数目 PathNodeDat TemPath[33]; //存储临时路径 PathNodeDat MinPath[33]; //存储目前为止的最小路径 int MinTime/*目前最小时间*/,DepTime/*出发时间*/; int curPath; const char CityFile[] ="city.txt"; const char TrainFile[] ="train.txt"; const char FlightFile[] ="flight.txt"; //////////////////////////////////////////////添加城市//////////////////////////// int AddCity (char *Name) //添加城市 { strcpy(CityName[NumofCity],Name); CityInfo[NumofCity].city/*int类型*/=NumofCity; CityInfo[NumofCity].FlightNum=0; CityInfo[NumofCity].TrainNum=0; NumofCity++; //始终在最后一个空位置 return 1; } ////////////////////////////查找城市并返回序号/////////////////////////////// int FindNumofCity (char *name) //查找城市并返回城市序号若无返回-1 { int i; for (i=0;i<NumofCity;i++) if (strcmp(name,CityName[i])==0) return i; return -1; } /////////////////////////////////////删除城市/////////////////////// int DelCity (char *Name) { int city,i,j; city=FindNumofCity(Name); //得到城市序号 for (i=city;i<NumofCity-1;i++) { strcpy(CityName[i],CityName[i+1]); //后一个城市序号覆盖要删除的城市序号 CityInfo[i].FlightNum=CityInfo[i+1].FlightNum; //后一个城市的航班数覆盖要删除的城市的航班数 CityInfo[i].TrainNum=CityInfo[i+1].TrainNum; //后一个城市的火车数覆盖要删除的城市的火车数 for (j=0;j<CityInfo[i].FlightNum;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; } //覆盖航班信息 } NumofCity--;//城市数减少1 return 1; } ////////////////////////////////////////////////添加列车////////////////////////////////////////////// int AddTrain (char *train,char *DepCity,char *DesCity,int DepTime,int EndTime,int cost) //添加列车 { int i,j; i=FindNumofCity(DepCity);//起始城市序号 j=FindNumofCity(DesCity); //终点城市序号 CityInfo[i].Train[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++;//复制各类信息后，列车数+1 return 1; } //////////////////////////////////////////////添加航班//////////////////////////// int AddFlight(char *flight,char *DepCity,char *DesCity,int DepTime,int EndTime,int cost) //添加航班 { int i,j; i=FindNumofCity(DepCity); j=FindNumofCity(DesCity); CityInfo[i].Flight[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; } //////////////////////////////////////删除列车或航班////////////////////////////////////// int DelPath (char *name) //删除路径 { int i; int j; int flag=0; for (i=0;i<NumofCity;i++) { for (j=0;j<CityInfo[i].FlightNum;j++) if (strcmp(CityInfo[i].Flight[j].name,name)==0) //找到该航班 { flag=1;break; //跳出for } if (flag) //找到了航班 { for (;j<CityInfo[i].FlightNum-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; } //用后面的覆盖 CityInfo[i].FlightNum--;break; //航班数-1 跳出大for } for (j=0;j<CityInfo[i].TrainNum;j++) if (strcmp(CityInfo[i].Train[j].name,name)==0) //找到该列车车次 { flag=1;break; } if (flag) { for (;j<CityInfo[i].TrainNum-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; } //覆盖 CityInfo[i].TrainNum--;break; } } return 1; } ////////////////////////////////打印最小费用路线////////////////////////////////////////// void FindMinPrice_Print(int matx[34][34],int PreCity[34],int p_end,int ByTorByP) { int track[34]; int i=0,j,k,min,tmp,end,cost=0; j=p_end; track[i++]=j; while (PreCity[j]>=0) { cost+=matx[PreCity[j]][j]; track[i++]=j=PreCity[j]; } printf("\n旅行路线:"); if (!ByTorByP) { for(i--;i>0;i--) { printf("\n%s:",CityName[track[i]]); end=track[i-1];min=32767; for (k=0;k<CityInfo[track[i]].TrainNum;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[tmp].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); } ///////////////////////////找出最小费用路线////////////////////////// void FindMinPrice(int matx[34][34],int p_start,int p_end,int ByTorByP) { int PreCity[34]; int i,j,min,pre,pos; for (i=0;i<NumofCity;i++) { PreCity[i]=-1; } PreCity[p_start]=-2; while (PreCity[p_end]==-1) { min=-1; for (i=0;i<NumofCity;i++) if (PreCity[i]!=-1) { for (j=0;j<NumofCity;j++) if (PreCity[j]==-1&&matx[i][j]>0&&(min<0||matx[i][j]<min)) { pre=i;pos=j;min=matx[i][j]; } } PreCity[pos]=pre; } FindMinPrice_Print(matx,PreCity,p_end,ByTorByP); } //////////////////////////////////////////////////初始化系统，读入内存//////////////////////////////////////////////////////////// int InitSysData () //初始化系统数据，将数据读入内存 { FILE *fp; int i,j,hour,minute,num,cost; char TempString1[15]; char TempString2[15]; char TempString3[15]; fp=fopen(CityFile,"r"); if (!fp) { printf("\n文件打开错误！\n请先初始化系统数据！"); return -1; } fscanf(fp,"%d",&NumofCity); //读入城市数 for (i=0;i<NumofCity;i++) //将城市全部读入内存 { fscanf(fp,"%s",&CityName[i]); CityInfo[i].city=i; CityInfo[i].TrainNum=0; //初始化列车数为0 CityInfo[i].FlightNum=0; //初始化航班数为0 } fclose(fp); fp=fopen(TrainFile,"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);//j等于起点的序号 CityInfo[j].Train[CityInfo[j].TrainNum].DesCity=FindNumofCity(TempString3); //把该列车的终点序号赋给经过起点的火车 strcpy(CityInfo[j].Train[CityInfo[j].TrainNum].name,TempString1); //车次赋值给该列车 fscanf(fp,"%d:%d",&hour,&minute); //读取出发时间 CityInfo[j].Train[CityInfo[j].TrainNum].DepTime=hour*60+minute; //出发时间赋值给starttime fscanf(fp,"%d:%d",&hour,&minute); //读取到达时间 CityInfo[j].Train[CityInfo[j].TrainNum].ArriveTime=hour*60+minute; //赋值 fscanf(fp,"%d",&cost); //读取价格 CityInfo[j].Train[CityInfo[j].TrainNum].Price=cost; //赋值 CityInfo[j].TrainNum++; } 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(TempString3); 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++; //同上 } fclose(fp);return 1; } //////////////////////////////////////////////////搜索最小时间路线//////////////////////////////////////////////////////// int SearchMinTime (NumType City/*现在到达城市可以去的城市*/,NumType DesCity/*终点城市*/,int CurTime/*目前用去的时间*/,int curPathNo/*目前经过站点的数目*/,int ByTorByP) { /*搜索出最小时间的路线*/ int i; if (City==DesCity) //到终点了 { // if1 if (MinTime>CurTime-DepTime) //目前为止的最小时间若大于current时间 { // if2 for (i=0;i<=curPathNo;i++) { // for1 MinPath[i].City=TemPath[i].City; MinPath[i].FlainNo=TemPath[i].FlainNo; curPath=curPathNo; }// for1 //则目前最为止最小路径改为current路径，即将cuurrent路径赋值给minpath if(CurTime<DepTime) MinTime=CurTime+1440-DepTime; else MinTime=CurTime-DepTime;//current时间赋值给最短时间 } // if2 } // if1 else //没到终点 { // 最大的else curPathNo++; //经过的站点数 TemPath[curPathNo].City=City; //记录现在到达的站点的所有名字 if (!ByTorByP) //没到终点，若是火车 { // 最大的else下的if for (i=0;i<CityInfo[City].TrainNum;i++) //一一搜索现在站点出发的火车 { // 最大的else下的if下的for if ((CityInfo[City].Train[i].DepTime>=(CurTime%1440))&&(CityInfo[City].Train[i].ArriveTime+(CurTime/1440)*1440-DepTime<MinTime)) //若此列车出发时间大于等于现在的时间也就是可以坐上 { // 最大的else下的if下的for的if1 //且（此列车的到站时间+已经花去的时间）-出发的时间小于 TemPath[curPathNo].FlainNo=i;//记录在此地应乘的经过这里的第i列火车 //目前为止的最小时间（若已经大于了，那就没有计算的必要了） SearchMinTime(CityInfo[City].Train[i].DesCity/*（后来调用）现在到达城市可以去的城市*/,DesCity,CityInfo[City].Train[i].ArriveTime+(CurTime/1440)*1440,curPathNo,ByTorByP); //再次搜索 } if ((CityInfo[City].Train[i].DepTime<(CurTime%1440))&&(CityInfo[City].Train[i].ArriveTime+(CurTime/1440)*1440-DepTime<MinTime)) //坐不上该车，所以要等一天 { TemPath[curPathNo].FlainNo=i; //记录在此地应乘的经过这里的第i列火车 SearchMinTime(CityInfo[City].Train[i].DesCity,DesCity,CityInfo[City].Train[i].ArriveTime+(CurTime/1440+1/*等一天*/)*1440,curPathNo,ByTorByP); } } } else //没到终点，不是火车是飞机 { for (i=0;i<CityInfo[City].FlightNum;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,CityInfo[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,CityInfo[City].Flight[i].ArriveTime+(CurTime/1440+1)*1440,curPathNo,ByTorByP); } } } } return 1; } ////////////////////////////////////计算最小时间////////////////////////////////////// int CalcMinTime (int DepCity,int DesCity,int ByTorByP) //计算最小时间，调用 searchmintime { int i; MinTime=32767;curPath=0; TemPath[0].City=DepCity; //第一站是起点 if (!ByTorByP)// 若是火车 { for (i=0;i<CityInfo[DepCity].TrainNum;i++) //循环搜索起点的火车 { TemPath[0].FlainNo=i;//记录在起点该坐得火车 DepTime=CityInfo[DepCity].Train[i].DepTime; //记录了开始时间 SearchMinTime(CityInfo[DepCity].Train[i].DesCity,DesCity,CityInfo[DepCity].Train[i].ArriveTime,0,ByTorByP);

展开阅读全文