连云港景点导游咨询资料.doc

淮 海 工 学 院 计算机工程学院 课程设计报告 设计名称： 数据结构课程设计 选题名称： 连云港市景点导游咨询 姓 名： 顾浩然 学 号： 110912109 专业班级： 网络工程 网络091 系 （院）： 计算机工程学院 设计时间： 2010.12.20~2010.12.31 设计地点： 软件工程实验室、教室 成绩：指导教师评语： 成绩： 签名： 年 月 日 数据结构课程设计报告 第 PAGE 23 页，共 页 1．课程设计目的 1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。 2．课程设计任务与要求： 任务：用无向网表示连云港市旅游景点平面图，图中顶点表示主要景点，存放景点编号、名称、简介等信息，图中边表示景点间的道路，存放路径长度信息。 要求：（1）查询各景点的相关信息； （2）查询图中任意两个景点间的最短路径 （3）查询图中任意两个景点间的所有路径 （4）可动态添加景点，加后可查询该景点到其它景点的最短路径 3．课程设计说明书 一 需求分析： 连云港作为一个著名的旅游城市，每年都有大量的国内外游客来港城旅游，大多数外地游客对连云港的旅游景点的相关信息不是非常了解，所以我们可以为他们设计一个方便在连云港外出旅游的咨询程序，即连云港市景点导游咨询程序。 连云港市导游咨询程序需要把连云港市的主要景点（争取十个左右，虽然我只认识几个而已）都包括在一个平面图内。 (1) 以图中各顶点存放连云港的各景点名称，代号，简介等相关信息 （2）程序中，以各个旅游景点名称为图的顶点，各个顶点的信息是景点的简要描述，权值就是任意两个景点间的路径长度 (3) 以边存放路径及路径长度等相关信息，游客可根据图所提供的景点来查询各个景点的相关信息及各景点的路径查询 (4) 提供两个景点间的所有路径并提示最短路径，为游客的旅游带来方便，游客可根据实际情况选择最佳的游览路线。 二 概要设计 1、基本操作： CreateGraph(G):创建图G。 LocateVertex(G,v):确定顶点v在图g中的位置，若图g中没有顶点v，则函数值为“空”。 GetVertex(G,i):取出图g中的第i个顶点的值，若i大于图g中顶点数，则函数值为“空”。 FirstAdjVertex（G，v）：求图G顶点v的第一个邻接点，若v无邻接点或图G中无顶点v，则函数值为“空”。 NextAdjVertex（G，v，w）：已知w是图G中顶点v的某个邻接点，求顶点v的下一个邻接点（紧跟在w后面），若w是v的最后一个邻接点，则函数值为“空”。 InsertVertex（G，u）：在图G中增加一个顶点u。 InsertArc（G，v，w）：在图G中增加一条从顶点v到顶点w的弧。 TraverseGraph（G）：按照某种次序，对图G的每个结点访问一次且仅访问一次。 2、系统中子程序及功能要求： ①path(MGraph g,int i,int j,int k)：确定路径上第k+1个顶点的序号,k初始值为0 ②apath(MGraph g,int i,int j)：初始化访问标志与路径条数，并调用path（）函数 ③cpath(MGraph g,int path1[],int i,int v0)：输出最短路径 ④bpath(MGraph g,int dist[],int path1[],int s[],int n,int v0,int i)：由path1计算从v0到i的最短路径 ⑤Dijkstra(MGraph g,int v0,int p)：采用迪杰斯特拉算法求从顶点v0到顶点p的最短路径 ⑥chanam