数据结构与算法基础报告.doc

.数据结构与算法基础课程项目实施总结报告题 目： 校园最短路径漫游 组 号： 110 任课教师： 朱晓强 组 长： 13121085 支姜茏 0.2 组 员： 13121570 汪舒雯 0.2 组 员： 13122979 胡 斌 0.2 组 员： 13121843 刘 鑫 0.2 组 员： 13122777 王佑磊 0.2 2015年10月18日目录一、项目要求1.项目名称2.项目要求3.项目介绍二、整体思路三、分部介绍1.Floyd算法程序部分1.1核心思路 1.1.1路径矩阵 1.1.2状态转移方程1.2算法过程1.3复杂度1.4算法描述1.5算法详情 2.网页与数据部分2.1网页显示2.2数据库 3.控制程序部分三、总结一、项目要求1、项目名称：校园最短路径漫游2、项目要求根据校园各主要生活、学习、活动等场所、地点，设计并实现基于校园各场所之间的最短路径漫游。设计要求： （1）掌握数据结构的输入/输出； （2）设计与实现校园各主要场所之间的最短路径算法； （3）根据场所之间的最短路径及不同场所之间的路况信息，设置相应的步行、骑行等出行方式，计算到达每一目的地的时间及总的路程耗时； （4）各主要场所、地点以及漫游状态，以地图缩、放方式动态展示；（5）校园各主要场所、地点不少于50个。3、项目介绍评分依据： （1） 功能实现； （2） 性能指标； （3） 工程规范（规范、安全性、可靠性、性价比等）； （4） 理论水平； （5） 团队分工合作情况。使用语言： JAVA,H5二、整体思路将地图背景存于网页之中并建立坐标，将目标点与路径存入，调用算法计算得出所求返回到网页显示出所求。实现方案：采用java做后台，H5的Canvar作为结果展示部分。总体架构：springMvc+hibernate+html5+jquery。三、分部介绍本项目总体分为三个部分：Floyd算法程序，网页与数据，总控制程序。1、 Floyd算法程序部分1.1核心思路 1.1.1路径矩阵通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=a(i,j) nn开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。采用松弛技术（松弛操作），对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n3)。1.1.2状态转移方程其状态转移方程如下： mapi,j:=minmapi,k+mapk,j,mapi,j；mapi,j表示i到j的最短距离，K是穷举i,j的断点，mapn,n初值应该为0，或者按照题目意思来做。当然，如果这条路没有通的话，还必须特殊处理，比如没有mapi,k这条路。1.2算法过程1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则Gi,j=d，d表示该路的长度；否则Gi,j=无穷大。定义一个矩阵D用来记录所插入点的信息，Di,j表示从Vi到Vj需要经过的点，初始化Di,j=j。把各个顶点插入图中，比较插点后的距离与原来的距离，Gi,j = min( Gi,j, Gi,k+Gk,j )，如果Gi,j的值变小，则Di,j=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为V5,V3,V1，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。1.3复杂度时间复杂度:O(n3)；空间复杂度:O(n2)1.4算法描述a)初始化：Du,v=Au,vb)For k:=1 to nFor i:=1 to nFor j:=1 to nIf Di,jDi,k+Dk,j ThenDi,j:=Di,k+Dk,j;c)算法结束：D即为所有点对的最短路径矩阵 1.5算法详情 （见附录一）2、网页与数据部分2.1网页显示首先来看一下H5的画布：上图就是用canvar画出来的（画图的主要脚本函数见附录二）从百度地图截取地图作为网页的背景，并在网页中建立直角坐标系，标注各个坐标点作为所需目标点，再录入目标点之间的路径同时录入距离，此时所有所需数据经控制程序读取载入到Floyd算法中几科求得所需。（关于前台网页总程序见附录三）2.2数据库如上文所述，数据获取之后存入数据库之中，一下即为数据结构的介绍数据结构的设计：Point表:ID地点名称编号横坐标纵坐标LongNameNumberXY主键StringIntIntIntLine表：ID起点横坐标起点纵坐标终点横坐标终点纵坐标长度是否可骑行编号LongFrom_xFrom_yTo_xTo_yLengthIsablebikeInt(例1_2)主键IntIntIntIntIntBooleanstring一共就两张数据表，来记录所有的点和线。使用的是mysql数据库。（操作类代码见附录四）以上为接口，数据有了，就可以进行操作了。什么添加点，添加线啊什么的直接在控制器里买呢调用上面的接口就可以了。如下举一个添加线的例子。（见附录五）3、控制程序部分控制程序部分为整体运作部分，在网页中操作选取需要求最短路径的两个目标点并与数据库一同读入程序，调用Floyd算法求得经过的路径与目标点，即可得到距离总长及所需时间，再将对应路径在网页中用红色线段表示，测试者即可清晰看到“最短路径”。（程序部分见附录六）三、总结本次课程项目，我们在实际过程中遇到了不少的问题。比如说我们在选择图形界面的显示工具时，讨论了不少方案，最后我们选择了通过网页的形式来显示。因为以网页的方式来呈现，更具开放性和交互性。比如说地图的缩放问题，开始时我们想到的是通过对数据库中坐标的大小变换，来实现对地图的缩放，然而我们觉得这样子的做法过于繁琐，恰巧通过网页，我们可以用网页自带的ctrl+鼠标滚轮的方式进行缩放，这样即减少了程序的复杂度，也充分运用了网页的优势功能。比如我们用floyd算法计算两点之间最短距离通过的路径时，刚开始我们用二维矩阵，记录点和点之间的最短距离，却发现计算出来的路径点顺序是错乱的。通过查阅资料，我们发现了将二维矩阵变成三维矩阵，多出来的一维用来记录点的顺序，即可解决。又比如一开始我们在每次运行程序时，都需要计算一遍各个点之间的路径最短距离。为了提高计算的效率，我们重新加入了一个标志位，只需要在第一次运行的时候将计算结果存入服务器内存，再次调用时就不需要花费过多的时间来计算了。这次课程项目，锻炼了我们对java编程语言的理解程度，了解了网页和面向对象语言之间建立联系的方式，对floyd算法的具体深入学习，收获不小。附录一：Floyd算法package com.main.controller;import java.util.List;import com.global.dao.LineDAO;import com.global.dao.PointDAO;import com.global.daoimpl.LineDAOImpl;import com.global.daoimpl.PointDAOImpl;import com.global.models.Line;import com.global.models.Point;public class FLOYD public static int MAX =999999;public static int INF =999999;int length = null;/ 任意两点之间路径长度int path = null;/ 任意两点之间的路径public static int isInit=2;public static boolean isrun=false;public static FLOYD floyd;public static void init(int isBike) /找到所有的点PointDAO pdao=new PointDAOImpl();LineDAO ldao=new LineDAOImpl();List points=pdao.findAllPoint();int pointNum=points.size();int map=new intpointNumpointNum;/构造权值矩阵/读取数据库，赋初值for(int i=0;ipointNum;i+) for(int j=0;jpointNum;j+) if(i=j) mapij=0;/自己到自己距离为0continue;Line line=ldao.find(i+1, j+1); if(line=null) /不存在此路径，权值为无穷大mapij=INF;else mapij=line.getLenth(); floyd=new FLOYD(map,isBike);isrun=true;public FLOYD(int G,int isbike) int row = G.length;/ 图G的行数int spot = new introwrow;/ 定义任意两点之间经过的点int onePath = new introw;/ 记录一条路径length = new introwrow;path = new introwrow;for (int i = 0; i row; i+)/ 处理图两点之间的路径for (int j = 0; j row; j+) /if (Gij = 0)/Gij = MAX;/ 没有路径的两个点之间的路径为默认最大if (i = j)Gij = 0;/ 本身的路径长度为0for (int i = 0; i row; i+)/ 初始化为任意两点之间没有路径for (int j = 0; j row; j+)spotij = -1;for (int i = 0; i row; i+)/ 假设任意两点之间的没有路径onePathi = -1;for (int v = 0; v row; +v)for (int w = 0; w row; +w)lengthvw = Gvw;for (int u = 0; u row; +u)for (int v = 0; v row; +v)for (int w = 0; w lengthvu + lengthuw) lengthvw = lengthvu + lengthuw;/ 如果存在更短路径则取更短路径spotvw = u;/ 把经过的点加入if(isbike=0) LineDAO ldao=new LineDAOImpl();if (lengthvw lengthvu + lengthuw&!ldao.find(v+1, u+1).isAbleBike()&!ldao.find(u+1, w+1).isAbleBike() lengthvw = lengthvu + lengthuw;/ 如果存在更短路径则取更短路径spotvw = u;/ 把经过的点加入if(isbike=1) LineDAO ldao=new LineDAOImpl();if (lengthvw lengthvu + lengthuw&ldao.find(v+1, u+1).isAbleBike()&ldao.find(u+1, w+1).isAbleBike() lengthvw = lengthvu + lengthuw;/ 如果存在更短路径则取更短路径spotvw = u;/ 把经过的点加入/是否可以骑自行车endfor (int i = 0; i row; i+) / 求出所有的路径int point = new int1;for (int j = 0; j row; j+) point0 = 0;onePathpoint0+ = i;outputPath(spot, i, j, onePath, point);pathij = new intpoint0;for (int s = 0; s point0; s+)pathijs = onePaths;void outputPath(int spot, int i, int j, int onePath, int point) / 输出i/ 到j/ 的路径的实际代码，point记录一条路径的长度if (i = j)return;if (spotij = -1)onePathpoint0+ = j;/ System.out.print( +j+ );else outputPath(spot, i, spotij, onePath, point);outputPath(spot, spotij, j, onePath, point);public static void main(String args) int data= 0,5,MAX,MAX,3,1,MAX, / x1 5,0,4,MAX,MAX,1,MAX, / 1 MAX,4,0,5,MAX,1,MAX, / 2 MAX,MAX,5,0,MAX,MAX,1, / 3 3,MAX,MAX,MAX,0,4,MAX, / 4 1,1,1,MAX,4,0,MAX , / 5 MAX,MAX,MAX,1,MAX,MAX,0 , / 6;/for (int i = 0; i data.length; i+)/for (int j = i; j data.length; j+)/if (dataij != dataji)/return;FLOYD test = new FLOYD(data,2);for (int i = 0; i data.length; i+)for (int j = i; j datai.length; j+) System.out.println();System.out.print(From + i + to + j + path is: );for (int k = 0; k test.pathij.length; k+)System.out.print(test.pathijk + );System.out.println();System.out.println(From + i + to + j + length : + test.lengthij);附录二：画图脚本function draw(id)/初始化函数 var canvers=document.getElementById(mycanver); if(canvers = null) return false; var cxt=canvers.getContext(2d); canvers.addEventListener(click, function (evt) canversClick(canvers,evt,cxt), false);/添加点击事件 drawPoint(cxt,200,100,上海大学北门); drawPoint(cxt,450,160,上海大学图书馆); drawPoint(cxt,100,180,上大南区); drawPoint(cxt,300,30,上大新世纪); dramLine(200,100,450,160,cxt); function drawPoint(cxt,x,y,text)/描点函数 cxt.beginPath(); cxt.arc(x,y,10,0,360,false); cxt.fillStyle=cornflowerblue;/填充颜色,默认是黑色 cxt.fill();/画实心圆 cxt.closePath(); cxt.font = 14px; cxt.textAlign = center; cxt.textBaseline = top; cxt.strokeStyle = black; cxt.strokeText(text, x, y+15); function dramLine(fromX,fromY,toX,toY,cxt,color)/连线函数 cxt.save(); if(color=null) cxt.strokeStyle=black; else cxt.strokeStyle = color; cxt.translate(0.5,0.5); cxt.lineWidth = 1; cxt.beginPath(); cxt.moveTo(fromX, fromY); cxt.lineTo(toX,toY); cxt.stroke(); cxt.restore(); 附录三：关于前台网页代码 var curentMode=0;var startPoint=new point(0,0);var endPoint=new point(0,0);/0：浏览模式 1：添加标注模式 2：连线模式function point(x,y)this.x=x;this.y=y;function draw(id)var canvers=document.getElementById(mycanver);var cxt=canvers.getContext(2d);if(canvers = null)return false;canvers.addEventListener(click, function (evt) canversClick(canvers,evt,cxt), false);/添加点击事件/* drawPoint(cxt,200,100,上海大学北门);drawPoint(cxt,450,160,上海大学图书馆);drawPoint(cxt,100,180,上大南区);drawPoint(cxt,300,30,上大新世纪);dramLine(200,100,450,160,cxt); */function drawPoint(cxt,x,y,text)cxt.beginPath();cxt.arc(x,y,10,0,360,false);cxt.fillStyle=cornflowerblue;/填充颜色,默认是黑色cxt.fill();/画实心圆cxt.closePath(); cxt.font = 14px; cxt.textAlign = center; cxt.textBaseline = top; cxt.strokeStyle = black; cxt.strokeText(text, x, y+15); function dramLine(fromX,fromY,toX,toY,cxt,color)cxt.save(); if(color=null)cxt.strokeStyle=black;else cxt.strokeStyle = color; cxt.translate(0.5,0.5); cxt.lineWidth = 1; cxt.beginPath(); cxt.moveTo(fromX, fromY); cxt.lineTo(toX,toY); cxt.stroke(); cxt.restore(); /Get Mouse Position function getMousePos(canvas, evt) var rect = canvas.getBoundingClientRect(); return x: evt.clientX - rect.left * (canvas.width / rect.width), y: evt.clientY - rect.top * (canvas.height / rect.height) function canversClick(canvas,evt,cxt) var mousePos = getMousePos(canvas, evt); /alert(); $(#pointInput).val(parseInt(mousePos.x) +, + parseInt(mousePos.y);if(curentMode=1)drawPoint(cxt,mousePos.x,mousePos.y,上海大学北门);if($(input:radioname=pointState:checked).val()=0)startPoint=new point(mousePos.x,mousePos.y);$(#startPoint).text(startPoint.x+,+startPoint.y)else endPoint=new point(mousePos.x,mousePos.y);$(#endPoint).text(endPoint.x+,+endPoint.y) function zoom_click() var can=document.getElementById(mycanver); var cans = can.getContext(2d);/ drawCircle(red); cans.scale(0.1,0.1);/ drawCircle(green); jQuery(document).on(click, inputname=mode, function() curentMode=$(this).val(); );jQuery(document).on(click, .dramLine, function() if(curentMode=2)var canvers=document.getElementById(mycanver);if(canvers = null)return false;var cxt=canvers.getContext(2d);dramLine(startPoint.x,startPoint.y,endPoint.x,endPoint.y,cxt); );$(document).ready(function() %List points=(List)request.getAttribute(points);List lines=(List)request.getAttribute(lines);%if(points!=null)for(int i=0;ivar canvers=document.getElementById(mycanver);var cxt=canvers.getContext(2d);drawPoint(cxt,);%if(lines!=null)for(int i=0;ivar canvers=document.getElementById(mycanver);var cxt=canvers.getContext(2d);dramLine(,cxt); jQuery(document).on(click, .searchPath, function() var data=fr