文档介绍：Java数据结构和算法
第0讲综述
参考教材:Java数据结构和算法(第二版),[美] Robert lafore
1. 数据结构的特性
数据结构
优点
缺点
数组
插入快;如果知道下标,可以非常快地存取
查找慢,删除慢,大小固定
有序数组
比无序的数组查找快
删除和插入慢,大小固定
栈
提供后进先出方式的存取
存取其他项很慢
队列
提供先进先出方式的存取
存取其他项很慢
链表
插入快,删除快
查找慢
二叉树
查找、插入、删除都快(如果树保持平衡)
删除算法复杂
红-黑树
查找、插入、删除都快;树总是平衡的
算法复杂
2-3-4树
查找、插入、删除都快;树总是平衡的;类似的树对磁盘存储有用
算法复杂
哈希表
如果关键字已知,则存储极快;插入快
删除慢,如果不知道关键字则存储很慢,对存储空间使用不充分
堆
插入、删除快;对大数据项的存取很快
对其他数据项存取慢
图
对现实世界建模
有些算法慢且复杂
2. 经典算法总结
查找算法:线性查找和二分查找
排序算法:
用表展示
第一讲数组
Java中数组的基础知识
创建数组
在Java中把数组当作对象来对待,因此在创建数组时必须使用new操作符:
int[] intArr = new int[10];
一旦创建数组,数组大小便不可改变。
访问数组数据项
数组数据项通过方括号中的下标来访问,其中第一个数据项的下标是0:
intArr[0] = 123;
数组的初始化
当创建数组之后,除非将特定的值赋给数组的数据项,否则它们一直是特殊的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;
面向对象编程方式
使用自定义的类封装数组
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) {
("[" + arr[i] + ", ");
} else if(i==size-1) {
(arr[i] + "]");
} else {
(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,删除最后一个数时,不