[理学]数据结构实训全国交通咨询模拟.doc

学生实训报告实训名称： 数据结构实训指导教师：姓名： 学号： 班级： 日期： 一、实训项目项目名称：全国交通咨询模拟二、实训的目的1.熟悉图数据结构;2.掌握图的顺序存储结构邻接表;3.掌握最短路径算法4.上机调试程序,掌握查错、排错使程序能正确运行。三实训要求1.每个人独立完成实训项目，相互之间可以交流，不能抄袭2.实训的成果包括程序代码和报告3.程序代码要有注释和说明三、实验的环境:1.硬件环境: PC机2.软件环环境:Windows2000 +Visual C+6四、算法描述: 建立图的数据结构，采用邻接矩阵作为其存储结构。存储以上的全国主要城市的交通信息。通过软件模拟的方法实现：给定出发点和终点，求出它们之间的最短路径，并给出最短路径的线路。五、源程序清单:#include #include#define VEX_NUM 26#define MAXINT 1000000typedef struct graph char cityVEX_NUM10; int arcsVEX_NUMVEX_NUM;Mgraph;void CreatGraph(Mgraph *G,int e);void Dijkstra(Mgraph *Gn, int v0,int path,int dist);void PutPath(Mgraph *g,int v0,int v1,int p,int d);int index(char s,Mgraph *g);void main() Mgraph *g; int i; int e; int v0,v1; char sr10,dt10; int distVEX_NUM; int pathVEX_NUM; g=new Mgraph; 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);void CreatGraph(Mgraph *G,int e) int i,j,k,cost; printf(输入城市名称n); for(i=0;icityi); for(i=0;iVEX_NUM;i+) for(j=0;jarcsij=MAXINT; printf(输入城市之间的距离n); for(k=0;karcsij=cost; G-arcsji=cost; void Dijkstra(Mgraph *Gn, int v0,int path,int dist) int sVEX_NUM; int v; int w; int i,j,k; int min; for(v=0; varcsv0v; if(distvMAXINT) pathv=v0; else pathv=-1; distv0=0;sv0=1; for(i=1;iVEX_NUM -1;i+) min=MAXINT; for(w=0;wVEX_NUM;w+) if(!sw & distwmin) v=w; min=distw; sv=1; for(j=0;jarcsvjarcsvj; pathj=v; void PutPath(Mgraph *g,int v0,int v1,int p,int d) int k; int next; int top=0; int st20; if(dv1%s:没有路径n,g-cityv0,g-cityv1); return; sttop+=v0; while(top) next=st-top; if(top!=0) printf(%s-,g-citynext); else printf(%sn,g-citynext); printf(两个城市之间的最短距离为：%dn,dv1);int index(char s