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

数据结构课程设计报告实验三：校园导游一、设计要求用无向图表示校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。要求：（1）查询任意景点的相关信息（2）查询图中任意两个景点间的最短路径（3）查询图中任意两个景点间的所有路径（4）增加、删除、更新有关景点和道路的信息实际输入输出情况如下：（1）有关景点和路线的操作（2）查看现有导游路线图（3）对景点信息的增删改与查询增加景点删除景点更改景点信息查询景点信息（4）对道路信息的增删改增加道路删除道路更改道路信息（5）查询两景点间所有路径（6）查询两景点间最短路径（7）查询经过多个景点的最短路径一、数据结构与算法描述1、校园导游的数据结构整个校园导游图以一个无向加权图描述，采用邻接表作为实现图结构的方式。（1）景点结构每个景点是一个链表，其结构如下：#pragmaonce#includestring#includeGraphNode.husingnamespacestd;classGraphVertex{friendclassDiGraph;friendostream&operator(ostream&os,DiGraph&DG);protected:intvertexid;stringname;GraphNode*head;stringinformation;boolflag;//到达该点的标记public:GraphVertex(){vertexid=0;name=;head=0;flag=false;information=;}GraphVertex(intvertexid,stringname){this-vertexid=vertexid;this-name=name;head=0;flag=false;};~GraphVertex(){};intLength()const;//该顶点的度boolFind(intgoal,GraphNode*&index)const;//查找该顶点和goal之间是否有路径，如果找到则将该路径指针的引用保存在indexboolinsert(intgoal,intlength,stringroadname);//按照权值递增规则将顶点goal插入该顶点链表boolDelete(intgoal);//删除该顶点和goal间的路径};（2）路线的结构邻接链表中的每个节点代表了一条路线，其结构如下：#pragmaonce#includestringusingnamespacestd;classGraphNode{friendclassGraphVertex;public:inttovertex;intlength;stringroadname;GraphNode*next;GraphNode(intto,intlength,stringroadname=,GraphNode*next=0){this-length=length;this-tovertex=to;this-roadname=roadname;this-next=next;};~GraphNode(){};intoperator==(GraphNodey)const{returnthis-tovertex==y.tovertex;}};（3）图结构整个图的结构是用链表的数组表示，为了使景点的添加删除操作可以充分地利用该数组空间，对该数组使用模拟指针的结构进行描述。#pragmaonce#includeGraphVertex.h#includeGraphNode.h#includesimNode.hclassDiGraph{friendostream&operator(ostream&os,DiGraph&DG);friendintmain();private:intn;inte;GraphVertex*v;Simspace*sp;intMaxN;voidgetpath(intfrom,intto,int**kay,int**l,string&path);voidgetallpath(intfrom,intto,string&path_temp);public:DiGraph(intMaxN=100){this-MaxN=MaxN;n=0;e=0;v=newGraphVertex[MaxN+1];sp=newSimspace(MaxN);};~DiGraph(){delete[]v;deletesp;};intfindid(stringname);DiGraph&addV(stringname,stringinformation){inti=sp-allc();if(!i)return*this;//空间用完v[i].name=name;v[i].information=information;v[i].vertexid=i;n++;return*this;}DiGraph&DeleteV(stringname);DiGraph&addE(stringname1,stringname2,intlength,stringroadname);DiGraph&DeleteE(stringname1,stringname2);voidallpair(int**kay,int**l);voidOutput_path(stringfrom,stringto,int**kay,int**l);voidOutput_allpath(stringfrom,stringto);voidgetroute(int**l,int*min_route,int*now_route,intn,ints,inte);voidOutput_route(int**l,int**kay,string*route,intn);voidchange_vertex_name(stringfrom,stringto);voidchange_road_name(stringfrom_vertex,stringto_vertex,stringroad_name,intlength);voidget_info(stringname);voidchange_info(stringname,stringinfo);};2、对算法中的主要方法的描述：A.两点间所有路径算法：要求两点间所有路径，可以采用一个比较直观的递归算法，即从起点开始，对该起点所有邻接点执行以下操作：如果该顶点已经到达，停止递归过程。设置该顶点为已到达。如果该顶点是目标顶点，停止递归过程。对该顶点执行同样操作。其关键代码如下：voidDiGraph::getallpath(intstart,intend,string&path_temp)//这是获得两点间所有路径的递归方法{v[start].flag=true;if(start==end){coutpath_tempendl;v[start].flag=false;return;}GraphNode*p;p=v[start].head;while(p)//对每个可达的点，进行同样的寻找所有路径操作{intpos=path_temp.size();//在目标路径中记录完成剩下的递归操作之前的位置if(v[p-tovertex].flag){p=p-next;continue;}path_temp=path_temp+p-roadname+\t+v[p-tovertex].name+\t;getallpath(p-tovertex,end,path_temp);path_temp.erase(pos);//递归该点完毕，抹去递归操作过程中对字符串的改动p=p-next;}v[start].flag=false;return;}B.两点间最短路径算法采用folyd算法，求出该算法所使用的kay[][]和l[][]两个二维数组，继而利用这两个数组进行输出最短路径的操作。关键代码如下：生成kay和l的操作：voidDiGraph::allpair(int**kay,int**l)//所有点对最短路径{for(inti=1;i=n;i++)for(intj=1;j=n;j++)kay[i][j]=0;for(inti=1;i=n;i++)for(intj=1;j=n;j++)l[i][j]=-1;//初始化kay和lintindex=1;for(inti=1;i=n;){if(v[index].vertexid==0){if(index=MaxN)break;index++;continue;}//若遍历到已经被删除的点则忽略GraphNode*gn=v[index].head;while(gn){l[index][gn-tovertex]=gn-length;gn=gn-next;}if(index==MaxN)break;i++;index++;}//以上代码初始化l将边长度信息写入，无边则为-1for(intk=1;k=n;k++)for(inti=1;i=n;i++)for(intj=1;j=n;j++)if(l[i][k]!=-1&&l[k][j]!=-1&&((l[i][j]==-1)||(l[i][k]+l[k][j])l[i][j])){l[i][j]=l[i][k]+l[k][j];l[j][i]=l[i][k]+l[k][j];kay[i][j]=k;kay[j][i]=k;}}//floyd算法以下是输出路径的递归算法：voidDiGraph::getpath(intfrom,intto,int**kay,int**l,string&path){if(kay[from][to]==0){GraphNode*road_temp;v[from].Find(to,road_temp);path=path+road_temp-roadname+\t;return;}getpath(from,kay[from][to],kay,l,path);path=path+v[kay[from][to]].name+\t;getpath(kay[from][to],to,kay,l,path);return;}C.经过多个顶点的最短路径算法这里我利用folyd算法产生的两个二维数组，生成途径景点的全排列，然后利用l[][]求出排列中路径最短的路，再用与floyd算法相同的输出最短路径的算法进行输出，其关键代码如下：voidDiGraph::getroute(int**l,int*min_route,int*route,intn,ints,inte)//暴力的O(n!)算法保证得到最短路径//经过多个顶点的最短路径利用全排列算法和floyd算法得到{//在perm的输出部分做改动if(s==e){intlength=0,min_length=0;for(inti=0;in-1;i++){if(l[route[i]][route[i+1]]==-1)return;//有两点间没有路径；直接忽略该路径length+=l[route[i]][route[i+1]];min_length+=l[min_route[i]][min_route[i+1]];}//若lengthmin_length则交换两个数组的值if(lengthmin_length){for(inti=0;in;i++)min_route[i]=route[i];}return;};//做perm处理for(inti=s;in;i++){swap(route[s],route[i]);getroute(l,min_route,route,n,s+1,e);swap(route[s],route[i]);}}二、分析与探讨1.测试结果分析通过测试结果我们发现，虽然采用的旅