数据结构(一)线性表

1.数据结构基础

1.什么是数据结构

数据结构是计算机存储、组织数据的方式。
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。
数据结构往往同高效的检索算法和索引技术有关。
可以使用逻辑结构描述数据结构

2. 逻辑结构(描述数据与数据之间的关系)

1. 集合结构
   image
2. 线性结构
   image
   
3. 树形结构
   image
4. 图形结构
   image
   
   逻辑结构需要保存在加算计中,称为存储结构

3.存储结构(重点)

1. 表
2. 堆栈
3. 队列
4. 数组
5. 树
6. 二叉树
7. 图

4.什么是算法

用来解决问题的方法,一个算法的好坏可以用空间复杂度与时间复杂度来衡量


程序好坏=空间复杂度+时间复杂度+应用场景

1.空间复杂度

算法运行占用多少运行内存

2.时间复杂度(主要考虑对象)

算法的效率O(n),关键代码的执行次数

1. 时间复杂度O(n) = n*n+n+1

function1() {
   for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j ++) {
        // dosomething;
        }   
    }

    for(int i = 0; i < n; i++) {
    //dosomething   
    }

   // dosomething
}

2.O(n) = n*n

function2() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j ++) {
          // dosomething;
        } 
}

上面俩中算法的时间复杂度是相等的(n=>无穷大),考虑n的几次方

3.使用数据交换看程序好坏(考虑场景)

俩个数据交换的几种方式


1.可读性最好(不影响用户体验情况下，优先选择可读性最好的情况下)

    int a = 5;
    int b = 6;
    int t = a;
    a = b;
    b = t;

2.相比于1节省了一个空间复杂度,但无法做对象的交换

    a = a + b;
    b = a - b;
    a = a - b;

3.性能最优,任何情况下都能用,但可读性低,主要应用在无人机,车载等空间占用少,性能要求高的情况下

    a = a ^ b;
    b = a ^ b;
    a = a ^ b;

2.线性表

1.顺序存储结构(顺序表)

• 存储是连续的,ArrayList就是顺序表
  image
  image
  a1是a2的前驱,ai+1是ai的后继,a1没有前驱,a2没有后继,n是线性表长度,n=0时线性表是空表
  
  
• 判断图中班级是不是顺序表 image
  图中的班级表是顺序表,数组都是连续的存储空间
• 向数组指定位置添加数据

    int index = 1;
    int data = 2;
    int array[] = {1, 3, 4, 5, 6, 7};
    array[array.length] = 0;
    for (int i = array.length - 1; i > index; i++) {
        array[i] = array[i - 1];
    }
    array[index]=data;

这种插入的优点是尾插入效率高,支持随机访问,缺点是中间插入或者删除效率低

纸牌排序问题

1. 定义纸牌类

    public int pokerColors;//花色
    public int cardPoints;//点数

    public Cards(int pokerColors, int cardPoints) {
        this.pokerColors = pokerColors;
        this.cardPoints = cardPoints;
    }
    //提供一个方法，用来比较对象的大小
    @Override
    public int compareTo(@NonNull Object o) {
        Cards c=(Cards)o;
        if(this.cardPoints>c.cardPoints){
            return 1;
        }else if(this.cardPoints<c.cardPoints){
            return -1;
        }
        if(this.pokerColors>c.pokerColors){
            return 1;
        }else if(this.pokerColors<c.pokerColors){
            return -1;
        }
        return 0;
    }

2. 使用sort排序

        Cards[] cards = {
                new Cards(3, 9),
                new Cards(2, 7),
                new Cards(1, 1),
                new Cards(3, 3),
                new Cards(4, 4),
                new Cards(2, 5),
                new Cards(3, 6),
                new Cards(3, 7),
        };
        //效率很低，执行代码至少在一百行以上
//        Arrays.sort(cards);

3. 蛮力法进行排序(也称为穷举法或枚举法)
   
   在数据量足够少的情况下是所有算法里效率最高的
   
   在数据量趋于无穷大的时候效率是最低的
4. 冒泡排序(蛮力法的一种)
   
   应用于数据量足够小,如炸金花,斗牛游戏中的牌排序(个位数内排序)
   
   时间复杂度O(n)=n*(n-1)/2

    public static int[] bubbleSort(int[] array) {
        for (int i = array.length - 1; i > 0; i--) {
            boolean flag = true;
            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;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
        return array;
    }

5. 选择排序
   
   学习快速排序的基础

    //选择排序
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int index = i;
            for (int j = i + 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;
                System.out.println(index);
            }
        }
    }

2.链式存储结构

1.ArrayList分析

1. 创建ArrayList会创建一个空数组和一个size大小
2. 调用add添加元素时

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);//检测数组容量,如果满足继续添加,不满足就扩展容量
        Increments modCount!!
        elementData[size++] = e;
        return true;
    }

3. 扩展容量

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//右移1:用之前的容量加上之前容量的一半
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);//把原来的数据拷贝一下
    }

4. 向指定位置添加元素

    public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);//index后面的数据copy一份添加到index+1的位置,在把element添加到index的位置
        elementData[index] = element;
        size++;
    }

2.链表

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

单链表是由很多的节点组织起来的,MessageQueue就是单链表

1. 节点

• 每个节点分成俩块,数据域和指针域,数据域是可以有很多数据的
• 数据域都有对自己的引用,例如Message中有Message引用(Message消息就是一个节点)
  image
  
  删除102只需要把101中的指向改成103
  
  插入也是改响应的指向
  
  Handler中的死循环,p=p.next就是取下一个message
• MessageQueue插入enqueueMessage(Message msg,long when),删除next()

2. 链表排序麻将(适合数据量在二三十个左右,空间占用少)
   
   
   使用链表先对点数进行排序,再使用链表对花色进行排序 image

    @Test
    public void testMj(){
        LinkedList<Majiang> linkedList = new LinkedList<>();
        linkedList.add(new Majiang(3,1));
        linkedList.add(new Majiang(1,1));
        linkedList.add(new Majiang(2,1));
        linkedList.add(new Majiang(3,3));
        linkedList.add(new Majiang(4,1));
        linkedList.add(new Majiang(3,6));
        linkedList.add(new Majiang(3,1));
        linkedList.add(new Majiang(2,2));
        linkedList.add(new Majiang(1,3));
        linkedList.add(new Majiang(2,4));
        linkedList.add(new Majiang(3,5));
        linkedList.add(new Majiang(4,6));
        linkedList.add(new Majiang(3,9));
        linkedList.add(new Majiang(2,8));
        linkedList.add(new Majiang(1,7));
        linkedList.add(new Majiang(3,6));
        raidxSort(linkedList);
    }

    /**
     * 麻将排序，参数可以是任意的链表
     *
     * @param list
     */
    public static void raidxSort(LinkedList<Majiang> list) {
        //先对点数进行分组
        LinkedList[] rankList = new LinkedList[9];
        for (int i = 0; i < rankList.length; i++) {
            rankList[i] = new LinkedList<>();
        }
        while (list.size() > 0) {
            //取一个
            Majiang majiang = list.remove();
            //放到组中，下表=点数-1的
            rankList[majiang.rank - 1].add(majiang);
        }
        //把九组合并在一起
        for (int i = 0; i < rankList.length; i++) {
            list.addAll(rankList[i]);
        }
        //花色进行分组
        LinkedList[] suitList = new LinkedList[4];
        for (int i = 0; i < suitList.length; i++) {
            suitList[i] = new LinkedList();
        }
        //把数据一个一个放到对应的花色链表中
        while (list.size() > 0) {
            Majiang majiang = list.remove();
            //下表=点数-1
            suitList[majiang.suit - 1].add(majiang);
        }
        for (int i = 0; i < suitList.length; i++) {
            list.addAll(suitList[i]);
        }
        for (Majiang majiang : list) {
            System.out.print(majiang.toString());
        }
    }

3. 单循环链表

围成一个圈,末尾一个指向第一个

3.双链表

解释:一个节点带俩个指针


应用:LinkedList

image

优点:不仅可以向后查,还可以向前查,增加查询效率

5.双向循环链表

最后一个循环指向第一个

3.手写LinkedList

public class LinkedList<E> {

    /**
     * 节点
     *
     * @param <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;
        }
    }

    //头节点
    Node<E> first;
    //尾节点
    Node<E> last;
    //节点个数
    int size;

    /**
     * 添加数据
     *
     * @param e
     */
    public void add(E e) {
        linkLast(e);
    }

    /**
     * 添加数据在index位置
     *
     * @param index
     * @param e
     */
    public void add(int index, E e) {
        if (index < 0 || index > size) {
            return;
        }
        if (index == size) {
            linkLast(e);
        } else {
            Node<E> target = node(index);
            Node<E> prevNode = target.prev;
            Node<E> newNode = new Node<E>(prevNode, e, target);
            if (prevNode == null) {
                first = newNode;
                target.prev = newNode;
            } else {
                prevNode.next = newNode;
                target.prev = newNode;
            }
            size++;
        }
    }

    /**
     * 添加到最后
     *
     * @param e
     */
    public 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 >> 1) {
            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;
        }

    }

    /**
     * 删除元素
     */
    public void remove(int index) {
        Node<E> target = node(index);
        unLinkNode(target);
    }

    private void unLinkNode(Node<E> node) {
        Node<E> prev = node.prev;
        Node<E> next = node.next;
        if (prev == null) {
            first = node.next;
        } else {
            prev.next = node.next;
        }
        if (next == null) {
            last = next.prev;
        } else {
            next.prev = node.prev;
        }
        size--;
    }

}

测试

public class test {
    private static final String TAG = "test";
    @Test
    public void test() {
        LinkedList<Object> list = new LinkedList<>();
        list.add("3");
        list.add("2");
        list.add("4");
        list.add("6");
        list.add("1");
        for (int i = 0; i < list.size; i++) {
            System.out.print(" "+list.get(i).toString());
        }
        System.out.println();
        list.add(1, "10");
        for (int i = 0; i < list.size; i++) {
            System.out.print(" "+list.get(i).toString());
        }
        System.out.println();
        list.add(0, "9");
        for (int i = 0; i < list.size; i++) {
            System.out.print(" "+list.get(i).toString());
        }
        System.out.println();
        list.remove(3);
        for (int i = 0; i < list.size; i++) {
            System.out.print(" "+list.get(i).toString());
        }
    }

}

输出结果

 3 2 4 6 1
 3 10 2 4 6 1
 9 3 10 2 4 6 1
 9 3 10 4 6 1