资源描述
校园导游课程设计一、问题描述:用无向网表示你所在学校的校园景点平面图,图中顶点表示主要景点,存放景点的编号、名称、简介等信息,图中的边表示景点间的道路,存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。二、实验内容:基本要求:查询各景点的相关信息;查询图中任意两个景点间的最短路径;查询图中任意两个景点间的所有路径;增加、删除、更新有关景点和道路的信息。选作内容:求多个景点的最佳(最短)游览路径。区分机动车道和人行道。实现导游图的仿真界面。三、数据结构: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(p-date.name,锦绣);strcpy(p-date.number,1);strcpy(p-date.introduce,又称一教,是学校主要教学楼之一,位于春华路与校园西路交叉口西北150米(来自高德地图),是同学们上课的主要场所之一);p-next=q-next;q-next=p;q=p;p=(Place *)malloc(sizeof(Place);p-num=2;strcpy(p-date.name,丹青);strcpy(p-date.number,2);strcpy(p-date.introduce,又称二教,是学校主要教学楼之一,位于哈尔滨市香坊区和兴路26号(来自高德地图),是同学们上课的主要场所之一);p-next=q-next;q-next=p;q=p;p=(Place *)malloc(sizeof(Place);p-num=3;strcpy(p-date.name,俭德园);strcpy(p-date.number,3);strcpy(p-date.introduce,位于学校9A公寓东北方150M处,是学生们经常去的地方,适合平民消费,价格实惠。);p-next=q-next;q-next=p;q=p;p=(Place *)malloc(sizeof(Place);p-num=4;strcpy(p-date.name,行政楼);strcpy(p-date.number,4);strcpy(p-date.introduce,位于学校操场西行200M处,是学生,老师日常处理教学事务的地点,也是学校的行政地点。);p-next=q-next;q-next=p;q=p;p=(Place *)malloc(sizeof(Place);p-num=5;strcpy(p-date.name,图书馆);strcpy(p-date.number,5);strcpy(p-date.introduce,位于篮球场西行200M处,是同学们日常,考研的学习地点,同时有大量的图书可供借阅,是黑龙江高校中藏书量最多的地点。);p-next=q-next;q-next=p;q=p;p=(Place *)malloc(sizeof(Place);p-num=6;strcpy(p-date.name,成栋);strcpy(p-date.number,6);strcpy(p-date.introduce,位于学校新食堂颐丰园西北方400米处,是各个学院事务的主要办公地点。);p-next=q-next;q-next=p;q=p;p=(Place *)malloc(sizeof(Place);p-num=7;strcpy(p-date.name,主楼);strcpy(p-date.number,7);strcpy(p-date.introduce,位于哈尔滨市香坊区农林七道街与和兴路交叉口南150米(来自高德地图)是学校众多行政,组织部门的主要办公地点。);p-next=q-next;q-next=p;q=p;p=(Place *)malloc(sizeof(Place);p-num=8;strcpy(p-date.name,颐丰园);strcpy(p-date.number,8);strcpy(p-date.introduce,位于成栋东南方400M处,是学校在15年新开放的食堂,环境优美怡人,但是物价偏高,味道一般。);p-next=q-next;q-next=p;q=p;p=(Place *)malloc(sizeof(Place);p-num=9;strcpy(p-date.name,9A);strcpy(p-date.number,9);strcpy(p-date.introduce,位于学校俭德园西南方行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;coutp-date.name;coutp-date.introduce;x=p-num;coutendl;cout请输入路径条数、相关服务的位置y、路径长度a;coutendl;for(i=1;iy;cinb;MGr.legsxy=MGr.legsyx=b;cout服务位置:numendl;cout服务编号:date.numberendl;cout服务名称:date.nameendl;cout服务简介:date.introduceendl;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-date.name 关闭!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服务名称:next-date.nameendl;cout服务简介:next-date.introducenext;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(p-next-date.name,name1);strcpy(p-next-date.number,number2);strcpy(p-next-date.introduce,introduce1);coutendl;cout服务位置:next-numendl;cout服务编号:next-date.numberendl;cout服务名称:next-date.nameendl;cout服务简介:next-date.introduceendl;coutnext;if(p-next=NULL)cout该服务不存在!endl;cout endl;coutendl;void menu() /主菜单 cout endl;cout endl;cout1 查询服务请按1键; endl;cout2 修改服务请按2键; endl;cout3 增加服务请按3键; endl;cout4 删除服务请按4键 endl;cout5 路径搜索请按5键 endl;cout6 退出系统请按6键; endl;cout endl;cout endl;int main() /主函数cout 欢迎使用东北林业大学校园导游查询系统 endl;cout endl;coutendl;int x;init(p);while(1)cout当前存在的服务个数为:Numendl;coutx;switch(x)case 1:find(p); break;case 2:replace(p);break;case 3:add(p);break;case 4:deleted(p);break;case 5:shortdistance(p);break;case 6:cout 恭喜您,成功退出系统! endl;exit(0);
展开阅读全文