算法基础数据结构

2019-09-25 本文已影响0人烟雨乱平生

数据结构分类

数据结构.png

数组

数组是可以在内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。

String[] array = new String[10];

大小固定无法扩容，只能存储一种类型的数据

链表

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。

单链表

public class OneWayLinkedList<T> {

    /*
     * 指向头节点的指针
     */
    private Node<T> head;

    private Node<T> tail;

    private int size;

    /*
     * 每添加一个元素，尾节点指针向后移一位
     */
    public void add(T t){
        addLast(t);
    }

    public void add(T t,int index){
        if(index<0||size<index){
            throw new IllegalArgumentException("坐标越界");
        }
        Node<T> node = new Node<>(t,null);
        if(size==0){
            this.head = this.tail = node;
        }else{
            if(index==0){
                node.next = this.head;
                this.head = node;
            }
            else if(index==size){
                this.tail.next = node;
                this.tail = node;
            }
            else{
                Node<T> preTarget = findPreTarget(index);
                node.next = preTarget.next;
                preTarget.next = node;
            }
        }
        this.size++;
    }

    /**
     * 寻找目标节点的前置节点
     * @param index
     * @return
     * @primary
     */
    private final Node<T> findPreTarget(int index) {
        if(index==0){
            return null;
        }
        Node<T> preTarget = this.head;
        for (int i = 0; i < index-1; i++){
            preTarget = preTarget.next;
        }
        return preTarget;
    }

    public void addFirst(T t){
        add(t,0);
    }

    public void addLast(T t){
        add(t,size);
    }

    public T remove(int index){
        Node<T> target;
        if(size==0||index<0||size<=index){
            throw new IllegalArgumentException("坐标越界");
        }
        if(index==0){
            target = this.head;
            this.head = this.head.next;
        }else if(index==size-1){
            Node<T> preTarget = findPreTarget(index);
            target = preTarget.next;
            this.tail = preTarget;
        }else{
            Node<T> preTarget = findPreTarget(index);
            target = preTarget.next;
        }
        size--;
        return target.data;
    }

    public T removeFirst(){
        return remove(0);
    }

    public T removeLast(){
        return remove(size-1);
    }

    public T remove(){
        return removeFirst();
    }

    public T get(int index){
        if(size==0||index<0||index>=size){
            throw new IllegalArgumentException("坐标越界");
        }
        Node<T> preTarget = findPreTarget(index);
        if(preTarget==null){
            return this.head.data;
        }
        return preTarget.next.data;
    }

    public int size(){
        return this.size;
    }

    static class Node<T>{
        /*
         * 保存数据
         */
        T data;
        /*
         * 指向下一个节点的指针
         */
        Node<T> next;

        public Node(T t,Node<T> next){
            this.data = t;
            this.next = next;
        }
    }
}

双向链表

public class TwoWayLinkedList<E> {

    /*
     * 指向头节点的指针
     */
    private Node<E> head;
    /*
     * 指向尾节点的指针
     */
    private Node<E> tail;

    private int size;

    /**
     * 添加头节点
     * @param e
     */
    public void addFirst(E e){
        add(e,0);
    }

    /**
     * 添加尾节点
     * @param e
     */
    public void addLast(E e){
        add(e);
    }

    /**
     * 添加节点
     * @param e
     */
    public void add(E e){
        add(e,size);
    }

    /**
     * 在任意位置添加节点
     * @param e
     * @param index
     */
    public void add(E e,int index){
        if(index<0||size<index){
            throw new IllegalArgumentException("坐标越界");
        }
        Node<E> node = new Node<>(e,null,null);
        //空节点
        if(size==0){
            this.head=this.tail=node;
        }else{
            //插入头节点
            if(index==0){
                /*
                 * 建立节点之间的联系
                 */
                this.head.pre = node;
                node.next = this.head;
                /*
                 * 移动头节点
                 */
                this.head = node;
            }
            //插入尾节点
            else if (index==size){
                /*
                 * 建立节点之间的联系
                 */
                node.pre = this.tail;
                this.tail.next = node;
                /*
                 * 移动尾节点
                 */
                this.tail = node;
            }
            //插入中间节点
            else {
                //找到目标节点位置
                Node<E> target = findTarget(index);
                /*
                 * 建立前一个节点和新节点的关系
                 */
                target.pre.next = node;
                node.pre = target.pre;
                /*
                 * 建立新节点和目标节点的关系
                 */
                target.pre = node;
                node.next = target;
            }
        }
        size++;
    }

    public E removeFilrst(){
        return remove(0);
    }

    public E removeLast(){
        return remove(size-1);
    }

    public E remove(){
        return removeFilrst();
    }

    /**
     * 删除任意节点的位置
     * @param index
     * @return
     */
    public E remove(int index){
        Node<E> target;
        /*
         * 不允许删除该链表长度之外的数据
         */
        if(size==0||index<0||size<=index){
            throw new IllegalArgumentException("坐标越界");
        }
        //删除头节点
        if(index==0){
            target = this.head;
            /*
             * 将下一个节点的前置节点置空
             */
            this.head.next.pre = null;
            /*
             * 向后移动头节点的指针
             */
            this.head = this.head.next;
        }
        //删除尾节点
        else if (index==size-1){
            target = this.tail;
            /*
             * 将前一个节点的后置节点置空
             */
            this.tail.pre.next = null;
            /*
             * 向前移动尾节点的指针
             */
            this.tail = this.tail.pre;
        }
        //删除中间节点
        else{
            target = findTarget(index);
            /*
             * 建立前一个节点和后一个节点的关系
             */
            target.pre.next = target.next;
            target.next.pre = target.pre;
        }
        size--;
        return target.data;
    }

    /**
     * 查找目标节点
     * 相比于单向链表，双向链表可以直接查找目标节点
     * @param index
     * @return
     */
    private Node<E> findTarget(int index){
        Node<E> target;
        if(index>size/2){
            target = this.tail;
            for (int i = size-1; i > index; i--) {
                target = target.pre;
            }
        }else{
            target = this.head;
            for (int i = 0; i < index; i++) {
                target = target.next;
            }
        }
        return target;
    }

    public E get(int index){
        if(index<0||size<index){
            throw new IllegalArgumentException("坐标越界");
        }
        Node<E> target = findTarget(index);
        return target.data;
    }


    public int size(){
        return size;
    }

    static class Node<E>{
        E data;
        Node<E> pre;
        Node<E> next;

        public Node(E data,Node<E> pre,Node<E> next){
            this.data = data;
            this.pre = pre;
            this.next = next;
        }
    }
}

循环链表

public class CircleLinkedList<T> {

    /*
     * 指向头节点的指针
     */
    private Node<T> head;
    /*
     * 指向尾节点的指针
     */
    private Node<T> tail;

    private int size;

    public int size(){
        return size;
    }

    public void addFirst(T t){
        add(t,0);
    }

    public void addLast(T t){
        add(t,size);
    }

    public void add(T t){
        addLast(t);
    }

    /**
     * 任意位置添加节点
     * @param t
     * @param index
     */
    public void add(T t,int index){
        if(index<0||size<index){
            throw new IllegalArgumentException("坐标越界");
        }
        Node<T> node = new Node<>(t,null);
        /*
         * 空链表(不能和前置节点为空做相同处理)
         */
        if(this.size==0){
            this.head = this.tail = node;
            this.tail.next = this.head;
        }else{
            /*
             * 前置节点为空
             * (2)目标节点为头节点
             */
            if(index==0){
                node.next = this.head;
                this.head = node;
                this.tail.next = this.head;
            }
            /*
             * 处理尾节点
             */
            else if(index==size){
                this.tail.next = node;
                this.tail = node;
                this.tail.next = head;
            }else{
                Node<T> preTarget = findPreTarget(index);
                Node<T> target = preTarget.next;
                preTarget.next = node;
                node.next = target;
            }
        }
        size++;
    }


    public T removeFirst(){
        return remove(0);
    }

    public T removeLast(){
        return remove(size-1);
    }

    public T remove(){
        return removeLast();
    }

    /**
     * 任意位置删除节点
     * @param index
     * @return
     */
    public T remove(int index){
        if(size==0||size<=index||index<0){
            throw new IllegalArgumentException("坐标越界");
        }
        Node<T> target;
        if(index==0){
            target = this.head;
            this.head = this.head.next;
            this.tail.next = this.head;
        }
        else if (index==size-1){
            target = this.tail;
            Node<T> preTarget = findPreTarget(index);
            this.tail = preTarget;
            this.tail.next = this.head;
        }
        else{
            Node<T> preTarget = findPreTarget(index);
            target = preTarget.next;
            preTarget.next = target.next;
        }
        size--;
        return target.data;
    }

    /**
     * 单向链表只能单向查找
     * 注意：不应该找target节点应该是目标节点的前置节点（思考为什么？）
     * @param index
     * @return
     */
    private Node<T> findPreTarget(int index) {
        if(index==0){
            return null;
        }
        Node<T> preTarget = this.head;
        for (int i = 0; i < index-1; i++){
            preTarget = preTarget.next;
        }
        return preTarget;
    }

    public T get(int index){
        if(size==0||size<=index||index<0){
            throw new IllegalArgumentException("坐标越界");
        }
        Node<T> preTarget = findPreTarget(index);
        if(preTarget==null){
            return this.head.data;
        }else{
            return preTarget.next.data;
        }
    }

    static class Node<T>{
        /*
         * 保存数据
         */
        T data;
        /*
         * 指向下一个节点的指针
         */
        Node<T> next;

        public Node(T t, Node<T> next){
            this.data = t;
            this.next = next;
        }
    }
}

队列

队列是一种特殊的线性表，其特点是先进先出

方法	说明
add	添加一个元素，如果队列已满，则抛出异常
offer	添加一个元素，如果队列已满返回false
put	添加一个元素，如果队列已满则阻塞
remove	移出并返回队列头部的元素,如果队列为空则抛出异常
poll	移出并返回队列头部的元素,如果队列为空返回null
take	移出并返回队列头部的元素
element	返回队列头部的元素，如果队列为空，则抛出异常
peek	返回队列头部的元素，如果队列为空，则返回null

public class Queue<E> {

    public Queue(int capacity){
        elements = new Object[capacity];
    }

    Object[] elements;

    int size = 0;

    Object lockin = new Object();

    Object lockout = new Object();

    /**
     *  增加一个元素，如果队列已满，则抛出异常
     */
    public void add(E e){
        if (size==elements.length){
            throw new RuntimeException("队列已满");
        }
        elements[size++] = e;
        synchronized (lockout){
            lockout.notify();
        }
    }

    /**
     * 添加一个元素，如果队列已满返回false
     */
    public boolean offer(E e){
        if (size==elements.length){
            return false;
        }
        elements[size++] = e;
        synchronized (lockout){
            lockout.notify();
        }
        return true;
    }

    /**
     * 添加一个元素，如果队列已满则阻塞
     */
    public void put(E e) {
        try {
            synchronized (lockin){
                while (size==elements.length){
                    lockin.wait();
                }
                elements[size++] = e;
                synchronized (lockout){
                    lockout.notify();
                }
            }
        } catch (InterruptedException exception) {
            exception.printStackTrace();
        }
    }

    /**
     * 移出并返回队列头部的元素,如果队列为空则抛出异常
     */
    public E remove(){
        if(size<=0){
            throw new RuntimeException("对列已经空了");
        }
        Object data = elements[0];
        removeInnerElement(0);
        return (E)data;
    }

    /**
     * 移出并返回队列头部的元素,如果队列为空返回null
     */
    public E poll(){
        if(size<=0){
            return null;
        }
        Object data = elements[0];
        removeInnerElement(0);
        return (E)data;
    }


    /**
     * 移出并返回队列头部的元素
     */
    public E take() {
        try {
            synchronized (lockout){
                while (size<=0){
                    lockout.wait();
                }
                Object data = elements[0];
                removeInnerElement(0);
                return (E)data;
            }
        } catch (Exception exception){
            exception.printStackTrace();
        }
        return null;
    }

    /**
     * 返回队列头部的元素，如果队列为空，则抛出异常
     */
    public E element(){
        if(size<=0){
            throw new RuntimeException("对列已经空了");
        }
        Object data = elements[0];
        return (E)data;
    }

    /**
     * 返回队列头部的元素，如果队列为空，则返回null
     */
    public E peek(){
        if(size<=0){
            return null;
        }
        Object data = elements[0];
        return (E)data;
    }


    void removeInnerElement(int index){
        for (int i = index; i < size-1; i++) {
            elements[i] = elements[i+1];
        }
        elements[size-1] = null;
        size--;
        synchronized (lockin){
            lockin.notify();
        }
    }
}

栈

栈是一种特殊的线性表，只允许在栈顶操作，栈的特点是先进后出。

public class Stack<E> {

    Object[] elements;

    int size;

    public Stack(){
        elements = new Object[5];
    }

    /**
     * 将数据入栈
     */
    public void push(E e){
        if (size==elements.length){
            grow();
        }
        elements[size++] = e;
    }

    /**
     * 取出栈顶元素
     */
    public E pop(){
        if (size<=0){
            return null;
        }
        Object data = elements[size-1];
        elements[size--] = null;
        return (E)data;
    }

    /**
     * 获取栈顶元素，不出栈
     */
    public E peek(){
        if (size<=0){
            return null;
        }
        Object data = elements[size];
        return (E)data;
    }

    private void grow() {
        Object[] copy = Arrays.copyOf(elements,size*2);
        elements = copy;
    }
}

树

树是一种非线性的数据结构，是由n（n >=0）个结点组成的有限集合。树的特点是：

每个节点有零个或多个子节点
没有父节点的节点称为根节点
每个非根节点有且只有一个父节点
除了根节点外，每个子节点可以分为多个不相交的子树

image.png

节点的度

一个节点直接含有的子树个数，叫做节点的度，度为0的节点为叶节点，度不为0的节点称为分支节点。比如上图A节点的度是2，B节点的度是3.

树的度

树的度定义为树的所有节点中度的最大值。

树的前驱和后继

节点的直接后继称为节点的孩子，节点称为孩子的双亲；节点的孩子的孩子称为节点的孙子，节点称为子孙的祖先；同一个双亲的孩子之间互称兄弟。

树中节点的层次

树中根节点为第1层，根节点的孩子为第2层，以此类推。

树的高度

树的高度是从叶子节点开始，自底向上增加。

树的深度

与高度相反，树的深度从根节点开始，自顶向下增加。

整个树的高度、深度是一样的，但是中间节点的高度和深度是不同的，比如I节点的深度是4，高度是2。

树的遍历

前序遍历：先根节点，后左孩子节点，再右孩子节点
中序遍历：先左孩子节点，后根节点，再右孩子节点
后序遍历：先左孩子节点，后右孩子节点，再根节点
深度优先遍历：简称DFS，其原则是，沿着一条路径一直找到最深的那个节点，当没有子节点的时候，返回上一级节点，寻找其另外的子节点，继续向下遍历，没有就向上返回一级，直到所有的节点都被遍历到，每个节点只能访问一次。
广度优先遍历：简称BFS；广度优先遍历的原则就是对每一层的节点依次访问，一层访问结束后，进入下一层，直到最后一个节点，同样的，每个节点都只访问一次。

树的存储结构

双亲表示法
孩子表示法
孩子兄弟表示法

    /**
     * 普通树节点的定义
     */
    static class Node<E>{
        private E value;
        private Node<E> parent;//节点的双亲

        public Node(Node<E> parent, E value){
            this.value = value;
            this.parent = parent;
        }

        public E getValue() {
            return value;
        }

        public void setValue(E value) {
            this.value = value;
        }

        public Node<E> getParent() {
            return parent;
        }

        public void setParent(Node<E> parent) {
            this.parent = parent;
        }
    }

算法基础数据结构

数据结构分类

数组

链表

队列

栈

树

节点的度

树的度

树的前驱和后继

树中节点的层次

树的高度

树的深度

树的遍历

树的存储结构

猜你喜欢

热点阅读

算法基础 数据结构

数据结构分类

数组

链表

队列

栈

树

节点的度

树的度

树的前驱和后继

树中节点的层次

树的高度

树的深度

树的遍历

树的存储结构

猜你喜欢

热点阅读

算法基础数据结构