CHINA交通咨询系统目录一、需求分析 (2)1、程序的功能及设计要求 (2)2、输入输出的要求 (2)二、环境说明 (2)三、详细设计 (3)1、模块设计 (3)2、画出各函数的调用关系图、主要函数的流程图。

32、详细代码 (4)四、调试分析 (4)1、测试数据: (4)2、借鉴的资料 (5)五、课程总结 (6)六、附录 (6)需求分析1、程序的功能及设计要求在交通网络非常发达、交通工具和交通方式不断更新的今天，人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需时间等问题也感兴趣。

对于这样一个人们关心的问题，通过建立交通网络图的存储结构图，提供用户查询的功能，功能一：通过输入城市名及任意两个城市的距离，查询任意两个城市之间的最短距离，从而达到最省目的；功能二：通过输入城市名以及任意两个程序的距离，查询中转路线最少。

程序所具有的功能特色本程序主要目的是为了给用户提供路径咨询，可以通过输入设置，延续程序的拓展性。

设计要求及分析设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的中转次数最少问题或最低花费或最少时间（最短路径）问题。

该设计共分三个部分：一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现任意两个城市顶点之间的最短路径问题。

1.建立交通网络图的存储结构要实现设计要求，首先要定义交通图的存储结构：邻接链表和邻接矩阵；2•解决任意两个城市顶点之间的中转次数最少的问题；3•解决任意两个城市顶点之间的最短路径（最低花费或最少时间）问题。

2、输入输出的要求定义变量类型应该保持类型一致，通过键盘输入，确保输入输出一致，使最短路径途径以及最短路径能够简单明了的输出，同时保持程序简洁美观，效果明显。

输入要求为输入界面直观、亲切；有利于快速输入；有利于准确输入；有利于输入、修改；方便操作。

输出要求：输出要求应简单、直观，一目了然，尽量符合用户的习惯，便于用户阅读、理解与使用。

输出内容应尽量汉字化，从而使输出格式醒目；各种输出设计要长考虑以利于系统发展和输出项目扩充、变动的需要；输出操作方便二、环境说明系统：WIND0S7开发软件：vc6+三、详细设计1、模块设计交通咨询系统模块图如下由模块图可知，该设计共分三个部分：一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现任意两个城市顶点之间的最短路径问题。

开始运行程序，输入命令，进入各种不同的功能区，进行各自的功能，分别运行，然后输出结果。

结束后，如果退出就结束，不退出重复上面的功能2、画出各函数的调用关系图、主要函数的流程图。

通过Mian主函数调用函数void creatDN(lode &g)调用函数void ShortestPath_DIJ(lode &g,char a[],char b[])调用函数void void 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[])函数调用函数Ini tQueue(L in kQueue &Q)调用函数En Queue(L in kQueue & Q,i nt e) 调用函数DeQueue(L in kQueue & Q,i nt e) 调用函数int localvex(lode & g,char *m)2、详细代码见附录六四、调试分析1、测试数据:准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。

构建网络图：L ■耳'DA/C 6WC6 iMyP reject5-MS 5\De buc\4£ 5, exr .查询中转次数少:查询最短距离并退出:2、借鉴的资料[1]《数据结构C语言版》严蔚敏、吴伟民，清华大学出版社，2002五、课程总结这次任务分配，从难度上来说，我这个交通咨询系统程序并不复杂，在书本上基本能找到一摸一样的程序，但关键是理解，虽然书上的程序能看懂，但实践设计不比理解，要是练得少，往往捉襟见肘，要学会融会贯通，那就难上加难了。

所以这次就不断演练，不断打击信心，我想还是练少了，酱油打多了，尽管这学期课听的还是很多，但效果还是不好。

总的来说，这次变成还是学到了一些东西，尽管微乎其微，算法毕竟是死的，人的大脑是活的，只有不断的实验，才能找到信心，也才能学到东西，但还是可以学到很多东西，怎样的思考方法，怎样连接使逻辑结构语句更完善，所以在编程中和调试过程中要成认真分析和善于发现问题并及时解决的习惯，不懂的及时问老师或者其他同学。

通过本次实验，就要掌握了最短路径问题，并结合图的储存结构、狄克斯特拉算法、广度优先遍历等解决了交通咨询系统的设计。

源程序打出来后有多处错误，大小写错误、符号错误、遗漏等等，经反复检查调试后实验成功。

六、附录源程序清单（带注释）#i nclude"stdio.h"#i nclude"stri ng.h"#i nclude"stdlib.h"#defi ne INFINITY 65315in t visited[20];//邻接链表typedef struct arcno de{ int adjvex; //城市编号struct arcnode *n extarc;}arc no de;typedef struct vnode { char ctn ame[20]; arcnode *firstarc;}adjlist[20]; // 城市个数//邻接邻接表typedef struct no de{int adjvex; int route; struct node *n ext;} no de;typedef struct arccell{int adj; //两城市之间的距离}adjmatrix[20][20];typedef struct{adjmatrix arcs;adjlist vexs;int v,a;〃顶点边数}lode;//定义城市在位置typedef struct QNode{int data;struct QNode *n ext;}QNode,*QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;}Lin kQueue;in t localvex(lode &g,char *m){int i;for(i=0;i<g.v;i++){// prin tf("%s\n",g.vexs[i].ct name);if(strcmp(g.vexs[i].ct name,m)==0)break;}return i;}//创建连接表void creatDN(lode &g){int i,j,k,w;char v1[20],v2[20];arcnode *p,*s;printf("输入城市的个点和两城市之间连通的路径条数:\n");scan f("%d%d", &g.v, &g.a);for(i=0;i<g.v;i++){printf("输入第%d个城市的名称:\n",i+1);sca nf("%s",g.vexs[i].ct name);g.vexs[i].firstarc=0;getchar();}for(i=0;i<g.v;i++)for(j=0;j<g.v;j++)g.arcs[i][j].adj=INFINITY;for(k=0;k<g.a;k++){\n" ,k+1);printf("输入第%d条城市路径通过的两个城市以及所需的价钱:scan f("%s%s%d"，&v1,&v2,&w);i=localvex(g,v1);// prin tf("i=%d",i);j=localvex(g,v2);// prin tf("j=%d",j);g.arcs[i][j].adj=w;g.arcs[j][i].adj=g.arcs[i][j].adj;p=(arc node *)malloc(sizeof(arc no de)); p_>adjvex=j;p->n extarc=g.vexs[i].firstarc; g.vexs[i].firstarc=p;s=(arc node *)malloc(sizeof(arc no de));s->adjvex=i;s->n extarc=g.vexs[j].firstarc;g.vexs[j].firstarc=s;}/* for(i=0;i<g.v;i++){for(j=0;j<g.v;j++)printf(" %d",g.arcs[i][j].adj);}*/}/*void prin tfb(lode &g){arcnode *p;i nt i;printf("%4s%6s%12s\n","编号","顶点","相邻边编号"); for(i=0;i<g.v;i++){prin tf("%4d %s",i,g.vexs[i].ct name);for(p=g.vexs[i].firstarc;p;p=p->n extarc){prin tf("%4d",p->adjvex);prin tf("\n");}}/* for(i=0;i<g.v;i++){for(j=0;j<g.v;j++)printf(" %d",g.arcs[i][j].adj);}*/void Ppath(lode &g,int P[],int i,int v){int k;while(k!=v){k=P[i];if(k!=v)printf("%s,",g.vexs[k].ctname); /* 输出顶点k*/i=k;}// Ppath(P,k,v); /*找顶点k的前一个顶点*//*找到了起点则返回*/return;}//最短路径void ShortestPath_DIJ(lode &g,char a[],char b[]){int v,w,i,mi n,v0, x;int fin al[20];int D[20]; //最短路径长度int P[20];〃最短路径的顶点vO=localvex(g,a);x=localvex(g,b);for(v=0;v<g.v;++v){fin al[v]=0;D[v]=g.arcs[vO][v].adj;if (g.arcs[vO][v].adj<INFINITY) /* 路径初始化*/P[v]=vO;elseP[v]=-1;}D[vO]=O; fin al[vO]=1;P[vO]=vO;//开始循环；for(i=1;i<g.v;++i){min=INFINITY;v=-1;for(w=0;w<g.v;++w)if(!fi nal[w])if(D[w]<mi n){ v=w; min=D[w];}〃求出VO到W最短距离的fin al[v]=1;for(w=0;w<g.v;++w)if(!fi nal[w] &&(mi n+g.arcs[v][w].adj<D[w])&&(g.arcs[v][w].adj<INFINITY)){ D[w]=mi n+g.arcs[v][w].adj;P[w]=v;} }/* for(v=1;v<g.v;v++){if(fin al[v]){printf("%s 到%s 的最短路径为",a,g.vexs[v].ctname);prin tf("%s,",a);Ppath(Pv,v0);prin tf("%s\n",g.vexs[v].ct name);printf("%s 到%s 的最短路径长度为%d\n",a,g.vexs[v].ctname,D[v]);} elseprintf("从%s到%s不存在路径\n",a,g.vexs[v].ctname);}*/if(fin al[x]){printf("%s到%s用最少的钱通过的城市为:",a,b);prin tf("%s,",a);Ppath(g,Rx,v0);prin tf("%s\n",b);printf("%s 到%s 的所需最少价钱为:%d\n",a,b,D[x]);}elseprintf("%s 不能到达%s!\n",a,b);}/*void prin tf(lode *g){int i;arc node *p; for(i=0;i<g->vex nu m;i++){ prin tf("%d",g->AdjList[i].data);p=g->AdjList[i].firstarc;while(p!=0){printf(" %d",p->adjvex);p=p->n extarc;}prin tf("\n ”);}}*/void Ini tQueue(L in kQueue & Q){Q.fro nt=Q.rear=(QueuePtr)malloc(sizeof(QNode)); Q.fr on t=Q.rear;Q.fro nt-> next=NULL;}Lin kQueue En Queue(L in kQueue &Q,i nt e){QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); p->data=e;p-> next=NULL;Q.rear- >n ext=p;Q.rear=p;return Q;}int DeQueue(L in kQueue &Q,i nt e){QueuePtr p;if(Q.fro nt!=Q.rear){p=Q.fr ont->n ext; e=p->data; Q.front->n ext=p->n ext;if(Q.rear==p) Q.rear=Q.fr on t;}free(p);return e;}//最少旅行中转次数处理void Tran sferDispose(lode &G,char a[],char b[]){int v0,v1,v,w ,n=1;L in kQueue Q; arcnode *t;node *p,*q,*r,*s;p=(no de*)malloc(G.v*sizeof( no de));for(v=0;v<G.v;v++){visited[v]=O;p[v]. next=NULL;}vO=localvex(G,a);v1=localvex(G,b);Ini tQueue(Q);visited[v0]=1;q=(no de*)malloc(sizeof( no de));q->adjvex=vO;q-> next=NULL;p[vO]. next=q;En Queue(Q,vO);while(Q.front!=Q.rear)〃队列不空{v=DeQueue(Q,v);t=G.vexs[v].firstarc;while(t!=NULL){w=t->adjvex;//w为与城市v相连的第一个城市if(!visited[w])〃城市w 未访问{visited[w]=1;〃将城市w设为已访问q=&p[w];s=p[v] .n ext;while(s!=NULL){r=(no de*)malloc(sizeof( no de));r->adjvex=s->adjvex;q-> next=r;q=r;s=s->n ext;}r=(no de*)malloc(sizeof( no de));r->adjvex=w;r- >n ext=NULL;q-> next=r;if(w==v1)//w 等于v1{q=p[w]. next;r=q _>n ext;printf("\n 旅行路线是:\n");while(r!=NULL){printf(” 从%s至U %s\n",G.vexs[q->adjvex].ctname,G.vexs[r->adjvex].ctname); q=r;r=r->n ext ;n++;}printf(”最少中转次数是%d次\n\n”,n-2);for(v=0;v<G.v;v++){q=p[v]. next;while(q!=NULL){s=q;q=q_>n ext; free(s);}p[v]. next=NULL;}free(p);return;}EnQueue(Q,w);}〃将城市w 入队t=t->nextarc;//w等于城市v相连的下一个城市}}for(v=0;v<G.v;v++){q=p[v]. next;while(q!=NULL){s=q;q=q_>n ext;free(s);}p[v]. next=NULL;}free(p);printf(”不存在％s到％s的路线",a,b);}void mai n(){in t c=1,d=1;char a[20],b[20];lode g;creatDN(g);printf("欢迎使用！\n”);while(d!=2){printf(”请输入你出发的城市:\n");sca nf("%s",a);printf(”请输入你到达的城市:\n");sca nf("%s",b);printf("——请选择你所需要的功能——:\n"); printf("1:中转次数少的路线\n");printf("2:两城市之间所需的钱最少\n");//printf("3:退出系统!\n");printf(” 请选择：\n");getchar();sca nf("%d",&c);switch(c){case 1:Tran sferDispose(g,a,b);prin tf("\n");break;case 2:ShortestPath_DIJ(g,a,b);break;}printf(”继续查询吗？\n”);printf(” 继续请按1\n");printf(” 退出请按2\n"); sea nf("%d", &d); if(d==2)printf("谢谢使用! \n");}}。