数据结构实验图

1、实验7：图的应用一、实验目的图是应用极为广泛的数据结构，也是这门课程的重点，继续使学生更了解数据结构加操作的程序设计观点。二、问题描述给出一张某公园的导游图，游客通过终端询问可知：a) 从某一景点到另一个景点的最短路径。b) 游客从公园大门进入，选一条最佳路线，使游客可以不重复的游览各景点，最后回到出口。三、实验要求1、将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构。2、为游客提供图中任意景点相关信息的查询；1、 为游客提供任意两个景点之间的一条最短的简单路径。2、 为游客选择最佳游览路径。 四、实验环境PC微机DOS操作系统

2、或 Windows 操作系统Turbo C 程序集成环境或 Visual C+ 程序集成环境 五、实验步骤1、设计公园平面图，图中顶点表示公园的各个景点，存放名称、代号、简介等信息；边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构；2、设计图的最短路径算法，如果有几条路径长度相同，选择途径景点较少的路径给游客；3、设计图的深度优先搜索算法，如果有多种路径可选，则选带权路径最短的路线给游客；4、选择适当语言实现算法；3、 调试程序。 六、测试数据 可根据实际情况指定。 测试数据见南昌大学平面示意图。七、实验报告要求1、 问题描述； 该程序包扩以下内容： （1）设计学校的校园平面图，

3、所含景点为9个。（2）以图中顶点表示校内各景点，存放景点名称、代号、间介等信息；以边表示路径，存放路径长度等相关信息。（3）为来访客人提供图中任意景点相关信息的查询。（4）提供途中任意景点问路查询，即求任意两个景点间的一条最短的简单路径。（5）提供途中任意景点问路查询，即求任意两个景点间的所有路径。（6）提供校园图中多个景点的最佳访问路线查询，即求途经这多个景点的最佳（短）路径。设计思路：对系统功能抽象，分析问题描述。首先，平面图用输出模拟；存储景点信息采用结构体；对各景点用字母代替，字母组成图，通过对图的操作，狄克斯特拉算法求出指定最短路径及一点到其它所有点的最短路径，递归进行图的遍历求两点

4、所有路径。由此可实现以上所有功能。2、 图的建立图的建立：这是一个无向带权图，实际上无向带权图与有向带权图相似，采用邻接矩阵存储比较方便。邻接矩阵的结点结构体如下：其赋值如下：3、 图的最短路径算法算法思想：设置两个结点集合S和T，集合S中存放已找到的最短路径的结点，集合T中存放当前还没找到的最短路径的结点。初始状态时，集合S中只包含源点，没为v0，然后不断的从集合T中选择到源点v0的路径长度最短的结点u加入到集合S中，集合S中每加入一新的结点u，都要修改源点v0到集合T中剩余结点的当前最短路径长度值，集合T中各点的新的当前最短路径长度值为原来的当前最短路径长度值，与结点u的最短路径长度值加上

5、结点u到该结点的路径长度值（即为从源点结点u到达该结点的路径长度）中的较小者。此过程不断重复，直到集合T中的对号点全部加到集合S中为止。算法实现如下： void Dijkstra(MGraph g,int v, int to) /Dijkstra g图中v为起点求出到所有点的最短路径 int distMAXV,pathMAXV; /dist存路径 path存顶点int sMAXV; /标记int mindis,i,j,u; for(i=0;ig.n;i+) disti=g.edgesvi; si=0; if(g.edgesviINF) pathi=v; else pathi=-1; sv=1;

6、pathv=0; for(i=0;ig.n;i+) mindis=INF; for(j=0;jg.n;j+) if(sj=0&distjmindis) u=j; mindis=distj; su=1; for(j=0;jg.n;j+) if(sj=0) if(g.edgesujINF&distu+g.edgesujdistj) distj=distu+g.edgesuj; pathj=u; Dispath(dist,path,s,g.n,v,to); 4、 公园平面图； 5、 程序的测试结果和问题（0） 进入系统（1） 浏览学校景点（2） 查找单个景点（3） 查看学校平面示意图（4） 推荐路线

7、（5） 景点最短路线（6） 两点所有路径（7） 退出6、 实验总结。 身是数据结构中最复杂的一种，所以其有关操作的算法自然也就相对于其他数据结构更为复杂，也更为巧妙，最充分体现了数据结构对算法的描述作用。实验中，图的存储是以邻接矩阵来表示的，邻接矩阵存储易于理解，方便存储，但是修改起来就有问题了，所以我没能将思考题1给做出来。实验中的一个重要算法，Dijkstra算法是图在日常应用中最突出的例子，基于此，我加深了对该算法的认知，虽然现在自己写出来仍热有难度，但是理解了思想就离成功不远了。最后，声明一下，这个程序的大部分出于网上，自己只是做到了，理解、修改、整理再创作的过程。八、思考题1、 扩充

8、景点数和道路。2、 试着提供图的多个景点的最佳访问路线查询。九、附录 本部分包含三个文件，sight.h主要是对景区的构建，描述和展示。graph.h则主要对景区的操作算法。main.cpp为程序主程序，简单地调用graph.h中的操作，程序力求交互性好，界面友好，但是是基于DOS，所以再美化也是不尽如人意的。以下为程序源码，可能由于粘贴过程中，可能会导致部分源码出现不整齐。sight.h/景点及景点的相关函数#ifndef Sighth#define Sighth#include#include#include#include#includeconio.h#includevoid stcpy

9、(char str1,char str2 )/定义定符串赋值int i,len;len=strlen(str2);for(i=0;ilen;i+) str1i=str2i; str1len=0; /字符串1结束class Sight/定义景点类public:char SN;char pl_name20; /景点名称char pl_sy1000; /景点简介Sight(char s,char pl,char ps) SN=s; stcpy(pl_name,pl); stcpy(pl_sy,ps);friend void browse(); /浏览友元函数;/定义景点 Sight A(A,学校大门

10、,大门由集散广场、大门、游廊、门卫室、门前广场、清水平台及水景区组成。学校大门是亚洲最大的校门。);Sight B(B,和平女神像,世界和平自由女神像位于大门前的集散广场,作品由著名艺术家南昌大学遥远教授设计，以纪念诺曼底登陆60周年，现已成为世界和平的象征。);Sight C(C,体育馆,南昌大学前湖校区体育馆内部主要分为比赛馆、训练馆和功能设施用房，宛如伏在南昌大学美丽校园山丘上的一块巨石。); Sight D(D,游泳馆,又称钱红游泳俱乐部，以服务广大昌大学子及教职员工为主旨，同时对外开放经营，集教学、健身、休闲、娱乐为一体的服务机构。);Sight E(E,商业街,我们学校最繁华的商业

11、街，是大家主要的消费场所,从生活用品到小吃零食,各色风味,商业街连着后街构成了我们最好的消费园地。);Sight F(F,教学主楼,这是红黄色相间雄伟的建筑,由南昌大学建筑设计院设计，位于前湖校区北部，占地面积2.5公顷，东西两面为天然的润溪湖，西北两面为校园道路。);Sight G(G,正气广场,正气广场是一座半径为92米，占地3万平方米的圆形下沉式（深六米）万人广场，依临正气龙。);Sight H(H,图书馆,南昌大学图书馆现有馆舍面积6万余平方米， 我们的图书馆集借、藏、阅多功能服务为一体。); Sight I(I,天健园,天健园在校车的终点站，这里是理工科学生的宿舍楼，服务大楼则主要提

12、供各种服务，包括购物、打印、理发、各色小吃之类，但倘若你要极致的享受，还是去商业街吧!); void Gprint()/地图cout*南昌大学前湖校区平面示意图(单位：M)*endl;coutendl;cout D游泳馆 C体育馆 endl; cout 150 endl; cout endl; cout 250 endl; cout E商业街 F教学主楼 endl;cout 200 A B endl;cout G正气广场 学 和 endl; cout 校 平 endl;cout 800 400 200 100 女 endl;cout 400 大 神 endl;cout 门 像 endl;cou

13、t I天健园 H图书馆 endl;cout 300 endl; cout endl; coutendl;void S_print(Sight item)/单个景点输出函数cout item.SN. item.pl_namen 简介：item.pl_syendlendl;void browse()/输出所有景点信息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

14、);system(cls);void FunMenue()/功能菜单 cout endl;cout -欢迎使用南昌大学导游帮助小程序- endl;cout endl;cout 1.浏览学校景点 2.查找单个景点信息 endl;cout 3.学校地图平面示意图 4.路线推荐 endl;cout 5.景点最短线路 6.两景点所有路径 endl;cout 7.退出系统 endl;cout endl;void FunMenue2()/景点菜单cout -南昌大学大学景点-endl;cout A. 学校大门 B. 和平女神像endl;cout C. 体 育 馆 D. 游 泳 馆 endl;cout E.

15、 商 业 街 F. 教 学 主 楼endl;cout G. 正 气 广 场 H. 图 书 馆endl;cout I. 天 健 园 key;switch(key)case A:return A;break;case B:return B;break;case C:return C;break;case D:return D;break;case E:return E;break;case F:return F;break;case G:return G;break;case H:return H;break;case I:return I;break;default:cout您的输入有误！请选择

16、AI！n;system(pause);system(cls);FunMenue2();C_IN2();int Sprint(char item)/对字母表示的景点输出switch(item)case A:coutA.SNA.pl_name;break;case B:coutB.SNB.pl_name;break;case C:coutC.SNC.pl_name;break;case D:coutD.SND.pl_name;break;case E:coutE.SNE.pl_name;break;case F:coutF.SNF.pl_name;break;case G:coutG.SNG.pl

17、_name;break;case H:coutH.SNH.pl_name;break;case I:coutI.SNI.pl_name;break;default:cout无此景点n;return 1;break;return 0;#endifgraph.h/构造图 及图的相关操作，由狄克斯拉算法改成。#include Sight.h#define MAXV 100 #define INF 32767 typedef int InfoType; /邻接矩阵存储方法 typedef struct int edgesMAXVMAXV; int n; MGraph; /狄克斯特拉算法 void Pp

18、ath(int path,int i,int v) int k; k=pathi; if(k=v) return; Ppath(path,k,v); Sprint(k+A);coutchar(k+A); void Dispath(int dist,int path,int s,int n,int v,int i) /对最短路径输出 if(si=1) cout ;Sprint(v+A);coutchar(v+A)到;Sprint(i+A);coutchar(i+A)n 最短路径：disti米 n 途经： ; Sprint(v+A);coutchar(v+A); Ppath(path,i,v);

19、Sprint(i+A);coutchar(i+A)endl; else cout从char(v+A)到char(i+A)不存在的路径endl; cout; void Dijkstra(MGraph g,int v, int to) /Dijkstra g图中v为起点求出到所有点的最短路径 int distMAXV,pathMAXV; /dist存路径 path存顶点int sMAXV; /标记int mindis,i,j,u; for(i=0;ig.n;i+) disti=g.edgesvi; si=0; if(g.edgesviINF) pathi=v; else pathi=-1; sv=

20、1;pathv=0; for(i=0;ig.n;i+) mindis=INF; for(j=0;jg.n;j+) if(sj=0&distjmindis) u=j; mindis=distj; su=1; for(j=0;jg.n;j+) if(sj=0) if(g.edgesujINF&distu+g.edgesujdistj) distj=distu+g.edgesuj; pathj=u; Dispath(dist,path,s,g.n,v,to); void Dijkstra(MGraph g,int v)/重载，当只有一点求最短路径时，用到int to;for(to=0;tog.n;t

21、o+)if(to=v)continue; Dijkstra(g,v,to);/int path10;int pathF10=0;int BPsize=0;int EofV(MGraph g,int start)int con=0;for(int j=0;jg.n;j+)if(g.edgesstartj!=0&g.edgesstartjINF)con+;return con;int Nest(MGraph g,int start,int i)int con=0;for(int j=0;jg.n;j+)if(g.edgesstartj!=0&g.edgesstartjINF)con+;if(con

22、=i)return j;return 0;void Print(MGraph g) /打印找到路径int TVal=0;for(int j=0;jBPsize-1;j+)TVal=TVal+g.edgespathjpathj+1;Sprint(pathj+A);cout;Sprint(pathj+A);coutn总 长：TVal 米endl;void FindAllWay(MGraph g,int start,int end,int n) /寻找所有路径int i;if(start=end)pathn=start;BPsize=n+1;Print(g);return ;int num=EofV

23、(g,start);pathn=start;for(i=1;i=num;i+)if(pathFNest(g,start,i)!=1)pathFstart=1;FindAllWay(g,Nest(g,start,i),end,n+1);pathFstart=0;/Shortest函数 int Shortest(int choice) /最短路径函数 char from,to;int i,j,n; MGraph g; n=9;/图信息for(i=0;in;i+)for(j=0;jn;j+)if(i!=j)g.edgesij=32767;else g.edgesij=0;g.edges01=g.ed

24、ges10=100;g.edges02=g.edges20=500;g.edges06=g.edges60=200;g.edges07=g.edges70=350;g.edges23=g.edges32=150;g.edges35=g.edges53=250;g.edges45=g.edges54=200;g.edges48=g.edges84=800;g.edges57=g.edges75=600; g.edges67=g.edges76=400;g.edges78=g.edges87=300; g.n=n; if(choice=5) cout请输入起点和终点：fromto; cout+竭诚为您提供最短路径+; i=from-A;j=to-A; Dijkstra(g,i,j); coutendl; if(choice=4) cout请输入起点：from; system(cls); cout+我为您提供这里到学校其它景点最好选择+; cout 您选择了; if(Sprint(from)=1)return 0; cout为