数据结构课程设计-校园导游.doc

数据结构课程设计报告 实验三：校园导游1、 设计要求用无向图表示校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。要求：（1） 查询任意景点的相关信息（2） 查询图中任意两个景点间的最短路径（3） 查询图中任意两个景点间的所有路径（4） 增加、删除、更新有关景点和道路的信息实际输入输出情况如下：（1）有关景点和路线的操作（2）查看现有导游路线图（3） 对景点信息的增删改与查询增加景点删除景点更改景点信息查询景点信息（4） 对道路信息的增删改增加道路删除道路更改道路信息（5）查询两景点间所有路径（6） 查询两景点间最短路径（7） 查询经过多个景点的最短路径1、 数据结构与算法描述1、 校园导游的数据结构 整个校园导游图以一个无向加权图描述，采用邻接表作为实现图结构的方式。（1）景点结构每个景点是一个链表，其结构如下：#pragma once#include#includeGraphNode.husing namespace std;class GraphVertexfriend class DiGraph;friend ostream& operatorvertexid=vertexid;this-name=name;head=0;flag=false;GraphVertex();int Length()const;/该顶点的度bool Find(int goal,GraphNode*& index)const;/查找该顶点和goal之间是否有路径，如果找到则将该路径指针的引用保存在indexbool insert(int goal,int 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 roadname=,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#includesimNode.hclass DiGraphfriend ostream& operatorMaxN=MaxN;n=0;e=0;v=new GraphVertexMaxN+1;sp=new Simspace(MaxN);DiGraph()delete v;delete sp;int findid(string name);DiGraph& addV(string name,string information)int i=sp-allc();if(!i)return *this;/空间用完=name;rmation=information;vi.vertexid=i;n+;return *this;DiGraph& DeleteV(string name);DiGraph& addE(string name1,string name2,int length,string roadname);DiGraph& DeleteE(string name1,string name2);void allpair(int* kay,int* l);void Output_path(string from,string to,int* kay,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,int 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)/这是获得两点间所有路径的递归方法vstart.flag=true;if(start=end)coutpath_temptovertex.flag)p=p-next;continue;path_temp=path_temp+p-roadname+t++t;getallpath(p-tovertex,end,path_temp);path_temp.erase(pos);/递归该点完毕，抹去递归操作过程中对字符串的改动p=p-next;vstart.flag=false;return;B. 两点间最短路径算法采用folyd算法，求出该算法所使用的kay和l两个二维数组，继而利用这两个数组进行输出最短路径的操作。关键代码如下：生成kay和l的操作：void DiGraph:allpair(int* kay,int* l)/所有点对最短路径for(int i=1;i=n;i+)for(int j=1;j=n;j+)kayij=0;for(int i=1;i=n;i+)for(int j=1;j=n;j+)lij=-1;/初始化kay和lint index=1;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;k=n;k+)for(int i=1;i=n;i+)for(int j=1;j=n;j+)if(lik!=-1&lkj!=-1&(lij=-1)|(lik+lkj)roadname+t;return;getpath(from,kayfromto,kay,l,path);path=path++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!)算法 保证得到最短路径/经过多个顶点的最短路径 利用全排列算法和floyd算法得到/在perm的输出部分做改动if(s=e)int length=0,min_length=0;for(int i=0;in-1;i+)if(lrouteiroutei+1=-1)return;/有两点间没有路径；直接忽略该路径length+=lrouteiroutei+1;min_length+=lmin_routeimin_routei+1;/若lengthmin_length则交换两个数组的值if(lengthmin_length)for(int i=0;in;i+)min_routei=routei;return;/做perm处理for(int i=s;in;i+)swap(routes,routei);getroute(l,min_route,route,n,s+1,e);swap(routes,routei);2、 分析与探讨1.测试结果分析 通过测试结果我们发现，虽然采用的旅行商问题的算法为O(n!)的算法，但因为一般经过的景点数目不多，所以执行速度仍然比较快。其他部分的算法运行2.算法分析1、 两点间所有路径算法：O(n!)2、 查询任意两点间的最短路径:O(n*3)3、 经过多点的最短路径算法：O(n!)附录 所有源代码文件一:GraphNode.h#pragma once#includeusing 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-roadname=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 ostream& operatorvertexid=vertexid;this-name=name;head=0;flag=false;GraphVertex();int Length()const;/该顶点的度bool Find(int goal,GraphNode*& index)const;/查找该顶点和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=Maxsize;space=new intMaxsize+1;for(int i=1;iMaxsize;i+)spacei=i+1;spaceMaxsize=-1;first=1;int allc();void deallc(int &i);文件四 DiGraph.h#pragma once#includeGraphVertex.h#includeGraphNode.h#includesimNode.hclass DiGraphfriend ostream& operatorMaxN=MaxN;n=0;e=0;v=new GraphVertexMaxN+1;sp=new Simspace(MaxN);DiGraph()delete v;delete sp;int findid(string name);DiGraph& addV(string name,string information)int i=sp-allc();if(!i)return *this;/空间用完=name;rmation=information;vi.vertexid=i;n+;return *this;DiGraph& DeleteV(string name);DiGraph& addE(string name1,string name2,int length,string roadname);DiGraph& DeleteE(string name1,string name2);void allpair(int* kay,int* l);void Output_path(string from,string to,int* kay,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,int length);void get_info(string name);void change_info(string name,string info);文件五 simNode.cpp#include simNode.hint Simspace:allc()if(first=-1)return 0;int i=first;first=spacefirst;return i;void Simspace:deallc(int& i)spacei=first;first=i;i=-1;return;文件六 GraphVertex.cpp#include GraphVertex.h#includeint GraphVertex:Length()constint result=0;GraphNode* current=head;while(current!=0)current=current-next;result+;return result;bool GraphVertex:Find(int goal,GraphNode*& index)constGraphNode* p=head;while(p!=0)if(p-tovertex=goal)index=p;return true;p=p-next;return false;bool GraphVertex:insert(int goal,int length,string roadname)GraphNode*p;if(Find(goal,p)cout已经存在该条道路endl;return false;if(head=0)head=new GraphNode(goal,length,roadname);return true;if(lengthlength)head=new GraphNode(goal,length,roadname,head);return true;p=head-next;GraphNode* pp=head;while(p!=0)if(lengthpp-length&lengthlength)pp-next=new GraphNode(goal,length,roadname,p);return true;pp=p;p=p-next;pp-next=new GraphNode(goal,length,roadname);return true;bool GraphVertex:Delete(int goal)GraphNode* p;if(!Find(goal,p)return false;if(p=head)head=head-next;delete p;return true;GraphNode* pp=head;while(pp-next!=p)pp=pp-next;pp-next=p-next;delete p;return true;文件七 DiGraph.cpp#include DiGraph.h#include#include#includeusing namespace std;using std:cout;int DiGraph:findid(string name)/临时的O(n)的寻找顶点id的算法int index=1;for(int i=1;i=MaxN)break;index+;continue;/若遍历到已经被删除的点则忽略if(=name)return index;if(index=MaxN)break;i+;index+;return 0;void DiGraph:change_vertex_name(string from,string to)int id=findid(from);=to;void DiGraph:change_road_name(string from,string to,string road_name,int length)int from_int=findid(from);int to_int=findid(to);GraphNode* target;vfrom_int.Find(to_int,target);target-roadname=road_name;target-length=length;vto_int.Find(from_int,target);target-roadname=road_name;target-length=length;void DiGraph:get_info(string name)int id=findid(name);rmationendl;void DiGraph:change_info(string name,string info)int id=findid(name);rmation=info;DiGraph& DiGraph:addE(string name1,string name2,int length,string roadname)int id1=findid(name1);int id2=findid(name2);if(vid1.insert(id2,length,roadname)&vid2.insert(id1,length,roadname)e+;return *this;DiGraph& DiGraph:DeleteV(string name)int id=findid(name);if(id=0)std:cout不存在該景點。tovertex;vid.Delete(head);vhead.Delete(id);e-;vid.vertexid=0;sp-deallc(id);n-;return *this;DiGraph& DiGraph:DeleteE(string name1,string name2)int id1=findid(name1);int id2=findid(name2);if(vid1.Delete(id2)&vid2.Delete(id1)e-;return *this;ostream& operator(ostream& os,DiGraph& DG)os景点个数:DG.n;道路条数：DG.eendl;GraphVertex GV;int index=1;for(int i=1;i=DG.MaxN)break;index+;continue;/不遍历已经删除的顶点osGV.namenext)osroadname to ,length=length;os=DG.MaxN)break;index+;i+;return os;void DiGraph:getpath(int from,int to,int* kay,int *l,string& path)if(kayfromto=0)GraphNode* road_temp;vfrom.Find(to,road_temp);path=path+road_temp-roadname+t;return;getpath(from,kayfromto,kay,l,path);path=path++t;getpath(kayfromto,to,kay,l,path);return;void DiGraph:allpair(int* kay,int* l)/所有点对最短路径for(int i=1;i=n;i+)for(int j=1;j=n;j+)kayij=0;for(int i=1;i=n;i+)for(int j=1;j=n;j+)lij=-1;/初始化kay和lint index=1;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;k=n;k+)for(int i=1;i=n;i+)for(int j=1;j=n;j+)if(lik!=-1&lkj!=-1&(lij=-1)|(lik+lkj)lij)lij=lik+lkj;lji=lik+lkj;kayij=k;kayji=k;/*for(int i=1;i=n;i+)for(int j=1;j=n;j+)coutlijt;coutendl;for(int i=1;i=n;i+)for(int j=1;j=n;j+)coutkayijt;coutendl;*/floyd算法void DiGraph:Output_path(string from,string to,int* kay,int* l)/输出任意两点最短路径，使用已经准备好的kay和lstring path_passed;int start=findid(from);int end=findid(to);coutfromt;getpath(start,end,kay,l,path_passed);coutpath_passedflush;couttoendl;void DiGraph:getallpath(int start,int end,string& path_temp)/这是获得两点间所有路径的递归方法vstart.flag=true;if(start=end)coutpath_temptovertex.flag)p=p-next;continue;path_temp=path_temp+p-roadname+t++t;getallpath(p-tovertex,end,path_temp);path_temp.erase(pos);p=p-next;/if(fpath_temp.end()path_temp.erase(f,path_temp.end();/操作完毕，抹去经过该点的所有痕迹vstart.flag=false;return;void DiGraph:Output_allpath(string from,string to)int start=findid(from);int end=findid(to);string path_temp=from+t;getallpath(start,end,path_temp);inline void swap(int &a,int& b)/内联函数负责交换两个变量的值int c=a;a=b;b=c;void DiGraph:getroute(int* l,int* min_route,int* route,int n,int s,int e)/暴力的O(n!)算法 保证得到最短路径/经过多个顶点的最短路径 利用全排列算法和floyd算法得到/在perm的输出部分做改动if(s=e)int length=0,min_length=0;for(int i=0;in-1;i+)if(lrouteiroutei+1=-1)return;/有两点间没有路径；直接忽略该路径length+=lrouteiroutei+1;min_length+=lmin_routeimin_routei+1;/若lengthmin_length则交换两个数组的值/*for(int i=0;in;i+)coutrouteit;*/*coutlength;coutendl;*/if(lengthmin_length)for(int i=0;in;i+)min_routei=routei;return;/做perm处理for(int i=s;in;i+)swap(routes,routei);getroute(l,min_route,route,n,s+1,e);swap(routes,routei);void DiGraph:Output_route(int* l,int* kay,string * route_name,int n)/这里输出经过多个顶点的最短路径，利用getroute方法/并且使用了前面定义的输出最短路径的getpath方法int* route=new intn;int* min_route=new intn;string path_pass=;for(int i=0;in;i+)routei=min_routei=findid(route_namei);getroute(l,min_route,route,n,0,n-1);for(int i=0;in-1;i+)/coutiendl;coutvmin_t;getpath(min_routei,min_routei+1,kay,l,path_pass);coutpath_pass;path_pass=;coutvmin_endl;int main()string input;DiGraph dg;dg.addV(校门,学校的大门);dg.addV(食堂,学生吃饭的地方);dg.addV(教学楼,学生上课的地点);dg.addV(实验楼,学生做实验的地方);dg.addV(宿舍,学生们日常生活的地方);dg.addV(操场,给学生提供运动的场所);dg.addV(澡堂,学生洗澡的地方);dg.addE(校门,食堂,4,A路);dg.addE(校门,教