数据结构实现（Java）

对Java数据结构的简单实现（持续更新）

1、线性表

1.1、线性表抽象类

(顺序表和链表均继承此抽象类)

实现功能：获取表长，增，删，查

/**
 * 线性表抽象类
 * @param <E> 存储的元素(Element)类型
 * 获取长度，增，删，查
 */
public abstract class _00LineListAbstract<E> {


    /**
     * 获取表的长度
     * @return 顺序表的长度
     */
    public abstract int size();


    /**
     * 添加一个元素
     * @param e 元素
     * @param index 要添加的位置(索引)
     */
    public abstract void add(E e, int index);


    /**
     * 移除指定位置的元素
     * @param index 位置
     * @return 移除的元素
     */
    public abstract E remove(int index);


    /**
     * 获取指定位置的元素
     * @param index 位置
     * @return 元素
     */
    public abstract E get(int index);
}

1.2、顺序表

1.2.1、顺序表继承抽象类

public class _01ArrayListDooo<E> extends _00LineListAbstract<E> {

    private Object[] arr = new Object[1];

    //得是数组里面元素的多少，不能是数组的长度
    private int size = 0;

    @Override
    public int size() {
        //size在其他操作中动态变化
        return size;
    }

    @Override
    public void add(E e, int index) {
        //判断插入位置是否合法
        if(index > size){
            throw new IllegalArgumentException("非法的位置插入异常");
        }
        //判断数组够不够长
        if(size >= arr.length){
            Object[] arr = new Object[this.arr.length + 10];
            for (int i = 0; i < this.arr.length; i++) {
                arr[i] = this.arr[i];
            }
            this.arr = arr;
        }

        //把后面的元素往后移,index是参数,必须倒着来啊！不然就撞了
        int i = size - 1;
        while(i >= index){
            arr[i+1] = arr[i];
            i--;
        }
        //插入
        arr[index] = e;
        size++;
    }

    @Override
    public E remove(int index) {
        //只能删除存在的元素,查看删除位置是否合法
        if (index > size - 1) {
            throw new IllegalArgumentException("非法的位置插入异常");
        }
        //前移后面的元素（从index+1开始），不用删除，直接覆盖就行
        int i = index;
        E e = (E) arr[index];
        while (i <= size-1) {
            arr[i] = arr[i + 1];
            i++;
        }
        size--;
        return e;
    }

    @Override
    //查询index位置的元素
    public E get(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException("无法访问到下标位置");
        }
        return (E) arr[index];
    }
}

1.2.2、顺序表Main

public class _01ArrayListMain {
    public static void main(String[] args) {
        _01ArrayListDooo<Integer> list = new _01ArrayListDooo<>();
        list.add(1,0);// 1
        list.add(2,0);// 2 1
        list.add(3,0);// 3 2 1
        list.add(4,0);// 4 3 2 1
        list.add(5,0);// 5 4 3 2 1
        list.remove(0);//4 3 2 1
        System.out.println(list.get(1));//3
        System.out.println(list.size());//4
        System.out.println("debug");
    }
}

1.3、链表

1.3.1、链表继承抽象类

public class _02LinkListDooo<E> extends _00LineListAbstract<E> {
// 头结点 -> 首结点 -> ........-> 尾结点

    //类似'结点'结构体
    static  class Node<E>{
        //左边，存储的元素
        private E e;
        //右边，下一个结点的引用
        private Node<E> next;
        //构造方法，创建结点直接赋值
        public Node(E e){
            this.e = e;
        }
    }

    //创建一个头结点，里面没有值
    Node<E> head = new Node<>(null);
    //链表的长度
    private int size;

    //返回链表的长度
    @Override
    public int size() {
        return size;
    }
    //插入一个结点
    @Override
    //原理 e1 -> e2 -> e3，插入一个e0变成，e1 -> e0 -> e2 -> e3
    // ① e1 -> e0 ② e0 -> e2
    public void add(E e, int index) {
        //判断对象是否合法，链表不需要扩容，也不需要移动后面的元素，只需要改变指针（在Java中是引用）
        if (index > size) {
            throw new IllegalArgumentException("非法的插入位置！");
        }

        //前驱节点，一开始什么都没有，前驱节点就是head
        Node<E> node = head;
        //暂时先起个名字，一会儿代表后面的结点
        Node<E> temp;
        for (int i = 0; i < index; i++) {

            //先让外面的结点移动到对应位置
            node = node.next;

            //         e0
            //    e1   ->    e2   ->   e3
            //    |          |
            //  (node)     (temp)

        }
        temp = node.next;
        //连接e1与e0
        node.next = new Node<>(e);
        //连接e0 与 e2
        node.next.next = temp;
        size++;
    }

    @Override
    //删除一个结点
    public E remove(int index) {
        //判断对象是否合法
        if (index > size) {
            throw new IllegalArgumentException("非法的插入位置！");
        }
        Node<E> node = head,temp;
        for (int i = 0; i < index; i++) {
            //移动指针
            node = node.next;
        }

        //    e1   ->  e2  ->    e3
        //    |                  |
        //   node   (remove)    temp
        //①直接把e1 和 e3进行连接就好，让e1.next = e3.e
        temp = node.next;
        node.next = node.next.next;
        size --;
        return temp.e;
    }

    @Override
    public E get(int index) {
        //判断对象是否合法
        if (index > size) {
            throw new IllegalArgumentException("非法的插入位置！");
        }
        Node<E> node = head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node.e;
    }
}

1.3.2、链表Main

public class _02LinkListMain {
    public static void main(String[] args) {
        _02LinkListDooo<Integer> list = new _02LinkListDooo<>();
        list.add(1,0);
        list.add(2,0);
        list.add(3,0);
        list.remove(0);
        System.out.println(list.get(1));
        System.out.println(list.size());
        System.out.println(1);//随便加上一个输出，方便看上一行的调试结果

    }
}

1.4、栈

1.4.1、栈抽象类

实现：入栈操作，出栈操作

/**
 * 抽象类型栈，待实现
 * @param <E> 元素类型
 */
public abstract class _03StackAbstract<E> {

    /**
     * 出栈操作
     * @return 栈顶元素
     */
    public abstract E pop();



    /**
     * 入栈操作
     * @param e 元素
     */
    public abstract void push(E e);
}

1.4.2、栈抽象类实现

public class _03StackDooo<E> extends _03StackAbstract {

    //用线性表存储
    private Object[] arr = new Object[20];
    //长度
    private int size = 0;


    @Override
    //出栈
    public E pop() {
        return (E) arr[(size--)-1];
    }

    @Override
    public void push(Object e) {
        //扩容
        if(size >= arr.length){
            Object[] arr = new Object[this.arr.length + 10];
            for (int i = 0; i < this.arr.length; i++) {
                arr[i] = this.arr[i];
            }
            this.arr = arr;
        }
        //赋值的同时给size+1
        arr[size++] = e;
    }
}

1.4.3、栈Main

public class _03StackMain {
    public static void main(String[] args) {
        _03StackDooo<Integer> stack = new _03StackDooo<>();
        stack.push("A");
        stack.push("B");
        stack.push("C");
        //pop之后虽然数组没变，但是指针变了，所以后面再来数据会顶替掉，栈是一个你想象出来的数据结构。
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(1);
    }
}

1.5、队列

1.5.1、队列抽象类

实现：入队，出队

public abstract class _04QueneAbstract<E> {
    /**
     * 进队操作
     * @param e 元素
     */
    public abstract void offer(E e);



    /**
     * 出队操作
     * @return 元素
     */
    public abstract E poll();
}

1.5.2、队列抽象类实现

public class _04QueneDooo<E> extends _04QueneAbstract<E> {
    //底层数组
    private Object[] arr = new Object[20];
    //队首队尾下标
    private int head = 0, tail = 0;

    //   e1  <-  e2  <-  e3  <-  e4
    //  head                    tail

    //e5入队：
    //  e1      e2     e3     e4     e5
    // head                         tail

    //e1出队：
    //  e2      e3       e4       e5
    // head                      tail


    @Override
    //从队尾进队操作
    public void offer(E e) {
        //取余能让尾巴从0开始循环开始,循环队列并没有真正的将head和tail进行连接，只是通过取余号让数值上进行循环
        //一定要判断，tail不能超越head，next是预测的tail的下一个值
        int next = (tail+1) % arr.length;
        if (next == head) {
            //要追上了，不行，违规了
            return;
        }
        arr[tail] = e;
        tail = next;
    }

    @Override
    //队首出队操作
    public E poll() {
        //把队首的值存起来
        E e = (E) arr[head];
        //移动head指针
        head = (head+1) % arr.length;
        return e;
    }
}

1.5.3、队列Main

public class _04QueneMain {
    public static void main(String[] args) {
        _04QueneDooo<Integer> Quene = new _04QueneDooo<>();
        Quene.offer(123);
        Quene.offer(456);
        Quene.offer(789);

        System.out.println(Quene.poll());
        System.out.println(Quene.poll());
        System.out.println(Quene.poll());
        System.out.println(1);
    }
}

2、二叉树

2.1、二叉树结构

public class _05TreeNodeDooo<E> {
    E e;
    _05TreeNodeDooo<E> left;
    _05TreeNodeDooo<E> right;

    public _05TreeNodeDooo(E e){
        this.e = e;
    }


}

2.2、二叉树Main

package _13数据结构;

public class _05TreeNodeMain {
    public static void main(String[] args) {
        _05TreeNodeDooo<String> root = new _05TreeNodeDooo<>("A");

        root.left = new _05TreeNodeDooo<>("B");
        root.right = new _05TreeNodeDooo<>("E");
        root.left.left = new _05TreeNodeDooo<>("C");
        root.left.right = new _05TreeNodeDooo<>("D");
        root.right.right = new _05TreeNodeDooo<>("F");
        preprint(root);
        System.out.println();
        midprint(root);
        System.out.println();
        backprint(root);
        System.out.println();

        //                 A
        //                / \
        //              B     E
        //             / \     \
        //            C   D     F

    }
    //先序遍历
    private static void preprint(_05TreeNodeDooo<String> root){
        if(root == null){return;}
        System.out.print(root.e+" ");
        preprint(root.left);
        preprint(root.right);
    }
    //中序遍历
    private static void midprint(_05TreeNodeDooo<String> root){
        if(root == null){return;}
        midprint(root.left);
        System.out.print(root.e+" ");
        midprint(root.right);
    }
    //后序遍历
    private static void backprint(_05TreeNodeDooo<String> root){
        if(root == null){return;}
        backprint(root.left);
        backprint(root.right);
        System.out.print(root.e+" ");
    }

}