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

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

学生实训报告

实训名称：数据结构实训指导教师：姓名：学号：班级：日期：一、实训项目项目名称：数据结构实训全国交通咨询模拟全文共7页，当前为第1页。全国交通咨询模拟数据结构实训全国交通咨询模拟全文共7页，当前为第1页。二、实训的目的1.熟悉图数据结构;2.掌握图的顺序存储结构—邻接表;3.掌握最短路径算法4.上机调试程序,掌握查错、排错使程序能正确运行。三．实训要求1.每个人独立完成实训项目，相互之间可以交流，不能抄袭2.实训的成果包括程序代码和报告3.程序代码要有注释和说明三、实验的环境:1.硬件环境:PC机2.软件环环境:Windows2000+VisualC++6四、算法描述:数据结构实训全国交通咨询模拟全文共7页，当前为第2页。数据结构实训全国交通咨询模拟全文共7页，当前为第2页。建立图的数据结构，采用邻接矩阵作为其存储结构。存储以上的全国主要城市的交通信息。通过软件模拟的方法实现：给定出发点和终点，求出它们之间的最短路径，并给出最短路径的线路。五、源程序清单:#include<stdio.h>#include<string.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);数据结构实训全国交通咨询模拟全文共7页，当前为第3页。voidmain()数据结构实训全国交通咨询模拟全文共7页，当前为第3页。{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;i<VEX_NUM;++i)scanf("%s",G->city[i]);for(i=0;i<VEX_NUM;i++)for(j=0;j<VEX_NUM;j++)G->arcs[i][j]=MAXINT;printf("输入城市之间的距离\n");for(k=0;k<e;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;数据结构实训全国交通咨询模拟全文共7页，当前为第4页。inti,j,k;数据结构实训全国交通咨询模拟全文共7页，当前为第4页。intmin;for(v=0;v<VEX_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;i<VEX_NUM-1;i++){min=MAXINT;for(w=0;w<VEX_NUM;w++)if(!s[w]&&dist[w]<min){v=w;min=dist[w];}s[v]=1;for(j=0;j<VEX_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;数据结构实训全国交通咨询模拟全文共7页，当前为第5页。next=p[next];数据结构实训全国交通咨询模拟全文共7页，当前为第5页。}}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;i<VEX_NUM;i++)if(strcmp(s,g->city[i])==0)returni;}数据结构实训全国交