数据结构实验十

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

2、nclude <malloc.h>typedef structint *vexs; int *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

3、=(int*)malloc(g->vexnum*sizeof(int*); for(i=0;i<g->vexnum;i+) g->arcsi=(int*)malloc(g->vexnum*sizeof(int); for(i=0;i<g->vexnum;i+) for(j=0;j<g->vexnum;j+)g->arcsij=0; return g;void ylx_creategraph (ylx_graph *g)int i,j; for(i=0;i<g->vexnum;i+)g->vexsi=i; g->

4、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->arcs612=674; g->arcs89=216; g->arcs910=676; g->arcs1011=511;g->arcs1013=842; g->arcs1112=349;g->arcs1114=534; g->a

5、rcs1215=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=255;g->arcs2324=140; for(i=0;i<g->vexnum;i+) for(

6、j=i;j<g->vexnum;j+) if(g->arcsij) g->arcsji=g->arcsij;void ylx_printgraph (ylx_graph *g)int x,y; printf("n城市间连通图为:n"); for(x=0;x<g->vexnum;x+) for(y=x;y<g->vexnum;y+) if(g->arcsxy)printf("(%d,%d)距离:%dt",x,y,g->arcsxy);int ylx_selectnearvex (ylx_ma

7、rkedg *mark,int *flag,int num)int j; int nearestv; int lowcost=32767; for(j=0;j<num;j+)if(flagj!=1&&markj.lowcost<lowcost)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

8、;j<num;j+)if(g->arcsnearestvj>0)if(flagj!=1)if(markj.lowcost>(marknearestv.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->

9、vexnum;flag=(int *)malloc(num)*sizeof(int);flagstart=1; for(i=0;i<g->vexnum;i+)marki.adjvex=start; if( g->arcsstarti>0)marki.lowcost=g->arcsstarti; elsemarki.lowcost=32767; for(i=1;i<g->vexnum;i+)nearestv=ylx_selectnearvex (mark,flag,num); ylx_markothervex (g,mark,nearestv,num,f

10、lag);void ylx_printshortpath (ylx_graph *g,ylx_markedg *mark,int start)int i,j,k,path25; for(i=0;i<g->vexnum;i+)if(i!=start) printf("从%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("%

11、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_mark