数据结构实验十

1、一、实验目的1.使学生熟悉最短路径算法实现。2.掌握带权图的存储结构和处理方法。二、实验环境 1.硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； 2.软件：DOS或Windows操作系统+Turbo c;三、实验要求 1.能够独立完成带权图的存储和最短路径的生成。四、实验内容 1.现在假设我国铁路交通图如下（权值表示距离），请用合适的存储结构将下图存储到计算机中方便进行处理。 2.现在我想以最小的代价从徐州出发到达其他目的地，请用Dijkstra算法实现我的要求的路径。五、代码如下#include #include typedef structint *vexs; int

2、*arcs; int vexnum;ylx_graph ;typedef structint adjvex; int lowcost;ylx_markedg ;ylx_graph *ylx_initgraph ()int i,j;ylx_graph *g; g=(ylx_graph *)malloc(sizeof(ylx_graph ); g-vexnum=25; g-vexs=(int*)malloc(g-vexnum*sizeof(int); g-arcs=(int*)malloc(g-vexnum*sizeof(int*); for(i=0;ivexnum;i+) g-arcsi=(in

3、t*)malloc(g-vexnum*sizeof(int); for(i=0;ivexnum;i+) for(j=0;jvexnum;j+)g-arcsij=0; return g;void ylx_creategraph (ylx_graph *g)int i,j; for(i=0;ivexnum;i+)g-vexsi=i; g-arcs09=1892; g-arcs13=242; g-arcs24=668; g-arcs29=1145; g-arcs35=305; g-arcs46=137; g-arcs411=695; g-arcs56=704; g-arcs57=397; g-arc

4、s612=674; g-arcs89=216; g-arcs910=676; g-arcs1011=511;g-arcs1013=842; g-arcs1112=349;g-arcs1114=534; g-arcs1215=651;g-arcs1316=110; g-arcs1317=967;g-arcs1418=409; g-arcs1519=825;g-arcs1617=639; g-arcs1718=902;g-arcs1721=607; g-arcs1819=367;g-arcs1821=672; g-arcs1823=675;g-arcs1920=622; g-arcs2122=25

5、5;g-arcs2324=140; for(i=0;ivexnum;i+) for(j=i;jvexnum;j+) if(g-arcsij) g-arcsji=g-arcsij;void ylx_printgraph (ylx_graph *g)int x,y; printf(n城市间连通图为:n); for(x=0;xvexnum;x+) for(y=x;yvexnum;y+) if(g-arcsxy)printf(%d,%d)距离:%dt,x,y,g-arcsxy);int ylx_selectnearvex (ylx_markedg *mark,int *flag,int num)int

6、 j; int nearestv; int lowcost=32767; for(j=0;jnum;j+)if(flagj!=1&markj.lowcostlowcost)nearestv=j; lowcost=markj.lowcost;flagnearestv=1; return nearestv;void ylx_markothervex (ylx_graph *g,ylx_markedg *mark,int nearestv,int num,int*flag)int j; for(j=0;jarcsnearestvj0)if(flagj!=1)if(markj.lowcost(mark

7、nearestv.lowcost+g-arcsnearestvj)markj.lowcost= marknearestv.lowcost+g-arcsnearestvj;markj.adjvex=nearestv;void ylx_shortestpath (ylx_graph *g,ylx_markedg *mark,int start)int i,num;int *flag;int nearestv;num=g-vexnum;flag=(int *)malloc(num)*sizeof(int);flagstart=1; for(i=0;ivexnum;i+)marki.adjvex=st

8、art; if( g-arcsstarti0)marki.lowcost=g-arcsstarti; elsemarki.lowcost=32767; for(i=1;ivexnum;i+)nearestv=ylx_selectnearvex (mark,flag,num); ylx_markothervex (g,mark,nearestv,num,flag);void ylx_printshortpath (ylx_graph *g,ylx_markedg *mark,int start)int i,j,k,path25; for(i=0;ivexnum;i+)if(i!=start) p

9、rintf(从%d到%d最短路径为:%d; ,start,i,marki.lowcost); printf(途经:); k=0;pathk=i; j=marki.adjvex; while(j!=start)path+k=j; j=markj.adjvex; printf(%d,start); for(j=k;j=0;j-)printf(,%d,pathj); printf(.n);void main() int city; ylx_graph *g;ylx_markedg *mark; g=ylx_initgraph (); ylx_creategraph (g); printf(城市对应编号:n); printf(0-乌鲁木齐 1-哈尔滨 2-呼和浩特 3-长春 4-北京 n); printf( 5-沈阳 6-天津 7-大连 8-西宁 9-兰州 10-西安 11-郑州n); printf(12-徐州 13-成都 14-武汉 15-上海 16-昆明 17-贵阳 18-株州n); printf(19-南昌 20-福州 21-柳州 22-南宁 23-广州 24-深圳.n); ylx_printgraph (g); mark=(ylx_ma