文档介绍：精品资料
Java数据结构和算法
第0讲综述
参考教材：Java数据结构和算法（第二版）， ［美］Robert lafore
.数据结构的特性
数据结构
优点
数组
插入快；如果知底下标，可以非常快地存取
查找慢，删除慢，大小固定
有序数组
比无序的数组查找快
删除和插入慢，大小固定
栈
提供后进先出方式的存取
存取其他项很慢
队列
提供先进先出方式的存取
存取其他项很慢
插入快，删除快
查找慢
二叉树
查找、插入、删除都快（如果树保持平衡）
删除算法复杂
红-黑树
查找、插入、删除都快；树总是平衡的
算法复杂
2-3-4 树
查找、插入、删除都快；树总是平衡的；类 似的树对磁盘存储有用
算法复杂
哈布表
如果关键字已知，则存储极快；插入快
删除慢，如果不知道关键字则存 储很慢，对存储空间使用不充分
堆
插入、删除快；对大数据项的存取很快
对其他数据项存取慢
对现实世界建模
有些算法慢且复杂
.经典算法总结
查找算法：线性查找和二分查找
排序算法：
用表展示
第一讲数组
. Java中数组的基础知识
1）创建数组
在Java中把数组当作对象来对待，因此在创建数组时必须使用 new操作符:
int 口 intArr = new int [10];
一旦创建数组，数组大小便不可改变。
2）访问数组数据项
数组数据项通过方括号中的下标来访问，其中第一个数据项的下标是 0:
精品资料
intArr[0] = 123;
3）数组的初始化
当创建数组之后，除非将特定的值赋给数组的数据项，否则它们一直是特殊的 null对
int 口 intArr = {1,2, 3, 4, 5};
等效于下面使用 new来创建数组并初始化:
int 口 intArr = new int [5];
intArr[0] = 1;
intArr[1] = 2;
intArr[2] = 3;
intArr[3] = 4;
intArr[4] = 5;
.面向对象编程方式
1)使用自定义的类封装数组
MyArray 类：
public class MyArray { private long 口 arr; private int size; //记录数组的有效长度
public MyArray() { arr = new long [10];
}
public MyArray( int maxSize) { arr = new long [maxSize];
}
//向数组中插入数据
public void insert( long element) { arr[size] = element;
size++;
}
//显示数组中的数据
public void show() {
for (int i=0; i<size; i++) { if (i==0) {
System. out .print("[" + arr[i] + ",");
} else if (i==size-1) {
System. out .println(arr[i] + "]");
} else {
System. out .print(arr[i] + ",");
}
}
}
//根据值查找索引(出现该值的第一个位置)：线性查找
public int queryByValue( long element) {
int i;
精品资料
for (i=0; i<size; i++) { // linear search if (arr[i] == element) break ;
}
if (i == size) { return -1;
} else { return i;
}
}
//根据索引查找值
public long queryByIndex( int index) {
if (index >= size || index < 0) {
throw new ArrayIndexOutOfBoundsException();
else { return arr[index];
}
}
//删除数据
public void delete( int index) {
if (index >= size || index < 0) {
throw new ArrayIndexOutOfBoundsException();
} else {
// 当size=maxSize ,删除最后一个数时，不会执行 for
for (int i=i