数据结构实训全国交通咨询模拟

学生实训报告实训名称：数据结构实训指导教师：姓名：学号：班级：日期：一、实训项目项目名称：全国交通咨询模拟二、实训的目的1.熟悉图数据结构;2.掌握图的顺序存储结构—邻接表;3.掌握最短路径算法4.上机调试程序,掌握查错、排错使程序能正确运行。三．实训要求1.每个人独立完成实训项目，相互之间可以交流，不能抄袭2.实训的成果包括程序代码和报告3.程序代码要有注释和说明三、实验的环境:1.硬件环境:PC机2.软件环环境:Windows2000+VisualC++6四、算法描述:建立图的数据结构，采用邻接矩阵作为其存储结构。存储以上的全国主要城市的交通信息。通过软件模拟的方法实现：给定出发点和终点，求出它们之间的最短路径，并给出最短路径的线路。五、源程序清单:#includestdio.h#includestring.h#defineVEX_NUM26#defineMAXINT1000000typedefstructgraph{charcity[VEX_NUM][10];intarcs[VEX_NUM][VEX_NUM];}Mgraph;voidCreatGraph(Mgraph*G,inte);voidDijkstra(Mgraph*Gn,intv0,intpath[],intdist[]);voidPutPath(Mgraph*g,intv0,intv1,intp[],intd[]);intindex(chars[],Mgraph*g);voidmain(){Mgraph*g;inti;inte;intv0,v1;charsr[10],dt[10];intdist[VEX_NUM];intpath[VEX_NUM];g=newMgraph;CreatGraph(g,30);printf(输入出发城市和终点城市\n);getchar();gets(sr);v0=index(sr,g);gets(dt);v1=index(dt,g);Dijkstra(g,v0,path,dist);PutPath(g,v0,v1,path,dist);}voidCreatGraph(Mgraph*G,inte){inti,j,k,cost;printf(输入城市名称\n);for(i=0;iVEX_NUM;++i)scanf(%s,G-city[i]);for(i=0;iVEX_NUM;i++)for(j=0;jVEX_NUM;j++)G-arcs[i][j]=MAXINT;printf(输入城市之间的距离\n);for(k=0;ke;k++){scanf(%d,%d,%d,&i,&j,&cost);G-arcs[i][j]=cost;G-arcs[j][i]=cost;}}voidDijkstra(Mgraph*Gn,intv0,intpath[],intdist[]){ints[VEX_NUM];intv;intw;inti,j,k;intmin;for(v=0;vVEX_NUM;v++){s[v]=0;dist[v]=Gn-arcs[v0][v];if(dist[v]MAXINT)path[v]=v0;elsepath[v]=-1;}dist[v0]=0;s[v0]=1;for(i=1;iVEX_NUM-1;i++){min=MAXINT;for(w=0;wVEX_NUM;w++)if(!s[w]&&dist[w]min){v=w;min=dist[w];}s[v]=1;for(j=0;jVEX_NUM;j++)if(!s[j]&&(min+Gn-arcs[v][j]dist[j])){dist[j]=min+Gn-arcs[v][j];path[j]=v;}}}voidPutPath(Mgraph*g,intv0,intv1,intp[],intd[]){intk;intnext;inttop=0;intst[20];if(d[v1]MAXINT&&v1!=v0){st[top++]=v1;next=p[v1];while(next!=v0){st[top++]=next;next=p[next];}}elseif(v1!=v0){printf(%s-%s:没有路径\n,g-city[v0],g-city[v1]);return;}st[top++]=v0;while(top){next=st[--top];if(top!=0)printf(%s-,g-city[next]);elseprintf(%s\n,g-city[next]);}printf(两个城市之间的最短距离为：%d\n,d[v1]);}intindex(chars[],Mgraph*g){inti;for(i=0;iVEX_NUM;i++)if(strcmp(s,g-city[i])==0)returni;}六、运行结果:七、实验运行情况分析(包括算法、运行结果、运行环境等问题的讨论)。