Java数据结构和算法笔记

Java数据结构和算法第0讲综述参考教材：Java数据结构和算法（第二版），美RobertIafore1 .数据结构的特性数据结构I优点缺点数纽插入快；如果知道下标，可以非常快地存取查找慢,删除慢,大小固定有序数组比无序的数组查找快IW除和插入慢，大小固定栈提供后进先出方式的存取存取其他项很慢队列提供先进先出方式的存取存取其他项很慢链表插入快，删除快0)totaI=totaI+n;returntotaI;直接转换法直才妾转换法通常用来消除尾遏归和单向遏归，将递归结构用循环结构来替代。尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。例如求阶乘的递归算法：publiclongfact(irTtn)if(n=0)return1;eIsereturnn*fact(nT);当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以，不必利用栈来保存返回信息。对于尾递归形式的递归算法，可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法：publiclongfact(irvtn)(ints=0;for(inti=1;is=s*i;间接转换法该方法使用栈保存中间结果，一般需根抵递归函数在执行过程中栈的变化得到。其一般过程如下：将初始状态sO进栈while(栈不为空)退栈，将栈顶元素赋给s;if(s是要找的结果)返回；eIse*寻找到S的相关状态S1；将S1进栈）间接转换法在数据结构中有较多实例，如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现等等，请读者参考主教材中相关内容第八讲希尔排序希尔排序是由Donald提出来的.希尔排序基于插入排序，并且添加了一些新的特性，从而大大提离T插入排序的执行效率。插入排序的缺陷：多次移动。假如一个很小的数据在靠右端位置上，那么要将该数据排序到正确的位置上，即所有的中间数据都要向右移动一位。希尔排序的优点：希尔排序通过加大插入排序中元素元素之间的间隔，并对这些间隔的元素进行插人排序，从而使得数据可以大幅皮的移动。当完成该间隔的排序后，希尔排序会减少数据间的间隔再进行排序。依次进行下去。1 .基本思想希尔排序（最小增量排序）：算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减至W时，进行直接插入排序后，排序完成。间隔的计算：间隔h的初始值为1,通过h=3*h+1来循环计算，知道该间隔大于数组的大小时停止。最大间隔为不大于数组大小的最大值。间隔的减少：通过公式h=（h-1）/3来计算。2 .算法实现希尔排序的Java代码:)while(h0)后序遍历后序遍历：先后序遍历左子树，再后序遍历右子树，最后访问根节点。etName();etName();etName();etName();ntVaIue();)3 .压缩后仍可能出现的问题冲究，不能保证每个单词都映射到数纽的空白单元。解决办法:开放地址法链地址法第十六讲开放地址法1什么是开放地址法当冲突发生时，通过查找数组的一个空位，并将数据填入，而不再用哈希函数得到的数组下标，即开放地址法。2 .一3 .数据的插入数据插入的Java代码实现:etName()!=null)+code;if(arrcode.getldO=key)etName();etName();etId()二二key)Infotemp二arrcode;etName(null);etName();nsertFirst(info);HashTabletable=newHashTableO;(newlnfo(HaH,nzhangSanH);(newlnfo(RctM,HwangWu);1 .数据的查找数据杳找的Java代码实现:ind(key)info；a),getName();etName();elete(key)-info;Ha),getName();etName();图的基本概念1）什么是图图是一种和树相像的数据结构，通常有一个固定的形状，这是由物理或抽象的问题来决定的。2）邻接如果两个顶点被同一条边连接，就称这两个顶点是邻接的。3)路径路径是从一个顶点到另一个顶点经过的边的序列。4)连通图和非连通图至少有一条路径可以连接所有的顶点，那么这个图就是连通的，否则是非连通的。5)有向图弓豳无向图有向图的边是有方向的，如果只能从A到B,不能从B到A。无向图的边是没有方向的,可以从A到B,也可以从B到A。6)带权图有些图中，边被赋予了一个权值，权值是一个数字，可以代表如两个顶点的物理距离，或者是一个顶点到另一个顶点的口寸间等等。这样的图叫做带权图。2 .图的Java代码实现Vertex顶点类：publicclassVertexcharlabel；booleanwasVisited;publicVertex(charlabel)=label;wasVisited=false;)Graph图类：publicclassGraphprivateintmaxSize=20;privatoVertexvertexList;asVisited=true;asVisited二true;asVisited=false;IasVisited=faIse)returni;)return-1;asVisited=true;asVisited二true;asVisited=false;0;/A-BB-CC-D