数据结构校园导游程序设计合集.docx

《数据结构校园导游程序设计合集.docx》由会员分享，可在线阅读，更多相关《数据结构校园导游程序设计合集.docx（50页珍藏版）》请在三一办公上搜索。

1、数据结构校园导游程序设计合集校园导游程序(c+) 问题描述: 用无向网表示你所在学校的校园景点平面图,图中顶点表示主要景点,存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。 基本要求： 1、查询各景点的相关信息。 2、查询图中任意两个景点间的最短路径。 3、查询图中任意两个景点间的所有路径。 4、增加、删除、更新有关景点和道路的信息。 /*校园导游程序*/*问题描述 用无向网表示学校的校园景点平面图，图中顶点表示主要景点， 存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景

2、点介绍、游览路径等问题。 游客通过终端可询问： 从某一景点到另一景点的最短路径。 游客从公园进入，选取一条最佳路线。 使游客可以不重复地浏览各景点，最后回到出口。 基本要求 将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路， 边上的权值表示距离为此图选择适当的数据结构。 把各种路径都显示给游客，由游客自己选择浏览路线。 画出景点分布图于屏幕上。 实现提示 构造一个无向图G并用邻接矩阵来存储。 利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组pi来记录， 最短路径长度就用一维数组di存放；i的范围：020。 一维数组have是用来记录最短路径出现顶点的顺

3、序。 根据起点和终点输出最短路径和路径长度。 */ #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include #include #include #include typedef struct ArCell int adj; /路径长度 ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct /图中顶点表示主要景点，存放景点的编号、名称、简介等信息， char name30; int num; char introductio

4、n100;/简介 infotype; typedef struct infotype vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; MGraph; MGraph b; void cmd(void); MGraph InitGraph(void); void Menu(void); void Browser(MGraph *G); void ShortestPath_DIJ(MGraph * G); void Floyd(MGraph *G); void Search(MGraph *G); int LocateVex(MGraph

5、 *G,char* v); MGraph * CreatUDN(MGraph *G); void print(MGraph *G); /*/ void main(void) system(color 1f); system(mode con: cols=140 lines=130); cmd; /*/ void cmd(void) int i; b=InitGraph; Menu; scanf(%d,&i); while(i!=5) switch(i) case 1:system(cls);Browser(&b);Menu;break; case 2:system(cls);ShortestP

6、ath_DIJ(&b);Menu;break; case 3:system(cls);Floyd(&b);Menu;break; case 4:system(cls);Search(&b);Menu;break; case 5:exit(1);break; default:break; scanf(%d,&i); MGraph InitGraph(void) MGraph G; int i,j; G.vexnum=10; G.arcnum=14; for(i=0;iG.vexnum;i+) G.vexsi.num=i; strcpy(G.vexs0.name,综合食堂); strcpy(G.v

7、exs0.introduction,新建标准化食堂); strcpy(G.vexs1.name,东西办公楼); strcpy(G.vexs1.introduction,全体教师办公场所，楼高12层，各种设施齐全); strcpy(G.vexs2.name,5号学生宿舍楼); strcpy(G.vexs2.introduction,计算机系男生宿舍楼，苏式建筑); strcpy(G.vexs3.name,医院); strcpy(G.vexs3.introduction,校医院,设施不是很齐全，只能看小病，收费较贵); strcpy(G.vexs4.name,图书馆); strcpy(G.vexs

8、4.introduction,藏书60万册,设施良好，2楼为电子阅览室，环境幽雅); strcpy(G.vexs5.name,足球场); strcpy(G.vexs5.introduction,现代化塑胶跑道,人造草坪,适宜锻炼身体的场所); strcpy(G.vexs6.name,沁园); strcpy(G.vexs6.introduction,绿树成荫,适宜休息和读书); strcpy(G.vexs7.name,主教学楼); strcpy(G.vexs7.introduction,学院最大的教学楼,共5层，环形建筑,适宜学习); strcpy(G.vexs8.name,西教学楼); str

9、cpy(G.vexs8.introduction,学院第二大教学楼,环境较差); strcpy(G.vexs9.name,多媒体楼); strcpy(G.vexs9.introduction,多媒体教学场所,设施先进,环境良好); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij.adj=INFINITY; G.arcs01.adj=100; G.arcs02.adj=200; G.arcs06.adj=400; G.arcs17.adj=300; G.arcs23.adj=120; G.arcs36.adj=220; G.arcs34.

10、adj=100; G.arcs45.adj=300; G.arcs49.adj=250; G.arcs59.adj=350; G.arcs67.adj=60; G.arcs69.adj=200; G.arcs78.adj=50; G.arcs89.adj=20; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsji.adj=G.arcsij.adj; return G; /InitGraph end void Menu printf(n printf( n); printf( n); printf( n); printf( n); print

11、f( n); printf( n); printf( n); printf(Option-:); void Browser(MGraph *G) 石家庄铁道学院导游图n); 1.浏览校园全景 2.查看所有游览路线 3.选择出发点和目的地 4.查看景点信息 5.退出系统 int v; printf(n); printf(编号景点名称 简介 n); for(v=0;vvexnum;v+) printf(%-4d%-16s%-56sn,G-vexsv.num,G-vexsv.name,G-vexsv.introduction); printf(n); / 迪杰斯特拉算法来计算出起点到各个顶点之间的最

12、短路径,v0为起点 void ShortestPath_DIJ(MGraph * G) int v,w,i,min,t=0,x,flag=1,v0; int final20, D20, p2020; while(flag) printf(请输入一个起始景点编号:); scanf(%d,&v0); if(v0G-vexnum) printf(景点编号不存在!请重新输入景点编号:); scanf(%d,&v0); if(v0=0&v0vexnum) flag=0; for(v=0;vvexnum;v+) finalv=0; Dv=G-arcsv0v.adj; for(w=0;wvexnum;w+)

13、 pvw=0; if(DvINFINITY) pvv0=1;pvv=1; Dv0=0;finalv0=1; for(i=1;ivexnum;i+) min=INFINITY; for(w=0;wvexnum;w+) if(!finalw) if(Dwmin)v=w;min=Dw; finalv=1; for(w=0;wvexnum;w+) if(!finalw&(min+G-arcsvw.adjarcsvw.adj; for(x=0;xvexnum;x+) pwx=pvx; pww=1; for(v=0;vvexnum;v+) if(v0!=v) printf(%s,G-vexsv0.name

14、); for(w=0;wvexnum;w+) if(pvw&w!=v0) printf(-%s,G-vexsw.name); t+; if(tG-vexnum-1&v0!=v)printf( 总路线长%dmnn,Dv); /ShortestPath_DIJ end void Floyd(MGraph *G) int v,u,i,w,k,j,flag=1,p101010,D1010; for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) Dvw=G-arcsvw.adj; for(u=0;uvexnum;u+) pvwu=0; if(DvwINFINITY) pvwv=

15、1;pvww=1; for(u=0;uvexnum;u+) for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) if(Dvu+DuwDvw) Dvw=Dvu+Duw; for(i=0;ivexnum;i+) pvwi=pvui|puwi; while(flag) printf(请输入出发点和目的地的编号:); scanf(%d%d,&k,&j); if(kG-vexnum|jG-vexnum) printf(景点编号不存在!请重新输入出发点和目的地的编号:); scanf(%d%d,&k,&j); if(k=0&kvexnum&j=0&jvexnum) flag=0

16、; printf(%s,G-vexsk.name); for(u=0;uvexnum;u+) if(pkju&k!=u&j!=u) printf(-%s,G-vexsu.name); printf(-%s,G-vexsj.name); printf( 总路线长%dmn,Dkj); /Floyd end void Search(MGraph *G) int k,flag=1; while(flag) printf(请输入要查询的景点编号:); scanf(%d,&k); if(kG-vexnum) printf(景点编号不存在!请重新输入景点编号:); scanf(%d,&k); if(k=0&

17、kvexnum) flag=0; printf(n); printf(编号景点名称 简介 n); printf(%-4d%-16s%-56sn,G-vexsk.num,G-vexsk.name,G-vexsk.introduction); printf(n); /Search end int LocateVex(MGraph *G,char* v) int c=-1,i; for(i=0;ivexnum;i+) if(strcmp(v,G-vexsi.name)=0) c=i;break; return c; MGraph * CreatUDN(MGraph *G)/初始化图形，接受用户输入

18、int i,j,k,w; char v120,v220; printf(请输入图的顶点数,弧数:); scanf(%d%d,&G-vexnum,&G-arcnum); printf(请输入景点的编号:、名称、简介:n); for(i=0;ivexnum;i+) printf(景点编号:); scanf(%d,&G-vexs-num); printf(景点名称:); scanf(%s,G-vexsi.name); printf(景点简介:); scanf(%s,G-vexs-introduction); for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) G-arcs

19、ij.adj=INFINITY; printf(请输入路径长度:n); for(k=0;karcnum;k+) printf(第%d条边:n,k+1); printf(景点对(x,y):); scanf(%s,v1); scanf(%s,v2); printf(路径长度:); scanf(%d,&w); i=LocateVex(G,v1); j=LocateVex(G,v2); if(i=0&j=0) G-arcsij.adj=w; G-arcsji=G-arcsij; return G; void print(MGraph *G) int v,w,t=0; for(v=0;vvexnum;v

20、+) for(w=0;wvexnum;w+) if(G-arcsvw.adj=INFINITY) printf( ); else printf(%-7d,G-arcsvw.adj); t+; if(t%G-vexnum=0) printf(n); 校园导游咨询 问题描述 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 基本要求 (1)设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 (2)为来访客人提供图中任意景点相关信息的查询。 (3)为来访客人提供图中任意景点的问路查询，即查询任意两个

21、景点之间的一条最短的简单路径。 实现提示 一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。 一需求分析 1从中北大学平面图中选取10个大家熟悉的景点，抽象成一个无向带权图。以图中顶点表示景点，边上的权值表示两地的距离。 2本程序的目的是为用户提供路径咨询和景点查询。根据用户指定的始点和终点输出相应路径或者根据用户指定的景点输出景点的信息。 南 北 二、概要设计 1本文采用的数据结构 */ /*包含头文件*/ #include #include /*定义符号常量*/ #define INT_MAX 10000 #define n 10 /*定义全局变量*/

22、 int costnn;/* 边的值*/ int shortestnn;/* 两点间的最短距离*/ int pathnn;/* 经过的景点*/ /*自定义函数原型说明*/ void introduce; int shortestdistance; void floyed; void display(int i,int j); 2个人分工 景点信息查询 两景点的最短距离 两个景点之间的路径 三、详细设计 void main /*主函数*/ int i,j; char k; for(i=0;i=n;i+) for(j=0;j10的数字编号！nn); break; /*introduce*/ int

23、 shortestdistance /*要查找的两景点的最短距离*/ int i,j; printf(请输入要查询的两个景点的编号(1-10的数字编号并用,间隔):); scanf(%d,%d,&i,&j); if(in|in|j10的数字编号并用,间隔):n); scanf(%d,%d,&i,&j); else floyed; display(i,j); return 1; /*shortestdistance*/ void floyed /*用floyed算法求两个景点的最短路径*/ int i,j,k; for(i=1;i=n;i+) for(j=1;j=n;j+) shortestij

24、=costij; pathij=0; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j(shortestik+shortestkj) /*用path记录从i到j的最短路径上点j的前驱景点的序号*/ shortestij=shortestik+shortestkj; pathij=k; pathji=k; /*floyed*/ void display(int i,int j) /* 打印两个景点的路径及最短距离 */ int a,b; a=i; b=j; printf(您要查询的两景点间最短路径是:nn); if(shortestij!=INT_MAX) if

25、(ij) printf(%d,b); while(pathij!=0) /* 把i到j的路径上所有经过的景点按逆序打印出来*/ printf(-%d,pathij); if(ij) j=pathij; else i=pathji; printf(%d)最短距离是:%d米nn,a,b,shortestab); else printf(%d,a); while(pathij!=0) /* 把i到j的路径上所有经过的景点按顺序打印出来*/ printf(-%d,pathij); if(i%d,b); printf(nn); printf(%d-%d)最短距离是:%5d米nn,a,b,shortest

26、ab); else printf(输入错误！不存在此路！nn); printf(n); /*display*/ 校园导游咨询 问题描述 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 基本要求 设计你所在学校的校园平面图，所含景点不少于10(*6*)个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 为来访客人提供图中任意景点相关信息的查询。 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 * 感想： 拿到这一题目，我有一种似曾相似的感觉，yeah 跟以前学C语言时做的“学生成绩管理系统”类似，程序

27、功能就是多了求最短路径，用到图方面的算法。所以我异想天开，认为简单的把“学生成绩管理系统”加以修改，增加一个求最短路径函数就大功告成了。结果写到最后麻烦就来了：景点结构体信息是可以保存到文件mystud.dat文件了，可边的信息该怎么表示出来？边似乎跟景点压根儿没联系得上。实在没办法，只好多建一文件me.dat独立存放边的信息。 通过写这个程序，给我的教训是深刻的，也让我重新认识到程序设计思路、规划的重要性。特发以下代码，让自己和后来者引以为戒！ #include #include #include #include #include #define M 10000 #define MaxSize 6/设定校园景点数 #define M 10000 /景点结构体 struct location