全国交通咨询模拟.docx

数据结构课程设计课题：全国交通咨询模拟学 院：计算机科学与技术专 业： 通信工程 班 级： 0903 学 号： 2009115020322学生姓名： 指导教师： 一、题目分析1.【问题描述】处于对不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能的短，出门旅游的游客则希望旅费尽可能的省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两到三种最优决策的交通咨询。2.【基本要求】（1）提供对城市信息进行编辑（添加、删除）的功能。（2）城市之间有两种工具：火车和飞机。提供对列车时刻表和飞机航班表的编辑。（3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。（4）旅途中耗费的总时间应该包括中转站的等候时间。（5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具。输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。二、概要设计1.【抽象数据类型】本程序运用了图这种数据结构，并以邻接表作交通图的存储结构。数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=VR VR=|v,wV且P(v,w),表示从v到w的弧。 谓词P(v,w)定义了弧的意义或信息基本操作：AdjInitiate(&G)初始化邻接表AdjDestroy（&G）撤销邻接表InsertVertex(&G,i,&a)插入结点DeleteVertex(&G,i)删除结点InsertEdge()插入边DeleteEdge()删除边GetFirstVex（）取第一个邻接结点GetNextVex()取下一个邻接结点CreatGraph()创建图邻接表的存储结构typedef struct Nodeint dest;struct Node *next;int t_time;float t_price;int t_start5;int t_get5;int f_time;float f_price;int f_start5;int f_get5;Edge;typedef structDataType data20;int score;Edge *adj;AdjLHeight;typedef structAdjLHeight aMax;int numOfVerts;int numOfEdges;AdjLGraph;栈的存储结构typedef struct snodeint data;struct snode *next;LSNode;其他基本操作：void Administer(AdjLGraph *G);void UserDemand(AdjLGraph *G);void CreatTraffic(AdjLGraph *G);void EditCity(AdjLGraph *G);void AddCity(AdjLGraph *G);void DeleteCity(AdjLGraph *G);void EditTraffic(AdjLGraph *G);int AddTraffic(AdjLGraph *G,int a);int DeleteTraffic(AdjLGraph *G,int a);void LeastMoney(AdjLGraph *G,int v1,int v2,int Traffic)void LeastTime(AdjLGraph *G,int v1,int v2,int Traffic)2.【程序的模块】主函数main退出用户咨询UserDemand管理系统AdministerAdminister(&G)Administer(&G)管理系统Administer退出编辑道路EditTraffic编辑城市EditCity初始化交通系统CreatTraffic编辑城市EditCity退出添加城市AddCity删除城市DeleteCity编辑道路EditTraffic退出添加道路Addtraffic删除道路DeleteTraffic用户咨询UserDemand退出最省钱到达LeastMoney最快到达LeastTime三、详细设计1.【函数调用关系】DeleteQueueEnterQueueTransferDisposePrintGraphCreatTrafficInsertVextexAddcityEditCityDeleteVextexDeletetCityInsertEdgeAddTrafficEditTrafficAdministerDeleteTrafficDeleteEdgeStackPushMain()LeastMoneyStackPopUserDemandStackTopLeastTime2.【源文件】#include#include#include#includetypedef char DataType;#define Max 30#define MaxEdges 60#define MaxWeight 10000int Traffic5*MaxEdges;int tag=0;#includeAdj.h#includeLStack.h#includeDijkstra.hvoid Administer(AdjLGraph *G);void UserDemand(AdjLGraph *G);void CreatTraffic(AdjLGraph *G);void EditCity(AdjLGraph *G);void AddCity(AdjLGraph *G);void DeleteCity(AdjLGraph *G);void EditTraffic(AdjLGraph *G);int AddTraffic(AdjLGraph *G,int a);int DeleteTraffic(AdjLGraph *G,int a);void main()AdjLGraph G;AdjInitiate(&G);int i; do system(cls);printf(nnnnnnn 请选择程序功能:n);printf( *n);printf( * 1=管理系统 *n);printf( * 2=用户咨询 *n);printf( * 3=退出 *n);printf( *n);printf( 选择?); scanf(%d,&i); getchar(); switch(i) case 1:Administer(&G); break; case 2:UserDemand(&G); break; case 3:break; while(i!=3);void Administer(AdjLGraph *G)int i; dosystem(cls);printf(nnnnnnn 请选择程序功能:n);printf( *n);printf( * 1=初始化交通系统 *n);printf( * 2=编辑城市 *n);printf( * 3=编辑交通 *n);printf( * 4=返回 *n);printf( *n);printf( 选择?);scanf(%d,&i);getchar(); switch(i) case 1:CreatTraffic(G); break; case 2:EditCity(G); break; case 3:EditTraffic(G); break; case 4:break; while(i!=4);void UserDemand(AdjLGraph *G)int i=0,e=0,j,v1,v2;FILE *fp,*fr;if(fp=fopen(city.txt,rb)=NULL)printf(无法打开文件!n);while(!feof(fp)fscanf(fp,%10s,G-ai.data);i+;fclose(fp);G-numOfVerts=i;if(fr=fopen(traffic.txt,rb)=NULL)printf(无法打开文件!n);while(!feof(fr)fscanf(fr,%5d,&Traffice);if(Traffice=-1)e-;e+;fclose(fr);G-numOfEdges=e/5;if(tag=0)for(j=0;jnumOfEdges;j+)Edge *p;p=(Edge *)malloc(sizeof(Edge); /*申请邻接边单链表结点空间*/p-dest=Traffic5*j+1; /*置邻接边弧头序号*/p-next=G-aTraffic5*j.adj; /*新结点插入单链表的表头*/G-aTraffic5*j.adj=p; /*头指针指向新的单链表表头*/EditEdge(p,Traffic5*j+2,Traffic5*j+3,Traffic5*j+4);system(cls);for(j=0;jnumOfVerts;j+)printf(%d=%sn,j,G-aj.data);printf(n 选取起始站：);scanf(%d,&v1);printf(n 选取终点站：);scanf(%d,&v2);do system(cls);printf(nnnnnnn 请选择程序功能:n);printf( *n);printf( * 1=最省钱到达 *n);printf( * 2=最快到达 *n);printf( * 3=返回 *n);printf( *n);printf( 选择?);scanf(%d,&i);getchar(); switch(i) case 1:LeastMoney(G,v1,v2,Traffic); break; case 2:LeastTime(G,v1,v2,Traffic); break; case 3:AdjDestroy(G);AdjInitiate(G); break; while(i!=3); tag=0;void CreatTraffic(AdjLGraph *G)tag=1;int i=0,e=0,j,v1,v2;DataType cityMax20;char flag=Y;while(flag=y|flag=Y)system(cls);printf(nnnnnnn 输入城市名:);gets(cityi);i+;printf(n 继续输入?(Y/N);flag=getchar();getchar();printf(n 是否保存城市文本?(Y/N);flag=getchar();getchar();if(flag=y|flag=Y)FILE *fp;if(fp=fopen(city.txt,wb)=NULL)printf(无法打开文件!n);for(j=0;ji;j+)fprintf(fp,%10s,cityj);fclose(fp);dosystem(cls);for(j=0;ji;j+)printf(%d=%sn,j,cityj); printf(n 选择初始站：); scanf(%d,&v1); printf(n 选择到达站：); scanf(%d,&v2);getchar();Traffic5*e=v1;Traffic5*e+1=v2;e+;printf(n 继续编辑?(Y/N);flag=getchar();getchar();while(flag=Y|flag=y);CreatGraph(G,city0,i,Traffic,e);printf(n 是否保存交通道路文本?(Y/N);flag=getchar();getchar();if(flag=y|flag=Y)FILE *fp;if(fp=fopen(traffic.txt,wb)=NULL)printf(无法打开文件!n);for(j=0;jai.data);i+;fclose(fp);G-numOfVerts=i;if(fr=fopen(traffic.txt,rb)=NULL)printf(无法打开文件!n);while(!feof(fr)fscanf(fr,%5d,&Traffice);if(Traffice=-1)e-;e+;fclose(fr);G-numOfEdges=e/5;if(tag=0)for(j=0;jnumOfEdges;j+)Edge *p;p=(Edge *)malloc(sizeof(Edge); /*申请邻接边单链表结点空间*/p-dest=Traffic5*j+1; /*置邻接边弧头序号*/p-next=G-aTraffic5*j.adj; /*新结点插入单链表的表头*/G-aTraffic5*j.adj=p; /*头指针指向新的单链表表头*/EditEdge(p,Traffic5*j+2,Traffic5*j+3,Traffic5*j+4); system(cls); printf(nnnnnnn 请选择程序功能:n); printf( *n); printf( * 1=新增城市 *n); printf( * 2=删除城市 *n); printf( * 3=返回 *n); printf( *n); printf( 选择?); scanf(%d,&i); getchar(); switch(i) case 1:AddCity(G); break; case 2:DeleteCity(G); break; case 3:break; void AddCity(AdjLGraph *G)tag=1;int i=0,j;DataType cityMax20;if(G-numOfVertsMax)FILE *fp;if(fp=fopen(city.txt,rb)=NULL)printf(无法打开文件!n);while(!feof(fp)fscanf(fp,%10s,cityi);i+;fclose(fp);system(cls);for(j=0;jnumOfVerts;j+)printf(%d=%sn,j,G-aj.data);printf(n 输入城市名:);DataType a20;scanf(%s,a);strcpy(cityi,a);i+;FILE *fr;if(fr=fopen(city.txt,wb)=NULL)printf(无法打开文件!n);for(j=0;jnumOfVerts,a);else printf(城市数量已达最大值);void DeleteCity(AdjLGraph *G)tag=1;int v1,j,e=0;system(cls);for(j=0;jnumOfVerts;j+)printf(%d=%sn,j,G-aj.data);printf(n 选取城市序号：);scanf(%d,&v1);j=0;while(jnumOfEdges)if(Traffic5*j=v1|Traffic5*j+1=v1)Traffic5*j=-1;Traffic5*j+1=-1;Traffic5*j+2=-1;Traffic5*j+3=-1;Traffic5*j+4=-1;j+;j=0;while(jnumOfEdges)if(Traffic5*jv1)Traffic5*j-;if(Traffic5*j+1v1)Traffic5*j+1-;j+;FILE *fp;if(fp=fopen(traffic.txt,wb)=NULL)printf(无法打开文件!n);for(j=0;jnumOfEdges;j+)fprintf(fp,%5d,Trafficj);fclose(fp);DeleteVertex(G,v1);if(fp=fopen(traffic.txt,rb)=NULL)printf(无法打开文件!n);while(!feof(fp)fscanf(fp,%5d,&Traffice);if(Traffice=-1)e-;e+;fclose(fp);G-numOfEdges=e/5;if(fp=fopen(traffic.txt,wb)=NULL)printf(无法打开文件!n);for(j=0;jnumOfEdges;j+)fprintf(fp,%5d,Trafficj);fclose(fp);if(fp=fopen(city.txt,wb)=NULL)printf(无法打开文件!n);for(j=0;jnumOfVerts;j+)fprintf(fp,%10s,G-aj.data);fclose(fp);void EditTraffic(AdjLGraph *G)int i=0,e=0,j;FILE *fp,*fr;if(fp=fopen(city.txt,rb)=NULL)printf(无法打开文件!n);while(!feof(fp)fscanf(fp,%10s,G-ai.data);i+;fclose(fp);G-numOfVerts=i;if(fr=fopen(traffic.txt,rb)=NULL)printf(无法打开文件!n);while(!feof(fr)fscanf(fr,%5d,&Traffice);if(Traffice=-1)e-;e+;fclose(fr);G-numOfEdges=e/5;if(tag=0)for(j=0;jnumOfEdges;j+)Edge *p;p=(Edge *)malloc(sizeof(Edge); /*申请邻接边单链表结点空间*/p-dest=Traffic5*j+1; /*置邻接边弧头序号*/p-next=G-aTraffic5*j.adj; /*新结点插入单链表的表头*/G-aTraffic5*j.adj=p; /*头指针指向新的单链表表头*/EditEdge(p,Traffic5*j+2,Traffic5*j+3,Traffic5*j+4); system(cls); printf(nnnnnnn 请选择程序功能:n); printf( *n); printf( * 1=新增道路 *n); printf( * 2=删除道路 *n); printf( * 3=返回 *n); printf( *n); printf( 选择?); scanf(%d,&i); switch(i) case 1:AddTraffic(G,Traffic); break; case 2:DeleteTraffic(G,Traffic); break; case 3:break; int AddTraffic(AdjLGraph *G,int a)tag=1;int i,j,v1,v2;system(cls);for(j=0;jnumOfVerts;j+)printf(%d=%sn,j,G-aj.data);printf(n 选取城市序号：);scanf(%d,&v1);printf(n 选取另一个城市序号：);scanf(%d,&v2);if(v1=G-numOfVerts|v2=G-numOfVerts)system(cls);printf(nnnnnnn 城市序号参数越界出错！);printf(n 请选择程序功能:n); printf( *n); printf( * 1=返回 *n); printf( *n); printf( 选择?); scanf(%d,&i); getchar();doswitch(i)case 1:return 0;while(i!=1); elsej=GetFirstVex(*G,v1);if(j=-1)Traffic5*G-numOfEdges=v1;Traffic5*G-numOfEdges+1=v2;char flag;InsertEdge(G,v1,v2);printf(n 是否保存交通道路文本?(Y/N);flag=getchar(); getchar(); if(flag=y|flag=Y) FILE *fp; if(fp=fopen(traffic.txt,wb)=NULL)printf(无法打开文件!n);for(j=0;jnumOfEdges;j+) fprintf(fp,%5d,Trafficj); fclose(fp);return 1;elsewhile(j!=v2&j!=-1)j=GetNextVex(*G,v1,j);if(j=v2)system(cls);printf(nnnnnnn %s-%s已被编辑过,G-av1.data,G-av2.data);printf(n 如需改动数据可先删除后再重新编辑);printf(n 请选择程序功能:n);printf( *n);printf( * 1=返回 *n);printf( *n);printf( 选择?);scanf(%d,&i);getchar();doswitch(i)case 1:return 0;while(i!=1);else char flag;Traffic5*G-numOfEdges=v1;Traffic5*G-numOfEdges+1=v2; InsertEdge(G,v1,v2); printf(n 是否保存交通道路文本?(Y/N); flag=getchar(); getchar(); if(flag=y|flag=Y) FILE *fp; if(fp=fopen(traffic.txt,wb)=NULL) printf(无法打开文件!n); for(j=0;jnumOfEdges;j+) fprintf(fp,%5d,Trafficj); fclose(fp);return 1;int DeleteTraffic(AdjLGraph *G,int a)tag=1;int i,j,v1,v2,e=0;system(cls);for(j=0;jnumOfVerts;j+)printf(%d=%sn,j,G-aj.data);printf(n 选取城市序号：);scanf(%d,&v1);printf(n 选取另一个城市序号：);scanf(%d,&v2);if(DeleteEdge(G,v1,v2)=0)printf(n 请选择程序功能:n);printf( *n); printf( * 1=返回 *n); printf( *n); printf( 选择?); scanf(%d,&i); getchar();doswitch(i)case 1:return 0;while(i!=1);j=0;while(Traffic5*j!=v1|Traffic5*j+1!=v2)j+;Traffic5*j=-1;Traffic5*j+1=-1;Traffic5*j+2=-1;Traffic5*j+3=-1;Traffic5*j+4=-1;char flag;getchar();printf(n 是否保存交通道路文本?(Y/N);flag=getchar();getchar();printf(%cn,flag);if(flag=y|flag=Y)FILE *fp;if(fp=fopen(traffic.txt,wb)=NULL)printf(无法打开文件!n);for(j=0;jnumOfEdges+1);j+)fprintf(fp,%5d,Trafficj);fclose(fp);if(fp=fopen(traffic.txt,rb)=NULL)printf(无法打开文件!n);while(!feof(fp)fscanf(fp,%5d,&Traffice);if(Traffice=-1)e-;e+;fclose(fp);G-numOfEdges=e/5;if(fp=fopen(traffic.txt,wb)=NULL)printf(无法打开文件!n);for(j=0;jnumOfEdges;j+)fprintf(fp,%5d,Trafficj);fclose(fp);return 1;3.【头文件】/*Adj.h(图的基本操作)添加到头文件*/typedef struct Nodeint dest;struct Node *next;int t_time;float t_price;int t_start5;int t_get5;int f_time;float f_price;int f_start5;int f_get5;Edge;typedef structDataType data20;int score;Edge *adj;AdjLHeight;typedef structAdjLHeight aMax;int numOfVerts;int numOfEdges;AdjLGraph;void AdjInitiate(AdjLGraph *G)/*初始化图G*/int i;G-numOfVerts=0;G-numOfEdges=0;for(i=0;iai.score=i;G-ai.adj=NULL;void AdjDestroy(AdjLGraph *G)/*撤销图G中所有邻家边单链表*/int i;Edge *p,*q;for(i=0;inumOfVerts;i+)p=G-ai.adj;while(p!=NULL)q=p-next;free(p);p=q;void InsertVertex(AdjLGraph *G,int i,DataType *vertex)/*在图G中第i（0iMax）个位置插入结点数据元素vertex*/if(i=0&iai.data,vertex);G-numOfVerts+;else printf(结点越界n);int DeleteEdge(AdjLGraph *G,int v1,int v2);void DeleteVertex(AdjLGraph *G,int i)int j,a;Edge *p,*q;p=G-ai.adj;while(p)q=p-next;free(p);p=q;G-numOfEdges-;G-ai.adj=NULL;for(j=i+1;jnumOfVerts-1;j+)strcpy(G-aj-1.data,G-aj.data);G-aj-1.adj=G-aj.adj;G-numOfVerts-;for(j=0;jnumOfVe