《数据结构课程设计-校园导游》由会员分享，可在线阅读，更多相关《数据结构课程设计-校园导游（29页珍藏版）》请在金锄头文库上搜索。
1、 数据结构课程设计报告实验三：校园导游1、设计要求用无向图表示校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。要求：（1）查询任意景点的相关信息（2）查询图中任意两个景点间的最短路径（3）查询图中任意两个景点间的所有路径（4）增加、删除、更新有关景点和道路的信息实际输入输出情况如下：（1）有关景点和路线的操作（2）查看现有导游路线图（3）对景点信息的增删改与查询增加景点删除景点更改景点信息查询景点信息（4）对道路信息的增删改增加道路删除道路更改道路信息（5）查询两景点间所有路径（6）
2、查询两景点间最短路径（7）查询经过多个景点的最短路径1、数据结构与算法描述1、 校园导游的数据结构 整个校园导游图以一个无向加权图描述，采用邻接表作为实现图结构的方式。（1）景点结构每个景点是一个链表，其结构如下：#pragma once#include#includeGraphNode.husing namespace std;class GraphVertexfriend class DiGraph;friend ostreamprotected:int vertexid;string name;GraphNode* head;string information;bool flag;/到
3、达该点的标记public:GraphVertex()vertexid=0;name=;head=0;flag=false;information=;GraphVertex(int vertexid,string name)this-vertexid=vertexid;this-name=name;head=0;flag=false;GraphVertex();int Length()const;/该顶点的度bool Find(int goal,GraphNode*/查找该顶点和goal之间是否有路径，如果找到则将该路径指针的引用保存在indexbool insert(int goal,int
4、length,string roadname);/按照权值递增规则将顶点goal插入该顶点链表bool Delete(int goal);/删除该顶点和goal间的路径;（2）路线的结构邻接链表中的每个节点代表了一条路线，其结构如下：#pragma once#includeusing namespace std;class GraphNodefriend class GraphVertex;public:int tovertex;int length;string roadname;GraphNode* next;GraphNode(int to,int length,string roadn
5、ame=,GraphNode* next=0)this-length=length;this-tovertex=to;this-roadname=roadname;this-next=next;GraphNode();int operator=(GraphNode y)constreturn this-tovertex=y.tovertex;（3）图结构整个图的结构是用链表的数组表示，为了使景点的添加删除操作可以充分地利用该数组空间，对该数组使用模拟指针的结构进行描述。#pragma once#includeGraphVertex.h#includeGraphNode.h#includesim
6、Node.hclass DiGraphfriend ostreamfriend int main();private:int n;int e;GraphVertex* v;Simspace* sp;int MaxN;void getpath(int from,int to,int* kay,int *l,stringvoid getallpath(int from,int to,stringpublic:DiGraph(int MaxN=100)this-MaxN=MaxN;n=0;e=0;v=new GraphVertexMaxN+1;sp=new Simspace(MaxN);DiGrap
7、h()delete v;delete sp;int findid(string name);DiGraph& addV(string name,string information)int i=sp-allc();if(!i)return *this;/空间用完vi.name=name;vi.information=information;vi.vertexid=i;n+;return *this;DiGraphDiGraphDiGraphvoid allpair(int* kay,int* l);void Output_path(string from,string to,int* kay,
8、int* l);void Output_allpath(string from,string to);void getroute(int* l,int* min_route,int* now_route,int n,int s,int e);void Output_route(int* l,int* kay,string *route,int n);void change_vertex_name(string from,string to);void change_road_name(string from_vertex,string to_vertex,string road_name,in
9、t length);void get_info(string name);void change_info(string name,string info);2、对算法中的主要方法的描述：A.两点间所有路径算法：要求两点间所有路径，可以采用一个比较直观的递归算法，即从起点开始，对该起点所有邻接点执行以下操作：如果该顶点已经到达，停止递归过程。设置该顶点为已到达。如果该顶点是目标顶点，停止递归过程。对该顶点执行同样操作。其关键代码如下：void DiGraph:getallpath(int start,int end,string& path_temp)/这是获得两点间所有路径的递归方法vsta
10、rt.flag=true;if(start=end)couttovertex.flag)p=p-next;continue;path_temp=path_temp+p-roadname+t+vp-tovertex.name+t;getallpath(p-tovertex,end,path_temp);path_temp.erase(pos);/递归该点完毕，抹去递归操作过程中对字符串的改动p=p-next;vstart.flag=false;return;B. 两点间最短路径算法采用 folyd 算法，求出该算法所使用的 kay和 l两个二维数组，继而利用这两个数组进行输出最短路径的操作。关键
11、代码如下：生成 kay 和 l 的操作：void DiGraph:allpair(int* kay,int* l)/所有点对最短路径for(int i=1;i=MaxN)break;index+;continue;/若遍历到已经被删除的点则忽略GraphNode* gn=vindex.head;while(gn)lindexgn-tovertex=gn-length;gn=gn-next;if(index=MaxN)break;i+;index+;/以上代码初始化l将边长度信息写入，无边则为-1for(int k=1;kroadname+t;return;getpath(from,kayfro
12、mto,kay,l,path);path=path+vkayfromto.name+t;getpath(kayfromto,to,kay,l,path);return;C.经过多个顶点的最短路径算法这里我利用 folyd 算法产生的两个二维数组，生成途径景点的全排列，然后利用 l求出排列中路径最短的路，再用与 floyd 算法相同的输出最短路径的算法进行输出，其关键代码如下：void DiGraph:getroute(int* l,int* min_route,int* route,int n,int s,int e)/暴力的O(n!)算法 保证得到最短路径/经过多个顶点的最短路径 利用全排列
13、算法和floyd算法得到/在perm的输出部分做改动if(s=e)int length=0,min_length=0;for(int i=0;iusing namespace std;class GraphNodefriend class GraphVertex;public:int tovertex;int length;string roadname;GraphNode* next;GraphNode(int to,int length,string roadname=,GraphNode* next=0)this-length=length;this-tovertex=to;this-r
14、oadname=roadname;this-next=next;GraphNode();int operator=(GraphNode y)constreturn this-tovertex=y.tovertex;文件二：GraphVertex.h#pragma once#include#includeGraphNode.husing namespace std;class GraphVertexfriend class DiGraph;friend ostreamprotected:int vertexid;string name;GraphNode* head;string informa
15、tion;bool flag;/到达该点的标记public:GraphVertex()vertexid=0;name=;head=0;flag=false;information=;GraphVertex(int vertexid,string name)this-vertexid=vertexid;this-name=name;head=0;flag=false;GraphVertex();int Length()const;/该顶点的度bool Find(int goal,GraphNode*/查找该顶点和goal之间是否有路径，如果找到则将该路径指针的引用保存在indexbool insert(int goal,int length,string roadname);/按照权值递增规则将顶点goal插入该顶点链表bool Delete(int goal);/删除该顶点和goal间的路径;文件三 SimNode.h#pragma onceclass Simspacepublic:int Maxsize;int *space;int first;Simspace(int Maxsize=100)this-Maxsize=Ma
