数据结构公园导游（精编版）

1、1. 课程设计的目的(1) 熟练使用 c + 语言编写程序，解决实际问题;(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力 ;(3) 初步掌握软件开发过程的问题分析、系统设计、 程序编码、 测试等基本方法和技能 ;(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;2. 需求分析(1 ）设计所在公园的公园平面图，所含景点不少于十个。以图中顶点表示园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等信息。（ 2）为来访客人提供图中任意景点相关信息的查询。（ 3）为来访客人提供图中任意景点的问路查询，即查询任意两个顶点之间的一条最短的简单路

2、径。（4） ）公园导游图的景点和道路的修改扩充功能。（5） ）扩充道路信息，如道路类别（车道、人行道），以致可按客人所需分别查询人行路径或车行路径。（ 6）扩充每个景点的林洁景点的方向等信息，使得路径查询结果能提供详尽的导向信息。图 1-1函数调用图4. 调试分析（ 7）实现公园导游的仿真界面。3. 公园导游问题的设计图 1-2图 1-3图 1-4图 1-5图 1-65. 小结数据结构书中的迪杰斯特拉算法只能求出最短路径中有哪个景 点，但无法求出这几个景点的经过顺序，所以先利用迪杰斯特拉算法记录下某个顶点求出到最短路径的顺序，然后再比对哪几个景点是最短路径里所经过的得出最短路径及景点路过的顺序

3、。6、参考文献1 严蔚敏，吴伟民编著.数据结构 (c语言版 )-北京:清华大学出版社， 2007.22 严蔚敏，吴伟民米 宁 编 著.数据结构题集 (c语言版 )-北京:清华大学出版社 ， 2007.33 网上搜索相关程序作为参考附录：#define infinity 1000#define maxvertexnum 35#define max 40#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<string.h>#include<iostream>using

4、namespace std;typedef struct arcell/边的权值信息int adj;/arcell,adjmatrixmaxvertexnummaxvertexnum;/权值图的邻接矩阵类型typedef struct vexsinfo/顶点信息int position;/景点的编号char name32;/景点的名称char introduction256;/景点的介绍vexsinfo;typedef struct mgraph/图结构信息vexsinfo vexsmaxvertexnum;/顶点向量 ( 数组)adjmatrix arcs;/邻接矩阵int vexnum,a

5、rcnum;/分别指定顶点数和边数mgraph;/ 全局变量int visited35;/用于标志是否已经访问过int d35;/用于存放权值或存储路径顶点编号mgraph campus;/图变量 ( 大公园园 )/ (1)对图初始化mgraph initgraph()int i=0,j=0;mgraph c;c.vexnum =28;c.arcnum =39;/顶点个数边的个数for(i=0;i<c.vexnum ;i+)/依次设置顶点编号c.vexsi.position =i;/ 依次输入顶点信息strcpy( ,"小 西 南 门 ");

6、strcpy(roduction ,"离公交站近 "); strcpy( ,"公园南正门 ");strcpy(roduction ,"公园大门、公园班车进出口"); strcpy( ,"东坡亭 ");strcpy(roduction ,"东坡亭，亭高3 层"); strcpy( ,"西 施 坡 "); strcpy(r

7、oduction ,"西施坡 , 风光优美 "); strcpy( ,"黄蓉亭 ");strcpy(roduction ,"黄蓉亭，名字来自于射雕英雄传"); strcpy(,"荷花塘 ");strcpy(roduction ,"荷花塘，里面有很多荷花"); strcpy( ,"广场 ");strcpy(roduction ,"很

8、大的一块空地"); strcpy(,"花 坛 "); strcpy(roduction ,"里面有很多花"); strcpy( ,"长椅 ");strcpy(roduction ,"这儿有很多椅子，有人可以做"); strcpy(, "慈悲庵 ");strcpy(roduction , "慈悲庵，慈悲庵是创建于元代的古刹");st

9、rcpy( ,"云绘楼 ");strcpy(roduction ,"云绘楼是一座皇家园林建筑"); strcpy( ,"九龙壁 ");strcpy(roduction ,"整壁用彩色琉璃瓦镶砌而成"); strcpy( ,"白塔 ");strcpy(roduction ,"白塔，高5 层 "); strcpy(c.vexs13.

10、name ,"游 泳 馆 "); strcpy(roduction ,"室内小型游泳馆"); strcpy( ,"彩 虹 桥 "); strcpy(roduction ,"彩虹桥，桥上有彩虹灯"); strcpy( ,"小 木 桥 "); strcpy(roduction ,"小木桥，环境优雅"); strcpy( ,"

11、;沙滩 ");strcpy(roduction ,"河边的沙滩 ");strcpy( ,"奇 石 "); strcpy(roduction ,"奇石大石头 ");strcpy( ,"超 市 "); strcpy(roduction ,"超 市 "); strcpy( ,"欧 阳 亭 "); strcpy(c.vexs1

12、9.introduction ,"亭高 3 楼"); strcpy( ,"明 光 塔 "); strcpy(roduction ,"明光塔 "); strcpy( ,"雷 峰 塔 "); strcpy(roduction ,"雷锋塔 "); strcpy( ,"洞 庭 湖 "); strcpy(roduction ,"

13、洞庭湖 "); strcpy( ,"苏 提 "); strcpy(roduction ,"苏 提 "); strcpy( ,"灯 塔 "); strcpy(roduction ,"灯 塔 "); strcpy( ,"");strcpy(roduction ,""); strcpy( ,&quo

14、t;树 林 "); strcpy(roduction ,"有很多树 "); strcpy( ,""); strcpy(roduction ,"");/ 依次输入边上的权值信息for(i=0;i<c.vexnum ;i+) for(j=0;j<c.vexnum ;j+)c.arcs ij.adj =infinity; /先初始化图的邻接矩阵/ 部分弧长c.arcs02.adj=50;c.arcs03.adj=60; c.arcs14.adj=

15、90;c.arcs23.adj=60;c.arcs28.adj=40;c.arcs34.adj=60;c.arcs36.adj=40;c.arcs45.adj=70;c.arcs49.adj=70;c.arcs410.adj=80; c.arcs417.adj=200;c.arcs57.adj=70;c.arcs69.adj=40;c.arcs718.adj=190;c.arcs811.adj=50;c.arcs912.adj=40;c.arcs1018.adj=70;c.arcs1112.adj=60;c.arcs1114.adj=50;c.arcs1115.adj=50; c.arcs12

16、16.adj=50;c.arcs1314.adj=40;c.arcs1322.adj=60;c.arcs1415.adj=50;c.arcs1420.adj=90;c.arcs1516.adj=60;c.arcs1521.adj=40; c.arcs1617.adj=60;c.arcs1718.adj=80;c.arcs1819.adj=60;c.arcs2021.adj=60;c.arcs2024.adj=80;c.arcs2223.adj=60;c.arcs2225.adj=80; c.arcs2324.adj=60;c.arcs2426.adj=100; c.arcs2427.adj=1

17、00; c.arcs2526.adj=90;c.arcs2627.adj=90;for(i=0;i<c.vexnum ;i+)/邻接矩阵是对称矩阵，对称赋值for(j=0;j<c.vexnum ;j+) c.arcsji.adj =c.arcsij.adj ;return c;/initgraph/ (2)查找景点在图中的序号int locatevex(mgraph c,int v)int i;for(i=0;i<c.vexnum ;i+) if(v=c.vexsi.position)return i;/找到，返回顶点序号ireturn -1;/否则，返回 -1/(3)、(4

18、)求两景点间的所有路径/ (3)打印序号为m,n 景点间的长度不超过8 个景点的路径void path(mgraph c, int m,int n,int k)int s,x=0;int t=k+1;/t记载路径上下一个中间顶点在d 数组中的下标if(dk=n && k<8)/dk存储路径顶点。若dk 是终点 n 且景点个数 <=8，则输出该路径/递归出口，找到一条路径for(s=0;s<k;s+)printf("%s->",);/输出该路径。 s=0 时为起点m printf("%s",

19、);/输出最后一个景点名( 即顶点n的名字，此时s=k)printf("nn");elses=0;while(s<c.vexnum)/从第m 个顶点，试探至所有顶点是否有路径if(c.arcsdks.adj<infinity)&& (visiteds=0)/ 初态：顶点m到顶点 s 有边，且未被访问visiteds=1;dk+1=s;/存储顶点编号s 至 dk+1 中path(c,m,n,t);/求从下标为t=k+1 的第 dt个顶点开始的路径 ( 递归调用 ) ，同时打印出一条m至 n 的路径visiteds=0;/将

20、找到的路径上顶点的访问标志重新设置为 0，以用于试探新的路径s+;/试探从下一个顶点s开始是否有到终点的路径/endwhile/endelse/endpath/(4)打印两景点间的景点个数不超过8 的所有路径。调用(3) int allpath(mgraph c)int k,i,j,m,n;printf("nn请输入你要查询的两个景点编号:nn"); scanf("%d%d",&i,&j);printf("nn");m=locatevex(c,i);/调用 (2) ，确定该顶点是否存在。若存在，返回该顶点编号n=loc

21、atevex(c,j);d0=m;/存储路径起点m (int d数组是全局变量 )for(k=0;k<c.vexnum;k+)/全部顶点访问标志初值设为0visitedk=0;visitedm=1;/第 m个顶点访问标志设置为1path(c,m,n,0);/调用 (3) 。k=0 ，对应起点d0=m 。k 为 d 数组下标return 1;/ (5)用迪杰斯特拉算法，求出一个景点到其他景点间的最短路径，并打印void shortestpath_dij(mgraph c)/ 迪杰斯特拉算法，求从顶点v0 到其余顶点的最短路经及其带权长度dv/ 若 pvw为 1，则 w 是从 v0 到 v

22、的最短路经上的顶点/finalv类型用于设置访问标志int v,w,i,min,t=0,x,flag=1,v0;/vo为起始景点的编号int final35,d35,p3535;printf("n请输入一个起始景点的编号：");scanf("%d",&v0);printf("nn"); while(v0<0|v0>c.vexnum)printf("n你所输入的景点编号不存在n"); printf("请重新输入： ");scanf("%d",&v0)

23、;/while for(v=0;v<c.vexnum ;v+)dvfinalv=0;/初始化各顶点访问标志dv=c.arcsv0v.adj;/v0到各顶点v的权值赋值给for(w=0;w<c.vexnum;w+)/初始化 p数组， 各顶点间的路径全部设置为空路径0pvw=0;if(dv<infinity)/v0到v有边相连，修改pvv0的值为 1pvv0=1;pvv=1;/各顶点自己到自己要连通/fordv0=0;/自己到自己的权值设为0finalv0=1;/v0的访问标志设为1，v 属于 s集for(i=1;i<c.vexnum ;i+)/对其余 c.vexnum-1

24、个顶点 w，依次求 v到 w 的最短路径min=infinity;for(w=0;w<c.vexnum ;w+)/在未被访问的顶点中，查找与v0 最近的顶点vif(!finalw)if(dw<min)/v0到 w ( 有边 ) 的权值 <minv=w; min=dw;/iffinalv=1;/v的访问标志设置为 1， v 属于 s 集for(w=0;w<c.vexnum ;w+)/修改 v0 到其余各顶点 w 的最短路径权值dwif(!finalw&&(min+c.arcsvw.adj <dw) /若 w 不属于s，且 v到 w 有边相连的权值 d

25、wdw=min+c.arcsvw.adj;/修 改 v0 到 wfor(x=0;x<c.vexnum ;x+)/所有 v0 到 v 的最短路径上的顶点x，都是 v0 到 w 的最短路径上的顶点pwx=pvx; pww=1;/if/forfor(v=0;v<c.vexnum;v+)/输出 v0到其它顶点v 的最短路径if(v!=v0)printf("%s",);/输出景点v0的景点名for(w=0;w<c.vexnum ;w+)/对图中每个顶点w，试探w是否是 v0到 v 的最短路径上的顶点输出该景点if(pvw &&

26、; w!=v0 && w!=v)/若 w 是且 w 不等于 v0，则printf("->%s",);printf(">%s",);printf("n总路线长为 %d米nn",dv);/for/shortestpath/ (12)输出图的邻接矩阵的值/void printmatrix(mgraph c)int i,j,k=0;/k用于计数，控制换行for(i=0;i<c.vexnum ;i+) for(j=0;j<c.vexnum ;j+)if(c.

27、arcsij.adj =infinity) printf("");elsek+;printf("%4d",c.arcsij.adj);/printpathif(k%c.vexnum =0) printf("n");void shortestpath_floyd(mgraph c)/ 用 floyd算法求各对顶点v 和 w 间的最短路经及其带权长度的dvw。/ 若 pvwu=1；则 u 是 v 到 w 的当前求得的最短路经上的顶点int i,j,k,d3535,p353535;int v,u,w;for(v=0;v<c.vexnu

28、m ;v+)/初始化各对顶点v ， w 之间的起始距离dvw及 路 径 pvw数组for(w=0;w<c.vexnum ;w+)分量全部清0dvw=c.arcsvw.adj;/dvw中存放 v至 w 间初始权值for(u=0;u<c.vexnum;u+)/初始化最短路径pvw数组，第 3个pvwu=0;if(dvw<infinity)/如果 v至 w 间有边相连pvwv=1;pvww=1;/ v/ w是 v是 v至 w最短路径上的顶点至 w最短路径上的顶点for(u=0;u<c.vexnum;u+)/求 v 至 w的最短路径及距离。对任意顶点u，试探其是否为 v 至 w

29、 最短路径上的顶点for(v=0;v<c.vexnum ;v+) for(w=0;w<c.vexnum ;w+)if(dvu+duw<dvw) /从 v经 u到 w 的一条路径更短dvw=dvu+duw; /修改 v至 w 的最短路径长度for(i=0;i<c.vexnum ;i+) /修改 v至 w 的最短路径数组。若i 是 v 至 u 的最短路径上的顶点,pvwi=pvui|puwi;/ 或 i 是 u 至 w 的最短路径上的顶点,则 i 是 v 至 w 的最短路径上的顶点/endforprintf("n请输入出发点和目的地编号："); scan

30、f("%d%d",&k,&j);printf("nn"); while(k<0|k>c.vexnum|j<0|j>c.vexnum)printf("n你所输入的景点编号不存在！"); printf("n请重新输入出发点和目的地编号：nn"); scanf("%d%d",&k,&j);printf("nn");printf("%s", );/输出出发景点名称for(u=0;u&l

31、t;c.vexnum ;u+)if(pkju && k!=u && j!=u)/输出最短路径上中间景点名称printf("->%s", );printf("->%s", );/输出目的地景点名称printf("nnn总长为 %d米nnn",dkj);/shortestpath_floyd/ (15)查询景点的信息void seeabout(mgraph c)int k;printf("n请输入要查询的景点编号："); sca

32、nf("%d",&k);while(k<0|k>c.vexnum)printf("n你所输入的景点编号不存在！"); printf("n请重新输入：");scanf("%d",&k);printf("nn编 号 ： %-4dn",c.vexsk.position ); printf("nn景点名称： %-10sn", ); printf("nn介绍： %-80snn",roducti

33、on );/seeabout/ (16)显示所有景点信息void browsecompus(mgraph c)int i;printf(" nn编号景点名称简介 n");printf(" n"); for(i=0;i<c.vexnum ;i+)printf("%-10d%-25s%-80sn",c.vexsi.position,, roduction);printf(" nn");/browsecompus/ (17)主要工作函数。操作区用户界面void main

34、work()int yourchoice; campus=initgraph();printf("n-欢迎使用公园导游程序-n");printf("n欢 迎 来 到 公 园!nn");printf("n菜单选择nn");printf("1.公园景点介绍2.查看游览路线n");n");n");printf("3.查询景点间最短路径4.景点信息查询printf("5.查询景点间可行路径6.打印邻接矩阵printf("7.退出n"); printf("n-n");printf("请输入你的选择