交通咨询系统 C语言.doc

CHINA交通咨询系统目录一、需求分析21、程序的功能及设计要求22、输入输出的要求2二、环境说明2三、详细设计31、模块设计32、画出各函数的调用关系图、主要函数的流程图。32、详细代码4四、调试分析41、测试数据：42、借鉴的资料5五、课程总结6六、附录6一、 需求分析1、 程序的功能及设计要求在交通网络非常发达、交通工具和交通方式不断更新的今天，人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需时间等问题也感兴趣。对于这样一个人们关心的问题，通过建立交通网络图的存储结构图，提供用户查询的功能，功能一：通过输入城市名及任意两个城市的距离，查询任意两个城市之间的最短距离，从而达到最省目的；功能二：通过输入城市名以及任意两个程序的距离，查询中转路线最少。程序所具有的功能特色本程序主要目的是为了给用户提供路径咨询，可以通过输入设置，延续程序的拓展性。设计要求及分析设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的中转次数最少问题或最低花费或最少时间（最短路径）问题。该设计共分三个部分:一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现任意两个城市顶点之间的最短路径问题。1. 建立交通网络图的存储结构 要实现设计要求，首先要定义交通图的存储结构：邻接链表和邻接矩阵； 2. 解决任意两个城市顶点之间的中转次数最少的问题； 3. 解决任意两个城市顶点之间的最短路径（最低花费或最少时间）问题。2、 输入输出的要求定义变量类型应该保持类型一致，通过键盘输入，确保输入输出一致，使最短路径途径以及最短路径能够简单明了的输出，同时保持程序简洁美观，效果明显。输入要求为输入界面直观、亲切；有利于快速输入；有利于准确输入；有利于输入、修改；方便操作。输出要求：输出要求应简单、直观，一目了然，尽量符合用户的习惯，便于用户阅读、理解与使用。输出内容应尽量汉字化，从而使输出格式醒目；各种输出设计要长考虑以利于系统发展和输出项目扩充、变动的需要；输出操作方便二、环境说明系统：WINDOS7开发软件：vc6+三、详细设计1、模块设计交通咨询系统模块图如下由模块图可知，该设计共分三个部分:一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现任意两个城市顶点之间的最短路径问题。开始运行程序，输入命令，进入各种不同的功能区，进行各自的功能，分别运行，然后输出结果。结束后，如果退出就结束，不退出重复上面的功能2、画出各函数的调用关系图、主要函数的流程图。通过Mian主函数调用函数voidcreatDN(lode &g)调用函数voidShortestPath_DIJ(lode &g,char a,char b)调用函数voidvoid TransferDispose(lode &G,char a,char b)主流程图如上图所示通过void creatDN(lode &g)函数调用函数 int localvex(lode &g,char *m)通过void ShortestPath_DIJ(lode &g,char a,char b)函数调用函数 int localvex(lode &g,char *m)调用函数 void Ppath(lode &g,int P,int i,int v)通过void void TransferDispose(lode &G,char a,char b)函数调用函数 InitQueue(LinkQueue &Q)调用函数 EnQueue(LinkQueue &Q,int e)调用函数 DeQueue(LinkQueue &Q,int e)调用函数 int localvex(lode &g,char *m)2、详细代码见附录六四、调试分析1、测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。构建网络图：查询中转次数少：查询最短距离并退出：2、借鉴的资料 1数据结构C语言版 严蔚敏、吴伟民，清华大学出版社，2002五、课程总结这次任务分配，从难度上来说，我这个交通咨询系统程序并不复杂，在书本上基本能找到一摸一样的程序，但关键是理解，虽然书上的程序能看懂，但实践设计不比理解，要是练得少，往往捉襟见肘，要学会融会贯通，那就难上加难了。所以这次就不断演练，不断打击信心，我想还是练少了，酱油打多了，尽管这学期课听的还是很多，但效果还是不好。总的来说，这次变成还是学到了一些东西，尽管微乎其微，算法毕竟是死的，人的大脑是活的，只有不断的实验，才能找到信心，也才能学到东西，但还是可以学到很多东西，怎样的思考方法，怎样连接使逻辑结构语句更完善，所以在编程中和调试过程中要成认真分析和善于发现问题并及时解决的习惯，不懂的及时问老师或者其他同学。通过本次实验，就要掌握了最短路径问题，并结合图的储存结构、狄克斯特拉算法、广度优先遍历等解决了交通咨询系统的设计。源程序打出来后有多处错误，大小写错误、符号错误、遗漏等等，经反复检查调试后实验成功。六、附录源程序清单（带注释）#includestdio.h#includestring.h#includestdlib.h#define INFINITY 65315 int visited20;/邻接链表typedef struct arcnodeint adjvex; /城市编号struct arcnode *nextarc; arcnode; typedef struct vnode char ctname20;arcnode *firstarc;adjlist20; /城市个数 /邻接邻接表typedef struct nodeint adjvex; int route;struct node *next;node;typedef struct arccell int adj; /两城市之间的距离adjmatrix2020;typedef struct adjmatrix arcs; adjlist vexs; int v,a;/顶点 边数lode;/定义城市在位置typedef struct QNodeint data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;int localvex(lode &g,char *m)int i;for(i=0;ig.v;i+)/printf(%sn,g.vexsi.ctname);if(strcmp(g.vexsi.ctname,m)=0)break;return i;/创建连接表void creatDN(lode &g)int i,j,k,w; char v120,v220; arcnode *p,*s;printf(输入城市的个点和两城市之间连通的路径条数:n);scanf(%d%d,&g.v,&g.a);for(i=0;ig.v;i+)printf(输入第%d个城市的名称:n,i+1);scanf(%s,g.vexsi.ctname); g.vexsi.firstarc=0; getchar();for(i=0;ig.v;i+)for(j=0;jg.v;j+)g.arcsij.adj=INFINITY;for(k=0;kadjvex=j;p-nextarc=g.vexsi.firstarc;g.vexsi.firstarc=p;s=(arcnode *)malloc(sizeof(arcnode);s-adjvex=i;s-nextarc=g.vexsj.firstarc;g.vexsj.firstarc=s;/*for(i=0;ig.v;i+)for(j=0;jg.v;j+)printf( %d,g.arcsij.adj);*/*void printfb(lode &g) arcnode *p;int i;printf(%4s%6s%12sn,编号,顶点,相邻边编号);for(i=0;inextarc)printf(%4d,p-adjvex);printf(n);/*for(i=0;ig.v;i+)for(j=0;jg.v;j+)printf( %d,g.arcsij.adj);*/void Ppath(lode &g,int P,int i,int v) int k; while(k!=v)k=Pi;if(k!=v)printf(%s,g.vexsk.ctname); /*输出顶点k*/i=k; / Ppath(P,k,v); /*找顶点k的前一个顶点*/ /*找到了起点则返回*/ return; /最短路径void ShortestPath_DIJ(lode &g,char a,char b)int v,w,i,min,v0,x;int final20;int D20; /最短路径长度int P20;/最短路径的顶点 v0=localvex(g,a); x=localvex(g,b);for(v=0;vg.v;+v)finalv=0;Dv=g.arcsv0v.adj; if (g.arcsv0v.adjINFINITY) /*路径初始化*/ Pv=v0; else Pv=-1; Dv0=0; finalv0=1; Pv0=v0;/开始循环；for(i=1;ig.v;+i)min=INFINITY;v=-1;for(w=0;wg.v;+w) if(!finalw)if(Dwmin) v=w; min=Dw;/求出V0到W最短距离的finalv=1; for(w=0;wg.v;+w)if(!finalw&(min+g.arcsvw.adjDw)&(g.arcsvw.adjINFINITY)Dw=min+g.arcsvw.adj;Pw=v; /* for(v=1;vg.v;v+)if(finalv) printf(%s到%s的最短路径为,a,g.vexsv.ctname); printf(%s,a); Ppath(P,v,v0); printf(%sn,g.vexsv.ctname);printf(%s到%s的最短路径长度为%dn,a,g.vexsv.ctname,Dv); else printf(从%s到%s不存在路径n,a,g.vexsv.ctname);*/if(finalx) printf(%s到%s用最少的钱通过的城市为:,a,b); printf(%s,a); Ppath(g,P,x,v0); printf(%sn,b);printf(%s到%s的所需最少价钱为:%dn,a,b,Dx); else printf(%s不能到达%s!n,a,b);/*void printf(lode *g)int i;arcnode *p;for(i=0;ivexnum;i+)printf(%d,g-AdjListi.data); p=g-AdjListi.firstarc;while(p!=0)printf( %d,p-adjvex);p=p-nextarc;printf(n);*/void InitQueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); Q.front=Q.rear;Q.front-next=NULL;LinkQueue EnQueue(LinkQueue &Q,int e) QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return Q;int DeQueue(LinkQueue &Q,int e)QueuePtr p;if(Q.front!=Q.rear)p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;free(p);return e;/最少旅行中转次数处理void TransferDispose(lode &G,char a,char b)int v0,v1,v,w,n=1;LinkQueue Q; arcnode *t;node *p,*q,*r,*s;p=(node*)malloc(G.v*sizeof(node);for(v=0;vadjvex=v0;q-next=NULL;pv0.next=q;EnQueue(Q,v0);while(Q.front!=Q.rear)/队列不空v=DeQueue(Q,v);t=G.vexsv.firstarc;while(t!=NULL)w=t-adjvex;/w为与城市v相连的第一个城市if(!visitedw)/城市w未访问visitedw=1;/将城市w设为已访问q=&pw;s=pv.next;while(s!=NULL)r=(node*)malloc(sizeof(node);r-adjvex=s-adjvex;q-next=r;q=r;s=s-next;r=(node*)malloc(sizeof(node);r-adjvex=w;r-next=NULL;q-next=r;if(w=v1)/w等于v1q=pw.next;r=q-next;printf(n旅行路线是:n); while(r!=NULL)printf(从%s到%sn,G.vexsq-adjvex.ctname,G.vexsr-adjvex.ctname);q=r;r=r-next;n+;printf(最少中转次数是%d次nn,n-2);for(v=0;vnext; free(s)