景区旅游信息管理系统.doc

安阳师范学院 数据结构课外实践 数据结构课外实践报告项 目 名 称 景区旅游信息管理系统 所 在 班 级： 小 组 成 员： 指 导 教 师： 起 止 时 间： 课外实践评定成绩记录指导教师意见系统完成情况：优 良 中 差报告完成情况：优 良 中 差答辩评定成绩团队整体成绩：成员成绩“姓名”“学号”综 合 成 绩项目基本信息项目名称景区旅游信息管理系统项目简介旅游业随着我国经济的增长和人民收入的提高迅速发展，而景区旅游管理问题日益紧迫。本项目提供基本的有关的管理操作，能够智能化的管理，还能够为导游提供指引，为游客指路，小组成员任务分工：项目基本框架设计、项目工程中“4.cpp”文件“main.cpp”文件和“structure.h”文件 、后期的调试工作、PPT制作。：项目工程中的“3.cpp”文件、课外实践报告。：项目工程中的“2.cpp”文件。：项目工程中的“1.cpp”文件。一、 问题描述及分析在旅游景区，经常会遇到游客打听从一个景点到另一个景点的最短路径和最短距离，这类游客不喜欢按照导游图的线路来游览，而是挑选自己感兴趣的景点游览。为于帮助这类游客信息查询，就需要计算出所有景点之间最短路径和最短距离。算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一个景区旅游信息管理系统，实现的主要功能包括制订旅游景点导游线路策略和制订景区道路铺设策略。任务中景点分布是一个无向带权连通图，图中边的权值是景点之间的距离。 （1）景区旅游信息管理系统中制订旅游景点导游线路策略，首先通过遍历景点，给出一个入口景点，建立一个导游线路图，导游线路图用有向图表示。遍历采用深度优先策略，这也比较符合游客心理。（2）为了使导游线路图能够优化，可通过拓朴排序判断图中有无回路，若有回路，则打印输出回路中的景点，供人工优化。（3）在导游线路图中，还为一些不愿按线路走的游客提供信息服务，比如从一个景点到另一个景点的最短路径和最短距离。在本线路图中将输出任意景点间的最短路径和最短距离。（4）在景区建设中，道路建设是其中一个重要内容。道路建设首先要保证能连通所有景点，但又要花最小的代价，可以通过求最小生成树来解决这个问题。本任务中假设修建道路的代价只与它的里程相关。因此归纳起来，本任务有如下功能模块：创建景区景点分布图；输出景区景点分布图（邻接矩阵）输出导游线路图；判断导游线路图有无回路；求两个景点间的最短路径和最短距离；输出道路修建规划图。主程序用菜单选项供用户选择功能模块。二、 功能模块及结构描述1.结构: *图的邻接表存储结构*typedef struct ArcNodeint adjvex;/该弧所指向的顶点的位置;int weight;/弧长度struct ArcNode*nextarc;/指向下一条弧的指针;ArcNode;typedef struct VNodeVertexType data;/顶点信息ArcNode *firstarc;/指向第一条依附该顶点的弧的指针VNode,*AdjList;typedef structAdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数;ALGraph;/*end*/*图的邻接矩阵存储结构*typedef char VertexType;typedef structVertexType*vexs;/顶点向量;int*arcs;/邻接矩阵/存储对应的长度int vexnum,arcnum;/图的当前顶点数和弧数;MGraph;/*end*/*十字链表存储结构*typedef struct ArcBoxint tailvex,headvex;/该弧的尾和头顶点的位置int weight;/该弧的长度;struct ArcBox *hlink,*tlink;/分别为弧头相同和弧尾相同的弧的链域ArcBox;typedef struct VexNodeVertexType data;ArcBox *firstin,*firstout;/分别指向该顶点的第一条入弧和出弧VexNode;typedef struct VexNode *xlist;/表头向量int vexnum,arcnum;/当前顶点数和边数;OLGraph;/*end*/*求导游线路所用的结构(双向链表)*struct guideNodeint adj;guideNode*next;/指向节点后继guideNode*prior;/指向节点前驱;2.功能模块: /*求导游线路图*void guideGraph(ALGraph&G,OLGraph&OG,guideNode*&H);/*创建有向图的十字链表*void createOLGraph(OLGraph&ag);/*创建图的邻接表存储结构*void createALGraph(ALGraph&ag);/#/*转换成邻接矩阵*void transition(ALGraph&ag,MGraph&mg);/*输出邻接矩阵*void printMGraph(MGraph mg);/*确定该顶点在十字链表结构中顶点向量的位置*int LocateOLGraphGraph(OLGraph&ag,VertexType d);/*确定该节点在邻接表结构中顶点向量中的位置*int LocateVexALGraph(ALGraph&ag,VertexType d);/*确定该节点在邻接矩阵结构中顶点向量中的位置*int LocateVexMGraph(MGraph&mg,VertexType d);/#/*深度优先遍历*void DFSTraverse(const ALGraph&G);/*从第v个顶点出发递归地深度优先遍历图G*void DFS(const ALGraph&G,int v);/*拓扑排序*int TopologicalSort(const OLGraph&G);/*Floyd算法*void ShortestPath_FLOYD(ALGraph&G,int *&path,int *&d);/*还原最短路径(非递归算法)*void explainPath(int*path,int i,int j,int *S,int &top);/从i到j的路径/*输出路径及长度*void printPath(ALGraph&G,int *path,int *d);/*最小生成树(普利姆算法)*/辅助结构typedef structVertexType adjvex;int lowcost;Closedeg,*CLOSEDEG;/*求出下一条最短的边*int minimum(CLOSEDEG closedeg);/*输出最小生产树的各条边*void MiniSpanTree_PRIM( ALGraph&G,VertexType u);欢迎进入管理系统,请选择:三、 主要流程描述判断图中有无回路输出深度优先遍历序列.退出输出最小生成树中的边输出由深度优先遍历序列得到的导游线路图.输出转换后的邻接矩阵.创建邻接表.四、 使用说明程序运行后，进入界面：备注:需按从1 到7的持续执行,因各模块不独立.在如上所示的界面下进行基本的操作。五、 问题及解决方法问题：调试时数据录入问题解决方法:使用文件保存图的信息 邻接表转换成矩阵时,那些在邻接表中体现不出的边如何赋值?解决方法:创建邻接矩阵时,全部元素先初始化为0,在邻接表中能体现的边赋值为相应的长度,而其余还为0 深度优先遍历时,如何保存遍历路径?解决方法:用全局变量. (4)如何完成从深度优先遍历序列到导游线路的转换?解决方法:开始时按”学生课外实践题目”中提供的算法设计,发现无法解决复杂的情况,”实践题目”中的算法是让p在深度优先遍历序列中回溯,我们用双向链表存储导游线路,并且让p在为完成的导游线路中回溯即可解决,在ppt中有详细解释. (5)在拓扑排序中如何统计各顶点入度? 解决方法:用图的十字链表存储结构. (6)在弗洛伊德算法中如何还原路径? 解决方法:用二维数组存储路径,使用非递归算法实现还原.六、 课外实践总结1、通过课外实践使我们在巩固了原有的理论知识上，又培养了灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力，使我们体会到自身知识和能力在实际中的应用和发挥。其次，它激发了我们创新意识，开发创造的能力和培养沟通能力。2、这次课外实践设计让我们受益匪浅。我们不仅学到了很多知识和技能，更重要的是我们学会了如何运用所学知识去解决实际问题。在完成实践报告的过程中，遇到一些困难，但经过共同努力，仔细研读教材和相关资料（网络），最终解决.既学到知识，我们也体会到了团队合作的重要性，锻炼了团队协作的意识，以及不怕困难，不惧失败的精神。3、通过这次课外实践，我们深刻的认识到了自己在学习方面的不足之处，但我们也认识到，要学好一门学科，没有刻苦钻研的精神是不行的，只有在不断的尝试中，经历失败，从失败中总结经验，然后再不断的尝试，才能获得成功。七、 源代码“structure.h”文件：#ifndef structre_h_h#define structre_h_h#include#includeusing namespace std;typedef char VertexType;#define MAX 10000/*图的邻接表存储结构*typedef struct ArcNodeint adjvex;/该弧所指向的顶点的位置;int weight;/弧长度struct ArcNode*nextarc;/指向下一条弧的指针;ArcNode;typedef struct VNodeVertexType data;/顶点信息ArcNode *firstarc;/指向第一条依附该顶点的弧的指针VNode,*AdjList;typedef structAdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数;ALGraph;/*end*/#/*图的邻接矩阵存储结构*typedef char VertexType;typedef structVertexType*vexs;/顶点向量;int*arcs;/邻接矩阵/存储对应的长度int vexnum,arcnum;/图的当前顶点数和弧数;MGraph;/*end*/#/*十字链表存储结构*typedef struct ArcBoxint tailvex,headvex;/该弧的尾和头顶点的位置int weight;/该弧的长度;struct ArcBox *hlink,*tlink;/分别为弧头相同和弧尾相同的弧的链域ArcBox;typedef struct VexNodeVertexType data;ArcBox *firstin,*firstout;/分别指向该顶点的第一条入弧和出弧VexNode;typedef struct VexNode *xlist;/表头向量int vexnum,arcnum;/当前顶点数和边数;OLGraph;/*end*/#/*求导游线路所用的结构(双向链表)*struct guideNodeint adj;guideNode*next;/指向节点后继guideNode*prior;/指向节点前驱;/*end*/#/*求导游线路图*void guideGraph(ALGraph&G,OLGraph&OG,guideNode*&H);/*创建有向图的十字链表*void createOLGraph(OLGraph&ag);/*创建图的邻接表存储结构*void createALGraph(ALGraph&ag);/#/*转换成邻接矩阵*void transition(ALGraph&ag,MGraph&mg);/*输出邻接矩阵*void printMGraph(MGraph mg);/*确定该顶点在十字链表结构中顶点向量的位置*int LocateOLGraphGraph(OLGraph&ag,VertexType d);/*确定该节点在邻接表结构中顶点向量中的位置*int LocateVexALGraph(ALGraph&ag,VertexType d);/*确定该节点在邻接矩阵结构中顶点向量中的位置*int LocateVexMGraph(MGraph&mg,VertexType d);/#/*深度优先遍历*void DFSTraverse(const ALGraph&G);/*从第v个顶点出发递归地深度优先遍历图G*void DFS(const ALGraph&G,int v);/*拓扑排序*int TopologicalSort(const OLGraph&G);/*Floyd算法*void ShortestPath_FLOYD(ALGraph&G,int *&path,int *&d);/*还原最短路径(非递归算法)*void explainPath(int*path,int i,int j,int *S,int &top);/从i到j的路径/*输出路径及长度*void printPath(ALGraph&G,int *path,int *d);/*最小生成树(普利姆算法)*/辅助结构typedef structVertexType adjvex;int lowcost;Closedeg,*CLOSEDEG;/*求出下一条最短的边*int minimum(CLOSEDEG closedeg);/*输出最小生产树的各条边*void MiniSpanTree_PRIM( ALGraph&G,VertexType u);#endif“1.cpp”文件#includestructure.h/*创建图的邻接表存储结构*void createALGraph(ALGraph&ag)ifstream fin(test.txt,ios:in);if(fin=NULL)cout文件无法打开!vnumanum;/输入顶点数,边数,和是否有信息的判断信息ag.vexnum=vnum;/ag.arcnum=anum;/ag.vertices=new VNodevnum;/开辟空间,存储顶点信息for(i=0;iag.verticesi.data;/输入顶点信息VertexType d1,d2;ArcNode *p;int weight;for(i=0;id1d2weight;m=LocateVexALGraph(ag,d1);/确定d1在顶点向量中的位置n=LocateVexALGraph(ag,d2);/确定d2在顶点向量中的位置p=new ArcNode;/开辟空间,存储边的信息p-adjvex=m;/p-weight=weight;/把该边链入邻接表p-nextarc=ag.verticesn.firstarc;ag.verticesn.firstarc=p;p=new ArcNode;p-adjvex=n;p-weight=weight;/把对应的边链入邻接表p-nextarc=ag.verticesm.firstarc;ag.verticesm.firstarc=p;cout邻接表:endl;for(i=0;iag.vexnum;i+)coutag.verticesi.datanextarc)coutadjvex.data ;/输出到屏幕以备查看coutendl;“2.cpp”文件#includestructure.h/*转换成邻接矩阵*void transition(ALGraph&ag,MGraph&mg)mg.vexnum=ag.vexnum;/顶点数mg.arcnum=ag.arcnum;/边数mg.vexs=new VertexTypemg.vexnum;/开辟空间,存储顶点信息for(int i=0;img.vexnum;i+)mg.vexsi=ag.verticesi.data;/复制节点信息/*开辟空间,存储邻接矩阵*mg.arcs=new int*mg.vexnum;for(i=0;img.vexnum;i+)mg.arcsi=new intmg.vexnum;/*end*ArcNode*p;int j;/*邻接表转化为邻接矩阵*for(i=0;img.vexnum;i+)for(j=0;jnextarc)mg.arcsip-adjvex=p-weight;/*end*/*输出邻接矩阵*void printMGraph(MGraph mg)int i,j;cout*endl;cout邻接矩阵为:endl;for(i=0;img.vexnum;i+)for(j=0;jmg.vexnum;j+)coutmg.arcsijt;coutendl;“3.cpp”文件#includestructure.hbool *visited;/访问标记数组;int *InDegree;/顶点入度数组;int *guide;/存储深度优先遍历路径int i=0;/*深度优先遍历*void DFSTraverse(const ALGraph&G)guide=new intG.vexnum;int i;int sum=0;visited=new boolG.vexnum;for(i=0;iG.vexnum;i+)visitedi=false;for(i=0;iG.vexnum;i+)if(!visitedi)sum+;/统计连通分量DFS(G,i);coutendl连通分量数为:sumendl;deletevisited;/*从第v个顶点出发递归地深度优先遍历图G*void DFS(const ALGraph&G,int v)visitedv=true;coutG.verticesv.datanextarc)/对剩下的图深度优先遍历if(!visitedp-adjvex)DFS(G,p-adjvex);/*求导游线路图*/H为双向循环链表,存储导游线路void guideGraph(ALGraph&G,OLGraph&OG,guideNode*&H)H=new guideNode;/建头结点H-next=H-prior=H;/双向循环链表/创建十字链表OG.vexnum=G.vexnum;OG.arcnum=G.arcnum;OG.xlist=new VexNodeG.vexnum;for(int j=0;jadj=guidei+;/初始化,表示第一个顶点已在导游线路中且是第一个顶点p_o-next=H-next;p_o-prior=H;H-next-prior=p_o;H-next=p_o;guideNode*p_o1;guideNode*p_end=p_o;while(iadj.firstarc;while(p_a)/查找是否有边if(p_a-adjvex=guidei)break;p_a=p_a-nextarc;if(p_a)/若有边p_o1=new guideNode;p_o1-adj=guidei;i+;/i指向下一个位置/插入到表尾p_o1-next=p_end-next;p_o1-prior=p_end;p_end-next-prior=p_o1;p_end-next=p_o1;p_end=p_end-next;/p_end始终指向最后一个元素p_o=p_end;/p_o指向最后一个元素elsep_o=p_o-prior;/p_o退一个位置p_o1=new guideNode;p_o1-adj=p_o-adj;/把p_o所指结点插入p_o1-next=p_end-next;p_o1-prior=p_end;p_end-next-prior=p_o1;p_end-next=p_o1;p_end=p_end-next;/p_end始终指向最后一个元素p_o=H-next;p_o1=p_o-next;/p_o1指向第一个节点ArcBox*p_arc;while(p_o1!=H)/创建十字链表结构,以便拓扑排序p_arc=new ArcBox;/弧结点p_arc-tailvex=p_o-adj;/弧尾位置p_arc-headvex=p_o1-adj;p_arc-tlink=OG.xlistp_o-adj.firstout;/顶点结点的弧尾链域地址赋值给相对应的弧的tlink链域p_arc-hlink=OG.xlistp_o1-adj.firstin;OG.xlistp_o-adj.firstout=p_arc;OG.xlistp_o1-adj.firstin=p_arc;p_o=p_o1;p_o1=p_o1-next;/*拓扑排序*int TopologicalSort(const OLGraph&OG)int i,indg,k,count=0;ArcBox*p;InDegree =new int OG.vexnum;int *S=new int OG.vexnum;/栈int top=0;/栈顶指针初始化for(i=0;ihlink)indg+;InDegreei=indg;if(!indg)/入度为零的顶点入栈;Stop+=i;while(top)/栈不空时循环k=S-top;/栈顶元素出栈coutOG.xlistk.datatlink)InDegreep-headvex-;/对应的顶点入度减1后入度为零if(InDegreep-headvex=0)Stop+=p-headvex;coutendl*endl;if(countOG.vexnum)cout导游线路中有回路!endl;cout回路中的顶点:t;for(i=0;iOG.vexnum;i+)if(InDegreei!=0)coutOG.xlisti.data ;elsecout导游线路中无回路!endl;coutj最短路径的j的前一个顶点void ShortestPath_FLOYD(ALGraph&G,int *&path,int *&d)int i,j,k;path=new int*G.vexnum;d=new int*G.vexnum;for(i=0;iG.vexnum;i+)pathi=new intG.vexnum;di=new intG.vexnum;ArcNode*p_a;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)dij=MAX;/表示无穷大pathij=0;/path初始化为-1,表示无路径;for(i=0;inextarc)pathip_a-adjvex=i;/路径dip_a-adjvex=p_a-weight;/长度for(k=0;kG.vexnum;k+)for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)if(dik+dkjk的路径已知,k-j的路径已知dij=dik+dkj;/*还原最短路径*void explainPath(int*path,int i,int j,int *S,int &top)/从i到j的路径top=0;/栈顶指针初始化Stop+=j;/最后一个顶点入栈while(pathij!=i)Stop+=pathij;j=pathij;Stop+=i;/第一个顶点入栈/*输出路径及长度*void printPath(ALGraph&G,int *path,int *d)char c1,c2;int *S=new intG.vexnum;/路径栈int top;/栈顶指针int i,j;for(i=0;iG.vexnum;i+)cout始点t终点t路径ttt长度n;for(j=0;jG.vexnum;j+)if(i=j)continue;coutG.verticesi.datatG.verticesj.datat;explainPath(path,i,j,S,top);while(top)coutG.verticesS-top.data ;/输出路径couttttdijendl;coutc1;coutc2;i=LocateVexALGraph(G,c1);j=LocateVexALGraph(G,c2);coutnnn路径ttt长度n;explainPath(path,i,j,S,top);while(top)coutG.verticesS-top.data ;/输出路径couttttdijendl;/*最小生成树(普利姆算法)*/*求出下一条最短的边*int minimum(int n,CLOSEDEG closedeg)int i;int k;for(i=0;in;i+)if(closedegi.lowcost!=0)k=i;break;for(i+;in;i+)if(closedegi.lowcost)&(closedegi.lowcostclosedegk.lowcost)k=i;return k;/*输出最小生产树的各条边*void MiniSpanTree_PRIM( ALGraph&G,VertexType u)CLOSEDEG closedeg=new ClosedegG.vexnum;int k=LocateVexALGraph(G,u);int k1;ArcNode*p;for(int i=0;inextarc)if(p-adjvex=k)continue;k1=p-adjvex;closedegk1.adjvex=u;/表示从u到p-adjvex有边closedegk1.lowcost=p-weight;/记录从u到p-adjvex的距离/循环G.vexnum-1次,每循环一次,找出一个结点for(