课程实验报告课程名称：并行与串行数据结构与算法专业班级：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 课设目的数据结构是计算机科学技术与信息安全等专业的一门重要专业基础课，牢固掌握数据结构的基础知识，熟练地运用数据结构的思想与技术方法解决实际应用问题是是本课程学习的基本任务与目标。
而课程设计是实现这一学习目标的重要环节和组成部分。
通过课程设计的训练，使学生加深对数据结构知识的理解，牢固掌握其应用方法，并合理灵活地解决一定实际问题，增强和提高综合分析问题与解决问题的能力。
1.2 课设要求题目：华科地图导航问题背景：华中科技大学（Huazhong University of Science and Technology），简称华中大，坐落于湖北省武汉市，学校面积7000余亩。
华科大校园具有典型的工科院校特征，道路笔直，建筑面积方方正正，这为构建电子地图提供了极大的便利。
本实验要求实现一个简单的华科地图程序，可以方便的实现搜索、导航等功能。
基本要求：1输入地点名，可以在地图中以一定标记标示出地点所在的位置鼠标移动到指定建筑处显示建筑名称2输入或点击起点和终点，找出最短的路径，并在图上描出路径，路径不能脱离道路3输入起点，输入特定的地点，如食堂，超市能够找到最近的两到三个地点至少要包括清单中所列的位置实验提示：将每个十字路口或特定建筑看作节点，构建图模型，两个节点的边即是一个路段。
对于某些节点，可能具有特定的意义，例如“图书馆”，可以为其设置一个名称；而对于大多数节点，例如普通路口，可能并不需要名称，只是用来构建图模型的一个节点。
信息的录入可能需要人为输入，需要编写辅助程序。
辅助程序可以如下构造：程序首先载入一张图片并显示。
程序具有多个文本框，当点击图片上特定点时，获取该点的坐标，第一个文本框显示该点的图像坐标，第二个文本框可以输入地点名，第三个文本框用来输入节点编号，剩下的文本框用来输入直接相邻的节点编号或者节点的属性。
点击“确认”后可以将信息保存到磁盘。
这样可以实现坐标、节点编号和位置名称的绑定，为实验构图采集数据。
特定建筑只需考虑建筑大门所对应的路段上的一点。
例如“图书馆”建筑，可认为“图书馆”位于图书馆大门和学校道路相接处，简化处理。
当鼠标移动到“图书馆”附近时，找到距离最近的具有名称的节点显示即可。
对于存在折线的路段，将其看作多段处理；对于细碎的弯折路线，当作直线简化处理。
1.3 实验环境android studio2、系统总体设计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[]）:nearbyPoint3.2 找附近的最近的特定地点（findNearby）算法：dijkstra的最短路径算法，并判断是否满足条件和满足条件的点的个数。
数据结构：a 存储到起点距离并排序：TreeSet<Coordinate>TreeSet是一种平衡二叉搜索树（基于红黑树实现），Coordinate中存储了点的编号和到起点的距离（TreeSet中按距离排序，由比较器实现）。
b 存储已加入的点：HashSetHashSet中将已访问的点的编号哈希一下，可以快速的存取和访问。
(平均常数时间)c 存储父节点：int[]数组中索引是点的编号，存储的是父节点的编号。
d 存储找到的点：ArrayList<Coordinate>ArrayList基于数组实现，可以获得数组的存取速度，又可以自动动态扩展其大小。
Coordinate中存储了点的编号和到起点的距离。
3.3 找最短路径算法：dijkstra的最短路径算法数据结构：a 存储到起点距离并排序：TreeSet<Coordinate>TreeSet是一种平衡二叉搜索树（基于红黑树实现），Coordinate中存储了点的编号和到起点的距离（TreeSet中按距离排序，由比较器实现）。
b 存储已加入的点：HashSetHashSet中将已访问的点的编号哈希一下，可以快速的存取和访问。
(平均常数时间)c 存储父节点：int[]数组中索引是点的编号，存储的是父节点的编号。
4、程序实现简要说明4.1开发环境Ubuntu + android studio+ android手机一部4.2 支持包android.content.Context;android.content.Intent;android.content.res.Resources;android.graphics.Bitmap;android.graphics.BitmapFactory;android.graphics.Canvas;android.graphics.Color;android.graphics.Paint;android.os.Bundle;android.os.Environment;android.support.v4.app.DialogFragment; android.support.v4.app.FragmentActivity; android.text.Editable;android.text.TextWatcher;android.util.DisplayMetrics;android.util.Log;android.view.Menu;android.view.MenuItem;android.view.MotionEvent;android.view.View;android.view.WindowManager;android.view.inputmethod.InputMethodManager; android.widget.Button;android.widget.EditText;android.widget.HorizontalScrollView; android.widget.ImageView;android.widget.LinearLayout;android.widget.ScrollView;android.widget.TextView;android.widget.Toast;java.io.File;java.io.FileInputStream;java.io.FileNotFoundException;java.io.FileOutputStream;java.io.IOException;java.util.ArrayList;java.util.Arrays;java.util.HashSet;java.util.TreeSet;java.util.regex.Matcher;java.util.regex.Pattern;android.app.Activity;android.content.Context;android.database.Cursor;.Uri;android.provider.MediaStore;4.3 函数原型MainActivity.java:实现了地图主要功能protected void onCreate(Bundle savedInstanceState);功能：初始化应用程序，设置各种监听器，监听器中有一些功能的实现输入参数：Bundle savedInstanceState保存了程序执行的时候的一些状态，方便恢复时接着当前状态继续执行，避免状态丢失影响用户体验。
输出参数：无public boolean onCreateOptionsMenu(Menu menu);功能：初始化菜单显示输入参数：Menu menu 系统变量输出参数：显示时候异常public boolean onOptionsItemSelected(MenuItem item);功能：处理菜单点击事件输入参数：MenuItem item菜单项标识输出参数：是否处理了点击事件指示变量protected void onActivityResult(int requestCode, int resultCode, Intent data);功能：对Setting.java的操作结果进行处理输入参数：int requestCode不同子程序区分变量int resultCode子程序处理结果指示变量Intent data子程序返回的一些信息输出参数：无public static int calculateInSampleSize(BitmapFactory.Options options, int reqWidth, int reqHeight);功能：根据屏幕尺寸，计算原始地图图片缩放比输入参数：BitmapFactory.Options options地图图片信息int reqWidth屏幕宽度int reqHeight屏幕高度输出参数：放大倍数的倒数public static Bitmap decodeSampledBitmapFromResource(Resources res, int resId, int reqWidth, int reqHeight);功能：从资源中提取所需的地图背景图片输入参数：Resources res资源句柄int resId地图背景图片id号int reqWidth屏幕宽度int reqHeight屏幕高度输出参数：地图背景图片private void customMap();功能：让地图背景图片适配屏幕尺寸输入参数：无输出参数：无public void loadData(int scale);功能：加载地图点数据输入参数：int scale初始数据规模大小输出参数：无public void resizeDataArray(int scale);功能：扩大地图点数组的大小输入参数：int scale当前地图点数组大小输出参数：无public void choose(int which);功能：处理地图点操作弹出菜单的选择结果输入参数：int which选择的子菜单索引输出参数：无public void showDialog();功能：弹出地图点操作子菜单输入参数：无输出参数：无public void findNearby(int touchPointSerialNumber, String target, int screenHeight, int screenWidth);功能：输入起点，输入特定的地点，找最近的3个输入参数：int touchPointSerialNumber点击的地图点编号String target特定的地点int screenHeight屏幕高度，显示搜索结果时使结果点在屏幕中心时用int screenWidth屏幕宽度，显示搜索结果时使结果点在屏幕中心时用输出参数：无public void singleSourcedShortestPath(int beginSerialNumber, int endSerialNumber, int screenHeight,int screenWidth);功能：找两点之间最短路劲输入参数：int beginSerialNumber起点编号int endSerialNumber终点编号int screenHeight屏幕高度，显示搜索结果时使起点点在屏幕中心时用int screenWidth屏幕宽度，显示搜索结果时使起点点在屏幕中心时用输出参数：无Setting.java：地图数据的录入protected void onCreate(Bundle savedInstanceState);功能：初始化应用程序，设置各种监听器，监听器中有一些功能的实现输入参数：Bundle savedInstanceState保存了程序执行的时候的一些状态，方便恢复时接着当前状态继续执行，避免状态丢失影响用户体验。