校园导游课程设计.doc

校园导游课程设计一、问题描述：用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。二、实验内容：基本要求：查询各景点的相关信息；查询图中任意两个景点间的最短路径；查询图中任意两个景点间的所有路径；增加、删除、更新有关景点和道路的信息。选作内容：求多个景点的最佳（最短）游览路径。区分机动车道和人行道。实现导游图的仿真界面。三、数据结构：typedef struct messageint num;/景点代码char name100;/景点名称char pro500;/简介Ciceroni;Ciceroni school10=1,行政楼n,2,食堂n,3,赛博楼,信息分院办公室所在地n,4,求是楼,实验楼计算机中心n,5,格致楼,法学管理学院,6,工程实习中心,金工实习n,7,仰仪楼,机电计测分院n,8,体育馆,旁边有篮球场足球场还有网球场n,9,一号教学楼，主要以阶梯教室为主n,10,二号教学楼，小教室为多n; /*景点名称和简介*/操作：/*给景点之间的路径赋最大值*/*最短路径的C语言函数*/*输出最短路径和最短距离函数*/*输入景点代码查景点名称和简介*/*输入景点代码查到其它景点的最短距离*/四、需求分析：现在大多数学校由于不断扩张，造成学校面积大而造成人们人出游困难的问题，人们如果不熟悉该地点。找到一个地方就会很困难，然而如果有一个校园导游系统，人们出行就会方便很多。五、概要设计：用图的算法进行构造，用链表建立无向图，然后再用深度优先遍历进行搜索，查找所需的路径。再用弗洛伊德算法求出两个景点之间的最短路径。系统结构图： 六、详细设计：浏览学校全景：用数组存放这个学校的全部景点，再通过遍历数组打印出学校的所有景点及其信息。寻找最短路径：利用佛洛伊德算法，在两个节点之间设置节点通过对比权值大小，找出权值最小的路径，即为所求路径。增加项目：在链表中增加一个元素，调整元素指针指向该元素，将该元素的指针指向后一个元素。删除项目：在链表中删除一个元素，将该元素前面的元素指针断开指向该元素后的元素，再将该元素的指针断开。七、程序源代码：#include#include#include#include#define N 100 /服务个数最大100#define Road 1000 /定义路径为1000int Num=9; /目前服务个数using namespace std;typedef struct Elemtypechar name30;char number10;char introduce200;Elemtype;typedef struct Placeint num; /位置序号Place *next;Elemtype date; /服务信息Place; /定义服务typedef struct MGraphPlace place;int legsNN; /存放路径长MGraph;MGraph MGr; /全局变量,定义MGr为MGraph类型int shortestNN; /定义全局变量存贮最小路径int pathNN; /定义存贮路径Place *p;void init(Place *&head) /定义服务位置Place *p,*q;head=(Place *)malloc(sizeof(Place);head-next=NULL;q=head;p=(Place *)malloc(sizeof(Place);p-num=1;strcpy(,锦绣);strcpy(p-date.number,1);strcpy(roduce,又称一教，是学校主要教学楼之一，位于春华路与校园西路交叉口西北150米（来自高德地图），是同学们上课的主要场所之一);p-next=q-next;q-next=p;q=p;p=(Place *)malloc(sizeof(Place);p-num=2;strcpy(,丹青);strcpy(p-date.number,2);strcpy(roduce,又称二教，是学校主要教学楼之一，位于哈尔滨市香坊区和兴路26号（来自高德地图），是同学们上课的主要场所之一);p-next=q-next;q-next=p;q=p;p=(Place *)malloc(sizeof(Place);p-num=3;strcpy(,俭德园);strcpy(p-date.number,3);strcpy(roduce,位于学校9A公寓东北方150M处，是学生们经常去的地方，适合平民消费，价格实惠。);p-next=q-next;q-next=p;q=p;p=(Place *)malloc(sizeof(Place);p-num=4;strcpy(,行政楼);strcpy(p-date.number,4);strcpy(roduce,位于学校操场西行200M处，是学生，老师日常处理教学事务的地点，也是学校的行政地点。);p-next=q-next;q-next=p;q=p;p=(Place *)malloc(sizeof(Place);p-num=5;strcpy(,图书馆);strcpy(p-date.number,5);strcpy(roduce,位于篮球场西行200M处，是同学们日常，考研的学习地点，同时有大量的图书可供借阅，是黑龙江高校中藏书量最多的地点。);p-next=q-next;q-next=p;q=p;p=(Place *)malloc(sizeof(Place);p-num=6;strcpy(,成栋);strcpy(p-date.number,6);strcpy(roduce,位于学校新食堂颐丰园西北方400米处，是各个学院事务的主要办公地点。);p-next=q-next;q-next=p;q=p;p=(Place *)malloc(sizeof(Place);p-num=7;strcpy(,主楼);strcpy(p-date.number,7);strcpy(roduce,位于哈尔滨市香坊区农林七道街与和兴路交叉口南150米（来自高德地图）是学校众多行政，组织部门的主要办公地点。);p-next=q-next;q-next=p;q=p;p=(Place *)malloc(sizeof(Place);p-num=8;strcpy(,颐丰园);strcpy(p-date.number,8);strcpy(roduce,位于成栋东南方400M处，是学校在15年新开放的食堂，环境优美怡人，但是物价偏高，味道一般。);p-next=q-next;q-next=p;q=p;p=(Place *)malloc(sizeof(Place);p-num=9;strcpy(,9A);strcpy(p-date.number,9);strcpy(roduce,位于学校俭德园西南方行150M处，是信息学院男生的主要休息场所，现在在该公寓楼居住的601寝室的人将会在二十年后成为男神。);p-next=q-next;q-next=p;q=p;int i,j; /定义服务间的距离for(i=1;i=N;i+)for(j=1;j=N;j+)MGr.legsij=Road;for(i=1;i=N;i+)shortestij=0;MGr.legs01=MGr.legs10=200;MGr.legs02=MGr.legs20=500;MGr.legs13=MGr.legs31=150;MGr.legs34=MGr.legs43=50;MGr.legs35=MGr.legs53=800;MGr.legs45=MGr.legs54=850;MGr.legs12=MGr.legs21=550;MGr.legs27=MGr.legs72=1000;MGr.legs87=MGr.legs78=950;MGr.legs79=MGr.legs97=26;void folyd() /佛洛依德算法int i,j,k;for(i=1;i=N;i+)for(j=1;j=N;j+)shortestij=MGr.legsij;pathij=0;for(k=1;k=N;k+)for(i=1;i=N;i+)for(j=1;j(shortestik+shortestkj)shortestij=shortestik+shortestkj;pathij=k;pathji=k; /记录经过的路径void display(int i,int j) /输出两个服务的路径及最短路径int a,b;a=i;b=j;cout我们向您推荐的最短路径是： ;if(ij)couta;while(pathij!=0)coutpathij;if(ij)j=pathij;elsei=pathji;coutbendl;cout endl;cout您所查找的ab两个服务之间的最短距离为:shortestab米。endl;elsecouta;while(pathij!=0)coutpathij;if(ij)j=pathij;elsei=pathji;coutbendl;cout您所查找的ab两个服务之间的最短路径是:shortestab 米。endl;cout next,*q=head-next;cout请输入要查询的两个服务的位置序号:ij;while(t)if(t-num=i)break;else t=t-next;while(q)if(q-num=j)break;else q=q-next;if(q=NULL|t=NULL)cout抱歉，没有通向的路径！endl;elsefolyd();display(i,j);coutnext;p=(Place *)malloc(sizeof(Place);int a;int b;int x;int y;int i;coutp-num;coutnum=p-num)cout此位置已被其它服务占用,请重新输入其它空白的位置。endl;cout p-num;continue;else t=t-next;if(t=NULL)coutp-date.number;;roduce;x=p-num;coutendl;cout请输入路径条数、相关服务的位置y、路径长度a;coutendl;for(i=1;iy;cinb;MGr.legsxy=MGr.legsyx=b;cout服务位置：numendl;cout服务编号：date.numberendl;cout服务名称：endl;cout服务简介：roduceendl;cout next;while(q-next)q=q-next;p-next=q-next;q-next=p;Num+;void deleted(Place *&head) /删除服务int text=0;char cnum10;Place *p=head;cout输入删除的服务编号：endl;cout cnum;while(p-next)if(strcmp(p-next-date.number,cnum)=0)cout恭喜您，您已成功将服务 关闭!next=p-next-next;Num-;break;elseif(p-next=NULL)cout该服务不存在！endl;cout next;coutendl;void find(Place *&head) /查询服务int n;Place *p=head;cout输入查询的服务位置序号：;cout n;while(p-next)if(p-next-num=n)cout服务位置：next-numendl;cout服务编号：next-date.numberendl;cout服务名称：endl;cout服务简介：roducenext;if(p-next=NULL)cout该服务不存在！endl;cout endl;cout endl;void replace(Place *&head) /修改服务char name120;char number110,number210;char introduce1100;Place *p=head;cout输入要修改的的服务编号：endl;cout number1;while(p-next)if(strcmp(p-next-date.number,number1)=0)coutname1;coutnumber2;coutintroduce1;strcpy(,name1);strcpy(p-next-date.number,number2);strcpy(roduce,introduce1);coutendl;cout服务位置：ne