[工学]全国交通咨询模拟.doc

课程设计课程名称：数据结构实验名称：全国交通咨询模拟实验类型：设计系 别：电子信息工程学院学生姓名：李晗、刘畅 指导教师：余先伦 2012年5月8一、需求分析该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。此程序规定：（1） 在程序中输入城市名称时，需输入10个字母以内的字母串；输入列车或飞机编号时需输入一个整型数据；输入列车或飞机的费用时需输入一个实型数据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据（以hh：mm的形式）；在选择功能时，应输入与所选功能对应的一个整型数据。（2） 程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。（3） 程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达。二、E-R流程图退出显示交通系统PrintGraph用户咨询UserDemand管理员管理Administer主函数main（） 返回上一级菜单列车车次编辑Administer飞机航班编辑Administer城市编辑cityedit管理员管理Administer初始化交通系统initgraph返回上一级菜单最少中转次数TransferDispose最少旅行时间TimeDispose用户咨询UserDemand最少旅行费用ExpenditureDisposeUserDemand显示城市显示飞机航班显示列车车次返回上一级菜单显示交通系统PrintGraph文档键盘初始化交通系统initgraph删除城市新增城市城市编辑cityedit删除航班新增航班飞机航班编辑planeedit删除车次新增车次火车列次编辑trainedit2.算法的描述本程序运用了图的知识，构造无了向带权费用图和无向带权时间图。（如图1，图2所示） 图1. 十三城市之间火车费用表（权值表示费用） 图2. 十三城市之间火车行驶时间表 （权值表示时间）三、概要设计系统用到的抽象数据类型定义：1ADT Graph数据对象V：一个集合，该集合中的所有元素具有相同的特性数据关系R：R=VRVR=|P(x,y)(x,y属于V)基本操作：（1） initgraph(&G)；（2） CreateGraph(&G)；（3） EnterVertex(&G)；（4） DeleteVertex(&G)；（5） EnterplaneArc(&G)；（6） DeleteplanArc(&G)；（7） EntertrainArc(&G)；（8） DeletetrainArc(&G)；ADT Graph2ADT LinkQueue数据元素：可以是任意类型的数据，但必须属于同一个数据对象关系：队列中数据元素之间是线性关系。基本操作：（1） InitQueue(&Q)；（2） IsEmpty(&Q)；（3） EnterQueue(&Q,x)；（4） DeleteQueue(&Q,&y)；ADT LinkQueue3ADT TimeTree数据对象D：一个集合，该集合中的所有元素具有相同的特性数据关系R：若D为空，则为空树。若D中仅含有一个数据元素，则R为空集，否则R=H，H为如下二元关系：（1） 在D中存在唯一的称为根的数据元素root，它在关系H中没有前驱（2） 除root以外，D中每个结点在关系H下有且仅有一个前驱。基本操作：（1） CreateTimeTree(p,i,j,&Q,infolist arcs)；（2） CopyTimeTree(p,q)；（3） VisitTimeTree(p)；ADT TimeTree系统中子程序及功能要求：1Administer(ALGraph *G)：提供管理员管理城市交通系统的界面，通过该子程序可调用其他管理交通系统的子程序。2initgraph(ALGraph *G)：初始化交通系统的子程序3createcityfile( )：创建城市文件的子程序4createplanefile( )：创建航班文件的子程序5createtrainfile( )：创建列车时刻表文件的子程序6LocateVertex(ALGraph *G,char *v)：提供城市名在城市交通系统中相应的编号7CreateGraph(ALGraph *G)：创建城市交通系统8cityedit(ALGraph *G)：提供城市编辑功能9EnterVertex(ALGraph *G)：提供在城市交通系统中加入城市的功能10DeleteVertex(ALGraph *G)：提供在城市交通系统中删除城市的功能11flightedit(ALGraph *G)：提供航班编辑功能12EnterplaneArc(ALGraph *G)：提供在城市交通系统中加入航班的功能13DeleteplaneArc(ALGraph *G)：提供在城市交通系统中删除航班的功能14：trainedit(ALGraph *G):提供列车车次的编辑功能15EntertrainArc(ALGraph *G)：提供在城市交通系统中加入列车车次的功能16DeletetrainArc(ALGraph *G)：提供在城市交通系统中删除列车车次的功能17UserDemand(ALGraph G)：提供用户咨询的界面18DemandDispose(int n,ALGraph G)：通过该子程序调用其他咨询子程序19InitQueue(LinkQueue *Q)：初始化队列20EnterQueue(LinkQueue *Q,int x)：入队操作21DeleteQueue(LinkQueue *Q,int *x)：出队操作22IsEmpty(LinkQueue *Q)：队列判空操作23.TransferDispose(int k,infolist(*arcs)MAX_VERTEX_NUM,(*arcs)MAX_VERTEX_NUM ,ALGraph G,ALGraph G,int v0,int v1)：提供最少中转次数决策的功能24MinExpenditure(infolist arcs,float *expenditure,float *route)：提供两个城市之间最少费用的功能25ExpenditureDispose(int k, infolist (*arcs)MAX_VERTEX_NUM,ALGraph G, int v0,int v1,float *D,int *final)：提供最少费用决策的功能26MinTime(infolist arcs,float *time,float *route)：提供两个城市之间最短时间的功能27TimeTreeDispose(Node *head,infolist(*arcs)MAX_VERTEX_NUM)：提供两个之间相隔一个以上城市的城市间的最短时间的功能28CreateTimeTree(TimeTree p,int i,int,LinkQueue *Q,infolist(*arcs)MAX_VERTEX_NUM)：创建时间树29CopyTimeTree(TimeTree p,TimeTree q)：复制时间树30VisitTimeTree(TimeTree p)：访问时间树31DestoryTimeTree(TimeTree p)：销毁时间树32TimeDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraphG,int v0,int v1,float *D,int *final)：提供最少时间决策的功能33：PrintGraph(ALGraph *G)：显示整个城市交通系统各程序模块之间的调用关系（子程序编号见上）：主函数可调用子程序1，17，33子程序1可调用子程序2，8，11，14子程序2可调用子程序3，4，5，7子程序7，12，13，15，16可调用子程序6子程序8可调用子程序9，10子程序11可调用子程序12，13子程序14可调用子程序15，16子程序17可调用子程序18子程序18可调用子程序23，25，32子程序23可调用子程序19，29，21，22子程序25可调用子程序24子程序32可调用子程序26，27子程序27可调用子程序28，30，31子程序28可调用子程序29四、详细设计创建交通图算法的伪码描述如下：int LocateVertex(ALGaph *G,char *v)/*找出城市名在图中对应结点位置*/for(k=0;kvexnum;k+)if(第k个结点中的城市名与传过来的城市名相同)j=k;/*记录位置*/break;返回k 的数值；int CreatGraph(ALGraph *G)if(打开城市文件，文件指针返回值为空）输出错误文件信息；程序返回值为0；while(文件不为空）将文件指针所指的字符串读到城市名数组 cityi中；i+;关闭文件；j=0;while(jvexnum=i;打开航班信息文件plane.txt;将文件中的内容以块为单位读到缓冲区数组a中；关闭文件；a的计数变量k=0;弧的计数变量 arc_num=0;while(kverticesi.planfirstarc;m=0;while(q!=NULL)if( 弧 q中的邻接顶点与j相等）将数组ai 中的内容都复制到弧q中；m=1;break;q=q-nextarc;if(m=0);开辟一个弧结点；将数组ai中的内容都复制到新的弧结点中；将弧结点连接到适当的位置中去；arc_num+;k+;G-planarcnum=arc_num;打开列车信息文件plane.txt;将文件中的内容以块为单位读到缓冲区数组a中；关闭文件；a的计数变量k=0;弧的计数变量 arc_num=0;while(kverticesi.trainfirstarc;m=0;while(q!=NULL)if( 弧 q中的邻接顶点与j相等）将数组ai 中的内容都复制到弧q中；m=1;break;q=q-nextarc;if(m=0);开辟一个弧结点；将数组ai中的内容都复制到新的弧结点中；将弧结点连接到适当的位置中去；arc_num+;k+;G-trainarcnum=arc_num;返回；创建航班算法的伪码描述如下：creatplanefile()while(flag) /*flag为标志位,初值为1*/ 提示“输入航班信息”；输入航班code;输入航班的出发城市vt;输入航班的到达城市vh;输入机票价格money;输入航班的出发时间bt;输入航班的到达时间at;a.count.co=code; /* a 为程序头部定义的结构体*/strcpy(a.count.vt,vt);strcpy(a.count.vh,vh);a.count.bt=bt;a.count.at=at;a.count.mo=money;计数值count+1;提示“是否要继续输入航班信息：”；scanf(“%d”,&flag);if(航班文件不能以读写形式打开)提示“无法打开文件”；将计数值count写入航班车文件；for(i=0;icount;i+)if(无法将ai写入航班文件)提示“文件无法写入”；关闭航班文件；删除城市结点算法的伪码描述如下：DeleteVertex(ALGraph *G) /* G是程序头部定义的结构体*/提示“输入删除城市名”；gets(城市名：v);提示“是否确定要删除（Y/N）“；c=getchar();if(c=Y|c=y)n=0; /*0是记数标志，控制循环次数*/while(n图G表头接点总个数&图G的存储城市名与v不同)/*G表头结点总个数比实际大1*/记数值n+1;if(n = =图G表头结点总个数)提示“无法找到此城市“；elsei=LocateVertex(G,v);/*利用G函数找到此城市名所处在G中位置*/删除从此结点出发的所有航班弧；删除从此结点出发的所有列车弧；for(j=i;j图G表头结点总个数-1；j+)将G第j个结点的信息依前移1位；将G第j个结点的信息制空；/*以下是删除所有指向此结点的航班弧*/for(k=0;kadjvex ）i）将该弧指向顶点位置-1；q=p；p指向下一条飞机弧；else if（该弧指向的顶点位置（p-adjvex ）= = i）if（p指向图G中k结点的第一条飞机弧） m=p；将图G中k结点的第二条飞机弧改为第一弧；p指向下一条飞机弧；释放（m）；else 将p的下一条弧赋给q的下一条弧；m=p；p指向下一条飞机弧；释放（q）；elseq=p；p指向下一条飞机弧；for(k=0;kadjvex ）i）将该弧指向顶点位置-1；q=p；p指向下一条列车弧；else if（该弧指向的顶点位置（p-adjvex ）=i）if（p指向图G中k结点的第一条列车弧） m=p；将图G中k结点的第二条列车弧改为第一弧；p指向下一条列车弧；释放（m）；else 将p的下一条弧赋给q的下一条弧；m=p；p指向下一条列车弧；释放（q）；elseq=p；p指向下一条列车弧；图G表头结点总个数-1；else return；求城市v0，v1之间的最少费用算法的伪码描述如下：ExpenditureDispose( )for(v=0；v城市个数；v+)城市v还未求得最少费用；*(D+v)=城市v0到v的最少费用；将城市v的路径设置为空；if(*(D+v)INFINITY)将城市v0和v加入到城市v的路径中；城市v0到城市v0的最少费用为0；城市v0设为已求得最少费用；for(i=1；i城市个数；v+)m=INFINITY;for(w=0；w城市个数；w+)if(城市w未求得最少费用)if(*(D+w)m)v=w;m=*(D+w);if(v等于v1)根据城市v的路径输出从城市v0到城市v1所需经过的城市及路线；输出最少费用*(D+v1)；返回；else将城市v设为已求得最少费用；for(w=0；m+城市v到w的最少费用)*(D+w)=m+城市v到w的最少费用；将城市w的路径改成城市v的路径并在最后加入城市w；输出没有列车或飞机从城市v0到v1；最少中转次数算法的伪码描述如下：求城市v0到城市v1的最少中转次数TransferDispose( )for(v=0；vG.vexnum；v+)城市v设为未访问；城市v的路径设为空；将城市v0设为已访问；将城市v0入队；while(队列不空)队首城市v出队；w为与城市v相连的第一个城市；while(w存在)if(城市w未访问)将城市w设为已访问；将城市w的路径改为城市v的路径并在最后加入城市w；if(w等于v1)根据城市w的路径输出从城市v0到城市v1所需经过的城市及路线；返回；将城市w入队；w等于城市v相连的下一个城市；输出没有列车或飞机从城市v0到v1；求城市v0，v1之间的最少时间算法的伪码描述如下：TimeDispose( )for(v=0；v城市个数；v+)城市v还未求得最少时间；*(D+v)=城市v0到v的最少时间；将城市v的路径设置为空；if(*(D+v)INFINITY)将城市v0和v加入到城市v的路径中；城市v0到城市v0的最少时间为0；城市v0设为已求得最少时间；for(i=1；i城市个数；v+)m=INFINITY;for(w=0；w城市个数；w+)if(城市w未求得最少时间)if(*(D+w)m)v=w;m=*(D+w);if(v等于v1)根据城市v的路径输出从城市v0到城市v1所需经过的城市及路线；输出最少时间v1；返回；else将城市v设为已求得最少时间；for(w=0；从城市v0到城市w的最少时间)*(D+w)=从城市v0到城市w的最少时间；else将城市w的路径还原；输出没有列车或飞机从城市v0到v1；五、程序代码#includestdio.h#includestdlib.h#includestring.h#define MAX_VERTEX_NUM 18#define NULL 0#define MAX_ARC_SIZE 100#define MAX_ROUTE_NUM 5#includestdio.h#includestdlib.h#includestring.h#define False 0#define True 1#define INFINITY 10000typedef structint number; float expenditure; int begintime2; int arrivetime2;Vehide;typedef structVehide stataMAX_ROUTE_NUM; int last;infolist;typedef struct ArcNodeint adjvex; struct ArcNode *nextarc; infolist info;ArcNode;typedef struct VNodechar cityname10; ArcNode *planefirstarc,*trainfirstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,planearcnum,trainarcnum;ALGraph;typedef struct Nodeint adjvex; int route; struct Node *next;Node;typedef struct QNodeint adjvex; struct QNode *next;QNode;typedef structQNode *front; QNode *rear;LinkQueue;typedef struct TimeNodeint adjvex; int route; int begintime2; int arrivetime2; struct TimeNode *childMAX_ROUTE_NUM;TimeNode,*TimeTree;struct arcint co; char vt10; char vh10; int bt2; int at2; float mo;aMAX_ARC_SIZE;char cityMAX_VERTEX_NUM10;int TTime2;int time2;int time12;int time22;int cMAX_VERTEX_NUM;int dMAX_VERTEX_NUM;void Administer(ALGraph *G);void cityedit(ALGraph *G);void CopyTimeTree(TimeTree p,TimeTree q);void createcityfile();void CreateGraph(ALGraph *G);void createplanefile();void CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist (*arcs)MAX_VERTEX_NUM);void createtrainfile();int DeleteplaneArc(ALGraph *G);void DeleteQueue(LinkQueue *Q,int *x);int DeletetrainArc(ALGraph *G);void DeleteVertex(ALGraph *G);void DemandDispose(int n,ALGraph G);void DestoryTimeTree(TimeTree p);void EnterplaneArc(ALGraph *G);void EnterQueue(LinkQueue *Q,int x);void EntertrainArc(ALGraph *G);void EnterVertex(ALGraph *G);void ExpenditureDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1,float *M,int *final);void flightedit(ALGraph *G);void initgraph(ALGraph *G);void InitQueue(LinkQueue *Q);int IsEmpty(LinkQueue *Q);int LocateVertex(ALGraph *G,char *v);void MinExpenditure(infolist arcs,float *expenditure,int *route);void MinTime(infolist arcs,int *time,int *route);void PrintGraph(ALGraph *G);int save(ALGraph *G);void TimeDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1,int (*T)2,int *final);void TimeTreeDispose(Node *head,infolist (*arcs)MAX_VERTEX_NUM);void trainedit(ALGraph *G);void TransferDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1);void UserDemand(ALGraph G);void VisitTimeTree(TimeTree p); int main()/* 显示程序功能选择界面*/ALGraph G; int i; printf(请选择程序功能:n); printf(1=管理员管理n2=用户咨询n3=显示交通系统n4=退出n); printf(选择?); scanf(%d,&i); getchar(); while(i!=4) switch(i) case 1:Administer(&G);break; case 2:UserDemand(G);break; case 3:PrintGraph(&G);break; printf(n请选择程序功能:n); printf(1=管理员管理n2=用户咨询n3=显示交通系统n4=退n); printf(选择?); scanf(%d,&i); getchar(); return 1; void Administer(ALGraph *G)/* 显示管理员管理项目选择界面*/int i; printf(n请选择管理项目:n); printf(1=初始化交通系统n2=城市编辑n3=飞机航班编辑n4=列车车次编辑n5=返回上一级菜单n); printf(选择?); scanf(%d,&i); getchar(); while(i!=5) switch(i) case 1:initgraph(G); /初始化交通系统 break; case 2:cityedit(G); /城市编辑 break; case 3:flightedit(G); /飞机航班编辑 break; case 4:trainedit(G); /列车车次编辑 break; printf(n请选择管理项目:n); printf(1=初始化交通系统n2=城市编辑n3=飞机航班编辑n4=列车车次编辑n5=返回上一级菜单n); printf(选择?); scanf(%d,&i); getchar(); void initgraph(ALGraph *G) /初始化交通系统/* 初始化交通系统方式选择界面*/int i; printf(n请选择初始化方式:n); printf(1=键盘n2=文档n); printf(选择?); scanf(%d,&i); getchar(); switch(i) case 1:createcityfile(); createplanefile(); createtrainfile(); CreateGraph(G); break; case 2:CreateGraph(G); break; void createcityfile()/* 创建城市名称文档*/int i=0; int j; char flag=y; FILE *fp; printf(n请输入城市名称的信息:n); while(flag=y|flag=Y) printf(城市名称:); gets(cityi); i+; printf(继续输入?(Y/N); scanf(%c,&flag); getchar(); printf(n); if(fp=fopen(city.txt,wb)=NULL) printf(无法打开文件!n); return; for(j=0;ji;j+) fprintf(fp,%10s,cityj); fclose(fp);void createplanefile()/* 创建飞机航班文档*/int code,bt2,at2; /code航班编号，bt出发时间，at到达时间 float money; int i; int count; char vt10,vh10,flag; /vt起始城市，vh目标城市 FILE *fp; flag=y; count=0; while(flag=Y|flag=y) /*flag为标志位,初值为1*/ printf(请输入飞机航班的信息:n); /提示输入航班信息 printf(飞机航班编号:); /输入航班code scanf(%d,&code); getchar(); printf(起始城市:); /输入航班的出发城市vt gets(vt); printf(目的城市:); /输入航班的到达城市vh gets(vh); printf(航班费用:); /输入机票价格money scanf(%f,&money); getchar(); printf(起飞时间:); /输入航班的出发时间bt scanf(%d:%d,&bt0,&bt1); getchar(); while(bt0=24|bt1=60) printf(n时间输入有误，请重新输入n); scanf(%d:%d,&bt0,&bt1); getchar(); printf(到达时间:); /输入航班的到达时间at scanf(%d:%d,&at0,&at1); getchar(); while(at0=24|at1=60) printf(n时间输入有误，请重新输入n); scanf(%d:%d,&at0,&at1); getchar(); acount.co=code; / a 为程序头部定义的结构体 strcpy(acount.vt,vt); strcpy(acount.vh,vh); acount.bt0=bt0; acount.bt1=bt1; acount.at0=at0; acount.at1=at1; acount.mo=money; count+; /计数值count+1 printf(继续输入?(Y/N); /提示是否要继续输入航班信息： scanf(%c,&flag); getchar(); printf(n); if(fp=fopen(plane.txt,wb)=NULL) /航班文件不能以读写形式打开 printf(n无法打开文件!n); /提示无法打开文件 fprintf(fp,%d,count); /将计数值count写入航班车文件 for(i=0;icount;i+) if(fwrite(&ai,sizeof(struct arc),1,fp)!=1) /无法将ai写入航班文件 printf(n文件写入错误!n); /提示文件无法写入 fclose(fp); /关闭航班文件void createtrainfile()/* 创建列车车次文档*/int code,bt2,at2; float money; int i; int count; char vt10,vh10,flag; FILE *fp; flag=y; count=0; while(flag=y|flag=Y) printf(请输入列车车次的信息:n); printf(列车车次编号:); scanf(%d,&code); getchar(); printf(起始城市:); gets(vt); printf(目的城市:); gets(vh); printf(车次费用:); scanf(%f,&money); getchar(); printf(发车时间:); scanf(%d:%d,&bt0,&bt1); getchar(); while(bt0=24|bt1=60) printf(n时间输入有误，请重新输入n); scanf(%d:%d,&bt0,&bt1); getchar(); printf(到达时间:); scanf(%d:%d,&at0,&at1); getchar(); while(at0=24|at1=60) printf(n时间输入有误，请重新输入n); scanf(%d:%d,&at0,&at1); getchar(); acount.co=code; strcpy(acount.vt,vt); strcpy(acount.vh,vh); acount.bt0=bt0; acount.bt1=bt1; acount.at0=at0; acount.at1=at1; acount.mo=money; count+; printf(继续输入?(Y/N); scanf(%c,&flag); getchar(); printf(n); if(fp=fopen(train.txt,wb)=NULL) printf(n无法打开文件!n); fprintf(fp,%d,count); for(i=0;icount;i+) if(fwrite(&ai,sizeof(struct arc),1,fp)!=1) printf(n文件写入错误!n); fclose(fp); int LocateVertex(ALGraph *G,char *v) /* 城市名在交通系统中定位操作，找出城市名在图中对应结点位置*/int j,k; j=-1; for(k=0;kvexnum;k+) if(strcmp(G-verticesk.cityname,v)=0) /第k个结点中的城市名与传过来的城市名相同 j=k; /*记录位置*/ break; return(j);void CreateGraph(ALGraph *G)/* 用city，plan，train三个文档创建城市交通系统*/ int i,j,k; int arc_num; int count1,count2; int m,t; ArcNode *p,*q; FILE *fp; i=0; if(fp=fopen(city.txt,rb)=NULL) /打开城市文件，文件指针返回值为空 printf(n无法打开文件!n); return; while(!feof(fp) /文件不为空 fscanf(fp,%10s,cityi); i+; fclose(fp); /关闭文件 j=0; while(jverticesj.cityname,cityj);/将 cityi 中的内容复制到图的结构体的结点数组中; G-verticesj.planefirstarc=NULL; / 图的结构体其他项赋初值; G-verticesj.trainfirstarc=NULL; j+; G-vexnum=i; if(fp=fopen(plane.txt,rb)=NULL) printf(n无法打开文件!n); k=0; fscanf(fp,%d,&count1); /打开航班信息文件plane.txt while(kcount1) if(fread(&ak,sizeof(struct arc),1,fp)!=1) printf(n文件读入错误!n); k+; fclose(fp); /关闭文件 k=0; /a的计数变量k=0 arc_num=0; /弧的计数变量 arc_num=0 while(kverticesi.planefirstarc; m=0; while(q!=NULL) if(q-adjvex=j) /弧 q中的邻接顶点与j相等 t=q-info.last+1; / 将数组ai 中的内容都复制到弧q中 q-info.statat.number=ak.co; q-info.statat.expenditure=ak.mo; q-info.statat.begintime0=ak.bt0; q-info.statat.begintime1=ak.bt1; q-info.statat.arrivetime0=ak.at0; q