并行与串行数据结构与算法课程设计报告.doc

课 程 实 验 报 告课程名称： 并行与串行数据结构与算法 专业班级： acm1301 学 号： 姓 名： 指导教师： 报告日期： 2015.9.23 计算机科学与技术学院目录1、课程设计概述21.1 课设目的21.2 课设要求21.3 实验环境32、系统总体设计42.1 系统主模块结构体42.2 找附近的最近的三个某地52.3 找两点之间最短路径62.4 数据录入模块73、数据结构和算法详细设计73.1 地图的存储73.1.1 地图背景图片的存储73.1.2 地图点73.2 找附近的最近的特定地点（findnearby）83.3 找最短路径84、程序实现简要说明94.1开发环境94.2 支持包94.3 函数原型10mainactivity.java:实现了地图主要功能10setting.java：地图数据的录入124.4 函数功能调用关系14mainactivity.java：地图主要功能程序15setting.java：数据录入程序155、程序测试及结果分析165.1 功能测试165.2 测试结果分析226、复杂度分析226.1 输入地点名查找，鼠标点击显示226.2 找两点之间的最短路径(dijkstra)226.3 找附近最近的三个某地227、软件的用户使用说明238、特色与不足238.1 特色238.2 不足23九、主要参考文献241、课程设计概述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 存储到起点距离并排序：treesettreeset是一种平衡二叉搜索树（基于红黑树实现），coordinate中存储了点的编号和到起点的距离（treeset中按距离排序，由比较器实现）。b 存储已加入的点：hashsethashset中将已访问的点的编号哈希一下，可以快速的存取和访问。(平均常数时间)c 存储父节点：int数组中索引是点的编号，存储的是父节点的编号。d 存储找到的点：arraylistarraylist基于数组实现，可以获得数组的存取速度，又可以自动动态扩展其大小。coordinate中存储了点的编号和到起点的距离。3.3 找最短路径算法：dijkstra的最短路径算法数据结构：a 存储到起点距离并排序：treesettreeset是一种平衡二叉搜索树（基于红黑树实现），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;vider.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保存了程序执行的时候的一些状态，方便恢复时接着当前状态继续执行，避免状态丢失影响用户体验。输出参数：无protected void onpause();功能：当前activity 变为pause状态时触发的函数输入变量：无输出变量：无public boolean oncreateoptionsmenu(menu menu);功能： 初始化菜单显示输入参数：menu menu 系统变量输出参数：显示时候异常public boolean onoptionsitemselected(menuitem item);功能： 处理菜单点击事件输入参数：menuitem item菜单项标识输出参数：是否处理了点击事件指示变量public static int calculateinsamplesize(bitmapfactory.options options, int reqwidth, int reqheight);功能：更换地图是，根据屏幕尺寸计算地图缩放比例输入变量：bitmapfactory.options options地图背景图片信息int reqwidth屏幕宽度 int reqheight屏幕高度输出变量：图片放大倍数的倒数public bitmap getmapbitmapimage(string path);功能：获得默认地图背景图片输入变量：地图背景图片的存储路劲输出变量：地图背景图片protected void onactivityresult(int requestcode, int resultcode, intent data);功能：处理更换地图背景图片子程序的返回结果输入变量：int requestcode子程序标识代码 int resultcode子程序处理结果状态码 intent data子程序返回的数据输出变量：无public void onbackpressed();功能：处理按返回键操作输入变量：无输出变量：无public void resizedataarray(int capacity);功能：扩大地图点数组的大小输入变量：当前数组大小输出变量：无public void loaddata(int scale);功能：加载地图点数据输入变量：默认地图点数组大小输出变量：无4.4 函数功能调用关系mainactivity.java：地图主要功能程序setting.java：数据录入程序5、程序测试及结果分析5.1 功能测试程序打开初始界面：搜索某地（西操）：搜索西操结果：红点标识点击某点，显示子菜单：点击搜周边后的输入界面（搜索框提示语变了）：搜周边结果（食堂）结果：按到当前点距离标号，并用红线标示路径搜索两点之间最短路径结果：用红线标示路径，并显示关键点名称地图录入界面：显示了每个点的编号，方便录入邻接关系地图点数据录入界面：最上面是数据录入框更换地图功能展示：现在可以构建一个武大地图了5.2 测试结果分析基本功能和扩展功能都良好实现，无bug。6、复杂度分析 6.1 输入地点名查找，鼠标点击显示在数组中线性查找，复杂度为o(n)6.2 找两点之间的最短路径(dijkstra)（n代表点数，m代表边数）sortedpoint（treeset）：pollfirst（删除当前最小）：log(m) m次 add(插入)：log(m) m次added (hashset) : contains(是否已弹出) o(1)m次 addo(1) n次对邻接点的访问（数