数据结构与算法线性表篇

线性表

1，顺序存储结构

例子（火车站排队）：数组，ArrayList(考察增删改查+排序 性能)

1544423425371.png

插入与删除：

1544423819403.png

优点：尾端插入效率高，支持随机访问。

缺点：中间插入或者删除效率低。

顺序表的插入：

public void ArrayInsert(int []array,int index,int data){
        //插入0在第一位
        //1,数组长度要增加一位
        int Size = array.length;
        array = Arrays.copyOf(array,Size+1);
        System.arraycopy(array,index,array,index+1,Size-index);
        array[index] = data;
    }

顺序表的删除：

    public void ArrayDel(int []array,int index){
        int Size = array.length;
        int numMoved = Size - index - 1;
        if(numMoved > 0){
                        System.arraycopy(array,index+1,array,index,numMoved);
        }
        arrays = Arrays.copyOf(arrays,Size-1);
    }

顺序表的排序：int[] array=new int[]{3,2,5,8,1,9,4,6,7};

冒泡排序法：第一轮两两比较确定最大的数，第二轮两两比较确定第二大的数，依次下去（应用场景：个位数的排序次数时 比如斗牛游戏中五张牌排序）

public static void bubbleSort(int [] array){
    for(int i=array.length-1;i>0;i--){
        for(int j = 0;j<i;j++){
            if(array[j] > array[j+1]){
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

选择排序法：两个两个进行比较，选出最小的，记住最小的所在位置的index索引，然后将最小的值换到index = 0的位置上去，下去再找到最小的值换到index = 1的位置上去，这样循环下去（应用场景：个位数的排序次数时）

   public static void selectSort(int [] array){
        for(int i =0;i<array.length-1;i++){
            int index = i;
            for(int j = index+1;j<array.length;j++){
                if(array[j] <array[index]){
                    index = j;
                }
            }
            if(index != i){//如果当前就是最小的，就不需要交换
                int temp = array[index];
                array[index] = array[i];
                array[i] = temp;
            }
        }
    }

2，链式存储结构

1544492694561.png

定义：线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的

种类：a，单链表

1544494175719.png

应用：MessageQueue

b，双链表

20170802162411952.png

应用：LinkedList

c，单循环链表

922236-20171220105321803-1108244770.png

d，双向循环链表

632293-20170306150003297-951612143.png

优点：插入删除快

缺点：不支持随机访问

手写单链表

package com.example.sven.algorithm.test_linkedlist;

import java.util.NoSuchElementException;

public class SingleLinkedList <T>{

    /**
     * 结点  单链表的元素结点
     * @param <T>
     */
    private static class Node<T>{
        T item;//单链表的数据
        Node<T> next;//单链表的下一个元素的指针
        public Node(T item,Node<T> next){
            this.item = item;
            this.next = next;
        }
    }

    //头结点
    Node<T> first;
    //尾结点
    Node<T> last;
    //大小
    int size;

    //手写单链表
    public SingleLinkedList(){

    }

    //添加元素
    public void add(T t){
        linkLast(t);
    }

    /**
     *添加数据在最后
     */
    public void linkLast(T t){
        Node<T> newNode = new Node<T>(t,null);
        Node<T> l = last;
        last = newNode;

        if(l == null){
            first = newNode;
        }else{
            l.next = newNode;
        }
        size++;
    }

    /**
     * 添加数据在index位置
     * @param index
     * @param t
     */
    public void add(int index,T t){
        if(index <0 || index >size){
            return;
        }

        if(index == size){
            linkLast(t);
        }else{
            Node<T> preTarget = node(index-1);
            Node<T> newNode = new Node<T>(t,preTarget.next);
            preTarget.next = newNode;
            size++;
        }
    }

    /**
     * 添加一整个单链表
     * @param c
     * @return
     */
    public boolean addAll(SingleLinkedList c){
        return addAll(size,c);
    }

    private boolean addAll(int index,SingleLinkedList c){
        checkPositionIndex(index);

        int numNew = c.size;
        if (numNew == 0)
            return false;

        Node<T> pred;
        pred = last;

        for(int i = 0;i<c.size;i++){
            T t = (T) c.get(i);
            Node<T> newNode = new Node<>(t,null);
            if(pred == null){
                first = newNode;
            }else{
                pred.next = newNode;
            }
            pred = newNode;
        }

        last = pred;
        size += numNew;
        return true;
    }


    //查找元素
    public T get(int index){
        if(index<0 || index>size){
            return null;
        }
        return node(index).item;
    }

    /**
     * 获取index位置上的结点
     */
    private Node<T> node(int index){
        //如果index在整个链表的前半部分
        Node<T> node = first;
        for(int i = 0;i<index;i++){
            node = node.next;
        }
        return node;
    }

    /**
     * 修改
     * @param index
     * @param t
     * @return
     */
    public T set(int index ,T t){
        checkElementIndex(index);
        return setNode(index,t);
    }

    private T setNode(int index,T t){
        Node<T> node = node(index);
        node.item = t;
        return t;
    }

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

    private T removeFirst(){
        final Node<T> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    /**
     * Unlinks non-null first node f.
     */
    private T unlinkFirst(Node<T> f) {
        T item = f.item;
        Node<T> next = f.next;
        f.item = null;
        f.next = null;
        first = next;
        if(next == null){//没有数据了
            last = null;
        }
        size --;
        return item;
    }

    /**
     * 删除数据
     * @param index
     */
    public T remove(int index){
        checkElementIndex(index);
        return unlinkNode(index);
    }

    private T unlinkNode(int index){
        Node<T> preTarget = node(index-1);
        Node<T> target = preTarget.next;
        preTarget.next = target.next;
        target.next = null;
        size -- ;
        return target.item;
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    public String toString() {
        if (size == 0)
            return "[]";

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (int i =0;i<size;i++) {
            T e = get(i);
            sb.append(e);
            if (i == size-1)
                return sb.append(']').toString();
            sb.append(',').append(' ');
        }
        return sb.toString();
    }
}

实际应用：将麻将进行排序摆放

radixSort.png

建一个麻将类

package com.example.sven.algorithm.test_linkedlist;

public class Mahjong {
    public int suit;//筒，万，索
    public int rank;//点数 一  二  三

    public Mahjong(int suit, int rank) {
        this.suit = suit;
        this.rank = rank;
    }

    @Override
    public String toString() {
        return "("+this.suit+" "+this.rank+")";
    }
}

进行单元测试

  @Test
    public void test(){
        SingleLinkedList<Mahjong> list = new SingleLinkedList<Mahjong>();
        list.add(new Mahjong(3,1));
        list.add(new Mahjong(2,3));
        list.add(new Mahjong(3,7));
        list.add(new Mahjong(1,1));
        list.add(new Mahjong(3,8));
        list.add(new Mahjong(2,2));
        list.add(new Mahjong(3,2));
        list.add(new Mahjong(1,3));
        list.add(new Mahjong(3,9));
        list.add(new Mahjong(3,5));
        list.add(new Mahjong(2,6));
        list.add(new Mahjong(3,1));
        list.add(new Mahjong(2,4));
        System.out.println(list);
        radixSort(list);
        System.out.println(list);

    }

    public static void radixSort(SingleLinkedList<Mahjong> list){
        //先对点数进行分组（1-9）
        SingleLinkedList [] rankList = new SingleLinkedList[9];
        for(int i = 0;i<rankList.length;i++){
            rankList[i] = new SingleLinkedList();
        }

        //把数据一个个的放入到对应的数组中
        while(list.size>0){
            //取一个
            Mahjong m = list.remove();
            //点数1-9放入到0-8的组中去
            rankList[m.rank - 1].add(m);
        }
        //已经把数据全部按照点数放入到对应的9个组中去了
        //将9组数据合并成一组数据
        for(int i = 0;i<rankList.length;i++){
            list.addAll(rankList[i]);
        }

        //先花色进行分组
        SingleLinkedList [] suitList = new SingleLinkedList[3];
        for(int i = 0 ;i<suitList.length;i++){
            suitList[i] = new SingleLinkedList();
        }
        //把数据按照花色一个个放到对应的组中
        while(list.size > 0){
            Mahjong m = list.remove();
            //放到对应的组中
            suitList[m.suit - 1].add(m);
        }
        //把三个花色的组合并成一个组
        for(int i = 0;i<suitList.length;i++){
            list.addAll(suitList[i]);
        }
    }

手写双链表

package com.example.sven.algorithm.test_linkedlist;

//手写双链表
public class DoubleLinkedList <E>{

    /**
     * 结点
     */
    private static class Node<E> {
        E item;//数据
        Node<E> prev;//前驱
        Node<E> next;//后继

        public Node(Node<E> prev, E item, Node<E> next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }

    public DoubleLinkedList(){

    }

    //头节点
    Node<E> first;
    //尾节点
    Node<E> last;
    //大小
    int size;

    /**
     * 添加数据在最后
     */
    public void add(E e) {
        linkLast(e);
    }

    /**
     * 添加到最后
     * @param e
     */
    private void linkLast(E e) {
        Node<E> newNode = new Node<E>(last, e, null);
        Node<E> l = last;
        last=newNode;

        if(l==null){
            first=newNode;
        }else {
            l.next = newNode;
        }
        size++;
    }
    /**
     * 查找位置
     */
    public E get(int index){
        if(index<0 || index>size){
            return null;
        }
        return node(index).item;
    }
    /**
     * 获取index位置上的节点
     */
    private Node<E> node(int index){

        //如果index在整个链表的前半部分
        if(index<(size/2)){   //1000 100   10
            Node<E> node=first;
            for (int i = 0; i < index; i++) {
                node=node.next;
            }
            return node;
        }else{
            Node<E> node=last;
            for (int i = size-1; i > index; i--) {
                node=node.prev;
            }
            return node;
        }
    }
    /**
     * 添加数据在index位置
     */
    public void add(int index,E e) {
        if(index<0 || index>size){
            return ;
        }
        if(index==size){
            linkLast(e);
        }else{
            Node<E> target=node(index);//  index=2
            Node<E> pre=target.prev;
            Node<E> newNode=new Node<E>(pre,e,target);

            if(pre==null){
                first=newNode;
                target.prev = newNode;//4
            }else {
                pre.next = newNode;//3
                target.prev = newNode;//4
            }
            size++;
        }
    }
    /**
     * 删除元素
     */
    public void remove(int index){
        Node<E> target=node(index);
        unlinkNode(target);
    }
    private void unlinkNode(Node<E> p) {//index=2
        Node<E> pre=p.prev;
        Node<E> next=p.next;
        if(pre==null){
            first=p.next;
        }else{
            pre.next=p.next;
        }
        if(next==null){
            last=p.prev;
        }else{
            next.prev=p.prev;
        }
        size--;
    }

}

双链表比单链表优秀的地方在于查找的时候可以将数据分为两半，判断要查找的数据在前半段还是在后半段，以此来加快查找速度