文档介绍：Java数据结构和算法
第0讲综述
参考教材：Java数据结构和算法（第二版），〔美〕Robert I afore
.数据结构的特性
数据结构
I
优点
缺点
数纽
插入快；如果知道下标，可以非常快地存取
查找慢,删除慢,大小固定
有序数组
比无序的数组查找快
IW除和插入慢，大小固定
栈
提供后进先出方式的存取
存取其他项很慢
队列
提供先进先出方式的存取
存取其他项很慢
链表
插入快，删除快
<
查找慢
二义树
查找、插入、删除都快（如果树保持平衡）
IW除算法复杂
红-黑树
查找、插入、删除都快；树总是平衡的
算法复杂
2-3-4 树
■
查找、插入、删除都快；树总是平衡的；类似的
树对磁盘存储有用
算法复杂
哈希表
如果笑键字已知，即存储极快：插入快
删除慢，如果不知道关键字则存 储 很慢，对存储空间使用不允分
堆
插入、删除快；对大数据项的存取很快
对其他数损项存取慢
图
对现实世界建模
有些算法慢且复杂
2,经典算法总结
查找算法：线性查找和二分查找排序算法: 用表展示
第一讲数组
1. Java中数组的基础知识
1）创建数组
在Java中把数组当作对象来对待，因此在创建数组时必须使用new B作符：int 口 mtArr = new int[10];
一旦创建数纽，数组大小便不可改变。
2）访问数组数据项
数组数据项通过方括号中的下标来访问，其中第一个数据项的下标是0： intArrfO] = 123;
3）数组的初始化
当创建数组之后，除非将特定的值赋给数组的数据项，否则它们一直是特殊的nul I对象。
int[] intArr = （1,2, 3, 4, 5};
等效于下面使用new来创建数组并初始彳匚int[] intArr = new int[5];
intArr[O] = 1;
intArr[1] = 2;
intArr[2] = 3;
intArr[3]二 4；
intArr[4] = 5;
.面向对象编程方式
1）使用自定义的类封装数组
MyArray 类：
出栈
{D,C,B,A}
队头
出队一do Q1血• •・
队尾
Q 〃 • 1 V—入队
isplayLink() ; isplayLink。;
子问题须与原始问题为同样的事，且更为他单：
，须有个出口 .化简为非递归状况处理。
1 .三角数字
该数列中的首项为1，第n项是由第nT项加n后得到的。
1）使用循环查找第n项
pub Iic static int totaI
int triangleByWhile(int n) {
=o；
wh i I e (n > 0)
totaI = totaI + n;
return totaI;
直接转换法 直才妾转换法通常用来消除尾遏归和单向遏归，将递归结构用循环结构来替代。尾递归是指在递归算 法中，递归调用语句只有一个，而且是处在算法的最后。例如求阶乘的递归算法：publ ic long fact(irTt n)
if (n==0) return 1; e I se ret urn n *f act (nT);
当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束 处，所以
，不必利用栈来保存返回信息。对于尾递归形式的递归算法，可以利用循环结构来替代。例如求阶乘的 递归算法
可以写成如下循环结构的非递归算法：
publ ic long fact(irvt n)
(
int s=0;
for (int i=1; i
s=s*i;间接转换法
该方法使用栈保存中间结果，一般需根抵递归函数在执行过程中栈的变化得到。其一般过程如 下：
将初始状态sO进栈
while (栈不为空)
退栈，将栈顶元素赋给s;
if (s是要找的结果)返回；
e I se { *
寻找到S的相关状态S1；
将S1进栈
）
）
间接转换法在数据结构中有较多实例，如二叉树遍历算法的非递归实现、图的深度优先遍历算法的 非递归实现等等，请读者参考主教材中相关内容
第八讲希尔排序
希尔