交通咨询系统C语言

CHINA交通咨询系统目录一、需求分析 21、 程序的功能及设计要求 22、 输入输出的要求 2二、环境说明 2三、详细设计 31、模块设计 32、画出各函数的调用关系图、主要函数的流程图。 32、详细代码 4四、调试分析 41、测试数据： 42、借鉴的资料 5五、课程总结 6六、附录 6需 求分析1 、 程序的功能及设计要求在交通网络非常发达、交通工具和交通方式不断更新的今天,人们在出差、旅游或做其他出行时,不仅关心节省交通费用，而且对里程和所需时间等问题也感兴趣.对于这样一个人们关心的问题，通过建立交通网络图的存储结构图,提供用户查询的功能，功能一：通过输入城市名及任意两个城市的距离，查询任意两个城市之间的最短距离，从而达到最省目的；功能二：通过输入城市名以及任意两个程序的距离，查询中转路线最少。 程序所具有的功能特色本程序主要目的是为了给用户提供路径咨询，可以通过输入设置，延续程序的拓展性.设计要求及分析设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的中转次数最少问题或最低花费或最少时间（最短路径）问题。该设计共分三个部分:一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现任意两个城市顶点之间的最短路径问题。1. 建立交通网络图的存储结构要实现设计要求,首先要定义交通图的存储结构:邻接链表和邻接矩阵；2. 解决任意两个城市顶点之间的中转次数最少的问题；3. 解决任意两个城市顶点之间的最短路径（最低花费或最少时间）问题。2、 输入输出的要求定义变量类型应该保持类型一致，通过键盘输入，确保输入输出一致,使最短路径途径以及最短路径能够简单明了的输出，同时保持程序简洁美观,效果明显。输入要求为输入界面直观、亲切;有利于快速输入；有利于准确输入；有利于输入、修改;方便操作。输出要求：输出要求应简单、直观，一目了然，尽量符合用户的习惯，便于用户阅读、理解与使用。输出内容应尽量汉字化，从而使输出格式醒目；各种输出设计要长考虑以利于系统发展和输出项目扩充、变动的需要;输出操作方便二、环境说明系统 :WINDOS7开发软件：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 locakex(lode &g , char * m)通过 void ShortestPath_DIJ (lode &g,char a口, char b口 )函数调用函数 int locakex (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、测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果.构建网络图：1 n JCAJ 工门广 id4查询中转次数少:w qtf-H!1、r吗t ? 词喜 堂请请 续金查询最短距离并退出:2、借鉴的资料20021数据结构C语言版 严蔚敏、吴伟民，清华大学出版社,五、课程总结这次任务分配，从难度上来说，我这个交通咨询系统程序并不复杂，在书本上基本能找到一摸一样的程序，但关键是理解，虽然书上的程序能看懂，但实践设计不比理解，要是练得少往往捉襟见肘,要学会融会贯通，那就难上加难了。所以这次就不断演练,不断打击信心，我想还是练少了,酱油打多了,尽管这学期课听的还是很多，但效果还是不好。总的来说，这次变成还是学到了一些东西，尽管微乎其微，算法毕竟是死的，人的大脑是活的，只有不断的实验,才能找到信心，也才能学到东西，但还是可以学到很多东西，怎样的思考方法,怎样连接使逻辑结构语句更完善，所以在编程中和调试过程中要成认真分析和善于发现问题并及时解决的习惯，不懂的及时问老师或者其他同学。通过本次实验，就要掌握了最短路径问题,并结合图的储存结构、狄克斯特拉算法、广度优先遍历等解决了交通咨询系统的设计.源程序打出来后有多处错误,大小写错误、符号错误、遗漏等等,经反复检查调试后实验成功。六、附录源程序清单（带注释） include"stdio 。 h”#include"string.h ”#include ” std。 libh"#define INFINITY 65315int visited 20；/ 邻接链表typedef struct arcnode int adjvex；/城市编号struct arcnode *nextarc; arcnode;typedef struct vnode char ctname 20 ; arcnode firstarc;adjlist 20；/ 城市个数/ 邻接邻接表typedef struct node int 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 struct QueuePtr front ；QueuePtr rear;LinkQueue；int localvex（lode g， char *m）int i；for（i=0;i<g。v; i+） / printf（ n”， g。 vexs i。 ctname）；if（strcmp（g.vexs i .ctname， m）=0）break;return i ；/ 创建连接表void creatDN（lode & g） int i， j,k， w;char v1 20 ,v2 20 ;arcnode p, s;printf（ ”输入城市的个点和两城市之间连通的路径条数 :n"） ；scanf（ ” d%d”, g。 v， &g。 a） ;for （i=0;i<g.v;i+） printf（" 输入第d 个城市的名称：n”， i+1） ；scanf（ " s” ,g.vexsi.ctname）;g。 vexsi .firstarc=0 ； getchar（ ）;for（ i=0;i g.v； i+）for（j=0 ； j g.v;j+）g.arcs ij 。 adj=INFINITY；for （k=0; k<g.a;k+） printf（" 输入第 %d 条城市路径通过的两个城市以及所需的价钱：n",k+1 ） ；scanf（ ” s%s%d” ， &v1, v2,&w） ;i=localvex（ g,v1）;/ printf （ "i= d” ） ,i ;j=localvex（g,v2）;/ printf （ "j= d"， j）；g.arcs i j 。 adj=w；g。 arcsj i 。 adj=g。 arcs i j 。 adj;p=（arcnode *）malloc（sizeof （ arcnode） ）；p- adjvex=j;p->nextarc=g.vexs i .firstarc；g.vexsi。 firstarc=p；s=（ arcnode * ） malloc（ sizeof（ arcnode） ）；s->adjvex=i；s- nextarc=g。 vexsj.firstarc;g。 vexs j .firstarc=s;/* for（i=0;i<g 。 v； i+）for（j=0 ； jg。 v； j+）printf "" %d", g。arcs i j。adj）; */ * void printfb （lode &g） arcnode *p ； int i ；printf（ "%4s%6s 12sn” ,”编号"," 顶点 "， ”相邻边编号”）;for（i=0; i g。v;i+） printf（"%4d %s"， i,g。 vexsi 。 ctname） ；for（ p=g.vexsi 。 firstarc； p； p=p->nextarc）printf（ " 4d" ， p adjvex） ;printf " "n" ）;/*for（ i=0;i<g。 v;i+）for（j=0 ； j<g.v； j+）printf（ % d", g。arcsi j。 adj）; */void Ppath（ lode &g ， int P ， int i ， int v） int k；while（k!=v）k=Pi ;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， min,v0,x；int final 20 ；int D20;/最短路径长度int P20 ;/ 最短路径的顶点 v0=localvex（g,a） ; x=localvex（ g， b）; for（v=0 ； v<g.v； +v） final v =0； D v=g。 arcs v0v 。 adj； if （g。 arcsv0 v.adj INFINITY） / 路径初始化*/P v=v0;elseP v=-1 ；D v0 =0；finalv0=1;Pv0 =v0； / 开始循环；for（i=1;ig。v； +i） min=INFINITY； v= 1； for（w=0;w<g.v ； +w） if（ ！ final w ） if（ D w min） v=w; min=Dw ; 求出 V0到 W最短距离的 finalv =1;for（ w=0;w<g.v； +w） if（！ final w &（ min+g.arcs vw .adj D w ）& （g。 arcs v w 。 adj INFINITY） Dw=min+g 。 arcs v w 。 adj;Pw=v； /* for（v=1 ； v g.v;v+） if （final v） 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。 vexs v.ctname ， Dv）； elseprintf（"从$到$ 不存在路径 n” ,a, g。vexsv。ctname）; /if（finalx ） printf （"%s到 s用最少的钱通过的城市为："，a, b）; printf（ ” %s，,”a） ； Ppath（ g,P,x,v0） ;printf（ ” %ns",b ） ;printf("%s 到$ 的所需最少价钱为：% dn" , a, b,Dx ); elseprintf " "%s不能到达 s! n” ,a, b);/*void printf(lode * g) int i； arcnode p;for( i=0； i g- vexnum； i+)printf("%d ， ”g AdjListi .data) ;p=g- AdjList i 。 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;v G.v； v+)visitedv =0； p v。 next=NULL;v0=localvex(G， a)；v1=localvex(G,b) ；InitQueue(Q ) ； visited v0=1; q=( node)malloc( sizeof(node) );q >adjvex=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(！ visited w )/ 城市 w 未访问visitedw=1 ； /将城市 w 设为已访问 q= pw ； s=pv 。 next; while(s! =NULD 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=p w 。 next； r=q next；printf( ” n 旅行路线是：n" ) ；while r 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;v G。 v； v+) q=p v.next； while(q!=NULL)s=q；q=q->next; free (s);pv .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 >next; free（s）; p v .next=NULL;free（p）；printf（"不存在%s到% s的路线"，a, b）;void main （）int c=1,d=1 ； char a 20 ， b20 ；lode g；creatDN（ g）;printf（ "欢迎使用！n”） ;while（d!=2 ） printf （"请输入你出发的城市：n ”）；scanf（"%s ”） ； ,aprintf（ "请输入你到达的城市:n”） ；scanf（ "%s"， b）;printf（ "-请选择你所需要的功能- -：n”） ；printf（"1: 中转次数少的路线n ” ）；printf（”2:两城市之间所需的钱最少n” ）;/printf （”3：退出系统!n ” ） ;printf （" 请选择：n"）;getchar（ ）；scanf（" d", c）;switch （ c）case 1:TransferDispose（ g， a， b）；printf （ ” n"） ； break；case 2:ShortestPath_DIJ（g,a,b）； break;printf（" 继续查询吗？n ” ）;printf （"继续请按1n"）;printf（" 退出请按2n" ） ;scanf（ ” %d， "d）;if（d=2）printf（ ”谢谢使用！ n" ） ；