第1页共8页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第1页共8页学生实训报告实训名称：数据结构实训指导教师：姓名：学号：班级：日期：一、实训项目项目名称：第2页共8页第1页共8页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第2页共8页全国交通咨询模拟二、实训的目的1.熟悉图数据结构;2.掌握图的顺序存储结构—邻接表;3.掌握最短路径算法4.上机调试程序,掌握查错、排错使程序能正确运行。三．实训要求1.每个人独立完成实训项目，相互之间可以交流，不能抄袭2.实训的成果包括程序代码和报告3.程序代码要有注释和说明三、实验的环境:1.硬件环境:PC机2.软件环环境:Windows2000+VisualC++6四、算法描述:第3页共8页第2页共8页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第3页共8页建立图的数据结构，采用邻接矩阵作为其存储结构。存储以上的全国主要城市的交通信息。通过软件模拟的方法实现：给定出发点和终点，求出它们之间的最短路径，并给出最短路径的线路。五、源程序清单:#include#include#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);第4页共8页第3页共8页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第4页共8页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;icity[i]);for(i=0;iarcs[i][j]=MAXINT;printf("输入城市之间的距离\n");for(k=0;karcs[i][j]=cost;G->arcs[j][i]=cost;}}voidDijkstra(Mgraph*Gn,intv0,intpath[],intdist[]){ints[VEX_NUM];intv;第5页共8页第4页共8页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第5页共8页intw;inti,j,k;intmin;for(v=0;varcs[v0][v];if(dist[v]arcs[v][j]arcs[v][j];path[j]=v;}}}voidPutPath(Mgraph*g,intv0,intv1,intp[],intd[]){intk;intnext;inttop=0;intst[20];if(d[v1]%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;icity[i])==0)returni;}六、运行结果:第7页共8页第6页共8页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第7页共8页七、实验运行情况分析(包括算法、运行结果、运行环境等问题的讨论)。第8页共8页第7页共8页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第8页共8页
