数据结构开门篇

数据结构

1、什么是数据结构

数据结构是数据组织、管理和存储格式，其使用目的是为了高效地访问和修改数据

2、时间复杂度和空间复杂度

什么是时间复杂度
时间复杂度是对一个算法运行时间长短的度量，用大O表示，记作

T(n)=O(f(n))

• 如果运行时间是常数量级，则用常数1表示
• 只保留时间函数中的最高阶项
• 如果最高阶项存在，则省区最高阶项前面的系数

O(1)

时间复杂度的场景：
线性、对数、常量、多项式

什么是空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，用大O表示，记作

S(n)=O(f(n))

空间复杂度的场景
常量空间、线性空间、二维空间、递归空间

O(1)、O(n)、O(n2)、O(n)

3、数组

public class ArrayDemo {
    private int[] array;
    private int size;

    public ArrayDemo(int capacity){
        this.array = new int[capacity];
        size = 0;
    }

    /**
     * 插入元素
     * @param index
     * @param element
     */
    public void insert(int index,int element){
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException("超过数组实际元素范围！");
        }
        if(size >= array.length){
            resize();
        }
        for (int i = size - 1; i >= size ; i--) {
            array[i+1] = array[i];
        }
        array[index] = element;
        size++;
    }

    /**
     * 扩容
     */
   public void resize(){
        int[] arrayNew = new int[array.length*2];
        System.arraycopy(array,0,arrayNew,0,array.length);
        array = arrayNew;
   }
    public void output(){
       StringBuffer buffer = new StringBuffer();
        for (int i = 0; i < size; i++) {
            buffer.append(array[i]);
        }
        System.out.println(buffer);
    }

    public int delete(int index){
       if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("超出数组实际元素范围");
       }
       int deletedElement = array[index];
       for(int i = index;i < size - 1; i++){
           array[i] = array[i - 1];
       }
       size--;
       return deletedElement;
    }

    public static void main(String[] args) {
        ArrayDemo arrayDemo = new ArrayDemo(2);
        arrayDemo.insert(0,3);
        arrayDemo.insert(1,7);
        arrayDemo.insert(2,9);
        arrayDemo.insert(3,5);
        arrayDemo.delete(3);
        arrayDemo.output();

    }
}

利用下标查找数组元素的时间复杂度是O(1)，中间插入、删除数组元素的时间复杂度是O(n)；

4、链表

public class LinkedListDemo {

    /**
     * 头节点指针
     */
    private Node head;

    /**
     * 尾节点指针
     */
    private Node tail;

    /**
     * 链表实际长度
     */
    private int size;
    private static class Node{
        int data;
        Node next;
        Node(int d){
            this.data = d;
        }

    }


    public void insert(int index,int data){
        if(index < 0 || index > size){
           throw new IndexOutOfBoundsException("超出链表节点范围！");
        }
        Node insetNode = new Node(data);
        if(size == 0){
            head = insetNode;
            tail = insetNode;
        }else if(index == 0){
            insetNode.next = head;
            head = insetNode;
        }else if(index  == size){
            tail.next = insetNode;
            tail = insetNode;
        }else{
            Node prevNode = getNode(index -1);
            insetNode.next = prevNode.next;
            prevNode.next = insetNode;
        }
        size++;
    }

    public Node remove(int index){
        if(index < 0 || index > size){
             throw new IndexOutOfBoundsException("超出链表节点范围！");
        }
        Node removeNode = null;
        if(index == 0){
            removeNode = head;
            head = head.next;
        }else if(index == size -1){
            Node prevNode = getNode(index - 1);
            //removeNode = prevNode.next;
            prevNode.next = null;
            tail = prevNode;
        }else{
            Node prevNode = getNode(index - 1);
            removeNode = prevNode.next;
            prevNode.next = removeNode.next;
        }
        size--;
        return removeNode;
    }
    /**
     * 获取某个位置的链表
     * @param index
     * @return
     */
    private Node getNode(int index) {
      if(index < 0 || index > size){
          throw  new IndexOutOfBoundsException("超出链表节点范围！");
      }
      Node temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    public void output(){
        Node temp = head;
        StringBuffer sb = new StringBuffer();
        while(temp!= null){
            sb.append(temp.data);
            temp = temp.next;
        }
        System.out.println(sb);
    }

    public static void main(String[] args) {
        LinkedListDemo linkedList = new LinkedListDemo();
        linkedList.insert(0,3 );
        linkedList.insert(1,4 );
        linkedList.insert(2,5 );
        linkedList.insert(3,6 );
        linkedList.remove(1);
        linkedList.output();
    }

}

查找链表节点的时间复杂度是O(n),中间插入和删除节点的时间复杂度是O(1)

5 栈和队列

栈
栈是一种线性数据结构，可以用数组实现，也可以用链表实现。只能先进后出（FILO）
无论是以数组还是链表实现，入栈和出栈的时间复杂度都是

O（1）

队列

队列是一种线性数据结构，可以用数组实现，也可以用链表实现。先进先出（FIFO）.
当（队尾下标+1）%数组长度 = 队头下标时，代表此队列真的满了

public class QueueDemo {
    private int[] array;
    private int front;
    private int rear;

    public QueueDemo(int capacity) {
        this.array = new int[capacity];
    }

    /**
     * 入队
     * @param element
     * @throws Exception
     */
    public void enQueue(int element) throws Exception {
        if((rear + 1)% array.length == front){
            throw new Exception("队列已满");
        }
        array[rear] = element;
        rear =(rear + 1)% array.length;
    }

    /**
     * 出队
     * @return
     * @throws Exception
     */
    public int dequeue() throws Exception {
        if(rear == front){
            throw new Exception("队列已空！");
        }
        int dequeueElement = array[front];
        front = (front + 1)% array.length;
        return dequeueElement;
    }

    public void output(){
        StringBuffer sb = new StringBuffer();
        for (int i = front; i != rear ; i = (i + 1)% array.length) {
            sb.append(array[i]);
        }
    }

    public static void main(String[] args) throws Exception {
        QueueDemo queue = new QueueDemo(3);
        queue.enQueue(3);
        queue.enQueue(4);
        queue.enQueue(5);
        queue.enQueue(6);
        queue.dequeue();
        queue.dequeue();
        queue.output();
    }
}

6 散列表

散列表也叫作哈希表，这种数据结构提供了键和值的映射关系。只要给出一个key，就可以高效查找到它匹配的value，时间复杂度接近O(1);
解决哈希冲突的方法主要有两种，一种是开放寻址法，一种是链表法。
在java中，ThreadLocal用的就是开放寻址法；Java集合类HashMap中，使用的是链表法

树

二叉树有两种特殊形式
一个叫做满二叉树，一个叫做完全二叉树
满二叉树？
一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树
完全二叉树？
只需保证最后一个节点前的节点都是齐全的就可以。
物理存储结构
二叉树可以用那些物理存储结构来表示：
1.链表
2.数组
下标计算
假如一个父节点的下标是parent，那么它的左孩子节点的下标就2 * parent + 1；它的右孩子节点的下标就是2 * parent + 2；
反过来，假如一个左孩子的节点的下标是leftChild，那么它的父亲节点下标是（leftChild-1）/2
二叉堆，是一种完全二叉树，用数组来存储
二叉树的应用
查找操作和维持相对顺序
二叉查找树要求左子树小于父节点，右子树大于父节点，保证了二叉树的有序性
二叉树的自平衡
红黑树、AVL树、树堆
深度优先遍历
前序遍历，中序遍历，后续遍历

public class TreeDemo {
    private static class TreeNode{
        int data;
        TreeNode leftChild;
        TreeNode rightChild;
        TreeNode(int data){
            this.data = data;
        }
    }

    public static TreeNode crateBinaryTree(LinkedList inputList){
        TreeNode node = null;
        if(inputList == null || inputList.isEmpty()){
            return  null;
        }
        Integer data = inputList.removeFirst();
        if(data != null){
            node = new TreeNode(data);
            node.leftChild = crateBinaryTree(inputList);
            node.rightChild = crateBinaryTree(inputList);
        }
        return node;
    }

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

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

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

    public static void main(String[] args) {
        LinkedList inputList = new LinkedList(
                Arrays.asList(3,4,8,null,null,12,null,null,7,null,4)
        );
        TreeNode treeNode = crateBinaryTree(inputList);
        System.out.println("前序遍历：");
        preOrderTraversal(treeNode);
        System.out.println("中序遍历：");
        inOrderTraversal(treeNode);
        System.out.println("后序遍历：");
        postOrderTraversal(treeNode);

    }


}

广度优先

/**
     * 二叉树层序遍历
     * @param treeNode
     */
    public static void levelOrderTraversal(TreeNode treeNode){
        Queue queue = new LinkedList();
        queue.offer(treeNode);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            System.out.println(node.data);
           if(node.leftChild != null){
               queue.offer(node.leftChild);
           }
           if(node.rightChild!= null){
               queue.offer(node.rightChild);
           }
        }
    }

二叉树
1.最大堆
最大堆的任意一个父节点的值，都大于或等于它左、右孩子节点的值
2.最小堆
最大堆的任意一个父节点的值，都小于或等于它左、右孩子节点的值