公园导游管理系统.doc

计算机信息工程学院

《数 据 结 构》
课 程 设 计 报 告

题 目： 公园导游系统

专 业： 计算机科学与技术（软件方向）
班 级：
学 号：
姓 名：
指导教师：
完成日期：
目 录

一、概要设计 1
1.题目的内容与要求 1
1.1 程序模块 6
1.2 系统涉及的数据结构 6
1.2.1 程序数据结构 7
1.2.2 具体数据类型定义 7
二、详细设计 2
2.1 创建图（Fprint-Link） 9
2.2 寻找最佳路径（DFSTraverse） 9
2.3 最短路径（ShortPath） 10
2.4 遍历出某一起点到终点的所有路径（SearchAllPath） 12
2.5 导入新文件（Loadnewmap） 13
三、测试分析 5
3.1 可行性分析 4
3.1.1技术可行性 4
3.1.2 工具可行性 4
3.1.3 经济可行性 4
3.1.4 操作可行性 5
3.2 需求分析 5
3.2.1 功能需求 5
3.2.2 输入输出的要求 5
四、使用说明与执行结果 6
4.1 主界面 14
4.2 游客界面 15
4.3 系统用户界面 15
附 录（程序清单） 8

山西工商学院课程设计报告

一、概要设计
1.题目的内容与要求
1.1课题的研究背景、要求和意义
现代公园范围的广阔，内容不断的增加，使得公园整个系统变得复杂。使用电脑对游客进行导游成为发展的趋势，以达到更好的为游客服务的目的。
对于公园的游客来说，他们要求：能够浏览整个公园的信息、查询每一个景点的信息、从任意景点遍历全部的景点、能够查找最短路径。对于系统用户来说，他们要求：删除地点、添加地点、添加路径、删除路径、保存修改、导入文件数据。
采用图这么一种数据结构，采用邻接表的存储方式，用一个二维数组来记录所有的边，为了实现地图的随时更新，采用了静态链表实现对图的接点的添加，删除。应用文件的读写来进行文件操作。
查找最短路径采用迪杰特斯拉算法实现，从任意景点遍历全部的景点采用深度优先遍历实现。
对于界面设计，游客不能进行地图的修改，更换，所以首先要验证身份，再出现对应的界面。
2.总体设计
程序模块
从文件中对出数据(Fprint-Link())：通过调用Update(L,g)，先将链表L的信息赋值给邻接数组g中，进行更新。 建立无向图，把公园的景点及景点的信息，连接起来建立邻接表采用链式加顺式存储。
浏览学校的全景（Browser）：列出学校的所有的景点。
寻找最佳路径（DFSTraverse：）：输入一个景点，会吧所有都浏览一边，并找出最佳的路径。
最短路径（ShortPath）:求出起点和终点的最佳路径，并求出最佳路径的长度。
遍历出某一起点到终点的所有路径（SearchAllPath）：找出所有路径，利用深度优先遍历。
删除地点、添加地点、添加路径、删除路径、保存修改、导入文件数据。对应代码函数如下：DeleteAdv(L,g)、InsertAdv(L,g)、InsertEdge()、DeleteEdge()、SaveMap(g)、Loadnewmap(p,g)。
总体结构设计如图1-1所示。
删除地点
主模块
系统用户
游客模块
添加地点
添加路径
删除路径
保存存修改
入文件数据
任意景点遍历
查询景点信息
和浏览公园简图
查询
任意两个景点最短的路径
遍历输出任意一个景点的所有路径

图1- 1 系统框架图

3.系统数据结构
3.1 程序数据结构
程序主要用了图和静态链表两种数据结构，采用矩阵来保存图形结构的地图，用数组来保存遍历经过的结点用以遍历回溯，以及存储最最终路径。
图的抽象数据类型：
ADT Graph{
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系：R={VR}
VR=｛<v,w>|v,w∈v且P(v,w)表示从v到w的弧，谓词P（v,w）定义了弧<v,w>的意义或信息｝
基本操作P：PrintMap(g)
Serach(g)
DFSTraverse(g)
ShortPath(g)。
｝ADT Graph
线性链表的抽象数据类型：
ADT List｛
数据对象：D=｛ai|ai∈ElemSet，i=1，2，…,n,n≥0｝
数据关系：R1=｛<ai-1,ai>|ai-1,ai∈D,i=2, …,n｝
基本操作: DeleteAdv(L,g) InsertAdv(L,g)
InsertEdge() DeleteEdge()
SaveMap(g) Loadnewmap(p,g)
｝ADT List。
3.2.2 具体数据类型定义
typedef struct LNode{
char name[30];
int num;
char introduction[100];
struct LNode *next;
}LNode,*Link;
typedef struct ArcNode
{int data; //该弧所得指向的顶点的位置
ArcNode *nextarc; //指向下一条弧的指针
}ArcNode,*ArcLink;
typedef struct VNode //顶点信息
{ char name[30];
int num;
char introduction[100];
ArcLink firstarc; //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX+1];
typedef struct ALGraph
{AdjList vdata;
int vexnum,arcnum; //图的顶点数和弧数
}ALGraph;
int Edge[MAX][MAX]; //用来存放路径的权值
int n,e;//存放结点数和边数
读取文件信息代码如下：
for(i=1;i<=n;i++)
{fscanf(fp,"%d",&num);fscanf(fp,"%s",name);
fscanf(fp,"%s",information);
ListInsert(L, num, name, information);
}
Update(L,g);
for ( j=1;j<=e;j++) //从文件中读入边的信息
{
fscanf(fp,"%d",&a);
fscanf(fp,"%d",&b);
fscanf(fp,"%d",&weight);
Edge[a][b]=weight;
Edge[b][a]=weight;
p=(ArcLink)malloc(sizeof(ArcNode));//为顶点申请空间
p->data=a;
p->nextarc=g[b].firstarc;
g[b].firstarc=p; //把p插进来
q=(ArcLink)malloc(sizeof(ArcNode));
q->data=b;
q->nextarc=g[a].firstarc;
g[a].firstarc=q;

二、详细设计
2.1 创建图（Fprint-Link）
从文件中读出数据，函数流程图2-1所示。
结束
j++
开始
读入n,e
ArcLink p,q;初始化链表，邻接表，Eage[ ][ ] i=1,j=1，p=q=(ArcLink)malloc(sizeof(ArcNode));
i<=n
读入结点，插入到链表L
i++
Y
N
读入边信息起点a,终点b，长度weight。Eage[ a][b ]=weight，Eage[ b][a ]=weightp->nextarc=g[b].firstarc; g[b].firstarc=p; //把p插进来q->nextarc=g[a].firstarc; g[a].firstarc=q;
j<=e
Y
N
Update(L,g);//给g赋值

图2- 1 Fprint-Link函数流程图
2.2 寻找最佳路径（DFSTraverse）
利用深度优先的思想，遍历图找出一条最佳最佳的的路径，让它遍历所有景点。利用递归的思想，往下遍历，访问标志位，若访问过在下次就不用访问。若找完一个分支在下次重新遍历，函数流程如图2-2所示。
开始
初始化visit[v]=0//初始化标志位
If（visit[v]==0） DFS(g,v,visited); v++
Count++
Count<=n
结束
Y
N

图2- 2 寻找最佳路径流程图
2.3 最短路径（ShortPath）
利用迪杰特斯拉算法，求v0到其余顶点的最短路径path[],distance []是用来存放各路径的权值，借助辅助数组s[]标志,是否当前顶点属于S(1,属于) 函数流程
图2-3所示。 开始
初始化distence[]，s[],path[]
开始主循环 ，每次求得v0到某顶点v
的最短距离，并将v并入中
minDis=MAXEDGE;//当前所知v0的最短距离并设初值为MAXEAGE，
int i=1,j=1,u=v0;

!s[j]&&distance[j]<minDis
u=j;//在s[]下一直往下找minDis=distance[j] ;
j<=n
j=0;更新当前最短路径及距离；
newDist=distance[u]+GetWeight[u]
distance[j]=newDist;path[j]=u;//记录寻找的最短的路径
i<=n

结束
If(newDist<distance[j])
J<=n
Y
N
Y
N
Y
Y
N

图2- 3 寻找最短路径流程图
2.4 遍历出某一起点到终点的所有路径（SearchAllPath）
利用图的深度优先遍历，利用访问标志位。path[]记录路径，visited[]设访问标志，v起点，des终点，length，代表的是访问景点的长度。若碰见死路或者不同的路，则从上一个景点，从新扫描，searchAllPath()流程如图2-4所示。
If（visited[V]）returen;//若所有景点都访问过，则终止
v==des
PrintfPath(G,path,length);
visited[v]=1;
GetWeight(v,i)!=MAXEDG&&!visited[i]
SearchAllPath(G,path,visited,i,des,length+1)
i++
i<=n
结束
开始
N
Y
visited[v]=0;
N
Y

图2- 4 searchAllPath()流程图
2.5 导入新文件（Loadnewmap）
将指定文件导入到邻接表中，再保存到zheke1.txt 中 ,
具体实现如图2-5所示。
开始
初始化Link p，输入文件名filename[20]
Fprint-Link(p，g，filename)
SaveMap(g)
L=P;
结束

图2- 5导入新文件结构示图

三、测试分析
3.1 可行性分析
所谓可行性分析就是用最小的代价在尽可能短的时间内确定问题是否能够解决。这步工作的主要是要进行一次大大压缩简化了的系统分析和设计的过程，也就是在较高层次上以比较抽象的方式进行系统分析和设计的过程。可行性研究的最根本任务是对以后的行动方针提出建议，以避免时间、资源、人力和金钱的浪费，推荐一个较好的解决方案，并且为工程制定一个初步的计划。
3.1.1技术可行性
查找最短路径以及查询任意两景点之间的所有路径采用迪杰特斯拉算法或弗洛伊德算法实现。解决这个问题的一个方法是：每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。这样，便可求得每一对顶点之间的最短路径。总的执行时间为O（n3）。虽然弗洛伊德算法时间复杂度也是O（n3），但形式简单些。
从任意景点遍历全部的景点采用深度优先遍历或广度优先搜索遍历图实现。
所谓可行性分析就是用最小的代价在尽可能短的时间内确定问题是否能够解决。这步工作的主要是要进行一次大大压缩简化了的系统分析和设计的过程，也就是在较高层次上以比较抽象的方式进行系统分析和设计的过程。可行性研究的最根本任务是对以后的行动方针提出建议，以避免时间、资源、人力和金钱的浪费，推荐一个较好的解决方案，并且为工程制定一个初步的计划。
本系统采用人机操作进行管理，用visual C++ 6.0进行前台设计、系统随机产生数据，用户通过界面操作，系统自动给予合理分析，由于visual C++ 6.0功能强大、使用的灵活、良好的可扩展性、以及广泛实际应用，充分说明本系统在技术方面的可行性。
3.1.2 工具可行性
软件方面：
信息时代对于软件的应用已不是人们的难题，人们在日常办公中用的计算机操作的系统等都属于软件部分。
硬件方面：
计算机普及到今天，人们对于它的拥有已不少见，它的硬件设备完全能够满足人们的需求，而价格也能被人们所接受。
3.1.3 经济可行性
线在大多数的公园景点及内容不断的增多和丰富，这也就使得整个公园系统不得不建立的更大。这也就为人们逛公园造成了很大的不便。人们往往不熟悉公园，找个东西，或某处带来了极大的不便。往往要花很多时间在这一方面。然而要是有一个公园导游系统这将给乘客带来极大的方便，使人们一下就能了解到这个公园的大致的情况。
这是个超小型的性能分析系统，从投入的人力，财力与物力来讲是非常之小的，只要一台电脑，一台打印机，这个系统就可以搞起来，考虑到学校里有电脑，现只要购置一台打印机就可以了。从节省人力方面，可以让管理人员从繁与复杂的工作中解脱出来，做更多的工作，可以给读者提高到更深的一个层次。
3.1.4 操作可行性
本系统设计清晰，有良好的用户接口，操作简洁，完全可以给用户解决，并达到操作过程中的直观、方便、实用、安全等要求，因此操作方面具有可行性。

3.2 需求分析
3.2.1 功能需求
对于游客，系统功能需求如下：能够浏览整个公园的信息、查询每一个景点的信息、从任意景点遍历全部的景点、能够查找最短路径。
对于系统后台操作功能需求如下：删除地点、添加地点、添加路径、删除路径、保存修改、导入文件数据。
3.2.2 输入输出的要求
程序执行是需要有描述地图的文件，并放在相应的位置。文件中开始位置存放景点个数，图存在多少条边；接着是存放景点序号、名称、相关信息；对后是存放着各个景点之间的距离矩阵。
执行程序先要先要进行选择。
修改地图是要验证密码。
查找任意两个景点的最短路径时，输入查找最短路径的两个点。运行各个小过程要求要输出的暂时的结果。

四、使用说明与执行结果
4.1主界面

图4- 1主界面

4.2 游客界面
图4- 2 游客界面
4.3 系统用户界面

图4- 3 系统用户登录界面
图4- 4 系统用户界面

4.5 浏览公园全景简图

4- 5涉外公园简图 ， 4- 6详细信息表

4.6 寻找某一起点的最佳路径和指定起点、终点的最短路径

图4- 7 查询最佳路径
图4- 8 查询最短路径

4.7 寻找指定起点、终点的所有路径

图4- 9 输入两点之间的所有路径

4.8 删除，添加结点，保存和导入新地图

图4- 10 删除结点

图4-10 导入新的地图

17

山西工商学院课程设计报告

附 录（程序清单）

#include<stdio.h>
#include<process.h>
#define INT_MAX 10000
#define n 10
int cost[n][n];/* 边的值*/
int shortest[n][n];/* 两点间的最短距离*/
int path[n][n];/* 经过的景点*/
void welcome()
{

printf("\n 欢迎光临\n");
printf("\n 凝香公园 \n\n\n\n\n");
printf("\n 给您最纯净的享受\n");
printf("\n Pure as the south polar snow \n\n");
printf("\n ");
system("pause");
}
void Menu()//函数的主显示界面
{
system("cls");
system("color 70");
printf(" ┏━━━━━━━━━━━━━━━━━┓ \n");
printf(" ┃ 凝香公园导游系统 ┃ \n");
printf(" ┗━━━━━━━━━━━━━━━━━┛ \n");
printf(" \n");
printf(" ┏━━━━━━━━━━━━━━━━━━━━━┓\n");
printf(" ┃ ┃\n");
printf(" ┃ 1：浏览公园全景 ┃\n");
printf(" ┃ ┃\n");
printf(" ┃ 2：最佳游览路线 ┃\n");
printf(" 主┃ ┃\n");
printf(" ┃ 3：查看单个景点 ┃\n");
printf(" 菜┃ ┃\n");
printf(" ┃ 4：游览线路查询 ┃\n");
printf(" 单┃ ┃\n");
printf(" ┃ 5：凝香公园简介 ┃\n");
printf(" ┃ ┃\n");
printf(" ┃ 6：退出导游系统 ┃\n");
printf(" ┃ ┃\n");
printf(" ┗━━━━━━━━━━━━━━━━━━━━━┛\n");
printf(" \n");
printf(" \n");
printf(" \n");
printf("\n\n >>>请按键选择:");
}
void Browser()
{
printf("\n ● 公园全景图 ● \n");
printf("————————————————————————————————\n");
printf(" ━━━━━━━━━ \n");
printf(" ━━━━┳━━━━ 紫金大道 \n");
printf(" ┃ ↑北 \n");
printf(" ┃ \n");
printf(" 1沁园━━━━━ 2公园大门━━━━━━━━┓ \n");
printf(" ┃ ┃ ┃ \n");
printf(" ┃ ┃ ┃ \n");
printf(" 3梨园━━━━━━━4春 园━━━━━━━10夏园 \n");
printf(" ┃ ┃ ┃ ┃ \n");
printf(" ┃ ┃ ┃ ┃ \n");
printf(" 5鼎湖 ┃ 8秋园━━━━━━9冬园 \n");
printf(" ┃ ┃ ┃ \n");
printf(" ┃ ┃ ┃ \n");
printf(" ┃ ┃ ┃ \n");
printf(" 6聚缘阁━━━━━━7凝香园 \n");
printf(" \n");
printf(" \n");
printf(" 2012年7月4日\n");
printf("————————————————————————————————\n");

}
void place()
{
char z;
printf("\n\n\n━━━━━━━━━━━━【公园简介】━━━━━━━━━━━━━━━━━━\n");
printf("\n \n 凝香园也称“正春园”，位于菏泽城东岳程办事处岳楼行政村。\n\n");
printf(" 始建于元末明初，原为袁姓所有，称“袁家堂”花园。\n\n");
printf(" 凝香园是我国古代北方八大名园之一，俗称“何家花园”，距今有近1000余年的历史。\n\n");
printf(" 园中有百多年的刺柏、几百年的腊梅、紫丁香，千年翠兰松和一块假山石。\n\n");
printf(" “凝香园”附近的何应瑞墓地古柏成林，苍郁参天。\n\n");
printf("\n ●注：本公园和真正的“凝香园”是同名，而非真实园林！\n");
printf("\n\n━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n");
printf("\n\n\n >>>>请输入任意字符【返回主菜单】\n");
z=getchar();z=getchar();
}
void go()
{

printf("\n\n\n\n\n\n ┏━━━━━━━━━━━━━感谢使用━━━━━━━━━━━━━━━━┓\n");
printf(" ┃ ┃\n");
printf(" ┃ ┃\n");
printf(" ┃ ┃\n");
printf(" ┃ 请按任意键退出！ ┃\n");
printf(" ┃ ┃\n");
printf(" ┃ ┃\n");
printf(" ┃ 程序制作：陈明 ┃\n");
printf(" ┃ 学号：3100931036┃\n");
printf(" ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n\n\n\n\n\n");
exit(0);

}

void way()
{
char z;
printf("\n━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n");
printf(" ●本公园的最佳全景游览路线为：\n\n");
printf(" 2公园大门→ 1沁园→ 3梨园→ 5鼎湖→ 6聚缘阁→ 7凝香园→ 4春园→ 8秋园→ 9冬园→ 10夏园→ 2公园大门\n");
printf(" ●全程所需行程：276米!\n\n");
printf(" ●如需其他路线请返回主菜单进入【浏览路线查询】\n");
printf("\n\n━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n");
printf("\n\n\n >>>>请输入任意字符【返回主菜单】\n");
z=getchar();
z=getchar();
}

void introduce()
{/*景点介绍*/
int a;
char z;
printf(">>>请输入您想查询的景点编号:");
scanf("%d",&a);
getchar();
printf("\n\n━━━━━━━━━━━━【 查询结果：】━━━━━━━━━━━━━━\n\n");
switch(a)
{
case 1:
printf(" 1:沁园\n\n　●一首《沁园春.雪》让您对眼前的梅花感慨万千。\n");break;
case 2:
printf(" 2:公园大门\n\n　●仿古的气势宏伟建筑仿佛置身于100年前。\n");break;
case 3:
printf(" 3:梨园\n\n　　●丛林间嬉戏的小鸟不禁让你回头倾听。\n");break;
case 4:
printf(" 4:春园\n\n　　●广阔的草地伴着阵阵花香，躺在上面可以仰望南天。\n");break;
case 5:
printf(" 5:鼎湖\n\n　 ●圆滑的湖面仿佛一面大鼎将湖水撑起来。\n");break;
case 6:
printf(" 6:聚缘阁\n\n　●来自大江南北的古玩古画齐聚一堂。\n");break;
case 7:
printf(" 7:凝香园\n\n　　●神奇的南方小筑隐匿在桂花林中。聚香也。\n");break;
case 8:
printf(" 8:秋园\n\n　　●当你独自一人行走在大片阔叶林里，才能感受自然的气息。\n");break;
case 9:
printf(" 9:冬园\n\n　　●冬日恋歌在这里尽情唱响，High起来吧！\n");break;
case 10:
printf(" 10:夏园\n\n　●荷花池中一抹红，荷塘月色任你赏！\n");break;
default:
printf(" ●Error：景点编号输入错误！请输入1~10的数字编号！\n\n");break;
}
printf("━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n\n");

}

void floyed()
{/*用floyed算法求两个景点的最短路径*/
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{ shortest[i][j]=cost[i][j];
path[i][j]=0;
}
for(k=1;k<=n;k++)
for(j=1;j<=n;j++)
for(i=1;i<=n;i++)
if(shortest[i][j]>(shortest[i][k]+shortest[k][j]))
{/*用path[][]记录从i到j的最短路径上点j的前驱景点的序号*/
shortest[i][j]=shortest[i][k]+shortest[k][j];
path[i][j]=k;
path[j][i]=k;
}
}
void display(int i,int j)

{/* 打印两个景点的路径及最短距离 */
int a,b;
a=i; b=j;
printf("\n━━━━━━━━━━━━【 查询结果：】━━━━━━━━━━━━━━\n\n");
printf(" ●路径: ");
if(shortest[i][j]!=INT_MAX)
{
if(i<j)
{
printf(" %d",b);
while(path[i][j]!=0)
{/* 把i到j的路径上所有经过的景点按逆序打印出来*/
printf(" ← %d",path[i][j]);
if(i<j) j=path[i][j];
else i=path[j][i];
}
printf(" ← %d",a); printf("\n\n");
printf(" ●距离：您需要步行 %dm才能到达目的地！",shortest[a][b]);

}
else
{ printf("%d",a);
while(path[i][j]!=0)
{/* 把i到j的路径上所有经过的景点按顺序打印出来*/
printf("→ %d",path[i][j]);
if(i<j) j=path[i][j];
else i=path[j][i];
}
printf("→ %d",b); printf("\n\n");
printf(" ●距离：您需要步行 %dm才能到达目的地！\n\n",shortest[a][b]);
printf("━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n\n");
}
}
else
printf("输入错误！不存在此路！\n\n"); printf("\n");
printf("━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n\n");
}
int shortestdistance()
{/*要查找的两景点的最短距离*/
int i,j;
char z;
printf(" >>>请输入要查询的两个景点的编号(用空格键隔开):");
scanf("%d %d",&i,&j);
if(i>n||i<=0||j>n||j<0)
{
printf("输入信息错误！\n\n");
prin