数据结构实验三图的应用(9页).doc
-数据结构实验三 图的应用-第 9 页数据结构实验三 图的应用（代码&测试界面）#include <stdio.h>#include <stdlib.h>#define FINITY 999 /用999代表无穷大 #define M 20 /城市最大个数 typedef struct /邻接矩阵类型定义 char name8;CityNode; /城市信息结点的结构体(顶点值类型)typedef int distype; /权值类型-距离 typedef int costype; /权值类型-费用 typedef struct CityNode citysM; /顶点信息域 distype disMM; /领接矩阵-距离costype cosMM; /邻接矩阵-费用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->citysi.name);for(i=0; i<g->n; i+) /初始化邻接矩阵 for(j=0; j<g->n; j+) if(i=j) g->disij=0;g->cosij=0;else g->disij=FINITY;g->cosij=FINITY; printf("n城市名称录入完毕，录入结果:nt"); for(i=0; i<g->n; i+) printf("%d->%st",i,g->citysi.name); printf("n录入路径的权值信息，示例：0 1 34 40"); printf("代表%s到%s的距离为34千米，费用为40元n",g->citys0.name,g->citys1.name);for(k=0; k<g->e; k+) /读入网络中的边scanf("%d %d %lf %lf",&i, &j, &d, &c);g->disij=g->disji=d;g->cosij=g->cosji=c;/Dijkstra算法求解单源最短路径 typedef enumFALSE,TRUE boolean; /FALSE为0，TRUE为1 void dijkstra(Mgraph g, int v0,const int q) /函数参数：图的领接矩阵g；源点v0；int dM;/权值（距离或费用）向量类型int pM;/路径类型boolean finalM; /表示当前元素是否已经求出最短路径int i,k,v,min;/第一步，初始化集合s与距离向量dfor (v=0; v<g.n; v+)finalv=FALSE;if(q) dv=g.disv0v;else dv=g.cosv0v;if (dv<FINITY && dv!=0)pv=v0; else pv=-1; /v无前驱finalv0=TRUE; dv0=0; /初始时s中只有v0一个结点/第二步，依次找出n-1个结点加入s中for(i=1; i<g.n; i+)min=FINITY;for(k=0;k<g.n;+k) /找最小边入结点 if(!finalk&&dk<min) /！finalk表示k还在V-S中 v=k;min=dk;if(min<FINITY)if(q) printf(" %s 到 %s 的最短距离为:%d千米n",g.citysv0.name,g.citysv.name,min);else printf(" %s 到 %s 的最小费用为:%d元n",g.citysv0.name,g.citysv.name,min);else if(min=FINITY) return;finalv=TRUE; /v加入S/第三步，修改V-S中各节点的距离for(k=0;k<g.n;+k)if(!finalk&&(min+g.disvk<dk)dk=min+g.disvk;pk=v; void floyd(Mgraph g,int q) /Floyd方法求所有顶点对间的最短路径(q用于判断参与算法的是距离还是费用) int eMM; /权值（距离或费用）向量类型 int pMM; /路径类型 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 && eij<FINITY) pij=i; else pij=-1;for(k=0;k<g.n;k+) /递推求解每一对顶点间的最短距离for(i=0;i<g.n;i+)for(j=0;j<g.n;j+) if(eij>(eik+ekj) eij=eik+ekj; pij=k; printf("n");for(i=0;i<g.n;i+) for(j=0;j<g.n;j+) if(i!=j&&eij!=0&&eij<FINITY) if(q) printf(" %s 到 %s 的最短距离为:%dkm。n",g.citysi.name,g.citysj.name,eij);else printf(" %s 到 %s 的最小费用为:%d元。n",g.citysi.name,g.citysj.name,eij);printf("n");void refer(Mgraph g, int *v0)for(int i=0; i<g.n; i+)printf("%d->%st",i,g.citysi.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; #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.disij=0;g.cosij=0;else g.disij=FINITY;g.cosij=FINITY; strcpy(g.citys0.name,"太原"); strcpy(g.citys1.name,"成都");strcpy(g.citys2.name,"上海"); strcpy(g.citys3.name,"北京");strcpy(g.citys4.name,"深圳"); strcpy(g.citys5.name,"重庆");strcpy(g.citys6.name,"杭州"); strcpy(g.citys7.name,"厦门");g.cos01=g.cos10=99; g.dis01=g.dis10=19;g.cos03=g.cos30=12; g.dis03=g.dis30=51;g.cos12=g.cos21=54; g.dis12=g.dis21=14; g.cos17=g.cos71=123; g.dis17=g.dis71=13;g.cos24=g.cos42=201; g.dis24=g.dis42=61;g.cos27=g.cos72=15; g.dis27=g.dis72=25;g.cos36=g.cos63=77; g.dis36=g.dis63=77;g.cos35=g.cos53=45; g.dis35=g.dis53=15;g.cos45=g.cos54=14; g.dis45=g.dis54=17;g.cos76=g.cos67=25; g.dis76=g.dis67=87;g.cos75=g.cos57=66; g.dis75=g.dis57=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("tttt欢迎下次使用!n");break;default:printf("无该选项对应的操作！n"); system("pause");system("cls");return 0;测试界面在下一页1507084143 刘安光2. 功能1-查询某地到它市最短路径（以太原为例）3.功能2-查询某地到它市最小费用（以太原为例）4. 功能3-显示各大城市间最短路径（截图为局部画面）5.功能4-显示各大城市间最小费用（截图为局部画面）
