title: Day29-数据结构与算法-线性表 date: 2020-10-16 10:20:47 tags:
斐波那契数的线性代数解法 - 特征方程
public static int fibFunction(int n){ double c = Math.sqrt(5); return (int)((Math.pow((1 + c) / 2, n) - Math.pow((1-c) / 2, n)) / c); }复杂度分析
最好情况复杂度最坏情况复杂度平均情况复杂度评估算法的优劣：
正确性、可读性、健壮性（对不合理输入的反应能力） 时间复杂度：估算程序指令的执行次数（执行时间）空间复杂度：估算所需占用的存储空间**注意：**大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率
执行次数复杂度非正式术语12O(1)常数阶2n + 3O(n)线性阶4n² + 2n + 6O(n²)平方阶4log2 + 25O(logn)对数阶3n + 2nlog3n + 15O(nlogn)nlogn阶4n³ + 3n² + 22n + 100O(n³)立方阶2nO(2n)指数阶 O1 < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2n) < O(n!) < O(nn)算法的优化方向：
尽量少的存储空间尽量少的执行步骤（执行时间）根据情况，可以：空间换时间，时间换空间数据结构是计算机存储、组织数据的方式：
线性结构：数组、链表、栈、队列、哈希表(散列表)等树形结构：二叉树、AVL树、红黑树、B树、堆、Trie、哈夫曼树、并查集等图形结构：邻接矩阵、邻接表等根据实际应用场景选择最合适的数据结构
线性表是具有n个相同类型元素的有限序列(n >= 0)
数组是一种顺序存储的线性表，所有元素的内存地址是连续的，数组的致命缺陷，一旦确定无法扩容
**泛型：**使用泛型计数可以让动态数组更加通用，可以存放任何数据类型
数组动态扩容：手撸ArrayList，使用泛型存在内存管理问题
package com.zimo.线性表.数组; import java.util.Objects; /** * 线性表 - 动态数组 * 接口设计： * 1.元素的数量：int size(); * 2.是否为空：boolean isEmpty(); * 3.是否包含某个元素：boolean contains(E element); * 4.添加元素到最后面：void add(E element); * 5.返回index位置对应的元素：E get(int index); * 6.设置index位置的元素：E set(int index, E element); * 7.往index位置添加元素：void add(int index, E element); * 8.删除index位置对应的元素：E remove(int index); * 9.查看元素的位置：int indexOf(E element); * 10.清楚所有元素：void clear(); * 11.删除index对应的元素：E remove(E element); * * @author Liu_zimo * @version v0.1 by 2020-10-16 13:59:56 */ public class AutoArray <E> { public static void main(String[] args) { AutoArray<Integer> array = new AutoArray<>(); array.add(10); array.add(12); array.add(14); array.add(15); System.out.println(array.toString()); array.remove(2); System.out.println(array.toString()); } private int size = 0; // 元素的数量 private E[] elements; // 所有的元素 private static final int DEFAULT_CAPACITY = 10; private static final int ELEMENT_NOT_FOUND = -1; public AutoArray() { this(DEFAULT_CAPACITY); } public AutoArray(int capacity) { capacity = capacity < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capacity; this.elements = (E[]) new Object[capacity]; } /** * 清楚所有元素 */ public void clear(){ // 为了支持泛型，需要将数据清空begin for (int i = 0; i < elements.length; i++) { elements[i] = null; } // end size = 0; } /** * 元素的数量 * @return 【out】返回元素的数量 */ public int size(){ return size; } /** * 是否为空 * @return 【out】返回数组是否为空 */ public boolean isEmpty(){ return size == 0; } /** * 是否包含某个元素 * @param element 【in】要校验的元素 * @return 【out】校验结果 */ public boolean contains(E element){ return indexOf(element) != ELEMENT_NOT_FOUND; } /** * 添加元素到尾部 * @param element 【in】要添加的元素 */ public void add(E element){ add(size, element); } /** * 添加元素到index * @param index 【in】要插入的位置 * @param element 【in】要插入的元素 */ public void add(int index, E element){ //if (element == null) return; // 是否允许存空值（null） // 允许等于size rangeCheckForAdd(index); ensuerCapacity(size + 1); for (int i = size; i > index; i--) { elements[i] = elements[i - 1]; } elements[index] = element; size++; } /** * 获取index位置的元素 * @param index 【in】要获取元素的位置 * @return 【out】返回元素值，如果没有返回null */ public E get(int index){ rangeCheck(index); return elements[index]; } /** * 设置index位置的元素 * @param index 【in】要设置元素的位置 * @param element 【in】要设置的元素 * @return 【out】原来的元素 */ public E set(int index, E element){ rangeCheck(index); E old = elements[index]; elements[index] = element; return old; } /** * 删除index位置的元素 * @param index 【in】要删除元素的位置 * @return 【out】返回被删除的元素 */ public E remove(int index){ rangeCheck(index); E old = elements[index]; for (int i = index + 1; i < size; i++) { elements[i - 1] = elements[i]; } size--; // 为了支持泛型，需要将最后一个引用清空 elements[size] = null; return old; } public E remove(E element){ return remove(indexOf(element)); } /** * 查看元素的索引 * @param element 【in】要查找的元素 * @return 【out】元素所在位置 */ public int indexOf(E element){ // 如果允许null，那么要特殊处理 if (element == null){ for (int i = 0; i < elements.length; i++) { if (elements[i] == null) return i; } }else { for (int i = 0; i < elements.length; i++) { // if (element == elements[i]) return i; // 泛型的改进 if (element.equals(elements[i])) return i; } } return ELEMENT_NOT_FOUND; } /** * 要保证有capacity的容量 * @param capacity 【in】至少需要的容量 */ private void ensuerCapacity(int capacity) { int oldCapacity = elements.length; // 旧数组的长度 if (oldCapacity >= capacity) return; // 新容量为旧容量的1.5倍 int newCapacityLength = oldCapacity + (oldCapacity >> 1); // 等价于 oldCapacity * 1.5 E[] newElements = (E[]) new Object[newCapacityLength]; for (int i = 0; i < size; i++){ newElements[i] = elements[i]; } elements = newElements; } private void outOfBounds(int index){ throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size); } private void rangeCheck(int index){ if (index < 0 || index >= size){ outOfBounds(index); } } private void rangeCheckForAdd(int index){ if (index < 0 || index > size){ outOfBounds(index); } } @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); stringBuilder.append("size = ").append(size).append(", ["); for (int i = 0; i < size; i++) { if (i != 0) stringBuilder.append(", "); stringBuilder.append(elements[i]); // if (i != size - 1){ // stringBuilder.append(", "); // } } stringBuilder.append("]"); return stringBuilder.toString(); } }优化：增加一个头节点指针，使数组变成环形数组，增强性能，减少增删移动次数
对象数组
如果内存使用比较紧张，动态数组有比较多的剩余空间，可以考虑进行缩容操作 如果扩容倍数、缩容时机设计不得当，有可能会导致复杂度震荡（扩容倍数 x 缩容倍数 = 1）
public E remove(int index) { rangeCheck(index); E old = elements[index]; for (int i = index + 1; i < size; i++) { elements[i - 1] = elements[i]; } size--; // 为了支持泛型，需要将最后一个引用清空 elements[size] = null; trim(); // 增加缩容操作 return old; } /** * 缩容：剩余空间占总容量的一半时，就进行缩容 */ private void trim() { int capacity = elements.length; int newCapacity = capacity >> 1; if (size >= newCapacity || capacity <= DEFAULT_CAPACITY) { return; } // 缩容:剩余空间还很多 E[] newElements = (E[]) new Object[newCapacity]; for (int i = 0; i < size; i++) { newElements[i] = elements[i]; } elements = newElements; }链表的大部分接口和动态数组是一致，所以可以抽取公共方法：
package com.zimo.线性表; /** * 线性表 - 公共的方法抽取 * * @author Liu_zimo * @version v0.1 by 2020-10-19 16:30:00 */ public interface List<E> { /** * 清楚所有元素 */ void clear(); /** * 元素的数量 * @return 【out】返回元素的数量 */ int size(); /** * 是否为空 * @return 【out】返回数组是否为空 */ boolean isEmpty(); /** * 是否包含某个元素 * @param element 【in】要校验的元素 * @return 【out】校验结果 */ boolean contains(E element); /** * 添加元素到尾部 * @param element 【in】要添加的元素 */ void add(E element); /** * 添加元素到index * @param index 【in】要插入的位置 * @param element 【in】要插入的元素 */ void add(int index, E element); /** * 获取index位置的元素 * @param index 【in】要获取元素的位置 * @return 【out】返回元素值，如果没有返回null */ E get(int index); /** * 设置index位置的元素 * @param index 【in】要设置元素的位置 * @param element 【in】要设置的元素 * @return 【out】原来的元素 */ E set(int index, E element); /** * 删除index位置的元素 * @param index 【in】要删除元素的位置 * @return 【out】返回被删除的元素 */ E remove(int index); E remove(E element); /** * 查看元素的索引 * @param element 【in】要查找的元素 * @return 【out】元素所在位置 */ int indexOf(E element); } package com.zimo.线性表; /** * 线性表 - 抽象类 * * @author Liu_zimo * @version v0.1 by 2020-10-19 16:40:00 */ public abstract class AbstractList<E> implements List<E> { protected int size; // 元素的数量 public int size() { return size; } public boolean isEmpty() { return size == 0; } public boolean contains(E element) { return indexOf(element) != ELEMENT_NOT_FOUND; } public void add(E element) { add(size, element); } public E remove(E element){ return remove(indexOf(element)); } protected void outOfBounds(int index){ throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size); } protected void rangeCheck(int index){ if (index < 0 || index >= size){ outOfBounds(index); } } protected void rangeCheckForAdd(int index){ if (index < 0 || index > size){ outOfBounds(index); } } }练习：反转链表（递归、非递归）、链表是否有环（快慢指针：[slow：1，fast：2]）
动态数组：开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费(可以通过缩容解决) 双向链表：开辟、销毁内存空间的次数相对较多，但不会造成内存空间浪费
如果频繁在尾部进行添加、删除操作，动态数组、双向链表均可选择如果频繁在头部进行添加、删除操作，建议选择使用双向链表如果有频繁的（在任意位置）进行添加、删除操作，建议选择使用双向链表如果有频繁的查询操作（随机访问操作），建议选择使用动态数组有了双向链表，单向链表是否就没有任何用处了?
并非如此，在哈希表的设计中就用到了单链表
将循环链表发挥最大威力：增设一个成员变量，3个方法
current：用于指向某个节点void reset()：让current指向头节点firstE next()：让current往后走一步，也就是current = current.nextE remove()：删除current指向的节点，删除成功后让current指向下一个节点 package com.zimo.线性表.链表; import com.zimo.线性表.AbstractList; /** * 线性表 - 双向循环链表 * * @author Liu_zimo * @version v0.1 by 2020-10-20 16:15:00 */ public class DupLoopLinkList<E> extends AbstractList<E> { public static void main(String[] args) { // 练习：解决约瑟夫问题 DupLoopLinkList<Integer> list = new DupLoopLinkList<>(); for (int i = 1; i < 9; i++) { list.add(i); } // 指向头节点 list.reset(); while (!list.isEmpty()){ list.next(); list.next(); System.out.println(list.remove()); } } private Node<E> firstNode; // 头节点 private Node<E> lastNode; // 尾节点 private Node<E> current; // 用于指向某个节点 private static class Node<E> { E element; // 元素 Node<E> prev; // 前节点 Node<E> next; // 后节点 public Node(E element, Node<E> prev, Node<E> next) { this.element = element; this.prev = prev; this.next = next; } } @Override public void clear() { size = 0; firstNode = null; lastNode = null; } @Override public void add(int index, E element) { rangeCheckForAdd(index); if (index == size) { // 往最后添加 Node<E> oldLast = lastNode; lastNode = new Node<>(element, oldLast, firstNode); if (oldLast == null) { // 链表的第一个元素 firstNode = lastNode; firstNode.next = firstNode; firstNode.prev = firstNode; } else { oldLast.next = lastNode; firstNode.prev = lastNode; } } else { Node<E> next = node(index); Node<E> prev = next.prev; Node<E> newNode = new Node<>(element, prev, next); next.prev = newNode; prev.next = newNode; if (index == 0) { // 往0插入节点 next == firstNode条件也可以 firstNode = newNode; } } size++; } @Override public E get(int index) { return node(index).element; } @Override public E set(int index, E element) { Node<E> node = node(index); E old = node.element; node.element = element; return old; } @Override public E remove(int index) { rangeCheck(index); return remove(node(index)); } private E remove(Node<E> node) { if (size == 1){ firstNode = null; lastNode = null; }else { Node<E> prev = node.prev; Node<E> next = node.next; prev.next = next; next.prev = prev; if (node == firstNode) { // index == 0 或 node == firstNode firstNode = next; } if (node == lastNode) { // index == size - 1 lastNode = prev; } } size--; return node.element; } @Override public int indexOf(E element) { Node<E> node = this.firstNode; if (element == null) { for (int i = 0; i < size; i++) { if (node.element == null) return i; node = node.next; } } else { for (int i = 0; i < size; i++) { if (element.equals(node.element)) return i; node = node.next; } } return ELEMENT_NOT_FOUND; } /** * 让current指向头节点first */ public void reset(){ current = firstNode; } /** * 让current往后走一步，也就是current = current.next * @return 当前current所指向的元素 */ public E next() { if (current == null) return null; this.current = current.next; return current.element; } /** * 删除current指向的节点，删除成功后让current指向下一个节点 * @return 删除节点的元素 */ public E remove(){ if (current == null) return null; Node<E> next = current.next; E remove = remove(current); current = size == 0 ? null : next; return remove; } /** * 根据index脚标获取索引对象 * * @param index * @return Node */ private Node<E> node(int index) { rangeCheck(index); if (index < (size >> 1)) { // 如果index 小于容量的一半，从左查找 Node<E> node = this.firstNode; for (int i = 0; i < index; i++) { node = node.next; } return node; } else { // 如果index 大于容量的一半，从右查找 Node<E> node = this.lastNode; for (int i = size - 1; i > index; i--) { node = node.prev; } return node; } } @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); stringBuilder.append("size = ").append(size).append(", ["); Node<E> node = this.firstNode; for (int i = 0; i < size; i++) { if (i != 0) stringBuilder.append(", "); stringBuilder.append(node.element); node = node.next; } stringBuilder.append("]"); return stringBuilder.toString(); } }应用：浏览器的前进和后退、撤销和恢复(两个栈实现)，括号匹配
练习：用栈模拟队列（inStack，outStack）
可以进行两端添加、删除操作的循环队列
package com.zimo.线性表.队列.循环队列; import com.zimo.线性表.List; import com.zimo.线性表.链表.DupLoopLinkList; /** * 线性表 - 循环双端队列 * * @author Liu_zimo * @version v0.1 by 2020-10-21 11:55:29 */ public class CircleDeque<E> { public static void main(String[] args) { CircleDeque<Integer> deque = new CircleDeque<>(); for (int i = 0; i < 10; i++){ deque.enQueueFront(i + 1); deque.enQueueRear(i + 100); } System.out.println(deque); for (int i = 0; i < 3; i++){ deque.deQueueFront(); deque.deQueueRear( ); } deque.enQueueFront(11); deque.enQueueFront(12); System.out.println(deque); while (!deque.isEmpty()){ System.out.println(deque.deQueueFront()); } } private int size; // 元素大小 private E[] elements; // 元素 private int front; // 对头游标 private static final int DEFAULT_CAPACITY = 10; public CircleDeque() { elements = (E[]) new Object[DEFAULT_CAPACITY]; } public int size(){ return size; } public boolean isEmpty(){ return size == 0; } /** * 头/尾入队 * @param element */ public void enQueueFront(E element){ ensuerCapacity(size + 1); front = index(-1); elements[front] = element; size++; } public void enQueueRear(E element){ ensuerCapacity(size + 1); int index = index(size); elements[index] = element; size ++; } /** * 头/尾出队 * @return */ public E deQueueFront(){ E frontElement = elements[front]; elements[front] = null; front = index(1); size--; return frontElement; } public E deQueueRear(){ int rearIndex = index(size - 1); E rear = elements[rearIndex]; elements[rearIndex] = null; size--; return rear; } /** * 获取头/尾元素 * @return */ public E front(){ return elements[front]; } public E rear(){ return elements[index(size - 1)]; } /** * 清空队列 */ public void clear(){ for (int i = 0; i < size; i++) { elements[index(i)] = null; } size = 0; front = 0; } // 环形脚标映射 private int index(int index){ index += front; if (index < 0){ return index + elements.length; } // 优化前 return index % elements.length; // 优化 return index - (index >= elements.length ? elements.length : 0); } // 动态扩容 private void ensuerCapacity(int capacity) { int oldCapacity = elements.length; // 旧数组的长度 if (oldCapacity >= capacity) return; // 新容量为旧容量的1.5倍 int newCapacityLength = oldCapacity + (oldCapacity >> 1); // 等价于 oldCapacity * 1.5 E[] newElements = (E[]) new Object[newCapacityLength]; for (int i = 0; i < size; i++){ newElements[i] = elements[index(i)]; } elements = newElements; // 重置front front = 0; } @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); stringBuilder.append("capacity = ").append(elements.length).append(", front = ").append(front) .append(", size = ").append(size).append(", array:["); for (int i = 0; i < elements.length; i++) { if (i != 0) stringBuilder.append(", "); stringBuilder.append(elements[i]); } stringBuilder.append("]"); return stringBuilder.toString(); } } 已知 n >= 0, m > 0 n % m 等价于 n - (m > n ? 0 : m)的前提条件：n < 2m