[数据结构与算法]数据结构学习笔记

1. 基本概念

数据结构指相互之间存在一种或多种特定关系的数据元素的集合，包括逻辑结构、存储结构和对数据的运算
数据的逻辑结构是对数据之间关系的描述，它与数据的存储结构无关，同一种逻辑结构可以有多种存储结构，主要有线性结构和非线性结构
线性结构的特点是数据元素之间存在一对一的线性关系
线性结构有两种不同的存储结构，即顺序存储结构(数组)和链式存储结构(链表)，顺序表中存储的元素是连续的，链表中存储的元素不一定是连续的
常见的线性结构有数组、队列、链表和栈
常见的非线性结构有二维数组、多维数组、广义表、树和图

2. 数组

数组是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素
特点：下标从0开始，内存中顺序存储

2.1. 数组的基本操作

数据结构的操作通常有增、删、改、查

2.1.1. 读取元素

由于数组在内存中顺序存储，所以只需给出一个数组下标，就可以读取到对应的数组元素。像这种根据下标读取元素的方式叫作随机读取，下标必须在数组的长度范围内，否则会出现数组越界

int[] array = new int[]{3,4,7,1,8};
System.out.println(array[3]);

2.1.2. 更新元素

直接利用数组下标，就可以把新值赋给该元素

int[] array = new int[]{3,4,7,1,8};
array[3] = 12;
System.out.println(array[3]);

数组读取元素和更新元素时间复杂度为O(1)

2.1.3. 插入元素

数组的实际元素数量有可能小于数组的长度，插入元素时，有三种情况，分别是尾部插入、中间插入和超范围插入
尾部插入，直接把插入的元素放在数组尾部的空闲位置，等同于更新元素操作
中间插入，先把插入位置及后面元素向后移动，再把要插入的元素放到对应的数组位置
超范围插入，创建一个新数组，长度是原来的2倍，再把旧数组中的元素复制过去

2.1.4. 删除元素

删除元素位于数组中间，其后的元素都需要向前挪动1位
插入元素和删除元素时间复杂度都是O(n)

2.2. 数组的优缺点

优点：高效的随机访问能力
缺点：插入、删除元素会导致大量元素被迫移动，影响效率
数组适合多读少写的场景

3. 链表

链表(linked list)是一种在物理上非连续、非顺序的数据结构，由多个节点(node)组成。单向链表每个节点包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next
链表的第一个节点称为头节点，最后一个节点称为尾节点，尾节点的next指针指向空

双向链表：每一个节点拥有data和next指针，还拥有指向前置节点的prev指针

链表的每个节点分布在内存的不同位置，依靠next指针关联起来，这样可以灵活有效利用零散的碎片空间

3.1. 链表的基本操作

3.1.1. 查找节点

从头节点开始向后一个个节点逐一查找，最差的时间复杂度是O(n)

3.1.2. 更新节点

如果不考虑查找节点的过程，直接把旧数据替换成新数据即可

3.1.3. 插入节点

包括尾部插入、头部插入和中间插入
尾部插入只需把最后一个节点的next指针指向新插入的节点即可
头部插入需要两步

• 把新节点的next指针指向原先的头节点
• 把新节点变为链表的头节点

中间插入需要两步

• 新节点的next指针，指向插入位置的节点
• 插入位置前置节点的next指针，指向新节点

注意：只要内存空间允许，不需要像数组考虑扩容

3.1.4. 删除节点

链表删除包括尾部删除、头部删除和中间删除
尾部删除：把倒数第二个节点的next指针指向空
头部删除：把链表的头节点设为原先头节点的next指针
中间删除：把要删除节点的前置节点的next指针，指向要删除元素的下一个节点
完整代码实现如下：

public class MyLinkedList {

    //头节点指针
    private Node head;
    //尾节点指针
    private Node last;
    //链表实际长度
    private int size;

    /**
     * 链表插入元素
     * @param data 插入元素
     * @param index 插入位置
     * @throws Exception
     */
    public void insert(int data, int index) throws Exception {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围!");
        }
        Node insertedNode = new Node(data);
        if (size == 0) {
            head = insertedNode;
            last = insertedNode;
        } else if (index == 0) {
            //插入头部
            insertedNode.next = head;
            head = insertedNode;
        } else if (size == index) {
            //插入尾部
            last.next = insertedNode;
            last = insertedNode;
        } else {
            //插入中间
            Node prevNode = get(index - 1);
            insertedNode.next = prevNode.next;
            prevNode.next = insertedNode;
        }
        size++;
    }

    /**
     * 链表删除元素
     * @param index 删除的位置
     * @return
     * @throws Exception
     */
    public Node remove(int index) throws Exception {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表节点范围!");
        }
        Node removedNode = null;
        if (index == 0) {
            //删除头节点
            removedNode = head;
            head = head.next;
        } else if (index == size - 1) {
            //删除尾节点
            Node prevNode = get(index - 1);
            removedNode = prevNode.next;
            prevNode.next = null;
            last = prevNode;
        } else {
            //删除中间节点
            Node prevNode = get(index - 1);
            Node nextNode = prevNode.next.next;
            removedNode = prevNode.next;
            prevNode.next = nextNode;
        }
        size--;
        return removedNode;
    }

    /**
     * 链表查找元素
     * @param index 查找位置
     * @return
     * @throws Exception
     */
    private Node get(int index) throws Exception {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表节点范围!");
        }
        Node tmp = head;
        for (int i = 0; i < index; i++) {
            tmp = tmp.next;
        }
        return tmp;
    }

    /**
     * 输出链表
     */
    public void output() {
        Node tmp = head;
        while (tmp != null) {
            System.out.println(tmp.data);
            tmp = tmp.next;
        }
    }

    /**
     * 链表节点
     */
    private static class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) throws Exception {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.insert(3, 0);
        myLinkedList.insert(7, 1);
        myLinkedList.remove(0);
        myLinkedList.output();;
    }
}

3.2. 数组与链表比较

数组适用于多读少写，链表适用于插入和删除

4. 栈和队列

4.1. 栈

一种线性数据结构，栈中的元素只能先进后出(First In Last Out，FILO)，最早进入的元素存放的位置叫栈底，最后进入的元素存放位置叫栈顶，既可以用数组实现，也可以用链表实现

4.1.1. 栈的基本操作

入栈(push)
将新元素添加进栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶
出栈(pop)
将栈中的元素弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新栈顶

4.2. 队列

一种线性数据结构，队列中元素只能先进先出(First In First Out，FIFO)，队列的出口端叫队头(front)，队列的入口端叫队尾(rear)

4.1.1. 队列的基本操作

入队(enqueue)
将新元素放入队列，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾
出队(dequeue)
将元素移除队列，只允许在队头移除元素，出队元素的后一个元素将会成为新的队头

5. 散列表

散列表又叫哈希表(hash table)，提供键(key)和值(value)的映射关系，根据key就可以高效查找所匹配的value，时间复杂度接近于O(1)，通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫散列函数，存放记录的数组叫散列表
在Java中每个对象都有属于自己的hashcode，这个hashcode是区分不同对象的重要标识，hashcode转化成数组的下标是按照数组长度进行取模运算index = HashCode(Key)%Array.length

5.1. 散列表读写操作

写操作(put)
写操作就是在散列表中插入新的键值对
步骤如下：

• 通过哈希函数将key转化成数组下标
• 如果数组下标对应的位置没有元素，就把这个Entry填充到数组下标的位置

由于数组长度有限，当插入的Entry越来越多，不同的key通过哈希函数获得的下标有可能相同，这种情况叫哈希冲突，解决办法有两种，一是开放寻址法，二是链表法
开放寻址法的原理是当一个key通过哈希函数获得对应的数组下标已被占用时，可以寻找下一个空挡位置，如Java中的ThreadLocal就是使用此方法
Java中的HashMap使用了链表法解决哈希冲突，HashMap数组的每个元素既是一个Entry对象，又是一个链表的头节点，每个Entry对象通过next指针指向它的下一个Entry节点，当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中
读操作(get)
具体步骤如下：

• 通过哈希函数将key转化为数组下标
• 找到数组下标所对应的元素，如果该元素的key是需要的数，就找到了，如果这个key不是需要的数，就顺着链表往下找，找到符合条件的节点

扩容(resize)
当散列表达到一定饱和度时，key映射位置发生冲突的概率会逐渐提高，大量元素在相同的数组下标位置，形成很长的链表，对后续插入操作和查询操作的性能都有很大的影响，此时散列表就需要扩展其长度
HashMap中影响其扩容的因素有两个

• Capacity：HashMap当前长度
• LoadFactor：HashMap加载因子，默认为0.75f

扩容的条件是HashMap.size >= Capacity * LoadFacotr

扩容步骤如下：

1. 创建一个新的Entry空数组，长度是原数组的2倍
2. 重新Hash，遍历原Entry数组，把所有的Entry重新Hash到新数组中

JDK8开始，当多个Entry被Hash到同一个数组下标位置时，为了提升插入和查找的效率，HashMap会把Entry的链表转化为红黑树

6. 树

树是n(n>=0)个节点的有限集，当n=0时，称为空树
非空树有如下两个特点：

• 有且仅有一个特定的根节点
• 当n>1时，其余节点可分为m(m>0)个互不相交的有限集，每个集合又是一个树，称为根的子树，树的最大层级数，称为数的高度或深度

6.1. 二叉树

二叉树(binary tree)：每个节点最多有两个孩子节点，可以只有一个，或者没有孩子节点

二叉树节点有两个孩子节点，一个称为左孩子(left child)，一个称为右孩子(right child)，两个子节点顺序是固定的
二叉树有两种特殊形式，一是满二叉树，二是完全二叉树
满二叉树：所有非叶子节点都存在左右孩子，且所有叶子节点都在同一层级上

完全二叉树：对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树

满二叉树要求所有分支都是满的，完全二叉树只需保证最后一个节点之前的节点都齐全即可
二叉树既可以用链表实现，也可以用数组实现
链表实现二叉树时，每个节点包含三部分，存储数据的data变量、指向左孩子的left指针和指向右孩子的right指针
数组实现二叉树时，按照层级顺序把二叉树的节点放到数组中对应的位置，如果某个节点的左孩子或右孩子空缺，则数组相应位置也空出来。假设父节点下标为n，左孩子下标为2n + 1，右孩子下标为2n + 2，假设左孩子下标是m，其父节点下标是(m - 1)/2，通常情况二叉堆使用数组实现

6.2. 二叉树的应用

主要应用包括进行查找操作和维持相对顺序
二叉查找树

• 如果左子树不为空，则左子树上所有节点的值均小于根节点的值
• 如果右子树不为空，则右子树上所有节点的值均大于根节点的值
• 左、右子树也都是二叉查找树

对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是n，那么搜索节点的时间复杂度就是O（logn），和树的深度是一样的
二叉查找树要求左子树小于父节点，右子树大于父节点，正是这样保证了二叉树的有序性，二叉查找树又称为二叉排序树(binary sort tree)

6.3. 二叉树的遍历

从节点之间位置关系划分
前序遍历、中序遍历、后序遍历、层序遍历
从宏观角度划分
深度优先遍历(前序遍历、中序遍历、后序遍历)
广度优先遍历(程序遍历)

6.3.1. 前序遍历

输出顺序是根节点、左子树、右子树

6.3.2. 中序遍历

输出顺序是左子树、根节点、右子树

6.3.3. 后序遍历

输出顺序是左子树、右子树、根节点

6.3.4. 代码实现

public class BinaryTree {

    /**
     * 构建二叉树
     * @param inputList
     * @return
     */
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
        TreeNode node = null;
        if (inputList == null || inputList.isEmpty()) {
            return null;
        }
        Integer data = inputList.removeFirst();
        if (data != null) {
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }
        return node;
    }

    /**
     * 二叉树前序遍历
     * @param node
     */
    public static void preOrderTraveral(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.println(node.data);
        preOrderTraveral(node.leftChild);
        preOrderTraveral(node.rightChild);
    }

    /**
     * 二叉树中序遍历
     * @param node
     */
    public static void inOrderTraveral(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrderTraveral(node.leftChild);
        System.out.println(node.data);
        inOrderTraveral(node.rightChild);
    }

    /**
     * 二叉树后序遍历
     * @param node
     */
    public static void postOrderTraveral(TreeNode node) {
        if (node == null) {
            return;
        }
        postOrderTraveral(node.leftChild);
        postOrderTraveral(node.rightChild);
        System.out.println(node.data);
    }

    /**
     * 二叉树节点
     */
    private static class TreeNode {
        int data;
        TreeNode leftChild;
        TreeNode rightChild;

        TreeNode(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        LinkedList<Integer> inputList = new LinkedList<>(Arrays.asList(new Integer[] {3, 2, 9, null, null, 10, null, null, 8, null, 4}));
        TreeNode treeNode = createBinaryTree(inputList);
        System.out.println("前序遍历：");
        preOrderTraveral(treeNode);
        System.out.println("中序遍历");
        inOrderTraveral(treeNode);
        System.out.println("后序遍历");
        postOrderTraveral(treeNode);
    }
}

6.3.5. 层序遍历

按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点

代码实现如下：

public static void preOrderTraveralWithStack(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode treeNode = root;
    while (treeNode != null || !stack.isEmpty()) {
        //迭代访问节点左孩子，并入栈
        while (treeNode != null) {
            System.out.println(treeNode.data);
            stack.push(treeNode);
            treeNode = treeNode.leftChild;
        }
        //如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
        if (!stack.isEmpty()) {
            treeNode = stack.pop();
            treeNode = treeNode.rightChild;
        }
    }
}

6.4. 二叉堆

本质是一种完全二叉树，分为最大堆和最小堆
最大堆：任意父节点的值，都大于或等于其左、右孩子节点的值，堆顶是最大元素

最小堆：任何一个父节点的值，都小于或等于其左、右孩子节点的值，堆顶是最小元素

6.4.1 二叉堆的操作

插入节点
当二叉堆插入节点时，插入位置是完全二叉树的最后一个位置，新节点与其父节点相比较，如果比其大(小)，就让新节点上浮，和父节点交换位置，依次比较、上浮，直到找到合适的位置
删除节点
删除的是处于堆顶的节点，将堆的最后一个节点临时补到原本堆顶的位置，暂处堆顶位置的节点与其左、右孩子进行比较，如果左、右孩子节点中最小的一个比父节点小，那么父节点下沉
构建二叉堆
让所有非叶子节点依次下沉，先从最后一个非叶子节点开始，与其左、右孩子节点中最小的一个比较，若比它大就下沉，依次再比较其他非叶子节点
二叉堆插入和删除操作时间复杂度为O(logn)，构建操作时间复杂度是O(n)

6.4.2. 代码实现

二叉堆的节点存储在数组中

public class BinaryHeap {

    /**
     * 上浮
     * @param array
     */
    public static void upAdjust(int[] array) {
        int childIndex = array.length - 1;
        int parentIndex = (childIndex - 1) / 2;
        int tmp = array[childIndex];
        while (childIndex > 0 && tmp < array[parentIndex]) {
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (parentIndex - 1) / 2;
        }
        array[childIndex] = tmp;
    }

    /**
     * 下沉
     * @param array 待调整的堆
     * @param parentIndex 需要下沉的父节点
     * @param length 堆有效大小
     */
    public static void downAdjust(int[] array, int parentIndex, int length) {
        int tmp = array[parentIndex];
        int childIndex = 2 * parentIndex + 1;
        while (childIndex < length) {
            if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
                childIndex++;
            }
            //如果父节点小于任何一个子节点，直接跳出
            if (tmp <= array[childIndex]) {
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        array[parentIndex] = tmp;
    }

    /**
     * 构建堆
     * @param array 待调整的堆
     */
    public static void buildHeap(int[] array) {
        for (int i = (array.length - 2) / 2; i >= 0 ; i--) {
            downAdjust(array, i, array.length);
        }
    }

    public static void main(String[] args) {
        int[] array = new int[] {1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
        upAdjust(array);
        System.out.println(Arrays.toString(array));

        array = new int[] {7, 1, 3, 10, 5, 2, 8, 9, 6};
        buildHeap(array);
        System.out.println(Arrays.toString(array));
    }
}

6.5. 优先队列

最大优先队列：当前最大元素优先出队
最小优先队列：当前最小元素优先出队
入队操作
插入新节点，新节点上浮找到合适的位置
出队操作
让原堆顶节点出队，把最后一个节点替换到堆顶位置，节点下沉，新的最大值节点成为新堆顶
代码实现如下：

public class PriorityQueue {

    private int[] array;
    private int size;
    private PriorityQueue() {
        array = new int[32];
    }

    /**
     * 入队
     * @param key 入队元素
     */
    public void enQueue(int key) {
        //对象长度超过范围，扩容
        if (size >= array.length) {
            resize();
        }
        array[size++] = key;
        upAdjust();
    }

    /**
     * 出队
     * @return
     * @throws Exception
     */
    public int deQueue() throws Exception {
        if (size <= 0) {
            throw new Exception("the queue is empty!");
        }
        //获取堆顶元素
        int head = array[0];
        //最后一个元素移动到堆顶
        array[0] = array[--size];
        downAdjust();
        return head;
    }

    /**
     * 上浮
     */
    private void upAdjust() {
        int childIndex = size - 1;
        int parentIndex = (childIndex - 1) / 2;
        int tmp = array[childIndex];
        while (childIndex > 0 && tmp > array[parentIndex]) {
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = parentIndex / 2;
        }
        array[childIndex] = tmp;
    }

    /**
     * 下沉
     */
    private void downAdjust() {
        int parentIndex = 0;
        int tmp = array[parentIndex];
        int childIndex = 1;
        while (childIndex < size) {
            if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]) {
                childIndex++;
            }
            if (tmp >= array[childIndex]) {
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        array[parentIndex] = tmp;
    }

    /**
     * 队列扩容
     */
    private void resize() {
        int newSize = this.size * 2;
        this.array = Arrays.copyOf(this.array, newSize);
    }

    public static void main(String[] args) throws Exception {
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.enQueue(3);
        priorityQueue.enQueue(5);
        priorityQueue.enQueue(10);
        priorityQueue.enQueue(2);
        priorityQueue.enQueue(7);
        System.out.println("出队元素为：" + priorityQueue.deQueue());
    }
}

6.6. 二叉查找树

前面介绍了二叉查找树的特性，下面介绍二叉查找树的操作

6.6.1. 二叉查找树的插入和删除

插入时需要先定位节点应当插入的位置，再将新节点插入进去就行了
删除时，可以分为三种情况

• 待删除的节点没有子节点，可以直接删除
• 待删除的节点有一个子节点，将其子节点取代被删除的节点，子节点以下的节点关系无须变动
• 待删除的节点右两个子节点，需要选择与待删除的节点最接近的节点来取代之

缺点：会发生数据偏重问题，如插入的数据依次比左子节点小