搜索
实验7：图的应用一、实验目的图是应用极为广泛的数据结构，也是这门课程的重点，继续使学生更了解数据结构加操作的程序设计观点。二、问题描述给出一张某公园的导游图，游客通过终端询问可知：a)从某一景点到另一个景点的最短路径。b)游客从公园大门进入，选一条最佳路线，使游客可以不重复的游览各景点，最后回到出口。三、实验要求1、将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构。2、为游客提供图中任意景点相关信息的查询；1、为游客提供任意两个景点之间的一条最短的简单路径。2、为游客选择最佳游览路径。四、实验环境PC微机DOS操作系统或Windows操作系统TurboC程序集成环境或VisualC++程序集成环境五、实验步骤1、设计公园平面图，图中顶点表示公园的各个景点，存放名称、代号、简介等信息；边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构；2、设计图的最短路径算法，如果有几条路径长度相同，选择途径景点较少的路径给游客；3、设计图的深度优先搜索算法，如果有多种路径可选，则选带权路径最短的路线给游客；4、选择适当语言实现算法；3、调试程序。六、测试数据可根据实际情况指定。测试数据见南昌大学平面示意图。七、实验报告要求1、问题描述；该程序包扩以下内容：（1）设计学校的校园平面图，所含景点为9个。（2）以图中顶点表示校内各景点，存放景点名称、代号、间介等信息；以边表示路径，存放路径长度等相关信息。（3）为来访客人提供图中任意景点相关信息的查询。（4）提供途中任意景点问路查询，即求任意两个景点间的一条最短的简单路径。（5）提供途中任意景点问路查询，即求任意两个景点间的所有路径。（6）提供校园图中多个景点的最佳访问路线查询，即求途经这多个景点的最佳（短）路径。设计思路：对系统功能抽象，分析问题描述。首先，平面图用输出模拟；存储景点信息采用结构体；对各景点用字母代替，字母组成图，通过对图的操作，狄克斯特拉算法求出指定最短路径及一点到其它所有点的最短路径，递归进行图的遍历求两点所有路径。由此可实现以上所有功能。2、图的建立图的建立：这是一个无向带权图，实际上无向带权图与有向带权图相似，采用邻接矩阵存储比较方便。邻接矩阵的结点结构体如下：其赋值如下：3、图的最短路径算法算法思想：设置两个结点集合S和T，集合S中存放已找到的最短路径的结点，集合T中存放当前还没找到的最短路径的结点。初始状态时，集合S中只包含源点，没为v0，然后不断的从集合T中选择到源点v0的路径长度最短的结点u加入到集合S中，集合S中每加入一新的结点u，都要修改源点v0到集合T中剩余结点的当前最短路径长度值，集合T中各点的新的当前最短路径长度值为原来的当前最短路径长度值，与结点u的最短路径长度值加上结点u到该结点的路径长度值（即为从源点结点u到达该结点的路径长度）中的较小者。此过程不断重复，直到集合T中的对号点全部加到集合S中为止。算法实现如下：voidDijkstra(MGraphg,intv,intto)//Dijkstrag图中v为起点求出到所有点的最短路径{intdist[MAXV],path[MAXV];//dist存路径path存顶点ints[MAXV];//标记intmindis,i,j,u;for(i=0;ig.n;i++){dist[i]=g.edges[v][i];s[i]=0;if(g.edges[v][i]INF)path[i]=v;elsepath[i]=-1;}s[v]=1;path[v]=0;for(i=0;ig.n;i++){mindis=INF;for(j=0;jg.n;j++){if(s[j]==0&&dist[j]mindis){u=j;mindis=dist[j];}}s[u]=1;for(j=0;jg.n;j++){if(s[j]==0){if(g.edges[u][j]INF&&dist[u]+g.edges[u][j]dist[j]){dist[j]=dist[u]+g.edges[u][j];path[j]=u;}}}}Dispath(dist,path,s,g.n,v,to);}4、公园平面图；5、程序的测试结果和问题（0）进入系统（1）浏览学校景点（2）查找单个景点（3）查看学校平面示意图（4）推荐路线（5）景点最短路线（6）两点所有路径（7）退出6、实验总结。身是数据结构中最复杂的一种，所以其有关操作的算法自然也就相对于其他数据结构更为复杂，也更为巧妙，最充分体现了数据结构对算法的描述作用。实验中，图的存储是以邻接矩阵来表示的，邻接矩阵存储易于理解，方便存储，但是修改起来就有问题了，所以我没能将思考题1给做出来。实验中的一个重要算法，Dijkstra算法是图在日常应用中最突出的例子，基于此，我加深了对该算法的认知，虽然现在自己写出来仍热有难度，但是理解了思想就离成功不远了。最后，声明一下，这个程序的大部分出于网上，自己只是做到了，理解、修改、整理再创作的过程。八、思考题1、扩充景点数和道路。2、试着提供图的多个景点的最佳访问路线查询。九、附录本部分包含三个文件，sight.h主要是对景区的构建，描述和展示。graph.h则主要对景区的操作算法。main.cpp为程序主程序，简单地调用graph.h中的操作，程序力求交互性好，界面友好，但是是基于DOS，所以再美化也是不尽如人意的。以下为程序源码，可能由于粘贴过程中，可能会导致部分源码出现不整齐。sight.h//景点及景点的相关函数#ifndefSighth#defineSighth#includeiostream.h#includeiomanip.h#includestdio.h#includestdlib.h#includeconio.h#includestring.hvoidstcpy(charstr1[],charstr2[])//定义定符串赋值{inti,len;len=strlen(str2);for(i=0;ilen;i++)str1[i]=str2[i];str1[len]='\0';//字符串1结束}classSight//定义景点类{public:charSN;charpl_name[20];//景点名称charpl_sy[1000];//景点简介Sight(chars,charpl[],charps[]){SN=s;stcpy(pl_name,pl);stcpy(pl_sy,ps);}friendvoidbrowse();//浏览友元函数};//定义景点SightA('A',学校大门,大门由集散广场、大门、游廊、门卫室、门前广场、清水平台及水景区组成。学校大门是亚洲最大的校门。);SightB('B',和平女神像,世界和平自由女神像位于大门前的集散广场,作品由著名艺术家南昌大学遥远教授设计，以纪念诺曼底登陆60周年，现已成为世界和平的象征。);SightC('C',体育馆,南昌大学前湖校区体育馆内部主要分为比赛馆、训练馆和功能设施用房，宛如伏在南昌大学美丽校园山丘上的一块巨石。);SightD('D',游泳馆,又称钱红游泳俱乐部，以服务广大昌大学子及教职员工为主旨，同时对外开放经营，集教学、健身、休闲、娱乐为一体的服务机构。);SightE('E',商业街,我们学校最繁华的商业街，是大家主要的消费场所,从生活用品到小吃零食,各色风味,商业街连着后街构成了我们最好的消费园地。);SightF('F',教学主楼,这是红黄色相间雄伟的建筑,由南昌大学建筑设计院设计，位于前湖校区北部，占地面积2.5公顷，东西两面为天然的润溪湖，西北两面为校园道路。);SightG('G',正气广场,正气广场是一座半径为92米，占地3万平方米的圆形下沉式（深六米）万人广场，依临正气龙。);SightH('H',图书馆,南昌大学图书馆现有馆舍面积6万余平方米，我们的图书馆集借、藏、阅多功能服务为一体。);SightI('I',天健园,天健园在校车的终点站，这里是理工科学生的宿舍楼，服务大楼则主要提供各种服务，包括购物、打印、理发、各色小吃之类，但倘若你要极致的享受，还是去商业街吧!);voidGprint()//地图{cout**************南昌大学前湖校区平面示意图(单位：M)*********************endl;cout┌────────────────────────────────────┐endl;cout│D游泳馆C体育馆│endl;cout│┏━━━━━━━━┳━⊙┅┅┅150┅┅┅⊙━━━━━━━┫│endl;cout│┃┃╲╲┃│endl;cout│┃┃250╲┃│endl;cout│┃E商业街┃╲F教学主楼╲┃│endl;cout│┣━━━━⊙┅┅┅┫200┅┅⊙╲┃AB│endl;cout│┃┇┃┇G正气广场╲┃学和│endl;cout│┃┇┃┇⊙╲┃校平│endl;cout│┃800┃400╱╰┉200┅┅╰⊙┅100┅⊙女│endl;cout│┃┇┃┇400┃大神│endl;cout│┃┇┃┇╱┃门像│endl;cout│┃I天健园┃⊙H图书馆┃│endl;cout│┣━━━⊙┉┉300┻┉┅┉┅╯━━━━━━━━━━━━┫│endl;cout││endl;cout└────────────────────────────────────┘endl;}voidS_print(Sightitem)//单个景点输出函数{coutitem.SN.item.pl_name\n简介：item.pl_syendlendl;}voidbrowse()//输出所有景点信息{system(cls);cout----------------南昌大学景点介绍----------------endl;S_print(A);S_print(B);S_print(C);S_print(D);S_print(E);S_print(F);S_print(G);S_print(H);S_print(I);system(pause);system(cls);}voidFunMenue()//功能菜单{cout┌────────────────────────────────┐endl;cout│--------------欢迎使用南昌大学导游帮助小程序--------------│endl;cout││endl;cout│1.浏览学校景点2.查找单个景点信息│endl;cout│3.学校地图平面示意图4.路线推荐│endl;cout│5.景点最短线路6.两景点所有路径│endl;cout│7.退出系统│endl;cout└────────────────────────────────┘endl;}voidFunMenue2()//景点菜单{cout----------------南昌大学大学景点----------------endl;coutA.学校大门B.和平女神像endl;coutC.体育馆D.游泳馆endl;coutE.商业街F.教学主楼endl;coutG.正气广场H.图书馆endl;coutI.天健园endl;}SightC_IN2()//字母转换为景点{charkey;cinkey;switch(key){case'A':returnA;break;case'B':returnB;break;case'C':returnC;break;case'D':returnD;break;case'E':returnE;break;case'F':r