完整版数据结构毕业课程设计校园导游.docx
- 文档编号:1990053
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:33
- 大小:27.28KB
完整版数据结构毕业课程设计校园导游.docx
《完整版数据结构毕业课程设计校园导游.docx》由会员分享,可在线阅读,更多相关《完整版数据结构毕业课程设计校园导游.docx(33页珍藏版)》请在冰点文库上搜索。
完整版数据结构毕业课程设计校园导游
数据结构课程设计报告
实验三:
校园导游
1、设计要求
用无向图表示校园景点平面图,图中顶点表示主要景点,存放景点的编号、名称、简介等信息,图中的边表示景点间的道路,存放路径长度等信息。
要求能够回答有关景点介绍、游览路径等问题。
要求:
(1)查询任意景点的相关信息
(2)查询图中任意两个景点间的最短路径
(3)查询图中任意两个景点间的所有路径
(4)增加、删除、更新有关景点和道路的信息
实际输入输出情况如下:
(1)有关景点和路线的操作
(2)查看现有导游路线图
(3)对景点信息的增删改与查询
增加景点
删除景点
更改景点信息
查询景点信息
(4)对道路信息的增删改
增加道路
删除道路
更改道路信息
(5)查询两景点间所有路径
(6)查询两景点间最短路径
(7)查询经过多个景点的最短路径
1、数据结构与算法描述
1、校园导游的数据结构
整个校园导游图以一个无向加权图描述,采用邻接表作为实现图结构的方式。
(1)景点结构
每个景点是一个链表,其结构如下:
#pragmaonce
#include
#include"GraphNode.;
boolflag;到达该点的标记
public:
GraphVertex(){vertexid=0;name="";="";}
GraphVertex(intvertexid,stringname){this->vertexid=vertexid;this->name=name;this->tovertex==y.tovertex;}
};
(3)图结构
整个图的结构是用链表的数组表示,为了使景点的添加删除操作可以充分地利用该数组空间,对该数组使用模拟指针的结构进行描述。
#pragmaonce
#include"GraphVertex.();
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)
{
cout< return; } GraphNode*p; p=v[start].; } 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和l intindex=1; for(inti=1;i<=n;) { if(v[index].vertexid==0) { if(index>=MaxN)break; index++; continue; }若遍历到已经被删除的点则忽略 GraphNode*gn=v[index].) { l[index][gn->tovertex]=gn->length; gn=gn->next; } if(index==MaxN)break; i++; index++; } 以上代码初始化l将边长度信息写入,无边则为-1 for(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][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;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]]; } 若length if(length { for(inti=0;i min_route[i]=route[i]; } return; }; 做perm处理 for(inti=s;i { swap(route[s],route[i]); getroute(l,min_route,route,n,s+1,e); swap(route[s],route[i]); } } 2、分析与探讨 1.测试结果分析 通过测试结果我们发现,虽然采用的旅行商问题的算法为O(n! )的算法,但因为一般经过的景点数目不多,所以执行速度仍然比较快。 其他部分的算法运行 2.算法分析 1、两点间所有路径算法: O(n! ) 2、查询任意两点间的最短路径: O(n*3) 3、经过多点的最短路径算法: O(n! ) 附录所有源代码 文件一: GraphNode.this->tovertex==y.tovertex;} }; 文件二: GraphVertex.; boolflag;到达该点的标记 public: GraphVertex(){vertexid=0;name="";="";} GraphVertex(intvertexid,stringname){this->vertexid=vertexid;this->name=name;(); 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); }; 文件五simNode.cpp #include"simNode.0; inti=first; first=space[first]; returni; } voidSimspace: : deallc(int&i) { space[i]=first; first=i; i=-1; return; } 文件六GraphVertex.cpp #include"GraphVertex.result; } boolGraphVertex: : Find(intgoal,GraphNode*&index)const { GraphNode*p=true; } p=p->next; } returnfalse; } boolGraphVertex: : insert(intgoal,intlength,stringroadname) { GraphNode*p; if(Find(goal,p)) { cout<<"已经存在该条道路"< returnfalse; } if(true; } if(length } p=true; } pp=p; p=p->next; } pp->next=newGraphNode(goal,length,roadname); returntrue; } boolGraphVertex: : Delete(intgoal) { GraphNode*p; if(! Find(goal,p))returnfalse; if(p==true; } GraphNode*pp=true; } 文件七DiGraph.cpp #include"DiGraph.)的寻找顶点id的算法 { intindex=1; for(inti=1;i<=n;) { if(v[index].vertexid==0) { if(index>=MaxN)break; index++; continue; }若遍历到已经被删除的点则忽略 if(v[index].name==name) returnindex; if(index==MaxN)break; i++; index++; } return0; } voidDiGraph: : change_vertex_name(stringfrom,stringto) { intid=findid(from); v[id].name=to; } voidDiGraph: : change_road_name(stringfrom,stringto,stringroad_name,intlength) { intfrom_int=findid(from); intto_int=findid(to); GraphNode*target; v[from_int].Find(to_int,target); target->roadname=road_name; target->length=length; v[to_int].Find(from_int,target); target->roadname=road_name; target->length=length; } voidDiGraph: : get_info(stringname) { intid=findid(name); cout< } voidDiGraph: : change_info(stringname,stringinfo) { intid=findid(name); v[id].information=info; } DiGraph&DiGraph: : addE(stringname1,stringname2,intlength,stringroadname) { intid1=findid(name1); intid2=findid(name2); if(v[id1].insert(id2,length,roadname)&&v[id2].insert(id1,length,roadname)) e++; return*this; } DiGraph&DiGraph: : DeleteV(stringname) { intid=findid(name); if(id==0) { std: : cout<<"不存在該景點。 "< return*this; } int--; return*this; } DiGraph&DiGraph: : DeleteE(stringname1,stringname2) { intid1=findid(name1); intid2=findid(name2); if(v[id1].Delete(id2)&&v[id2].Delete(id1)) e--; return*this; } ostream&operator<<(ostream&os,DiGraph&DG) { os<<"景点个数: "< "< GraphVertexGV; intindex=1; for(inti=1;i<=DG.n;) { GV=DG.v[index]; if(GV.vertexid==0) { if(index>=DG.MaxN)break; index++; continue; }不遍历已经删除的顶点 os< "; for(GraphNode*p=GV.os; } 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; } 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和l intindex=1; for(inti=1;i<=n;) { if(v[index].vertexid==0) { if(index>=MaxN)break; index++; continue; }若遍历到已经被删除的点则忽略 GraphNode*gn=v[index].) { l[index][gn->tovertex]=gn->length; gn=gn->next; } if(index==MaxN)break; i++; index++; } 以上代码初始化l将边长度信息写入,无边则为-1 for(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][k]+l[k][j]; l[j][i]=l[i][k]+l[k][j]; kay[i][j]=k; kay[j][i]=k; } *for(inti=1;i<=n;i++) { for(intj=1;j<=n;j++) cout< cout< } for(inti=1;i<=n;i++)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 完整版 数据结构 毕业 课程设计 校园 导游