Java数据结构和算法笔记.docx
《Java数据结构和算法笔记.docx》由会员分享，可在线阅读，更多相关《Java数据结构和算法笔记.docx（15页珍藏版）》请在冰点文库上搜索。
Java数据结构和算法笔记
Java数据结构和算法
第0讲综述
参考教材：
Java数据结构和算法（第二版），[美]Robertlafore
1.数据结构的特性
数据结构
<
优点
缺点
数组
插入快；如果知道下标，可以非常快地存取
查找慢，删除慢，大小固定
有序数组
比无序的数组查找快
删除和插入慢，大小固定
<
栈
提供后进先出方式的存取
存取其他项很慢
队列
提供先进先出方式的存取
存取其他项很慢
链表
插入快，删除快
—
查找慢
二叉树
查找、插入、删除都快（如果树保持平衡）
删除算法复杂
红-黑树
查找、插入、删除都快；树总是平衡的
算法复杂
2-3-4树
`
查找、插入、删除都快；树总是平衡的；类似的树对磁盘存储有用
算法复杂
哈希表
如果关键字已知，则存储极快；插入快
删除慢，如果不知道关键字则存储很慢，对存储空间使用不充分
堆
插入、删除快；对大数据项的存取很快
对其他数据项存取慢
》
图
对现实世界建模
有些算法慢且复杂
2.经典算法总结
查找算法：
线性查找和二分查找
排序算法：
用表展示
！
第一讲数组
1.Java中数组的基础知识
1）创建数组
在Java中把数组当作对象来对待，因此在创建数组时必须使用new操作符：
int[]intArr=newint[10];
<
一旦创建数组，数组大小便不可改变。
2）访问数组数据项
数组数据项通过方括号中的下标来访问，其中第一个数据项的下标是0：
intArr[0]=123;
3）数组的初始化
当创建数组之后，除非将特定的值赋给数组的数据项，否则它们一直是特殊的null对象。
—
int[]intArr={1,2,3,4,5};
等效于下面使用new来创建数组并初始化：
int[]intArr=newint[5];
intArr[0]=1;
intArr[1]=2;
intArr[2]=3;
intArr[3]=4;
intArr[4]=5;
|
2.面向对象编程方式
1）使用自定义的类封装数组
MyArray类：
publicclassMyArray{
privatelong[]arr;
privateintsize;
|
！
|
#
!
isplayLink（）;isplayLink（）;
，
=;
:
子问题须与原始问题为同样的事，且更为简单；
b.不能无限制地调用本身，须有个出口，化简为非递归状况处理。
1.三角数字
该数列中的首项为1，第n项是由第n-1项加n后得到的。
1）使用循环查找第n项
.
publicstaticinttriangleByWhile（intn）{
inttotal=0;
while（n>0）{
total=total+n;
n--;
}
returntotal;
}
&
，
直接转换法
直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。
尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。
例如求阶乘的递归算法：
publiclongfact（intn）
{
if（n==0）return1;
elsereturnn*fact（n-1）;
—
}
当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以
，不必利用栈来保存返回信息。
对于尾递归形式的递归算法，可以利用循环结构来替代。
例如求阶乘的递归算法
可以写成如下循环结构的非递归算法：
publiclongfact（intn）
{
ints=0;
for（inti=1;i
！
s=s*i;间接转换法
该方法使用栈保存中间结果，一般需根据递归函数在执行过程中栈的变化得到。
其一般过程如下：
将初始状态s0进栈
while（栈不为空）
{
退栈，将栈顶元素赋给s;
if（s是要找的结果）返回;
else{
?
寻找到s的相关状态s1;
将s1进栈
}
}
间接转换法在数据结构中有较多实例，如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现等等，请读者参考主教材中相关内容
%
第八讲希尔排序
希尔排序是由Donald提出来的，希尔排序基于插入排序，并且添加了一些新的特性，从而大大提高了插入排序的执行效率。
插入排序的缺陷：
多次移动。
假如一个很小的数据在靠右端位置上，那么要将该数据排序到正确的位置上，则所有的中间数据都要向右移动一位。
希尔排序的优点：
希尔排序通过加大插入排序中元素元素之间的间隔，并对这些间隔的元素进行插入排序，从而使得数据可以大幅度的移动。
当完成该间隔的排序后，希尔排序会减少数据间的间隔再进行排序。
依次进行下去。
1.基本思想
希尔排序（最小增量排序）：
算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。
当增量减到1时，进行直接插入排序后，排序完成。
[
间隔的计算：
间隔h的初始值为1，通过h=3*h+1来循环计算，知道该间隔大于数组的大小时停止。
最大间隔为不大于数组大小的最大值。
间隔的减少：
通过公式h=（h-1）/3来计算。
2.算法实现
希尔排序的Java代码：
.}
、
while（h>0）{
《
~
<
后序遍历
后序遍历：
先后序遍历左子树，再后序遍历右子树，最后访问根节点。
后序遍历的Java代码实现：
publicvoidafterOrder（Nodenode）{
if（node!
=null）{
afterOrder;
】
afterOrder;
}
}
;
&
etName（））;etName（））;
etName（））;etName（））;
$
ntValue（）;
}
3.压缩后仍可能出现的问题
冲突，不能保证每个单词都映射到数组的空白单元。
解决办法：
?
①开放地址法
②链地址法
第十六讲开放地址法
1.什么是开放地址法
当冲突发生时，通过查找数组的一个空位，并将数据填入，而不再用哈希函数得到的数组下标，即开放地址法。
2.|
3.数据的插入
数据插入的Java代码实现：
etName（）!
=null）{
++code;
if（arr[code].getId（）==key）{
etName（））;etName（））;
：
etId（）==key）{
Infotemp=arr[code];etName（null）;
etName（））;
）
nsertFirst（info）;
}
HashTabletable=newHashTable（）;
（newInfo（"a","zhangSan"））;
（newInfo（"ct","wangWu"））;
1.数据的查找
、
数据查找的Java代码实现：
ind（key）.info;
}
"a"）.getName（））;etName（））;
elete（key）.info;
}
"a"）.getName（））;etName（））;
?
图的基本概念
1）什么是图
图是一种和树相像的数据结构，通常有一个固定的形状，这是由物理或抽象的问题来决定的。
2）邻接
如果两个顶点被同一条边连接，就称这两个顶点是邻接的。
3）路径
…
路径是从一个顶点到另一个顶点经过的边的序列。
4）连通图和非连通图
至少有一条路径可以连接所有的顶点，那么这个图就是连通的，否则是非连通的。
5）有向图和无向图
有向图的边是有方向的，如果只能从A到B，不能从B到A。
无向图的边是没有方向的，可以从A到B，也可以从B到A。
]
6）带权图
有些图中，边被赋予了一个权值，权值是一个数字，可以代表如两个顶点的物理距离，或者是一个顶点到另一个顶点的时间等等。
这样的图叫做带权图。
2.图的Java代码实现
Vertex顶点类：
publicclassVertex{
charlabel;
booleanwasVisited;
publicVertex（charlabel）{
=label;
wasVisited=false;
}
}
Graph图类：
publicclassGraph{
privateintmaxSize=20;
privateVertex[]vertexList;
asVisited=true;asVisited=true;asVisited=false;
}
}
asVisited==false）{
returni;
}
}
return-1;
}
（）;
asVisited=true;asVisited=true;asVisited=false;
}
}
（）;//A-BB-CC-D
升级会员 