并行与串行数据结构与算法课程设计报告品要点.docVIP

课 程 实 验 报 告 课程名称： 并行与串行数据结构与算法 专业班级： ACM1301 学 号： U201315057 姓 名： 李海锋 指导教师： 陆枫 报告日期： 2015.9.23 计算机科学与技术学院  目录 1、课程设计概述 2 1.1 课设目的 2 1.2 课设要求 2 1.3 实验环境 3 2、系统总体设计 4 2.1 系统主模块结构体 4 2.2 找附近的最近的三个某地 5 2.3 找两点之间最短路径 6 2.4 数据录入模块 7 3、数据结构和算法详细设计 7 3.1 地图的存储 7 3.1.1 地图背景图片的存储 7 3.1.2 地图点 7 3.2 找附近的最近的特定地点（findNearby） 8 3.3 找最短路径 8 4、程序实现简要说明 9 4.1开发环境 9 4.2 支持包 9 4.3 函数原型 10 MainActivity.java:实现了地图主要功能 10 Setting.java：地图数据的录入 12 4.4 函数功能调用关系 14 MainActivity.java：地图主要功能程序 15 Setting.java：数据录入程序 15 5、程序测试及结果分析 16 5.1 功能测试 16 5.2 测试结果分析 22 6、复杂度分析 22 6.1 输入地点名查找，鼠标点击显示 22 6.2 找两点之间的最短路径(dijkstra) 22 6.3 找附近最近的三个某地 22 7、软件的用户使用说明 23 8、特色与不足 23 8.1 特色 23 8.2 不足 23 九、主要参考文献 24 1、课程设计概述 1.1 课设目的 数据结构是计算机科学技术与信息安全等专业的一门重要专业基础课，牢固掌握数据结构的基础知识，熟练地运用数据结构的思想与技术方法解决实际应用问题是是本课程学习的基本任务与目标。而课程设计是重要组成部分题目： 问题背景： 华中科技大学（Huazhong University of Science and Technology），简称华中大，坐落于湖北省武汉市，学校面积7000余亩。华科大校园具有典型的工科院校特征，道路笔直，建筑面积方方正正，这为构建电子地图提供了极大的便利。本实验要求实现一个简单的华科地图程序，可以方便的实现有哪些信誉好的足球投注网站、导航等功能。 基本要求： 1输入地点名，可以 鼠标移动到指定建筑处显示建筑名称 2输入或点击起点和终点，找出并在图上路径 3输入起点，输入 地点至少要包括清单中所列的位置 实验提示： 将每个十字路口或特定建筑看作节点，构建图模型，两个可能可以而对于例如可能只是需要 程序首先载入一张图片并显示。程序当点击第二个文本框剩下这样节点 特定建筑只需考虑建筑大门所对应的路段上的一点。例如位于当鼠标附近找到 对于存在折线的路段，将其对于当作 1.3 实验环境 android studio 2、系统总体设计 2.1 系统主模块结构体 2.2 找附近的最近的三个某地 2.3 找两点之间最短路径 2.4 数据录入模块 3、数据结构和算法详细设计 3.1 地图的存储 3.1.1 地图背景图片的存储 初次运行，软件默认显示华科地图，并根据屏幕尺寸设置地图尺寸，然后将地图背景图片存储到手机文件中，以后直接从文件中读取地图背景图片，提高效率。 3.1.2 地图点 未运行时，地图点的信息存储在手机文件中。运行时，地图点信息存储在一个一维数组中，数组索引是点的地图点的编号。数组中的元素是地图点类（MapPointPlus）,该类中含有以下成员： 编号（int）:serialNumber 坐标（Coordinate）:coordinate 属性（String）:property 名称（String）:name 邻接点（String）:stringNearbyPoint 邻接点（Coordinate[]）:nearbyPoint 3.2 找附近的最近的特定地点（findNearby） 算法：dijkstra的最短路径算法，并判断是否满足条件和满足条件的点的个数。 数据结构： a 存储到起点距离并排序：TreeSetCoordinate TreeSet是一种平衡二叉有哪些信誉好的足球投注网站树（基于红黑树实现），Coordinate中存储了点的编号和到起点的距离（TreeSet中按距离排序，由比较器实现）。 b 存储已加入的点：HashSet HashSet中将已访问的点的编号哈希一下，可以快速的存取和访问。(平均常数时间) c 存储父节点：int[] 数组中索引是点的编号，存储的是父节点的编号。