数据结构实验三图的应用数据结构实验三图的应用（代码&测试界面）//Traffic_Inquiry.h#include <stdio.h>#include <stdlib.h>#define FINITY 999 //用999代表无穷大#define M 20 //城市最大个数typedef struct { //邻接矩阵类型定义char name[8];}CityNode; //城市信息结点的结构体(顶点值类型)typedef int distype; //权值类型-距离typedef int costype; //权值类型-费用typedef struct {CityNode citys[M]; //顶点信息域distype dis[M][M]; //领接矩阵-距离costype cos[M][M]; //邻接矩阵-费用int n, e; //图中顶点总数与边数}Mgraph;//建立图的邻接矩阵存储结构void CreateGraph(Mgraph *g){int i, j, k;double d, c;printf("请输入城市数与路径数：");scanf("%d %d",&g->n, &g->e);for(i=0; i<g->n; i++) { //读入图的顶点数printf("请输入第%d个城市名称：",i);scanf("%s",g->citys[i].name);}for(i=0; i<g->n; i++) { //初始化邻接矩阵for(j=0; j<g->n; 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;}}}printf("\n城市名称录入完毕，录入结果:\n\t");for(i=0; i<g->n; i++) {printf("%d->%s\t",i,g->citys[i].name);}printf("\n录入路径的权值信息，示例：0 1 34 40");printf("代表%s到%s的距离为34千米，费用为40元\n",g->citys[0].name,g->citys[1].name);for(k=0; k<g->e; 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算法求解单源最短路径typedef enum{FALSE,TRUE} boolean; //FALSE为0，TRUE为1void dijkstra(Mgraph g, int v0,const int q) //函数参数：图的领接矩阵g；源点v0；{int d[M];//权值（距离或费用）向量类型int p[M];//路径类型boolean final[M]; //表示当前元素是否已经求出最短路径int i,k,v,min;//第一步，初始化集合s与距离向量dfor (v=0; v<g.n; v++){final[v]=FALSE;if(q) d[v]=g.dis[v0][v];else d[v]=g.cos[v0][v];if (d[v]<FINITY && d[v]!=0)p[v]=v0; else p[v]=-1; //v无前驱}final[v0]=TRUE; d[v0]=0; //初始时s中只有v0一个结点//第二步，依次找出n-1个结点加入s中for(i=1; i<g.n; i++){min=FINITY;for(k=0;k<g.n;++k) //找最小边入结点if(!final[k]&&d[k]<min) //！final[k]表示k还在V-S中{v=k;min=d[k];}if(min<FINITY){if(q) printf("[ %s ]到[ %s ]的最短距离为:%d千米\n",g.citys[v0].name,g.citys[v].name,min);else printf("[ %s ]到[ %s ]的最小费用为:%d元\n",g.citys[v0].name,g.citys[v].name,min);}else if(min==FINITY) return;final[v]=TRUE; //v加入S//第三步，修改V-S中各节点的距离for(k=0;k<g.n;++k)if(!final[k]&&(min+g.dis[v][k]<d[k])){d[k]=min+g.dis[v][k];p[k]=v;}}}void floyd(Mgraph g,int q) //Floyd方法求所有顶点对间的最短路径(q用于判断参与算法的是距离还是费用){int e[M][M]; //权值（距离或费用）向量类型int p[M][M]; //路径类型int i, j, k;if(q) memcpy(e,g.dis,M*M*sizeof(int));else memcpy(e,g.cos,M*M*sizeof(int));for(i=0;i<g.n;i++) //初始化for(j=0;j<g.n;j++){if(i!=j && e[i][j]<FINITY) p[i][j]=i;else p[i][j]=-1;}for(k=0;k<g.n;k++) //递推求解每一对顶点间的最短距离{for(i=0;i<g.n;i++)for(j=0;j<g.n;j++){if(e[i][j]>(e[i][k]+e[k][j])){e[i][j]=e[i][k]+e[k][j];p[i][j]=k;}}}printf("┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄\n");for(i=0;i<g.n;i++){for(j=0;j<g.n;j++){if(i!=j&&e[i][j]!=0&&e[i][j]<FINITY)if(q) printf("[ %s ]到[ %s ]的最短距离为:%dkm。

\n",g.citys[i].name,g.citys[j].name,e[i][j]);else printf("[ %s ]到[ %s ]的最小费用为:%d元。

\n",g.citys[i].name,g.citys[j].name,e[i][j]);}printf("┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄\n");}}void refer(Mgraph g, int *v0){for(int i=0; i<g.n; i++){printf("%d->%s\t",i,g.citys[i].name);}printf("\n请输入查询城市序号:");scanf("%d",v0);if(!(*v0<g.n)){printf("你的输入有误!\n");refer(g,v0);}}int menu () {int set;printf("\t ╔═════╗\n");printf("\t ╔═════╣操作目录╠═════╗\n");printf("\t╓┃╚═════╝┃\n");printf("\t 欢┃⊙1.查询某地到它市最短路径┃\n");printf("\t 迎┃┃\n");printf("\t 使┃⊙2.查询某地到它市最小费用┃\n");printf("\t 用┃┃\n");printf("\t 交┃⊙3.显示各大城市间最短路径┃\n");printf("\t 通┃┃\n");printf("\t 查┃⊙4.显示各大城市间最小费用┃\n");printf("\t 询┃┃\n");printf("\t 系┃⊙5.进入管理员模式修改数据┃\n");printf("\t 统┃┃\n");printf("\t ╜┃⊙6.退出交通查询及管理系统┃\n");printf("\t ┃┃\n");printf("\t ╚═════════════════╝\n");printf("\n请根据你的需求选择操作:");scanf("%d",&set);printf("\n");return set;}//main.c#include <stdio.h>#include <stdlib.h>#include <string.h>#include "Traffic_Inquiry.h"int main() {int v0;int set=1;Mgraph g;{ //默认交通图g.n=8; g.e=11;for(int i=0; i<g.n; i++) { //初始化邻接矩阵for(int j=0; j<g.n; 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;}}}strcpy(g.citys[0].name,"太原"); strcpy(g.citys[1].name,"成都");strcpy(g.citys[2].name,"上海"); strcpy(g.citys[3].name,"北京");strcpy(g.citys[4].name,"深圳"); strcpy(g.citys[5].name,"重庆");strcpy(g.citys[6].name,"杭州"); strcpy(g.citys[7].name,"厦门");g.cos[0][1]=g.cos[1][0]=99; g.dis[0][1]=g.dis[1][0]=19;g.cos[0][3]=g.cos[3][0]=12; g.dis[0][3]=g.dis[3][0]=51;g.cos[1][2]=g.cos[2][1]=54; g.dis[1][2]=g.dis[2][1]=14;g.cos[1][7]=g.cos[7][1]=123; g.dis[1][7]=g.dis[7][1]=13;g.cos[2][4]=g.cos[4][2]=201; g.dis[2][4]=g.dis[4][2]=61;g.cos[2][7]=g.cos[7][2]=15; g.dis[2][7]=g.dis[7][2]=25;g.cos[3][6]=g.cos[6][3]=77; g.dis[3][6]=g.dis[6][3]=77;g.cos[3][5]=g.cos[5][3]=45; g.dis[3][5]=g.dis[5][3]=15;g.cos[4][5]=g.cos[5][4]=14; g.dis[4][5]=g.dis[5][4]=17;g.cos[7][6]=g.cos[6][7]=25; g.dis[7][6]=g.dis[6][7]=87;g.cos[7][5]=g.cos[5][7]=66; g.dis[7][5]=g.dis[5][7]=12;}while(set){switch(menu()){case 1:refer(g,&v0);dijkstra(g,v0,1);break;case 2:refer(g,&v0);dijkstra(g,v0,0);break;case 3:floyd(g,1);break; //距离case 4:floyd(g,0);break; //费用case 5:CreateGraph(&g);break;case 6:set=0;printf("\t\t\t\t欢迎下次使用!\n");break;default:printf("无该选项对应的操作！\n");}system("pause");system("cls");}return 0;}测试界面在下一页1507084143 刘安光1.主界面2.功能1-查询某地到它市最短路径（以太原为例）3.功能2-查询某地到它市最小费用（以太原为例）4.功能3-显示各大城市间最短路径（截图为局部画面）5.功能4-显示各大城市间最小费用（截图为局部画面）6.功能5-进入管理员模式修改数据7.一些异常处理8.退出。