数据结构实验三图的应用

. . . .

数据结构实验三 图的应用（代码&测试界面）

//Traffic_Inquiry.h #include #include

#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(\

for(i=0; in; i++) { //读入图的顶点数 printf(\请输入第%d个城市名称：\ scanf(\ } for(i=0; in; 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; }

}

. 学习.资料.

. . . .

}

printf(\城市名称录入完毕，录入结果:\\n\\t\

for(i=0; in; i++) { printf(\ }

printf(\录入路径的权值信息，示例：0 1 34 40\ printf(\代表%s到%s的距离为34千米，费用为40元\\n\ for(k=0; ke; k++) { //读入网络中的边

scanf(\ 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为1

void 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与距离向量d

for (v=0; v

}

final[v0]=TRUE; d[v0]=0; //初始时s中只有v0一个结点 //第二步，依次找出n-1个结点加入s中

for(i=1; i

{ v=k;min=d[k]; }

if(min

. 学习.资料.

. . . .

if(q) printf(\到[ %s ]的最短距离为:%d千米

\\n\ else printf(\到[ %s ]的最小费用为:%d元\\n\ } else if(min==FINITY) return; final[v]=TRUE; //v加入S //第三步，修改V-S中各节点的距离

for(k=0;k

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

for(j=0;j

for(k=0;k

for(i=0;i(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

if(q) printf(\到[ %s ]的最短距离为:%dkm。

\\n\ else printf(\到[ %s ]的最小费用为:%d元。\\n\ } printf(\┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄\\n\ } }

void refer(Mgraph g, int *v0){ for(int i=0; i

printf(\你的输入有误!\\n\

refer(g,v0); } }

int menu () { int set; printf(\ ╔═════╗\\n\ printf(\ ╔═════╣ 操作目录 ╠═════╗\\n\ printf(\╓ ┃ ╚═════╝ ┃\\n\ printf(\ 欢 ┃ ⊙1.查询某地到它市最短路径 ┃\\n\ printf(\ 迎 ┃ ┃\\n\ printf(\ 使 ┃ ⊙2.查询某地到它市最小费用 ┃\\n\ printf(\ 用 ┃ ┃\\n\ printf(\ 交 ┃ ⊙3.显示各大城市间最短路径 ┃\\n\ printf(\ 通 ┃ ┃\\n\ printf(\ 查 ┃ ⊙4.显示各大城市间最小费用 ┃\\n\ printf(\ 询 ┃ ┃\\n\ printf(\ 系 ┃ ⊙5.进入管理员模式修改数据 ┃\\n\ printf(\ 统 ┃ ┃\\n\ printf(\ ╜ ┃ ⊙6.退出交通查询及管理系统 ┃\\n\

. 学习.资料.

. . . .

printf(\ ┃ ┃\\n\ printf(\ ╚═════════════════╝\\n\ printf(\请根据你的需求选择操作:\

scanf(\ printf(\ return set; }

//main.c

#include #include #include

#include \.h\int main() { int v0; int set=1; Mgraph g; { //默认交通图 g.n=8; g.e=11;

for(int i=0; i

for(int j=0; j

strcpy(g.citys[0].name,\ strcpy(g.citys[2].name,\ strcpy(g.citys[4].name,\ strcpy(g.citys[6].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;

. 学习.资料.