数据结构实验图(共20页).docx

精选优质文档-倾情为你奉上实验7：图的应用一、实验目的图是应用极为广泛的数据结构，也是这门课程的重点，继续使学生更了解数据结构加操作的程序设计观点。二、问题描述给出一张某公园的导游图，游客通过终端询问可知：a) 从某一景点到另一个景点的最短路径。b) 游客从公园大门进入，选一条最佳路线，使游客可以不重复的游览各景点，最后回到出口。三、实验要求1、将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构。2、为游客提供图中任意景点相关信息的查询；1、 为游客提供任意两个景点之间的一条最短的简单路径。2、 为游客选择最佳游览路径。 四、实验环境PC微机DOS操作系统或 Windows 操作系统Turbo C 程序集成环境或 Visual C+ 程序集成环境 五、实验步骤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中为止。算法实现如下： 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;i<g.n;i+) disti=g.edgesvi; si=0; if(g.edgesvi<INF) pathi=v; else pathi=-1; sv=1;pathv=0; for(i=0;i<g.n;i+) mindis=INF; for(j=0;j<g.n;j+) if(sj=0&&distj<mindis) u=j; mindis=distj; su=1; for(j=0;j<g.n;j+) if(sj=0) if(g.edgesuj<INF&&distu+g.edgesuj<distj) distj=distu+g.edgesuj; pathj=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/景点及景点的相关函数#ifndef Sighth#define Sighth#include<iostream.h>#include<iomanip.h>#include<stdio.h>#include<stdlib.h>#include"conio.h"#include<string.h>void stcpy(char str1,char str2 )/定义定符串赋值int i,len;len=strlen(str2);for(i=0;i<len;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',"学校大门","大门由集散广场、大门、游廊、门卫室、门前广场、清水平台及水景区组成。学校大门是亚洲最大的校门。");Sight B('B',"和平女神像","世界和平自由女神像位于大门前的集散广场,作品由著名艺术家南昌大学遥远教授设计，以纪念诺曼底登陆60周年，现已成为世界和平的象征。");Sight C('C',"体育馆","南昌大学前湖校区体育馆内部主要分为比赛馆、训练馆和功能设施用房，宛如伏在南昌大学美丽校园山丘上的一块巨石。"); Sight D('D',"游泳馆","又称钱红游泳俱乐部，以服务广大昌大学子及教职员工为主旨，同时对外开放经营，集教学、健身、休闲、娱乐为一体的服务机构。");Sight E('E',"商业街","我们学校最繁华的商业街，是大家主要的消费场所,从生活用品到小吃零食,各色风味,商业街连着后街构成了我们最好的消费园地。");Sight F('F',"教学主楼","这是红黄色相间雄伟的建筑,由南昌大学建筑设计院设计，位于前湖校区北部，占地面积2.5公顷，东西两面为天然的润溪湖，西北两面为校园道路。");Sight G('G',"正气广场","正气广场是一座半径为92米，占地3万平方米的圆形下沉式（深六米）万人广场，依临正气龙。");Sight H('H',"图书馆","南昌大学图书馆现有馆舍面积6万余平方米， 我们的图书馆集借、藏、阅多功能服务为一体。"); Sight I('I',"天健园","天健园在校车的终点站，这里是理工科学生的宿舍楼，服务大楼则主要提供各种服务，包括购物、打印、理发、各色小吃之类，但倘若你要极致的享受，还是去商业街吧!"); void Gprint()/地图cout<<"*南昌大学前湖校区平面示意图(单位：M)*"<<endl;cout<<""<<endl;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;cout<<" I天健园 H图书馆 "<<endl;cout<<" 300 "<<endl; cout<<" "<<endl; cout<<""<<endl;void S_print(Sight item)/单个景点输出函数cout<<" "<<item.SN<<". "<<item.pl_name<<"n 简介："<<item.pl_sy<<endl<<endl;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");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. 商 业 街 F. 教 学 主 楼"<<endl;cout<<" G. 正 气 广 场 H. 图 书 馆"<<endl;cout<<" I. 天 健 园 " <<endl; Sight C_IN2()/字母转换为景点char key;cin>>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<<"您的输入有误！请选择AI！n"system("pause");system("cls");FunMenue2();C_IN2();int Sprint(char item)/对字母表示的景点输出switch(item)case 'A':cout<<A.SN<<A.pl_name;break;case 'B':cout<<B.SN<<B.pl_name;break;case 'C':cout<<C.SN<<C.pl_name;break;case 'D':cout<<D.SN<<D.pl_name;break;case 'E':cout<<E.SN<<E.pl_name;break;case 'F':cout<<F.SN<<F.pl_name;break;case 'G':cout<<G.SN<<G.pl_name;break;case 'H':cout<<H.SN<<H.pl_name;break;case 'I':cout<<I.SN<<I.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 Ppath(int path,int i,int v) int k; k=pathi; if(k=v) return; Ppath(path,k,v); Sprint(k+'A');cout<<char(k+'A')<<"->" void Dispath(int dist,int path,int s,int n,int v,int i) /对最短路径输出 if(si=1) cout<<" "Sprint(v+'A');cout<<char(v+'A')<<"到"Sprint(i+'A');cout<<char(i+'A')<<"n 最短路径："<<disti<<"米 n"<<" 途经： " Sprint(v+'A');cout<<char(v+'A')<<"->" Ppath(path,i,v); Sprint(i+'A');cout<<char(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;i<g.n;i+) disti=g.edgesvi; si=0; if(g.edgesvi<INF) pathi=v; else pathi=-1; sv=1;pathv=0; for(i=0;i<g.n;i+) mindis=INF; for(j=0;j<g.n;j+) if(sj=0&&distj<mindis) u=j; mindis=distj; su=1; for(j=0;j<g.n;j+) if(sj=0) if(g.edgesuj<INF&&distu+g.edgesuj<distj) 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;to<g.n;to+)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;j<g.n;j+)if(g.edgesstartj!=0&&g.edgesstartj<INF)con+;return con;int Nest(MGraph g,int start,int i)int con=0;for(int j=0;j<g.n;j+)if(g.edgesstartj!=0&&g.edgesstartj<INF)con+;if(con=i)return j;return 0;void Print(MGraph g) /打印找到路径int TVal=0;for(int j=0;j<BPsize-1;j+)TVal=TVal+g.edgespathjpathj+1;Sprint(pathj+'A');cout<<"->"Sprint(pathj+'A');cout<<"n总 长："<<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(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;i<n;i+)for(j=0;j<n;j+)if(i!=j)g.edgesij=32767;else g.edgesij=0;g.edges01=g.edges10=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<<"请输入起点和终点："<<endl; cin>>from>>to; cout<<"+竭诚为您提供最短路径+" i=from-'A'j=to-'A' Dijkstra(g,i,j); cout<<endl; if(choice=4) cout<<"请输入起点："<<endl; cin>>from; system("cls"); cout<<"+我为您提供这里到学校其它景点最好选择+" cout<<" 您选择了" if(Sprint(from)=1)return 0; cout<<"为起点n" i=from-'A' Dijkstra(g,i); cout<<endl; if(choice=6) cout<<"请输入起点和终点："<<endl; char from,to; cin>>from>>to; int f,t; f=from-'A' t=to-'A' FindAllWay(g,f,t,0); return 0; main.cpp#include "sight.h"#include "graph.h"void exc();void C_IN(void)/对主选单操作char key;cin>>key;switch(key)case '1':browse();break;case '2':FunMenue2();S_print(C_IN2();system("pause");system("cls");break;case '3':Gprint();break;case '4':FunMenue2();Shortest(4);system("pause");system("cls");break;case '5':FunMenue2();Shortest(5);system("pause");system("cls");break;case '6':FunMenue2();Shortest(6);system("pause");system("cls");break;case '7':cout<<"nn 欢迎您的到来，谢谢您的使用！n"cout<<" 学校主页：n"exc();default:cout<<"您的输入有误！请选择14！n"system("pause");system("cls");FunMenue();C_IN(); void exc()cout<<"确认退出(Y/N)："char key;cin>>key;while(key!='Y'&&key!='N')cin>>key;if(key='Y')exit(1);if(key='N')system("cls");FunMenue();C_IN();int main()/主函数while(1)FunMenue();C_IN(); return 0;专心-专注-专业