学生实训报告 实训名称：数据结构实训指导教师：姓名：学号：班级：日期：一、实训项目项目名称：全国交通咨询模拟二、实训的目的1.熟悉图数据结构;2.掌握图的顺序存储结构—邻接表;3.掌握最短路径算法4.上机调试程序,掌握查错、排错使程序能正确运行。三．实训要求1.每个人独立完成实训项目，相互之间可以交流，不能抄袭2.实训的成果包括程序代码和报告3.程序代码要有注释和说明三、实验的环境:1.硬件环境:PC机2.软件环环境:Windows2000+VisualC++6四、算法描述:建立图的数据结构，采用邻接矩阵作为其存储结构。存储以上的全国主要城市的交通信息。通过软件模拟的方法实现：给定出发点和终点，求出它们之间的最短路径，并给出最短路径的线路。五、源程序清单:#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);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;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;inti,j,k;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;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;i<VEX_NUM;i++)if(strcmp(s,g->city[i])==0)returni;}六、运行结果:七、实验运行情况分析(包括算法、运行结果、运行环境等问题的讨论)。
本文档为【数据结构实训报告】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483