公园导游标准管理系统.doc

计算机信息工程学院数 据 结 构课 程 设 计 报 告题 目： 公园导游系统 专 业： 计算机科学与技术（软件方向） 班 级： 学 号： 姓 名： 指引教师： 完毕日期： 目 录一、概要设计11.题目内容与规定1 1.1 程序模块61.2 系统涉及数据构造61.2.1 程序数据构造71.2.2 详细数据类型定义7二、详细设计22.1 创立图（Fprint-Link）92.2 寻找最佳途径（DFSTraverse）92.3 最短途径（ShortPath）102.4 遍历出某一起点到终点所有途径（SearchAllPath）122.5 导入新文献（Loadnewmap）13三、测试分析53.1 可行性分析43.1.1技术可行性43.1.2 工具可行性43.1.3 经济可行性43.1.4 操作可行性53.2 需求分析53.2.1 功能需求53.2.2 输入输出规定5四、使用阐明与执行成果64.1 主界面144.2 游客界面154.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=VRVR=|v,wv且P(v,w)表达从v到w弧，谓词P（v,w）定义了弧意义或信息基本操作P：PrintMap(g) Serach(g)DFSTraverse(g)ShortPath(g)。ADT Graph线性链表抽象数据类型：ADT List数据对象：D=ai|aiElemSet，i=1，2，,n,n0数据关系：R1=|ai-1,aiD,i=2，,n基本操作：DeleteAdv(L,g) InsertAdv(L,g)InsertEdge() DeleteEdge()SaveMap(g) Loadnewmap(p,g)ADT List。 3.2.2 详细数据类型定义typedef struct LNodechar name30;int num;char introduction100;struct LNode *next;LNode,*Link;typedef struct ArcNodeint data； /该弧所得指向顶点位置ArcNode *nextarc； /指向下一条弧指针ArcNode,*ArcLink;typedef struct VNode /顶点信息char name30;int num; char introduction100;ArcLink firstarc； /指向第一条依附该顶点弧指针VNode,AdjListMAX+1;typedef struct ALGraphAdjList vdata； int vexnum,arcnum； /图顶点数和弧数ALGraph;int EdgeMAXMAX； /用来存储途径权值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;jdata=a; p-nextarc=gb.firstarc； gb.firstarc=p； /把p插进来 q=(ArcLink)malloc(sizeof(ArcNode); q-data=b; q-nextarc=ga.firstarc; ga.firstarc=q;二、详细设计2.1 创立图（Fprint-Link）从文献中读出数据，函数流程图2-1所示。结束j+开始读入n,eArcLink p,q;初始化链表，邻接表，Eage i=1,j=1，p=q=(ArcLink)malloc(sizeof(ArcNode);inextarc=gb.firstarc； gb.firstarc=p； /把p插进来q-nextarc=ga.firstarc； ga.firstarc=q;j=eYNUpdate(L,g);/给g赋值图2- 1 Fprint-Link函数流程图2.2 寻找最佳途径（DFSTraverse）运用深度优先思想，遍历图找出一条最佳最佳途径，让它遍历所有景点。运用递归思想，往下遍历，访问标志位，若访问过在下次就不用访问。若找完一种分支在下次重新遍历，函数流程如图2-2所示。开始初始化visitv=0/初始化标志位If（visitv=0）DFS(g,v,visited)；v+Count+Count=n结束YN图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;!sj&distancejminDisu=j;/在s下始终往下找minDis=distancej ;j=nj=0;更新当前最短途径及距离；newDist=distanceu+GetWeightudistancej=newDist;pathj=u;/记录寻找最短途径i=n结束If(newDistdistancej)J=nYNYNYYN图2- 3 寻找最短途径流程图2.4 遍历出某一起点到终点所有途径（SearchAllPath） 运用图深度优先遍历，运用访问标志位。path记录途径，visited设访问标志，v起点，des终点，length，代表是访问景点长度。若碰见死路或者不同路，则从上一种景点，从新扫描，searchAllPath()流程如图2-4所示。If（visitedV）returen;/若所有景点都访问过，则终结v=desPrintfPath(G,path,length);visitedv=1;GetWeight(v,i)!=MAXEDG&!visitediSearchAllPath(G,path,visited,i,des,length+1)i+i=n结束开始NYvisitedv=0;NY图2- 4 searchAllPath()流程图2.5 导入新文献（Loadnewmap）将指定文献导入到邻接表中，再保存到zheke1.txt 中 ,详细实现如图2-5所示。开始初始化Link p，输入文献名filename20Fprint-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#include#define INT_MAX 10000#define n 10int costnn;/* 边值*/int shortestnn;/* 两点间最短距离*/int pathnn;/* 通过景点*/void welcome()printf(n 欢迎光临n);printf(n 凝香公园 nnnnn);printf(n 给您最纯净享有n);printf(n Pure as the south polar snow nn);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(nn 请按键选取:);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(nnn【公园简介】n); printf(n n 凝香园也称“正春园”，位于菏泽城东岳程办事处岳楼行政村。nn); printf( 始建于元末明初，原为袁姓所有，称“袁家堂”花园。nn); printf( 凝香园是国内古代北方八大名园之一，俗称“何家花园”，距今有近1000余年历史。nn); printf( 园中有百近年刺柏、几百年腊梅、紫丁香，千年翠兰松和一块假山石。nn); printf( “凝香园”附近何应瑞坟场古柏成林，苍郁参天。nn); printf(n 注：本公园和真正“凝香园”是同名，而非真实园林！n); printf(nnn); printf(nnn 请输入任意字符【返回主菜单】n); z=getchar();z=getchar();void go() printf(nnnnnn 感谢使用n); printf( n); printf( n); printf( n); printf( 请按任意键退出！ n); printf( n); printf( n); printf( 程序制作：陈明 n); printf( 学号：n); printf( nnnnnn); exit(0);void way() char z; printf(nn); printf( 本公园最佳全景游览路线为：nn); printf( 2公园大门 1沁园 3梨园 5鼎湖 6聚缘阁 7凝香园 4春园 8秋园 9冬园 10夏园 2公园大门n); printf( 全程所需行程：276米!nn); printf( 如需其她路线请返回主菜单进入【浏览路线查询】n); printf(nnn); printf(nnn 请输入任意字符【返回主菜单】n); z=getchar(); z=getchar();void introduce()/*景点简介*/ int a; char z; printf(请输入您想查询景点编号:); scanf(%d,&a); getchar(); printf(nn【 查询成果：】nn); switch(a) case 1: printf( 1:沁园nn一首沁园春.雪让您对眼前梅花感触万千。n);break; case 2: printf( 2:公园大门nn仿古气势宏伟建筑好像置身于1前。n);break; case 3: printf( 3:梨园nn丛林间嬉戏小鸟不禁让你回头倾听。n);break; case 4: printf( 4:春园nn辽阔草地伴着阵阵花香，躺在上面可以仰望南天。n);break; case 5: printf( 5:鼎湖nn 圆滑湖面好像一面大鼎将湖水撑起来。n);break; case 6: printf( 6:聚缘阁nn来自大江南北古玩古画齐聚一堂。n);break; case 7: printf( 7:凝香园nn神奇南方小筑隐匿在桂花林中。聚香也。n);break; case 8: printf( 8:秋园nn当你独自一人行走在大片阔叶林里，才干感受自然气息。n);break; case 9: printf( 9:冬园nn冬日恋歌在这里尽情唱响，High起来吧！n);break; case 10: printf( 10:夏园nn荷花池中一抹红，荷塘月色任你赏！n);break; default: printf( Error：景点编号输入错误！请输入110数字编号！nn);break;printf(nn); void floyed()/*用floyed算法求两个景点最短途径*/ int i,j,k; for(i=1;i=n;i+) for(j=1;j=n;j+) shortestij=costij; pathij=0; for(k=1;k=n;k+) for(j=1;j=n;j+) for(i=1;i(shortestik+shortestkj) /*用path记录从i到j最短途径上点j前驱景点序号*/ shortestij=shortestik+shortestkj; pathij=k; pathji=k; void display(int i,int j)/* 打印两个景点途径及最短距离 */ int a,b; a=i；b=j; printf(n【 查询成果：】nn); printf( 途径：); if(shortestij!=INT_MAX) if(ij) printf( %d,b); while(pathij!=0) /* 把i到j途径上所有通过景点按逆序打印出来*/ printf( %d,pathij); if(ij) j=pathij; else i=pathji; printf( %d,a)； printf(nn); printf( 距离：您需要步行 %dm才干到达目地！,shortestab); else printf(%d,a); while(pathij!=0) /* 把i到j途径上所有通过景点按顺序打印出来*/ printf( %d,pathij); if(i请输入要查询两个景点编号(用空格键隔开):); scanf(%d %d,&i,&j); if(in|in|j请输入要查询两个景点编号(用空格键隔开):); 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