Java学习----数据结构
今日学习内容总结如下：
程序=算法（解决问题的步骤）+数据结构（合理的持有数据）
如何衡量算法的优劣？
1、计算时间
long start=System.currentTimeInMills();
处理步骤；
long end=System.currentTimeInMills();
System.out.println("该算法用时"+(end-start)+"ms");
2、时间复杂度
是一个用于度量一个算法的运算时间的一个描述，本质是一个函数，根据这个函数能在不用具体的测试数据来测试的情况下，粗略地估计算法的执行效率
查找一个算法中执行次数最多的部分和算法规模的相互关系--函数
常用大O来表述，这个函数描述了算法执行所要时间的增长速度
- 常量阶 O(1)
- 对数阶 O(logn)
- 线性阶 O(n)
- 线性对数阶 O(nlogn)
- n方阶 O(nⁿ)
- 指数阶 O(2ⁿ)
- 阶乘阶 O(n!)
package com.list0;
import java.util.Arrays;
public class Test1 {
public static void main(String[] args) {
int[] arr = new int[] { 1, 6, 2, 4, 3, 7, 9, 8 };
for (int i = 1; i < arr.length; i++) { // 7
for (int k = 0; k < arr.length - i; k++) { // 7 6 5 ... (n-1)*n/2
if (arr[k] > arr[k + 1]) {
int tmp = arr[k];
arr[k] = arr[k + 1];
arr[k + 1] = tmp;
}
}
}
System.out.println(Arrays.toString(arr));
// 时间复杂度为 n^2/2-n/2 时间和问题规模n成正相关关系
// 使用大O计法时，只保留最高次幂，去掉所有常量O(n^2)
// 折半查找
int target = 6;
int min = 0;
int max = arr.length - 1;
int pos = (min + max) / 2;
while (min <= max) {
pos=(min + max) / 2;
if (arr[pos] > target) {
max = pos - 1;
} else if (arr[pos] < target) {
min = pos + 1;
} else if (arr[pos] == target)
break;
}
System.out.println("位置为:" + pos);
//2^k=n k以2为底n的对数 时间复杂度为O(logN)
}
}线性表
数组
package com.list1;
import java.util.Arrays;
/*
* 存储区间是连续的，占用内存严重，故空间复杂度很大。但数组的二分查找(前提是必须有序)
* 时间复杂度小，为O(logN)；
*
* 数组的特点是：
* - 寻址容易(arr[n]=arr[0]+n*每个元素的长度，时间复杂度为O(1))
* - 插入和删除困难(可能会引发一半以上的数据元素移动，时间复杂度为O(n))；
* - Java中的数组是定长的，如果需要变长则需要自行编程实现
*/
public class ArrayList {
private Object[] data; // 真正存储数据
private int size = 0; // 记录存储的数据个数
public ArrayList() {
// data=new Object[10];
this(10);
}
public ArrayList(int len) {
data = new Object[len];
}
public void add(Object obj) {
data[size++] = obj;
if (size >= data.length)
resize(); //扩容处理
}
public void insert(int pos,Object obj) {
if(pos<0 || pos>=size)
throw new ArrayIndexOutOfBoundsException();
System.arraycopy(data, pos, data, pos+1, size-pos);
data[pos]=obj;
size++;
if (size >= data.length)
resize(); //扩容处理
}
private void resize() {
System.out.println(size);
Object[] res=new Object[data.length*3/2];
System.arraycopy(data, 0, res, 0, size);
this.data=res;
}
public void delete(int position) {
if(position<0 || position>=size)
throw new ArrayIndexOutOfBoundsException();
System.arraycopy(data, position+1, data, position, size-position-1);
data[--size]=null;
}
public void update(int pos,Object obj) {
if(pos<0 || pos>=size)
throw new ArrayIndexOutOfBoundsException();
data[pos]=obj;
}
public static void main(String[] args) {
ArrayList list=new ArrayList(5);
list.add(0);
for(int i=1;i<10;i++)
// list.add(i);
list.insert(0, i);
System.out.println(Arrays.toString(list.data));
//容器为15，浪费了6个存储空间
// list.delete(3);
// System.out.println(Arrays.toString(list.data));
// list.update(0, 99);
// System.out.println(Arrays.toString(list.data));
}
}package com.list1;
/*
* 存储区间离散(数据不是连续存放的)，占用内存比较宽松，故空间复杂度很小，
* 但时间复杂度很大O（N）。
*
* 链表的特点是：
* - 寻址困难（可能需要通过遍历的方式查找元素，时间复杂度为O(n)）
* - 插入和删除容易(不需要引发元素的移动，仅仅只是进行地址的拷贝，时间复杂度为O(1))。
*/
public class LinkedList { //单向链表，实现不够完善，重点是原理
private Node header;// 头指针,指向链表中的第一个元素
public void add(Object data) {
if (header == null) {
header = new Node(data);
} else {
Node p = header;
for (; p.next != null; p = p.next)
;
p.next = new Node(data);
}
}
//增加和实际长度无关，但是为了查询到对应的位置，时间复杂度还是O(n)
public void insert(int pos,Object data) {
Node p=header;
for(int i=1;i<=pos;i++) {
p=p.next;
}
Node tmp=new Node(data);
tmp.next=p.next;
p.next=tmp;
}
//功能并不完善
//删除和实际长度无关，O(1)；但是实际上为了查询到对应的位置，时间复杂度还是O(n)
public void delete(int pos) {
Node p=header;
for(int i=1;i<pos;i++)
p=p.next;
p.next=p.next.next;
}
public void show() {
Node p = header;
for (; p != null; p = p.next)
System.out.print(p.data + "\t");
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.add(99);
for (int i = 0; i < 10; i++)
list.insert(0,i);
list.show();
list.delete(3);
System.out.println();
list.show();
}
class Node {
private Object data;// 存储的数据
private Node next;// 指向下一个Node对象的指针
public Node(Object data) {
this.data = data;
}
}
}集合
Java集合类存放于 java.util 包中，是一个用来存放对象的容器
集合只能存放对象。比如存一个int型数据1放入集合中，其实它是自动转换成Integer 类后存入的(装箱操作)，Java中每一种基本类型都有对应的引用类型
集合存放的是多个对象的引用，对象本身还是放在堆内存中
集合可以存放不同类型，不限数量的数据类型。定义集合变量时如果不指定数据类型，则默认数据类型为Object
数组和集合的比较
针对Java中的数组定长，Java提出了集合框架，实现了一种变长存储数据的容器---集合
数组不是面向对象的，存在明显的缺陷，集合弥补了数组的缺点，比数组更灵活更实用，而且不同的集合框架类可适用不同场合。如下：
- 数组能存放基本数据类型和对象，而集合类存放的都是对象的引用，而非对象本身
- 数组容量固定无法动态改变，集合类容量动态改变
- 数组无法判断其中实际存有多少元素，length只告诉了数组的容量，而集合的size()可以确切知道元素的个数
- 集合有多种实现方式和不同适用场合，不像数组仅采用顺序表方式
- 集合以类的形式存在，具有封装、继承、多态等类的特性，通过简单的方法和属性即可
- 实现各种复杂操作，大大提高了软件的开发效率
Iterator迭代器
Iterator迭代器：走访器，可以理解为集合中元素的指针
它是Java集合的顶层接口（不包括map系列的集合，Map接口是map系列集合的顶层接口）
public interface Iterator<E> {
boolean hasNext(); 判断是否有后续元素
E next(); 指针向后移动，同时返回指向的数据
default void remove() { 删除指针所指向的元素
throw new UnsupportedOperationException("remove");
}
使用lambda表达式的方式遍历所有元素
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}Iterable接口用以表示实现类是可以迭代的
Iterator<T> iterator();package com.list2;
import java.util.ArrayList;
import java.util.Iterator;
public class Test1 {
public static void main(String[] args) {
ArrayList al = new ArrayList();
for (int i = 0; i < 100; i++)
al.add(i);
// 迭代访问集合中的每个元素
Iterator it = al.iterator();
// while(it.hasNext()) {
// Object tmp=it.next();
// System.out.println(tmp);
// }
it.forEachRemaining(System.out::println);
al.forEach(System.out::println); //底层就是迭代访问
}
}
package com.list2;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Date;
import java.util.Iterator;
/*
* 顶级接口Collection
* 无序、允许重复
*
* public interface Collection<E> extends Iterable<E>一般说Collection是集合
* 框架的顶级接口，但是事实上并不是顶级接口
*
* 提供的方法:
* int size(); 获取集合中的元素个数 区分容积和元素个数
*
* boolean isEmpty()判断集合中的元素个数是否为0
* 注意：只判断是否没有元素，但是并不判断集合对象是否为null
* boolean contains(Object o)用于判断集合中是否包含对象
*
* boolean add(Object o)用于向集合中追加元素o，成功true失败false
*
* boolean remove(Object o)删除集合中的指定元素o，成功true失败false
*
* Iterator<E> iterator();获取迭代器，通过迭代器遍历集合中的每个元素
*
* Object[] toArray();将集合转换为数组
*
* void clear();删除集合中的所有元素
*/
public class Test2 {
public static void main(String[] args) {
Collection cc = new ArrayList();
cc.add(123);
cc.add("bbbb");
cc.add(new Date());
System.out.println(cc.size());
System.out.println(cc.isEmpty());
System.out.println(cc.contains("bbbb"));
System.out.println(cc.contains(new Date()));
System.out.println(cc.remove(123));
System.out.println(cc.size());
}
}