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

1实验报告开课学院及实验室：年月日学院年级、专业、班姓名学号实验课程名称数据结构成绩实验项目名称实验5图的应用指导教师一实验目的1、掌握图的基本概念和基本存储方法；2、掌握有关图的操作算法，并用高级语言实现；3、熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构及算法有着密切联系；4、熟悉如何用图结构解决实际应用问题；5、培养数据抽象的设计能力和实际动手的综合能力，并进一步掌握完整应用系统的设计过程和方法。二实验原理图形结构是一种应用非常广泛的数据结构，它的应用已经渗透到语言学、逻辑学、物理、化学、电子、通信、数学、计算机科学等诸多学科领域。最短路径是指路径长度（即路劲上边的权值之和）最小的路径，一般讨论带权有向图，在实际应用中经常用于解决城市节点间运输代价最少或运输时间最短等问题。三实验内容请为珠江三角洲城市间设计与实现一个简单的交通咨询系统。基本要求：（1）设计简单的珠江三角洲城市间道路通行平面图，所含城市不少于10个。以图中顶点表示城市节点，存放城市名称、代号、简介等信息；以边表示通行道路，存放道路的路径长度。（2）提供图中任意城市的相关信息查询。（3）提供图中任意城市间的最短路径查询。四实验步骤1将珠江三角洲城市间的交通图抽象为无向带权图。（要求给出一个设计方案）2设计求图中任意结点间最短路径的算法。3编程实现。五实验方法1对问题进行需求分析，选取具体城市结点，通过调研获取城市间的交通网络，选取主要的通行道路抽象为图的无向带权边。2进行概要设计和详细设计，形成模块间的调用结构图和模块的算法。3编写程序，设计测试用例进行测试。4完成开发文档。2六实验结果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;structVertexType3{charname[MAX_NAME];//城市名字charmes[MAX_MES];//城市信息};typedefcharInfoType;//c1.h(程序名)#includestring.h#includemalloc.h//malloc()等#includelimits.h//INT_MAX等#includestdio.h//EOF(=^Z或F6),NULL#includeio.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;//图的种类标志};//邻接矩阵存储结构的基本操作4intLocateVex(MGraphG,charu[MAX_NAME]){//初始条件：图G存在，u和G中顶点有相同特征//操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1inti;for(i=0;iG.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;iG.vexnum;++i)//构造顶点向量fscanf(graphlist,%s,G.vexs[i].name);for(i=0;iG.vexnum;++i)//初始化邻接矩阵for(j=0;jG.vexnum;++j){G.arcs[i][j].adj=INFINITY;//网G.arcs[i][j].info=NULL;//没有相关信息}for(k=0;kG.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;iG.vexnum;++i)//构造城市信息fscanf(graphlist,%s,G.vexs[i].mes);fclose(graphlist);//关闭数据文件G.kind=UDN;5}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]。//若P[v][w][u]为TRUE，则u是从v到w当前求得最短路径上的顶点。算法7.16intu,v,w,i;for(v=0;vG.vexnum;v++)//各对结点之间初始已知路径及距离for(w=0;wG.vexnum;w++){D[v][w]=G.arcs[v][w].adj;//顶点v到顶点w的直接距离for(u=0;uG.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;uG.vexnum;u++)for(v=0;vG.vexnum;v++)for(w=0;wG.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;iG.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;kG.vexnum;k++)for(k=0;kG.vexnum;k++)if(G.arcs[m][k].adjINFINITY&&P[m][j][k])//m到k有直接通路，且k在m到j的最短路径上{6printf(%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;ig.vexnum;i++)g.arcs[i][i].adj=0;//ShortestPath_FLOYD()要求对角元素值为0，因为两点相同，其距离为0ShortestPath_FLOYD(g,p,d);//求每对顶点间的最短路径，在func7-2.cpp中while(q){printf(请选择：1路线查询2城市信息查询0结束\n);scanf(%d,&q);if(q){for(i=0;ig.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请输入要查询的起点城市代码终点城市代码:);7scanf(%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);}}}}map.txt1122广州深圳佛山东