校园导游系统

西安郵電學院

数据结构课程设计报告

题 目： 校园导游系统

系部名称 ： 计算机系 专业名称 ： 软件工程 班 级 ： 0604班 学

号 ： 04065139

学生姓名 ： 高孟迪 指导教师 ： 王春梅 时

间 ：

2008年6月1日 至2008年 6月8日

一． 实验目的

1. 对自己学过的知识进一步的加深理解，对数据结构的算法思想要有更深的理解。

2. 通过课程设计，学会通过系统分析、系统设计、编程调试，

写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用 。 3. 学会综合运用数据结构课程中学到的几种典型数据结构，如链表，栈，队列，以及程序设计语言（C语言），自行实现一个较为完整的应用系统的设计与开发。

二． 课程设计内容 基本要求：

? 校园平面图（景点、路径等信息）存储

选取校园或某景区中多个具有代表性景点，抽象成无向带权图。可采用邻接表或邻接

多重表存储。

? 查询图中任意景点的相关信息

? 查询道路信息（道路类别、沿途景色等） ? 查询任意两个景点之间的一条最短的简单路径 利用迪杰斯特拉或弗洛伊德算法确定最短路径 ? 从某个景点出发给出访问所有景点的最佳行走方案 利用深度优先和广度优先搜索遍历图 ? 查询任意两景点之间的所有路径（选做）

三． 需求分析

现在大多数的学校由于不断的扩张，这也就使得学校不得不建立的更大。这也就为人们拜访学校造成了很大的不便。人们往往不熟悉学校，找个东西，或某处带来了极大的不便。往往要花很多时间在这一方面。然而要是有一个学校导游系统这将给乘客带来极大的方便，使人们一下就能了解到这个学校的大致的情况。

功能：这个系统给用户提供查询景点，浏览路径，寻找最佳的方案到达目的地，还提供了最佳路径。

实现的目标：实现对某一个学校的校园导游系统。

四． 概要设计

1. 系统结构图

系统分析：用的图的算法进行构造，用邻接表建立图，然后再用深度优先遍历进行搜索，查找所需的路径。再用迪杰特斯拉算法求出两个景点之间的最佳路径。 结构图：

main创建图浏览学校全景寻找最佳路径查看景点浏览出的所有路径 2. 功能模块说明

2.1创建图(InitGraph):

建立无向图，把学校的景点及景点的信息，连接起来

建立邻接表采用链式加顺式存储。

浏览学校的全景（Browser）：列出学校的所有的景点。 寻找最佳路径（DFSTraverse：）：

输入一个景点，会吧所有都浏览一边，并找出最佳的路径。

最短路径（ShortPath）:求出起点和终点的最佳路径，并求出最佳路径的长度。

遍历出某一起点到终点的所有路径（SearchAllPath）： 找出所有路径，利用深度优先遍历。

五． 详细设计 5.1 创建图：

开始输入景点的总数和边的总数从文件读入顶点的信息idata=a;p->nextarc=g[b].firstarc; q->data=b;q->nextarc=g[a].firstarc; Edge[a][b]=weight; Edge[b][a]=weight;结束