数据结构实验三图的应用.doc

《数据结构实验三图的应用.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.数据结构实验三图的应用（代码&测试界面）//Traffic_Inquiry.h#include#include#defineFINITY999//用999代表无穷大#defineM20//城市最大个数typedefstruct{//邻接矩阵类型定义charname[8];}CityNode;//城市信息结点的结构体(顶点值类型)typedefintdistype;//权值类型-距离typedefintcostype;//权值类型-费用typedefstruct{CityNodecitys[M];//顶点信息域dis

2、typedis[M][M];//领接矩阵-距离costypecos[M][M];//邻接矩阵-费用intn,e;//图中顶点总数与边数}Mgraph;//建立图的邻接矩阵存储结构voidCreateGraph(Mgraph*g){inti,j,k;doubled,c;printf("请输入城市数与路径数：");scanf("%d%d",&g->n,&g->e);for(i=0;in;i++){//读入图的顶点数printf("请输入第%d个城市名称：",i);scanf("%s",g->citys[i].name);}for(i=0;in

3、;i++){//初始化邻接矩阵for(j=0;jn;j++){if(i==j){g->dis[i][j]=0;g->cos[i][j]=0;}else{g->dis[i][j]=FINITY;g->cos[i][j]=FINITY;}}word范文.}printf("城市名称录入完毕，录入结果:t");for(i=0;in;i++){printf("%d->%st",i,g->citys[i].name);}printf("录入路径的权值信息，示例：013440");printf("代表%s到%s的距离为34千米，费用为4

4、0元",g->citys[0].name,g->citys[1].name);for(k=0;ke;k++){//读入网络中的边scanf("%d%d%lf%lf",&i,&j,&d,&c);g->dis[i][j]=g->dis[j][i]=d;g->cos[i][j]=g->cos[j][i]=c;}}//Dijkstra算法求解单源最短路径typedefenum{FALSE,TRUE}boolean;//FALSE为0，TRUE为1voiddijkstra(Mgraphg,intv0,constintq)//函数参数：图的领接矩阵g；源

5、点v0；{intd[M];//权值（距离或费用）向量类型intp[M];//路径类型booleanfinal[M];//表示当前元素是否已经求出最短路径inti,k,v,min;//第一步，初始化集合s与距离向量dfor(v=0;v

6、，依次找出n-1个结点加入s中for(i=1;i

7、.citys[v].name,min);}elseif(min==FINITY)return;final[v]=TRUE;//v加入S//第三步，修改V-S中各节点的距离for(k=0;k

8、nti,j,k;if(q)memcpy(e,g.dis,M*M*sizeof(i