没有合适的资源?快使用搜索试试~ 我知道了~
Java数据结构和算法笔记.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 124 浏览量
2022-07-11
08:07:13
上传
评论
收藏 366KB DOC 举报
温馨提示
试读
49页
Java数据结构和算法 第0讲 综述 参考教材:Java数据结构和算法(第二版),[美] Robert lafore 1. 数据结构的特性 "数据结构"优点 "缺点 " "数组 "插入快;如果知道下标,可以非常快"查找慢,删除慢,大小固定" " "地存取 " " "有序数组"比无序的数组查找快 "删除和插入慢,大小固定 " "栈 "提供后进先出方式的存取 "存取其他项很慢 " "队列 "提供先进先出方式的存取 "存取其他项很慢 " "链表 "插入快,删除快 "查找慢 " "二叉树 "查找、插入、删除都快(如果树保持"删除算法复杂 " " "平衡) " " "红-黑树 "查找、插入、删除都快;树总是平衡"算法复杂 " " "的 " " "2-3-4树 "查找、插入、删除都快;树总是平衡"算法复杂 " " "的;类似的树对磁盘存储有用 " " "哈希表 "如果关键字已知,则存储极快;插入"删除慢,如果不知道关键字" " "快 "则存储很慢,对存储空间使" " " "用不充分 " "堆 "插入、删除快;对大数据项的存取很"对其他数据项存取慢 " " "快 " " "图 "对现实世界建模 "有
资源推荐
资源详情
资源评论
Java 数据结构和算法笔记
Java 数据结构和算法
第 0 讲 综述
参考教材:Java 数据结构和算法(第二版),[美] Robert lafore
1. 数据结构的特性
数据结构
优点
缺点
数组
插入快;如果知道下标,可以非常快地存取
查找慢,删除慢,大小固定
有序数组
比无序的数组查找快
删除和插入慢,大小固定
栈
提供后进先出方式的存取
存取其他项很慢
队列
提供先进先出方式的存取
存取其他项很慢
链表
插入快,删除快
查找慢
二叉树
查找、插入、删除都快(如果树保持平衡)
删除算法复杂
红-黑树
查找、插入、删除都快;树总是平衡的
算法复杂
2-3-4 树
查找、插入、删除都快;树总是平衡的;类
似的树对磁盘存储有用
算法复杂
哈希表
如果关键字已知,则存储极快;插入快
删除慢,如果不知道关键字则存
储很慢,对存储空间使用不充分
堆
插入、删除快;对大数据项的存取很快
对其他数据项存取慢
图
对现实世界建模
有些算法慢且复杂
2. 经典算法总结
查找算法:线性查找和二分查找
排序算法:
用表展示
第一讲 数组
1. Java 中数组的基础知识
1)创建数组
在 Java 中把数组当作对象来对待,因此在创建数组时必须使用 new 操作符:
int[] intArr = new int[10];
一旦创建数组,数组大小便不可改变。
2)访问数组数据项
数组数据项通过方括号中的下标来访问,其中第一个数据项的下标是 0:
Java 数据结构和算法笔记
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;
2. 面向对象编程方式
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] + ", ");
Java 数据结构和算法笔记
}
}
}
//根据值查找索引(出现该值的第一个位置):线性查找
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=index; i<size-1; i++) {
arr[index] = arr[index + 1];
System.out.println("for");
}
size--;
}
}
//更新数据
public void update(int index, long value) {
if(index >= size || index < 0) {
throw new ArrayIndexOutOfBoundsException();
Java 数据结构和算法笔记
} else {
arr[index] = value;
}
}
}
2)添加类方法实现数据操作
测试 MyArray 类方法:
public void testMyArray() throws Exception {
MyArray myArray = new MyArray();
myArray.insert(123);
myArray.insert(456);
myArray.insert(789);
myArray.show(); //[123, 456, 789]
System.out.println(myArray.queryByValue(111)); //-1
System.out.println(myArray.queryByIndex(2)); //789
myArray.delete(2);
myArray.show(); //[123, 456]
myArray.update(0, 0);
myArray.show(); //[0, 456]
}
3. 有序数组
1)有序数组简介以及其优点
有序数组是一种数组元素按一定的顺序排列的数组,从而方便使用二分查找来查找数组
中特定的元素。有序数组提高了查询的效率,但并没有提高删除和插入元素的效率。
2)构建有序数组
将 2.1 中自定义的类封装数组 MyArray 的 insert 方法改为如下:
//向有序数组中插入数据,按大小从前往后排列
public void insert(long element) {
int i;
for(i=0; i<size; i++) { // find where it goes
if(element<arr[i]) break;
}
for(int j=size; j>i; j--) { // move bigger ones up
arr[j] = arr[j-1];
}
arr[i] = element;
size++;
}
得到有序数组的类封装 MyOrderedArray 类,测试该类中的 insert 方法:
Java 数据结构和算法笔记
public void testMyOrderedArray() throws Exception {
MyOrderedArray myOrderedArray = new MyOrderedArray();
myOrderedArray.insert(999);
myOrderedArray.insert(555);
myOrderedArray.insert(777);
myOrderedArray.show(); //[555, 777, 999]
}
4. 查找算法
1)线性查找
在查找过程中,将要查找的数一个一个地与数组中的数据项比较,直到找到要找的数。
在 2.1 中自定义的类封装数组 MyArray 的 queryByValue 方法,使用的就是线性查找。
2)二分查找
二分查找(又称折半查找),即不断将有序数组进行对半分割,每次拿中间位置的数和
要查找的数进行比较:如果要查找的数<中间数,则表明要查的数在数组的前半段;如果要
查的数>中间数,则表明该数在数组的后半段;如果要查的数=中间数,则返回中间数。
在有序数组的类封装类 MyOrderedArray 中添加 binarySearch 方法
//根据值二分查找索引(前提:有序)
public int binarySearch(long value) {
int middle = 0;
int left = 0;
int right = size - 1;
while(true) {
middle = (left + right) / 2;
if(arr[middle] == value) {
return middle; // found it
} else if(left > right) {
return -1; // can't found it
} else { // divide range
if(arr[middle] > value) {
right = middle - 1; //in lower half
} else {
left = middle + 1; // in upper half
}
}
}
}
测试该二分查找方法:
剩余48页未读,继续阅读
资源评论
是空空呀
- 粉丝: 167
- 资源: 3万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功