• 简单模拟单/双链表实现 LinkedList作业

    接口

    定义MyLink接口，定义抽象方法。

    1. package mylinkedlist;
    2.  
    3. public interface MyLink{
    4.     //返回链表的长度
    5.     int size();
    6.     //判断链表是否为空
    7.     boolean isEmpty();
    8.     //默认在链表尾部添加元素
    9.     boolean add(E e);
    10.     //添加到链表第一个
    11.     boolean addFirst(E e);
    12.     //删除链表中的某个元素
    13.     boolean remove(E o);
    14.     //清空链表
    15.     void clear();
    16.     //在链表的某个位置添加元素
    17.     void add(int index, E element);
    18.     //删除链表中某个位置的元素
    19.     boolean remove(int index);
    20.     //返回链表中某个位置的元素
    21.     E get(int index);
    22.     //将链表中某个位置的元素替换为新元素
    23.     boolean set(int index, E element);
    24.     //查找链表中的某个元素
    25.     int indexOf(Object o);
    26.     //返回链表的字符串表示
    27.     String toString();
    28. }

    单链表实现

    1、定义属性，节点类和构造方法

    实现MyLink接口，定义一个单链表节点内部类，和私有属性。（定义为私有，只向外部暴露方法即可）带头节点head和尾节点last。

    1. public class MySingleLinkedList implements MyLink{
    2.     int size = 0;
    3.     private MyNode head;
    4.     private MyNode last;
    5.     private class MyNode{
    6.         E item;
    7.         MyNode next;
    8.         public MyNode(E element, MyNode next) {
    9.             this.item = element;
    10.             this.next = next;
    11.         }
    12.     }
    13.     public MySingleLinkedList() {
    14.         head = new MyNode<>(null,null);
    15.         head.next = last;
    16.     }
    17. }

    2、重写抽象方法

    1.  @Override
    2.     public int size() {
    3.         return size;
    4.     }
    5.  
    6.     @Override
    7.     public boolean isEmpty() {
    8.         return head.next == last;
    9.     }
    10.     //添加到链表尾部
    11.     @Override
    12.     public boolean add(Object o) {
    13.         MyNode preMyNode = head;
    14.         MyNode newNode = new MyNode(o,last);
    15.         while (preMyNode.next != last){
    16.             preMyNode = preMyNode.next;
    17.         }
    18.         preMyNode.next = newNode;
    19.         size++;
    20.         return true;
    21.     }
    22.  
    23.     @Override
    24.     public boolean addFirst(Object o) {
    25.         MyNode nextMyNode = head.next;
    26.         MyNode newNode = new MyNode(o,nextMyNode);
    27.         head.next = newNode;
    28.         size++;
    29.         return true;
    30.  
    31.     }
    32.  
    33.     @Override
    34.     public boolean remove(Object o) {
    35.         MyNode a = head;
    36.         MyNode b = a.next;
    37.         if(indexOf(o) == -1){
    38.             return false;
    39.         }else{
    40.             for(;b != last;a = a.next){
    41.                 if(b.item.equals(o)){
    42.                     break;
    43.                 }
    44.             }
    45.             a.next = b.next;
    46.             size--;
    47.             return true;
    48.         }
    49.  
    50.     }
    51.  
    52.  
    53.  
    54.     @Override
    55.     public void clear() {
    56.         head.next = last;
    57.         size = 0;
    58.  
    59.     }
    60.     //添加到链表的某个位置
    61.     @Override
    62.     public void add(int index, Object element) {
    63.         if (index < 0 || index > size) {
    64.             throw new IndexOutOfBoundsException("IndexOutOfBounds!!!! Index: "+index+", Size: "+size);
    65.         } else if (index == size-1) {
    66.             add(element);
    67.         } else if (index ==0) {
    68.             addFirst(element);
    69.         } else {
    70.             MyNode preMyNode = head;
    71.             for (int i = 0; i < index; i++) {
    72.                 preMyNode = preMyNode.next;
    73.             }
    74.             MyNode nextMyNode = preMyNode.next;
    75.             MyNode newNode = new MyNode(element, nextMyNode);
    76.             preMyNode.next = newNode;
    77.             size++;
    78.         }
    79.  
    80.     }
    81.  
    82.  
    83.  
    84.     @Override
    85.     public boolean remove(int index) {
    86.         if (index < 0 || index >= size) {
    87.             throw new IndexOutOfBoundsException("IndexOutOfBounds!!!! Index: " + index + ", Size: " + size);
    88.         }else {
    89.             MyNode preMyNode = head;
    90.             for (int i = 0; i < index; i++) {
    91.                 preMyNode = preMyNode.next;
    92.             }
    93.             MyNode nextMyNode = preMyNode.next.next;
    94.             preMyNode.next = nextMyNode;
    95.             size--;
    96.             return true;
    97.         }
    98.  
    99.  
    100.     }
    101.  
    102.     @Override
    103.     public Object get(int index) {
    104.         if (index < 0 || index >= size) {
    105.             throw new IndexOutOfBoundsException("IndexOutOfBounds!!!! Index: "+index+", Size: "+size);
    106.         }else {
    107.             MyNode preMyNode = head.next;
    108.             for (int i = 0; i < index; i++) {
    109.                 preMyNode = preMyNode.next;
    110.             }
    111.             return preMyNode.item;
    112.         }
    113.  
    114.     }
    115.  
    116.     @Override
    117.     public boolean set(int index, Object element) {
    118. if (index < 0 || index >= size) {
    119.             throw new IndexOutOfBoundsException("IndexOutOfBounds!!!! Index: "+index+", Size: "+size);
    120.         }else {
    121.             MyNode preMyNode = head.next;
    122.             for (int i = 0; i < index; i++) {
    123.                 preMyNode = preMyNode.next;
    124.             }
    125.             preMyNode.item = (E) element;
    126.             return true;
    127.         }
    128.  
    129.     }
    130.  
    131.     @Override
    132.     public int indexOf(Object o) {
    133.         MyNode preMyNode = head.next;
    134.         for (int i = 0; i < size; i++) {
    135.             if (preMyNode.item.equals(o)) {
    136.                 return i;
    137.             }
    138.             preMyNode = preMyNode.next;
    139.         }
    140.         return -1;
    141.  
    142.     }
    143.  
    144.     @Override
    145.     public String toString() {
    146.         StringBuilder sb = new StringBuilder();
    147.         sb.append("[");
    148.         MyNode preMyNode = head.next;
    149.         for (int i = 0; i < size; i++) {
    150.             if (i == size - 1) {
    151.                 sb.append(preMyNode.item);
    152.             } else {
    153.                 sb.append(preMyNode.item + ",");
    154.             }
    155.             preMyNode = preMyNode.next;
    156.         }
    157.         sb.append("]");
    158.         return sb.toString();
    159.  
    160.     }

    单链表测试

    测试类

    1. package mylinkedlist;
    2.  
    3. public class MySingleLinkedTest {
    4.     public static void main(String[] args) {
    5.         MySingleLinkedList mySingleLinkedList = new MySingleLinkedList<>();
    6.         mySingleLinkedList.add(1);
    7.         mySingleLinkedList.add(2);
    8.         mySingleLinkedList.add(3);
    9.         mySingleLinkedList.add(4);
    10.         mySingleLinkedList.add(5);
    11.         mySingleLinkedList.add(6);
    12.         System.out.println("=======Test add(E e)=======");
    13.         System.out.println(mySingleLinkedList.toString());
    14.         System.out.println("=======Test size()=======");
    15.         System.out.println("size="+mySingleLinkedList.size());
    16.         System.out.println("=======Test remove(E o) index= 2 =======");
    17.         mySingleLinkedList.remove(2);
    18.         System.out.println(mySingleLinkedList.toString());
    19.         System.out.println("=======Test add(int index, E element) index= 3 value = 66=======");
    20.         mySingleLinkedList.add(3,66);
    21.         System.out.println(mySingleLinkedList.toString());
    22.         System.out.println("=======Test remove(int index) index= 3=======");
    23.         mySingleLinkedList.remove(3);
    24.         System.out.println(mySingleLinkedList.toString());
    25.         System.out.println("=======Test get(int index) index= 3=======");
    26.         System.out.println(mySingleLinkedList.get(3));
    27.         System.out.println("=======Test set(int index, E element)index= 3 value = 88=======");
    28.         mySingleLinkedList.set(3,88);
    29.         System.out.println(mySingleLinkedList.toString());
    30.         System.out.println("=======Test indexOf(Object o)index= 3 value = 88=======");
    31.         System.out.println(mySingleLinkedList.indexOf(88));
    32.         System.out.println("=======Test clear()=======");
    33.         mySingleLinkedList.clear();
    34.         System.out.println(mySingleLinkedList.toString());
    35.     }
    36.  
    37.  
    38. }

    双链表实现

    1、定义属性，节点类和构造方法

    实现MyLink接口，定义一个双链表节点内部类，和私有属性。（定义为私有，只向外部暴露方法即可），带头节点first和尾节点last。

    1. public class MyLinkedList implements MyLink{
    2.     //头节点和为节点不计入链表的长度，也不计入下标！！！！
    3.     private int size = 0;
    4.     private MyNode first;
    5.     private MyNode last;
    6.  
    7.     public MyLinkedList() {
    8.         first = new MyNode<>(null,null,null);
    9.         last = new MyNode<>(first,null,null);
    10.         first.next = last;
    11.     }
    12.  
    13.  
    14.     private class MyNode{
    15.             E item;
    16.             MyNode next;
    17.             MyNode prev;
    18.  
    19.             public MyNode(MyNode prev, E element, MyNode next) {
    20.                 this.item = element;
    21.                 this.next = next;
    22.                 this.prev = prev;
    23.             }
    24.      }
    25. }

    2、重写抽象方法

    1.  @Override
    2.     public int size() {
    3.         return size;
    4.     }
    5.  
    6.     @Override
    7.     public boolean isEmpty() {
    8.         return first.next == last ;
    9.     }
    10.  
    11.     @Override
    12.     public boolean addFirst(E e) {
    13.         MyNode nextMyNode = first.next;
    14.         MyNode newNode = new MyNode(first,e,nextMyNode);
    15.         first.next = newNode;
    16.         nextMyNode.prev = newNode;
    17.         size++;
    18.         return true;
    19.  
    20.     }
    21.  
    22.     //添加到链表尾部
    23.     @Override
    24.     public boolean add(Object e) {
    25.          MyNode preMyNode = last.prev;
    26.          MyNode newNode = new MyNode(preMyNode,e,last);
    27.             last.prev = newNode;
    28.             preMyNode.next = newNode;
    29.             size++;
    30.             return true;
    31.  
    32.     }
    33.  
    34.     @Override
    35.     public boolean remove(E o) {
    36.          MyNode n = first;
    37.      if(indexOf(o) == -1){
    38.          return false;
    39.         }else{
    40.         for(int i = 0;i
    41.             n = n.next;
    42.         }
    43.         MyNode preMyNode = n.prev;
    44.         MyNode nextMyNode = n.next;
    45.         preMyNode.next = nextMyNode;
    46.         nextMyNode.prev = preMyNode;
    47.         size--;
    48.         return true;
    49.      }
    50.     }
    51.  
    52.     @Override
    53.     public void clear() {
    54.         first.next = last;
    55.         last.prev = first;
    56.         size = 0;
    57.     }
    58.  
    59. //添加到链表的某个位置
    60.     @Override
    61.     public void add(int index, E element) {
    62.         if (index < 0 || index >= size) {
    63.             throw new IndexOutOfBoundsException("IndexOutOfBounds!!!! Index: " + index + ", Size: " + size);
    64.         } else if (index == 0) {
    65.             addFirst(element);
    66.         } else if (index == size - 1) {
    67.             add(element);
    68.         } else if (index <= size / 2) {
    69.             MyNode n = first;
    70.             for (int i = 0; i <= index; i++) {
    71.                 n = n.next;
    72.             }
    73.             MyNode preMyNode = n.prev;
    74.             MyNode newNode = new MyNode(preMyNode, element, n);
    75.             preMyNode.next = newNode;
    76.             n.prev = newNode;
    77.             size++;
    78.         } else if (index > size / 2) {
    79.             MyNode n = last;
    80.             for (int i = size; i > index; i--) {
    81.                 n = n.prev;
    82.             }
    83.             MyNode preMyNode = n.prev;
    84.             MyNode newNode = new MyNode(preMyNode, element, n);
    85.             preMyNode.next = newNode;
    86.             n.prev = newNode;
    87.             size++;
    88.         }
    89.  
    90.     }
    91.  
    92.     @Override
    93.     public boolean remove(int index) {
    94.          if (index < 0 || index >= size) {
    95.              throw new IndexOutOfBoundsException("IndexOutOfBounds!!!! Index: " + index + ", Size: " + size);
    96.          }else {
    97.              MyNode n = first;
    98.              for(int i = 0;i<=index;i++){
    99.                  n = n.next;
    100.              }
    101.              MyNode preMyNode = n.prev;
    102.              MyNode nextMyNode = n.next;
    103.              preMyNode.next = nextMyNode;
    104.              nextMyNode.prev = preMyNode;
    105.              size--;
    106.              return true;
    107.          }
    108.  
    109.     }
    110.  
    111.     @Override
    112.     public E get(int index) {
    113.         if (index < 0 || index >= size) {
    114.             throw new IndexOutOfBoundsException("IndexOutOfBounds!!!! Index: " + index + ", Size: " + size);
    115.         }else if(index <= size/2){
    116.             MyNode n = first;
    117.             for(int i = 0;i<=index;i++){
    118.                 n = n.next;
    119.             }
    120.             return (E) n.item;
    121.         } else if (index > size/2){
    122.             MyNode n = last;
    123.             for(int i = size;i>index;i--){
    124.                 n = n.prev;
    125.             }
    126.             return (E) n.item;
    127.  
    128.         }
    129.         return null;
    130.     }
    131.  
    132.     @Override
    133.     public boolean set(int index, E element) {
    134.         if (index < 0 || index >= size) {
    135.             throw new IndexOutOfBoundsException("IndexOutOfBounds!!!! Index: " + index + ", Size: " + size);
    136.         }else if(index <= size/2){
    137.             MyNode n = first;
    138.             for(int i = 0;i<=index;i++){
    139.                 n = n.next;
    140.             }
    141.             n.item = element;
    142.             return true;
    143.         } else if (index > size/2){
    144.             MyNode n = last;
    145.             for(int i = size;i>index;i--){
    146.                 n = n.prev;
    147.             }
    148.             n.item = element;
    149.             return true;
    150.  
    151.         }
    152.         return false;
    153.     }
    154.  
    155.     @Override
    156.     public int indexOf(Object o) {
    157.         MyNode n = first.next;
    158.         int index = 0;
    159.         while(n.next != null){
    160.             if(n.item.equals(o)){
    161.                 return index;
    162.             }
    163.             n = n.next;
    164.             index++;
    165.         }
    166.         return -1;
    167.     }
    168.  
    169.     @Override
    170.     public String toString() {
    171.         MyNode n = first.next;
    172.         String str = "[";
    173.         if(first.next == last){
    174.             return "[]";
    175.         }
    176.       for (int i = 1;i
    177.           str += n.item + ",";
    178.           n = n.next;
    179.       }
    180.         str += n.item + "]";
    181.         return str;
    182.  
    183.     }

    双链表测试

    测试类

    1. package mylinkedlist;
    2.  
    3. import org.junit.jupiter.api.Test;
    4.  
    5. public class MyLinnkedListTest {
    6.     public static void main(String[] args) {
    7.         MyLinkedList myLinnkedListTest = new MyLinkedList<>();
    8.         myLinnkedListTest.add(1);
    9.         myLinnkedListTest.add(2);
    10.         myLinnkedListTest.add(3);
    11.         myLinnkedListTest.add(4);
    12.         myLinnkedListTest.add(5);
    13.         myLinnkedListTest.add(6);
    14.         System.out.println("=======Test add(E e)=======");
    15.         System.out.println(myLinnkedListTest.toString());
    16.         System.out.println("=======Test size()=======");
    17.         System.out.println("size="+myLinnkedListTest.size());
    18.         System.out.println("=======Test remove(E o) index= 2 =======");
    19.         myLinnkedListTest.remove(2);
    20.         System.out.println(myLinnkedListTest.toString());
    21.         System.out.println("=======Test add(int index, E element) index= 3 value = 66=======");
    22.         myLinnkedListTest.add(3,66);
    23.         System.out.println(myLinnkedListTest.toString());
    24.         System.out.println("=======Test remove(int index) index= 3=======");
    25.         myLinnkedListTest.remove(3);
    26.         System.out.println(myLinnkedListTest.toString());
    27.         System.out.println("=======Test get(int index) index= 3=======");
    28.         System.out.println(myLinnkedListTest.get(3));
    29.         System.out.println("=======Test set(int index, E element)index= 3 value = 88=======");
    30.         myLinnkedListTest.set(3,88);
    31.         System.out.println(myLinnkedListTest.toString());
    32.         System.out.println("=======Test indexOf(Object o)index= 3 value = 88=======");
    33.         System.out.println(myLinnkedListTest.indexOf(88));
    34.         System.out.println("=======Test clear()=======");
    35.         myLinnkedListTest.clear();
    36.         System.out.println(myLinnkedListTest.toString());
    37.  
    38.  
    39.     }
    40. }

    作业

    作业一

    第一题

    有一个整数顺序表L。设计一个尽可能高效的算法删除其中所有值为负整数的元素（假设L中值为负整数的元素可能有多个），删除后元素的相对次序不改变。并给出算法的时间和空间复杂度。例如，L=（1，2，-1，-2，3，-3），删除后L=（1，2，3）。

    代码实现
    1. @Test
    2.     public void workOne (){
    3.         MyLinkedList integerMyLinkedList = new MyLinkedList<>();
    4.         integerMyLinkedList.add(1);
    5.         integerMyLinkedList.add(2);
    6.         integerMyLinkedList.add(-1);
    7.         integerMyLinkedList.add(-2);
    8.         integerMyLinkedList.add(3);
    9.         integerMyLinkedList.add(-3);
    10.         System.out.println("=======before=======");
    11.         System.out.println(integerMyLinkedList);
    12.         System.out.println("=======after=======");
    13.         System.out.println(deleteNegative(integerMyLinkedList));
    14.     }
    15.  
    16.     public MyLinkedList deleteNegative(MyLinkedList integerMyLinkedList){
    17.         MyLinkedList integerMyLinkedList1 = new MyLinkedList<>();
    18.         for (int i = 0; i < integerMyLinkedList.size(); i++) {
    19.             if (integerMyLinkedList.get(i) >= 0) {
    20.                 integerMyLinkedList1.add(integerMyLinkedList.get(i));
    21.             }
    22.         }
    23.         return integerMyLinkedList1;
    24.     }
    复杂度分析

    时间复杂度：add方法为O(1),get方法为O（n），所以整体为O（n^n)

    空间复杂度O（n）

    第二题

    有一个整数顺序表L。设计一个尽可能高效的算法删除表中值大于等于x且小于等于y的所有元素（x≤y），删除后元素的相对次序不改变。并给出算法的时间和空间复杂度。例如，L=（4，2，1，5，3，6，4），x=2，y=4，删除后L=（1，5，6）。

    代码实现
    1. @Test
    2.     public void workTwo (){
    3.         MyLinkedList integerMyLinkedList = new MyLinkedList<>();
    4.         integerMyLinkedList.add(4);
    5.         integerMyLinkedList.add(2);
    6.         integerMyLinkedList.add(1);
    7.         integerMyLinkedList.add(5);
    8.         integerMyLinkedList.add(3);
    9.         integerMyLinkedList.add(6);
    10.         integerMyLinkedList.add(4);
    11.         System.out.println("=======before=======");
    12.         System.out.println(integerMyLinkedList);
    13.         System.out.println("=======after=======");
    14.         System.out.println(deleteOnCondition(integerMyLinkedList,2,4));
    15.     }
    16.  
    17.     public MyLinkedList deleteOnCondition(MyLinkedList integerMyLinkedList,int min,int max){
    18.         MyLinkedList integerMyLinkedList1 = new MyLinkedList<>();
    19.         for (int i = 0; i < integerMyLinkedList.size(); i++) {
    20.             if (integerMyLinkedList.get(i) < min || integerMyLinkedList.get(i) > max) {
    21.                 integerMyLinkedList1.add(integerMyLinkedList.get(i));
    22.             }
    23.         }
    24.         return integerMyLinkedList1;
    25.     }
    复杂度分析

    时间复杂度：get方法为O（n），所以整体为O（n^n)

    空间复杂度O（n）

    作业二

    第一题

    有一个整数单链表L，设计一个尽可能高效算法将所有负整数的元素移到其他元素的前面。例如，L=（1，2，-1，-2，3，-3，4），移动后L=（-1，-2，-3，1，2，3，4）。

    代码实现
    1.  @Test
    2.     public void workOne (){
    3.         MySingleLinkedList integerMyLinkedList = new MySingleLinkedList<>();
    4.         integerMyLinkedList.add(1);
    5.         integerMyLinkedList.add(2);
    6.         integerMyLinkedList.add(-1);
    7.         integerMyLinkedList.add(-2);
    8.         integerMyLinkedList.add(3);
    9.         integerMyLinkedList.add(-3);
    10.         integerMyLinkedList.add(4);
    11.         System.out.println("=======before=======");
    12.         System.out.println(integerMyLinkedList);
    13.         System.out.println("=======after=======");
    14.         System.out.println(moveNegativeFoward(integerMyLinkedList));
    15.     }
    16.  
    17.     private MySingleLinkedList moveNegativeFoward(MySingleLinkedList integerMyLinkedList) {
    18.         MySingleLinkedList mySingleLinkedList = new MySingleLinkedList();
    19.         for (int i = 0; i < integerMyLinkedList.size(); i++) {
    20.             if ((int)integerMyLinkedList.get(i) < 0) {
    21.                 mySingleLinkedList.addFirst(integerMyLinkedList.get(i));
    22.             }else {
    23.                 mySingleLinkedList.add(integerMyLinkedList.get(i));
    24.             }
    25.         }
    26.         return mySingleLinkedList;
    27.     }
    复杂度分析

    时间复杂度：addFirst方法为O(1),add方法为O(n),get方法为O（n），所以整体为O（n^n)

    空间复杂度O（n）

    第二题

    有两个集合采用整数单链表A、B存储，设计一个算法求两个集合的差集C，C仍然用单链表存储。并给出算法的时间和空间复杂度。例如A=（1，3，2），B=（5，1，4，2），差集C=（3）。

    代码实现
    1.  @Test
    2.     public void workTwo (){
    3.         MySingleLinkedList integerMyLinkedList1 = new MySingleLinkedList<>();
    4.         MySingleLinkedList integerMyLinkedList2 = new MySingleLinkedList<>();
    5.         integerMyLinkedList1.add(1);
    6.         integerMyLinkedList1.add(3);
    7.         integerMyLinkedList1.add(2);
    8.         integerMyLinkedList2.add(5);
    9.         integerMyLinkedList2.add(1);
    10.         integerMyLinkedList2.add(4);
    11.         integerMyLinkedList2.add(2);
    12.         System.out.println("=======before=======");
    13.         System.out.println(integerMyLinkedList1);
    14.         System.out.println(integerMyLinkedList2);
    15.         System.out.println("=======result=======");
    16.         System.out.println(deferenceSet(integerMyLinkedList1,integerMyLinkedList2));
    17.     }
    18.  
    19.     private MySingleLinkedList deferenceSet(MySingleLinkedList integerMyLinkedList1, MySingleLinkedList integerMyLinkedList2) {
    20.         MySingleLinkedList mySingleLinkedList = new MySingleLinkedList();
    21.        for (int i = 0;i < integerMyLinkedList1.size;i++){
    22.            for (int j = 0;j < integerMyLinkedList2.size;j++) {
    23.                if (integerMyLinkedList1.get(i) == integerMyLinkedList2.get(j)) {
    24.                    break;
    25.                } else if (j == integerMyLinkedList2.size - 1) {
    26.                    mySingleLinkedList.add(integerMyLinkedList1.get(i));
    27.                }
    28.            }
    29.        }
    30.         return mySingleLinkedList;
    31.     }
    复杂度分析

    时间复杂度：add方法为O(n),get方法为O（n），所以整体为O（n^n^n)

    空间复杂度O（n）

    仓库

    https://gitee.com/BenChuat/algorithm-exercise.git

  • 相关阅读:
    精英反向黄金正弦鲸鱼算法-附代码
    日均请求量1.6万亿次背后，DNSPod的秘密-国密DoH篇
    java学习之包
    数值常量如何转化为内存地址？
    第七章物理层
    网易数帆自主创新再获认可：轻舟微服务入选信创技术图谱
    计算机网络：帧中继的概念
    4.2.3 安装Windows操作系统步骤
    前端基础入门之JS的call、apply和argument
    嵌入式C语言自我修养《内存堆栈管理》学习笔记
  • 原文地址：https://blog.csdn.net/m0_73065928/article/details/133244898