数据结构-实验5-图的应用

实验报告开课学院及实验室：年月日学院年级、专业、班姓名学号实验课程名称数据构造成绩实验工程名称实验5图的应用指导教师一实验目的1、掌握图的根本概念和根本存储方法；2、掌握有关图的操作算法，并用高级语言实现；3、熟悉图的各种存储构造及其构造算法，理解实际问题的求解效率与采用何种存储构造及算法有着亲密联络；4、熟悉如何用图构造解决实际应用问题；5、培养数据抽象的设计才能和实际动手的综合才能，并进一步掌握完好应用系统的设计过程和方法。二实验原理图形构造是一种应用非常广泛的数据构造，它的应用已经浸透到语言学、逻辑学、物理、化学、电子、通信、数学、计算机科学等诸多学科领域。最短途径是指途径长度〔即路劲上边的权值之和〕最小的途径，一般讨论带权有向图，在实际应用中经常用于解决城市节点间运输代价最少或运输时间最短等问题。三实验内容请为珠江三角洲城市间设计与实现一个简单的交通咨询系统。根本要求：〔1〕设计简单的珠江三角洲城市间道路通行平面图，所含城市不少于10个。以图中顶点表示城市节点，存放城市名称、代号、简介等信息；以边表示通行道路，存放道路的途径长度。〔2〕提供图中任意城市的相关信息查询。〔3〕提供图中任意城市间的最短途径查询。四实验步骤1将珠江三角洲城市间的交通图抽象为无向带权图。〔要求给出一个设计方案〕2设计求图中任意结点间最短途径的算法。3编程实现。五实验方法1对问题进展需求分析，选取详细城市结点，通过调研获取城市间的交通网络，选取主要的通行道路抽象为图的无向带权边。2进展概要设计和详细设计，形成模块间的调用构造图和模块的算法。3编写程序，设计测试用例进展测试。4完成开发文档。六实验结果1需求分析：在中国城市，电子地图的认知度和使用率正在飞快递增，随着用户量不断增加，纸质地图逐渐被电子地图取而代之。在大中型城市，电子地图已经成为绝大多数用户出行前首选的参照工具和查询途径。电子地图强调准确性、简单易用以及查询速度。电子地图的另外一个特点是使用方便，无论是通过互联网还是手机都可以方便接触到并使用。出行前用电脑通过互联网地图规划道路、查找目的地，路上那么可以用手机连接无线网络，通过手机地图随时修正道路和辨识方向。2概要设计：3详细设计：4编程遇到的问题和调试分析：5用户手册：概述：简单的交通咨询系统功能： 1.珠三角地区交通查询； 2.珠三角地区各城市信息查询。使用说明： 1.翻开方法：翻开命令行窗口，进入map.exe文件所在目录〔如：cde:/map〕，输入map，进入程序。 2.构造地图信息，按提示输入map.txt. 3.交通查询功能的使用：输入1进入查询，按要求输入起点城市编号和终点城市编号，回车即可。 4.城市信息查询功能的使用：输入2进入查询，按要求输入城市编号，回车即可。6测试结果：7附录〔源程序清单〕#defineMAX_NAME9//顶点字符串的最大长度#defineMAX_INFO20//相关信息字符串的最大长度#defineMAX_MES300//顶点城市信息的最大长度typedefintVRType;structVertexType{charname[MAX_NAME];//城市名字charmes[MAX_MES];//城市信息};typedefcharInfoType;//c1.h(程序名)#include<string.h>#include<malloc.h>//malloc()等#include<limits.h>//INT_MAX等#include<stdio.h>//EOF(=^Z或F6),NULL#include<io.h>//eof()//函数结果状态代码#defineTRUE1#defineFALSE0typedefintStatus;//Status是函数的类型,其值是函数结果状态代码，如OK等typedefintBoolean;//Boolean是布尔类型,其值是TRUE或FALSE#defineINFINITYINT_MAX//用整型最大值代替∞#defineMAX_VERTEX_NUM26//最大顶点个数enumGraphKind{DG,DN,UDG,UDN};//{有向图,有向网,无向图,无向网}typedefstruct{VRTypeadj;//顶点关系类型。对无权图，//用1(是)或0(否)表示相邻否；//对带权图，那么为权值InfoType*info;//该弧相关信息的指针(可无)}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二维数组structMGraph{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量,原程序放城市名字,如今加上城市信息AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数GraphKindkind;//图的种类标志};//邻接矩阵存储构造的根本操作intLocateVex(MGraphG,charu[MAX_NAME]){//初始条件：图G存在，u和G中顶点有一样特征//操作结果：假设G中存在顶点u，那么返回该顶点在图中位置；否那么返回-1inti;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i].name)==0)returni;return-1;}//初始化无向图voidCreateFUDN(MGraph&G){//采用数组(邻接矩阵)表示法，由文件构造没有相关信息的无向网Ginti,j,k,w;charfilename[13];charva[MAX_NAME],vb[MAX_NAME];FILE*graphlist;printf("请输入数据文件名：");scanf("%s",filename);graphlist=fopen(filename,"r");//翻开数据文件，并以graphlist表示fscanf(graphlist,"%d",&G.vexnum);fscanf(graphlist,"%d",&G.arcnum);for(i=0;i<G.vexnum;++i)//构造顶点向量fscanf(graphlist,"%s",G.vexs[i].name);for(i=0;i<G.vexnum;++i)//初始化邻接矩阵for(j=0;j<G.vexnum;++j){G.arcs[i][j].adj=INFINITY;//网G.arcs[i][j].info=NULL;//没有相关信息}for(k=0;k<G.arcnum;++k){fscanf(graphlist,"%s%s%d",va,vb,&w);i=LocateVex(G,va);j=LocateVex(G,vb);G.arcs[i][j].adj=G.arcs[j][i].adj=w;//无向网}//读取城市信息数据for(i=0;i<G.vexnum;++i)//构造城市信息fscanf(graphlist,"%s",G.vexs[i].mes);fclose(graphlist);//关闭数据文件G.kind=UDN;}typedefintPathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];//3维数组typedefintDistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//2维数组//求有向网中各对顶点之间最短间隔的Floyd算法voidShortestPath_FLOYD(MGraphG,PathMatrixP,DistancMatrixD){//用Floyd算法求有向网G中各对顶点v和w之间的最短途径P[v][w]及其带权长度D[v][w]。intu,v,w,i;for(v=0;v<G.vexnum;v++)//各对结点之间初始途径及间隔for(w=0;w<G.vexnum;w++){D[v][w]=G.arcs[v][w].adj;//顶点v到顶点w的直接间隔for(u=0;u<G.vexnum;u++)P[v][w][u]=FALSE;//途径矩阵初值if(D[v][w]<INFINITY)//从v到w有直接途径P[v][w][v]=P[v][w][w]=TRUE;//由v到w的途径经过v和w两点}for(u=0;u<G.vexnum;u++)for(v=0;v<G.vexnum;v++)for(w=0;w<G.vexnum;w++)if(D[v][u]<INFINITY&&D[u][w]<INFINITY&&D[v][u]+D[u][w]<D[v][w]){//从v经u到w的一条途径更短D[v][w]=D[v][u]+D[u][w];//更新最短间隔for(i=0;i<G.vexnum;i++)P[v][w][i]=P[v][u][i]||P[u][w][i];//从v到w的途径经过从v到u和从u到w的所有途径}}//path()函数voidpath(MGraphG,PathMatrixP,inti,intj){//求由序号为i的起点城市到序号为j的终点城市最短途径沿途所经过的城市intk;intm=i;//起点城市序号赋给mprintf("依次经过的城市：\n");while(m!=j)//没到终点城市{G.arcs[m][m].adj=INFINITY;//对角元素赋值无穷大for(k=0;k<G.vexnum;k++)for(k=0;k<G.vexnum;k++)if(G.arcs[m][k].adj<INFINITY&&P[m][j][k])//m到k有直接通路，且k在m到j的最短途径上{printf("%s",G.vexs[m].name);G.arcs[m][k].adj=G.arcs[k][m].adj=INFINITY;//将直接通路设为不通m=k;//经过的城市序号赋给m，继续查找break;}}printf("%s\n",G.vexs[j].name);//输出终点城市}//主函数voidmain(){MGraphg;inti,j,q=1;intm;//查询城市信息有关PathMatrixp;//3维数组DistancMatrixd;//2维数组printf("数据文件名为map.txt\n");CreateFUDN(g);//通过文件构造无向网gfor(i=0;i<g.vexnum;i++)g.arcs[i][i].adj=0;//ShortestPath_FLOYD()要求对角元素值为0，因为两点一样，其间隔为0while(q){printf("请选择：1道路查询2城市信息查询0完毕\n");scanf("%d",&q);if(q){for(i=0;i<g.vexnum;i++){printf("%2d%-9s",i+1,g.vexs[i].name);if(i%6==5)//printf("\n");}if(q==2){printf("\n请输入你想要查询的城市：\n");scanf("%d",&m);printf("%s\n\n",g.vexs[m-1].mes);}else{printf("\n请输入要查询的起点城市代码终点城市代码:");scanf("%d%d",&i,&j);if(d[i-1][j-1]<INFINITY)//有通路{printf("%s到%s的最短间隔为%d\n",g.vexs[i-1].name,g.vexs[j-1].name,d[i-1][j-1]);path(g,p,i-1,j-1);//求最短途径上由起点城市到终点城市沿途所经过的城市}elseprintf("%s到%s没有途径可通\n",g.vexs[i-1].name,g.vexs[j-1].name);printf("\n");}}}}1122广州深圳佛山东莞中山珠海惠州江门肇庆香港澳门广州佛山34广州惠州141广州东莞72广州中山87广州深圳141广州澳门140深圳东莞74深圳惠州100深圳香港48深圳珠海158深圳中山126佛山肇庆86佛山江门78佛山中山79东莞惠州96东莞深圳74东莞中山97中山江门53中山珠海50中山香港169珠海江门91珠海澳门12广州，简称穗，别称羊城、花城，是广东省会、副省级市，中国国家中心城市，世界著名的港口城市，国家重要的经济、金融、贸易、交通、会展和航运中心。深圳，别称鹏城，广东省省辖市、副省级市、方案单列市、经济特区，中国四大一线城市之一，中国国家区域中心城市〔华南〕，国际重要的空海枢纽和外贸口岸，中国南方重要的高新技术研发和制造基地，中国重要的经济和金融中心，2021年经济总量居中国大陆第四位。佛山，简称佛，是广东省省辖市、特大城市，广东第三大城市，中国先进制造业基地、珠三角重要的制造业城市、广东重要的制造业中心，是珠三角核心地区辐射粤西沿海、西江流域的商务、物流中心和交通枢纽，是珠江三角洲经济圈中西部的重要城市，在广东省经济开展中处于领先地位。东莞是广东省省辖市，是“广东四小虎〞之一，号称“世界工厂〞，是全国4个不设市辖区的地级市之一。位于珠江口东岸，东接惠州、南抵深圳、西挨广州、北达博罗县，四周共与广州、深圳和惠州的10个县级行政区接壤。中