数据结构实验十讲课教案.doc

《数据结构实验十讲课教案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、如下#include#includetypedefstruct{int*vexs;int**arcs;intvexnum;}ylx_graph;typedefstruct{intadjvex;intlowcost;}ylx_markedg;ylx_graph*ylx_initgraph(){inti,j;ylx_graph*g;g=(ylx_graph*)malloc(sizeof(ylx_graph));g->vexnum=25;g->vexs=(int*)malloc(g->vexnum*sizeof(int

3、));g->arcs=(int**)malloc(g->vexnum*sizeof(int*));for(i=0;ivexnum;i++)g->arcs[i]=(int*)malloc(g->vexnum*sizeof(int));for(i=0;ivexnum;i++)for(j=0;jvexnum;j++){g->arcs[i][j]=0;}returng;}voidylx_creategraph(ylx_graph*g){inti,j;for(i=0;ivexnum;i++)g->vexs[i]=i;g->arc

4、s[0][9]=1892;g->arcs[1][3]=242;g->arcs[2][4]=668;g->arcs[2][9]=1145;g->arcs[3][5]=305;g->arcs[4][6]=137;g->arcs[4][11]=695;g->arcs[5][6]=704;g->arcs[5][7]=397;g->arcs[6][12]=674;g->arcs[8][9]=216;g->arcs[9][10]=676;g->arcs[10][11]=511;g->arcs[10][13]=842;g->arcs[11][12]=349;g->

5、arcs[11][14]=534;g->arcs[12][15]=651;g->arcs[13][16]=110;g->arcs[13][17]=967;g->arcs[14][18]=409;g->arcs[15][19]=825;g->arcs[16][17]=639;g->arcs[17][18]=902;g->arcs[17][21]=607;g->arcs[18][19]=367;g->arcs[18][21]=672;g->arcs[18][23]=675;g->arcs[19][20]=622;收集于网络，如有侵权请联系管理员删除精品文

6、档g->arcs[21][22]=255;g->arcs[23][24]=140;for(i=0;ivexnum;i++)for(j=i;jvexnum;j++)if(g->arcs[i][j])g->arcs[j][i]=g->arcs[i][j];}voidylx_printgraph(ylx_graph*g){intx,y;printf("城市间连通图为:");for(x=0;xvexnum;x++)for(y=x;yvexnum;y++)if(g->arcs[x][y])printf("(%d,%d)距

7、离:%dt",x,y,g->arcs[x][y]);}intylx_selectnearvex(ylx_markedg*mark,int*flag,intnum){intj;intnearestv;intlowcost=32767;for(j=0;j

8、,ylx_markedg*mark,intnearestv,intnum,int*flag){intj;fo