数据结构实验三图的应用.docx
- 文档编号:5561877
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:14
- 大小:219.06KB
数据结构实验三图的应用.docx
《数据结构实验三图的应用.docx》由会员分享,可在线阅读,更多相关《数据结构实验三图的应用.docx(14页珍藏版)》请在冰点文库上搜索。
数据结构实验三图的应用
数据结构实验三图的应用(代码&测试界面)
//Traffic_Inquiry.h
#include
#include
#defineFINITY999//用999代表无穷大
#defineM20//城市最大个数
typedefstruct{//邻接矩阵类型定义
charname[8];
}CityNode;//城市信息结点的结构体(顶点值类型)
typedefintdistype;//权值类型-距离
typedefintcostype;//权值类型-费用
typedefstruct{
CityNodecitys[M];//顶点信息域
distypedis[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;i
printf("请输入第%d个城市名称:
",i);
scanf("%s",g->citys[i].name);
}
for(i=0;i
for(j=0;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
printf("%d->%s\t",i,g->citys[i].name);
}
printf("\n录入路径的权值信息,示例:
013440");
printf("代表%s到%s的距离为34千米,费用为40元\n",g->citys[0].name,g->citys[1].name);
for(k=0;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为1
voiddijkstra(Mgraphg,intv0,constintq)//函数参数:
图的领接矩阵g;源点v0;
{
intd[M];//权值(距离或费用)向量类型
intp[M];//路径类型
booleanfinal[M];//表示当前元素是否已经求出最短路径
inti,k,v,min;
//第一步,初始化集合s与距离向量d
for(v=0;v { final[v]=FALSE; if(q)d[v]=g.dis[v0][v]; elsed[v]=g.cos[v0][v]; if(d[v] =0) p[v]=v0;elsep[v]=-1;//v无前驱 } final[v0]=TRUE;d[v0]=0;//初始时s中只有v0一个结点 //第二步,依次找出n-1个结点加入s中 for(i=1;i { min=FINITY; for(k=0;k if(! final[k]&&d[k] final[k]表示k还在V-S中 { v=k;min=d[k]; } if(min if(q)printf("[%s]到[%s]的最短距离为: %d千米\n",g.citys[v0].name,g.citys[v].name,min); elseprintf("[%s]到[%s]的最小费用为: %d元\n",g.citys[v0].name,g.citys[v].name,min); } elseif(min==FINITY)return; final[v]=TRUE;//v加入S //第三步,修改V-S中各节点的距离 for(k=0;k if(! final[k]&&(min+g.dis[v][k] { d[k]=min+g.dis[v][k]; p[k]=v; } } } voidfloyd(Mgraphg,intq)//Floyd方法求所有顶点对间的最短路径(q用于判断参与算法的是距离还是费用) { inte[M][M];//权值(距离或费用)向量类型 intp[M][M];//路径类型 inti,j,k; if(q)memcpy(e,g.dis,M*M*sizeof(int)); elsememcpy(e,g.cos,M*M*sizeof(int)); for(i=0;i for(j=0;j { if(i! =j&&e[i][j] elsep[i][j]=-1; } for(k=0;k { for(i=0;i for(j=0;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 for(j=0;j if(i! =j&&e[i][j]! =0&&e[i][j] if(q)printf("[%s]到[%s]的最短距离为: %dkm。 \n",g.citys[i].name,g.citys[j].name,e[i][j]); elseprintf("[%s]到[%s]的最小费用为: %d元。 \n",g.citys[i].name,g.citys[j].name,e[i][j]); } printf("┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄\n"); } } voidrefer(Mgraphg,int*v0){ for(inti=0;i printf("%d->%s\t",i,g.citys[i].name); } printf("\n请输入查询城市序号: "); scanf("%d",v0); if(! (*v0 printf("你的输入有误! \n"); refer(g,v0); } } intmenu(){ intset; 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"); returnset; } //main.c #include #include #include #include"Traffic_Inquiry.h" intmain(){ intv0; intset=1; Mgraphg; {//默认交通图 g.n=8;g.e=11; for(inti=0;i for(intj=0;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()){ case1: refer(g,&v0);dijkstra(g,v0,1);break; case2: refer(g,&v0);dijkstra(g,v0,0);break; case3: floyd(g,1);break;//距离 case4: floyd(g,0);break;//费用 case5: CreateGraph(&g);break; case6: set=0;printf("\t\t\t\t欢迎下次使用! \n");break; default: printf("无该选项对应的操作! \n"); } system("pause"); system("cls"); } return0; } 测试界面在下一页 1507084143安光 1.主界面 2.功能1-查询某地到它市最短路径(以为例) 3.功能2-查询某地到它市最小费用(以为例) 4.功能3-显示各大城市间最短路径(截图为局部画面) 5.功能4-显示各大城市间最小费用(截图为局部画面) 6.功能5-进入管理员模式修改数据 7.一些异常处理 8.退出
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 应用