公园导游标准管理系统.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 导入新地图

附 录（程序清单）

#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(" 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(" ┃ 学号：┃\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　●仿古气势宏伟建筑好像置身于1前。\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");
printf("　>>>请输入要查询两个景点编号(用空格键隔开):");
scanf("%d %d",&i,&j);
}
else
{
floyed()； display(i,j);
}
printf(" >>>>请输入任意字符【返回主菜单】\n");
z=getchar();z=getchar();

return 1;}

void main()
{/*主函数*/
system("color 8f");//界面背景颜色
system("mode con