软件设计师---数据结构上_双循环的时间复杂度

考察范围和比重

数据结构（大头6）+算法（小头3）
题目分布于57-65

大O表示法

对于 在循环和递归以外的代码，都看成常数阶O(1)
时间复杂度T(n)和问题规模n有关（循环次数和递归的次数）

分析代码的时间复杂度（考察的比较多）

非递归形式
问题规模和执行次数的关系

1. O(1)代码里面没有循环、递归
2. O(log2n)
   
   循环的判断是比循环多一次
   
   总计算步骤为：
   转换为大O表示法为：
3. O(n)
   循环的判断是比循环多一次

总运算次数为：
大O表示法为：
4. O(nlog2n)
分析思路是拆分来分析
看成线性阶套对数阶

对于最内层的循环次数：嵌套用乘法


总循环次数是：

加法看高阶，所以答案是线性对数阶O（nlog2n）
总结：嵌套循环只需关注最内层的循环的循环体时间复杂度（就代表了整个算法的时间复杂度）
5. O（n^2）
再次说明：嵌套循环只需关注最内层的循环的循环体时间复杂度（就代表了整个算法的时间复杂度）
O(n^3)

总结：计算时间复杂度只需要看最内层的循环的循环体时间复杂度

---

例子

分析代码的空间复杂度（考察的较少）

非递归方式
问题规模和存储空间的关系

---

例子如下

真题

A

A
代码实现如下

package dataStructure.one;
//2011年下半年64

public class a {
    public static void main(String[] args) {
        int [] A = {-1,0,1,-1,0,1};
        int n = A.length;
        int n1 = 0;//统计-1的数目
        int n2 = 0;//统计0的数目
        int n3 = 0;//统计1的数目
        //开始统计-1,0,1的数目
        for(int i=0;i<n;i++){
            if(A[i]==-1){
                n1++;
            }
            if(A[i]==0){
                n2++;
            }
            if(A[i]==1){
                n3++;
            }
        }
        //将数组按照统计的-1，0，1数目来赋值(下标从0开始所以全部按照逻辑图的值减1)
        for(int i=0;i<n1;i++){
            A[i]=-1;
        }
        for(int j=n1;j<n1+n2;j++){
            A[j]=0;
        }
        for(int k=n1+n2;k<n;k++){
            A[k]=1;
        }
        //输出看看
        for (int a:A){
            System.out.println(a);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

时间复杂度是O(n)

空间复杂度是O(1)

开辟的存储空间n1,n2,n3和问题规模之间没有关系

(上面俩个是题目条件，我们看空间复杂度看的是n1,n2,n3)

C
代码实现如下（我写代码的时候，交换A[i]和A[j]没有在条件if(i<j)下，所以错了）

package dataStructure.one;
public class b {
    public static void main(String[] args) {
        int [] A = {-1,-3,3,1,-2,2};
        int n = A.length;
        int i = 0;
        int j = n-1;
        //i向右移动，j向左移动，直到俩个重合，就完成了。
        while (i<j){
            while (A[i]<0){
                i = i+1;
            }
            while (A[j]>0){
                j = j-1;
            }
            //到这一步的时候,i指向的是正数，j指向的是负数，就交换他们的位置
            if(i<j){
                int temp;
                temp = A[i];
                A[i] = A[j];
                A[j] = temp;
            }
            //然后就开始下一轮的交换。。。
        }
        for (int a:A){
            System.out.println(a);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

时间复杂度就是遍历了长度为n的数组O(n)
空间复杂度就是定了了俩个变量O(1)

D
渐进分析就是时间复杂度分析

渐进符号

---

例子

解题方法：

1. 将10n²+4n+2估算，化为：n²
2. 对于（1）,O(n²)>=n²,成立； 对于（2），O(n³)>=n²,成立；对于（3），O(n)>=n²,不成立
3. 对于（4），Ω(n²)<=n²,成立；对于（5），Ω(n³)<=n²,不成立； 对于（6），Ω(n)<=n²,成立
   对于（7）成立

对于（8），（9）不能同时满足俩个，所以不成立。

C

递归的时间复杂度和空间复杂度

递归：自己调用自己。。

每次递归时间复杂度不变的情况

---

例如，求n的阶乘。

package dataStructure.one;
//求n的阶乘
public class c {

    public static int func(int n){
        if(n==1){
            return 1;
        }
        return n*func(n-1);
    }

    public static void main(String[] args) {
        int result = func(5);
        System.out.println(result);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

递归的时间复杂度：递归调用的次数x每次递归的时间复杂度

递归调用的空间复杂度：递归调用的次数x每次递归的空间复杂度

---

例如：

---

例子

时间复杂度：O(log2ⁿ)
空间复杂度：O(log2ⁿ)
先求递归调用的出口，也就是一共递归调用多少次

也就是：

求出x，就是递归调用的总次数

由于本来在一次递归中，时间复杂度和空间复杂度都是O(1),所以总的时间或空间复杂度都是O(log2ⁿ)

每次递归时间复杂度都不同的情况

---

例子

分析时间复杂度：
递归调用n次，但每次递归执行的循环次数不一样
总循环次数有等差数列求和公式得到：
只保留最高阶的项，时间复杂度为O(n²)

时间复杂度为：O(n²)
分析空间复杂度
空间复杂度为O(n)，因为每次递归，开辟的存储空间的空间复杂度相同，所以可以用之前的公式：
O(n)xO(1) = O(n)

---

例子

分析空间复杂度：

每次递归的空间复杂度都不一样。。
把所有的空间复杂度加起来：

所有，空间复杂度为:O(n²)

用主方法求递归式的时间复杂度

题目多考察定理1和定理2

---

例子

考察（1）和（2）

就是先算出logb^a的值，看套公式（1）还是（2）。
如果得到

就套用（1）求时间复杂度
如果得到（渐进紧致界括号内的阶要和f括号内的阶完全一样才行）这是之前渐进符号的定义

就套用（2）求时间复杂度

真题

B
自己调用自己：递归式
递归调用n次
并且每次递归的执行次数还不一样

直接求出所有的执行次数(n+1)n/2，时间复杂度为o(n²)

A

A

A

C,C

对于第二问：直接n=16,则T(n)=O(n²)就是256

D.C

线性结构

线性表

1. 顺序存储（顺序表）
2. 链式存储（链表）

顺序表

就是用数组实现顺序存储的物理结构（线性表是逻辑结构）

---

等概率下插入元素，需要移动元素个数的数学期望：

表长n是数组中当前元素个数是n

---

等概率下删除元素，需要移动元素个数的数学期望：

代码实现顺序存储

package dataStructure.SequenceList;

public class SequenceList {
    final int N = 10;  //最大容量

    int[] a;
    int n; //当前表长

    void init(){
        a = new int[N];
        for (int i = 0;i<N/2;i++){
            a[i] = i+1;
        }
        n = N/2;

        for (int i =0;i<n;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        SequenceList list = new SequenceList();

        list.init();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

插入

package dataStructure.SequenceList;

public class SequenceList {
    final int N = 10;  //最大容量

    int[] a;
    int n; //当前表长

    void init(){
        a = new int[N];
        for (int i = 0;i<N/2;i++){
            a[i] = i+1;
        }
        n = N/2;

        for (int i =0;i<n;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }

    /*
    * k是实际的位置   从1开始到n (n+1是最后的一个插入位置)
    * */
    void insert(int k,int x){
        if(k<1||k>n+1) return;

        for(int i =n;i>=k;i--){
            a[i] = a[i-1];
        }
        a[k-1] = x;
        n++;
    }

    void show(){
        for (int i=0;i<n;i++){
            System.out.print(a[i]+"  ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        SequenceList list = new SequenceList();

        list.init();
        list.insert(3,100);
        list.insert(0,11);
        list.show();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

---

分析时间复杂度

删除

package dataStructure.SequenceList;

public class SequenceList {
    final int N = 10;  //最大容量

    int[] a;
    int n; //当前表长

    void init(){
        a = new int[N];
        for (int i = 0;i<N/2;i++){
            a[i] = i+1;
        }
        n = N/2;

        for (int i =0;i<n;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }

    /*
    * k是实际的位置   从1开始到n (n+1是最后的一个插入位置)
    * */
    void insert(int k,int x){
        if(k<1||k>n+1) return;

        for(int i =n;i>=k;i--){
            a[i] = a[i-1];
        }
        a[k-1] = x;
        n++;
    }

    /*
    * n也是实际的位置
    * */
    void delete(int k){
        if(k<1||k>n) return;

        //后面的元素向前移动
        for(int i = k;i<n;i++){
            a[i-1] = a[i];
        }
        n--;

    }

    void show(){
        for (int i=0;i<n;i++){
            System.out.print(a[i]+"  ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        SequenceList list = new SequenceList();

        list.init();
        list.insert(3,100);
        list.insert(0,11);
        list.show();
        list.delete(1);
        list.show();
        list.delete(6);
        list.show();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

---

分析时间复杂度

查找

package dataStructure.SequenceList;

public class SequenceList {
    final int N = 10;  //最大容量

    int[] a;
    int n; //当前表长

    void init(){
        a = new int[N];
        for (int i = 0;i<N/2;i++){
            a[i] = i+1;
        }
        n = N/2;

        for (int i =0;i<n;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }

    /*
    * k是实际的位置   从1开始到n (n+1是最后的一个插入位置)
    * */
    void insert(int k,int x){
        if(k<1||k>n+1) return;

        for(int i =n;i>=k;i--){
            a[i] = a[i-1];
        }
        a[k-1] = x;
        n++;
    }

    /*
    * n也是实际的位置
    * */
    void delete(int k){
        if(k<1||k>n) return;

        //后面的元素向前移动
        for(int i = k;i<n;i++){
            a[i-1] = a[i];
        }
        n--;

    }

    int getElements(int k){
        if(k<1||k>n){
            return -1;
        }
        return a[k-1];
    }

    void show(){
        for (int i=0;i<n;i++){
            System.out.print(a[i]+"  ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        SequenceList list = new SequenceList();

        list.init();
        list.insert(3,100);
        list.insert(0,11);
        list.show();
        list.delete(1);
        list.show();
        list.delete(6);
        list.show();
        System.out.println(list.getElements(1));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

链表

代码实现单链表

不带头节点

不带头节点初始化

package dataStructure.LinkList;

class Node{
    int data;
    Node next;

    Node(int data){
        this.data = data;
    }
}

public class LinkList {
    Node list; //头指针

    void init(){
        Node n1 = new Node(1);
        Node n2 =  new Node(2);
        Node n3 = new Node(3);

        list = n1; //头指针指向头节点
        n1.next = n2;
        n2.next = n3;
    }

    void printList(){
        Node p = list; //头指针
        while (p!=null){
            System.out.println(p.data+" ");
            p = p.next;
        }
        System.out.println();

    }

    public static void main(String[] args) {
        LinkList ll = new LinkList();

        ll.init();
        ll.printList();
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

不带头节点插入（k位置的前面插入）

相比带头节点的插入，增加k=1的情况处理（因为k=1，按照之前的判断逻辑就找不到k之前的节点了，不能完成k位置的前面插入）

package dataStructure.LinkList;
//不带头节点
class Node{
    int data;
    Node next;

    Node(int data){
        this.data = data;
    }
}

public class LinkList {
    Node list; //头指针

    void init(){
        Node n1 = new Node(1);
        Node n2 =  new Node(2);
        Node n3 = new Node(3);

        list = n1; //头指针指向头节点
        n1.next = n2;
        n2.next = n3;
    }

    boolean insertOld(int k ,Node node){
        if(k<1) return false;

        //第一个元素
        int i = 1;
        Node p =list;
        while (i<k-1&&p!=null){
            i++;
            p = p.next;
        }

        if(p==null) return false;

        node.next = p.next;
        p.next = node;

        return true;
    }

    boolean insert(int k ,Node node){
        if(k<1) return false;

        if(k==1){
            node.next = list;
            list = node;
            return true;
        }

        //第一个元素
        int i = 1;
        Node p =list;
        while (i<k-1&&p!=null){
            i++;
            p = p.next;
        }

        if(p==null) return false;

        node.next = p.next;
        p.next = node;

        return true;
    }


    void printList(){
        Node p = list; //头指针
        while (p!=null){
            System.out.println(p.data+" ");
            p = p.next;
        }
        System.out.println();

    }

    public static void main(String[] args) {
        LinkList ll = new LinkList();

        ll.init();
        ll.printList();

        //之前插入
        ll.insertOld(4,new Node(4));
        ll.printList();
        //之前插入
        ll.insertOld(2,new Node(22));
        ll.printList();
        //如果是第一个位置，无法找到1前面的位置，会导致在后面插入了。。
        ll.insertOld(1,new Node(11));
        ll.printList();
        //1的前面插入
        ll.insert(1,new Node(111));
        ll.printList();

    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

优化一下代码逻辑，用变量存储表长。。

---

时间复杂度

不带头节点删除

package dataStructure.LinkList;
//不带头节点
class Node{
    int data;
    Node next;

    Node(int data){
        this.data = data;
    }
}

public class LinkList {
    Node list; //头指针

    void init(){
        Node n1 = new Node(1);
        Node n2 =  new Node(2);
        Node n3 = new Node(3);

        list = n1; //头指针指向头节点
        n1.next = n2;
        n2.next = n3;
    }

    boolean insertOld(int k ,Node node){
        if(k<1) return false;

        //第一个元素
        int i = 1;
        Node p =list;
        while (i<k-1&&p!=null){
            i++;
            p = p.next;
        }

        if(p==null) return false;

        node.next = p.next;
        p.next = node;

        return true;
    }

    boolean insert(int k ,Node node){
        if(k<1) return false;

        if(k==1){
            node.next = list;
            list = node;
            return true;
        }

        //第一个元素
        int i = 1;
        Node p =list;
        while (i<k-1&&p!=null){
            i++;
            p = p.next;
        }

        if(p==null) return false;

        node.next = p.next;
        p.next = node;

        return true;
    }

    //k也是实际位置
    boolean delete(int k){
        if(k<1) return false;

        //删除第一个节点
        if(k==1){
            list = list.next;
            return true;
        }

        int i = 1;
        Node p = list;//指向第一个节点
        //先找待插入节点之前的节点
        while (i<k-1&&p!=null){
            i++;
            p = p.next;
        }
        p.next= p.next.next;
        return true;
    }


    void printList(){
        Node p = list; //头指针
        while (p!=null){
            System.out.print(p.data+" ");
            p = p.next;
        }
        System.out.println();

    }

    public static void main(String[] args) {
        LinkList ll = new LinkList();

        ll.init();
        ll.printList();

        //之前插入
        ll.insertOld(4,new Node(4));
        ll.printList();
        //之前插入
        ll.insertOld(2,new Node(22));
        ll.printList();
        //如果是第一个位置，无法找到1前面的位置，会导致在后面插入了。。
        ll.insertOld(1,new Node(11));
        ll.printList();
        //1的前面插入
        ll.insert(1,new Node(111));
        ll.printList();

        System.out.println("删除第2个节点");
        ll.delete(2);
        ll.printList();

        System.out.println("删除第1个节点");
        ll.delete(1);
        ll.printList();
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

---

时间复杂度

不带头节点查找

package dataStructure.LinkList;
//不带头节点
class Node{
    int data;
    Node next;

    Node(int data){
        this.data = data;
    }
}

public class LinkList {
    Node list; //头指针

    void init(){
        Node n1 = new Node(1);
        Node n2 =  new Node(2);
        Node n3 = new Node(3);

        list = n1; //头指针指向头节点
        n1.next = n2;
        n2.next = n3;
    }

    boolean insertOld(int k ,Node node){
        if(k<1) return false;

        //第一个元素
        int i = 1;
        Node p =list;
        while (i<k-1&&p!=null){
            i++;
            p = p.next;
        }

        if(p==null) return false;

        node.next = p.next;
        p.next = node;

        return true;
    }

    boolean insert(int k ,Node node){
        if(k<1) return false;

        if(k==1){
            node.next = list;
            list = node;
            return true;
        }

        //第一个元素
        int i = 1;
        Node p =list;
        while (i<k-1&&p!=null){
            i++;
            p = p.next;
        }

        if(p==null) return false;

        node.next = p.next;
        p.next = node;

        return true;
    }

    //k也是实际位置
    boolean delete(int k){
        if(k<1) return false;

        //删除第一个节点
        if(k==1){
            list = list.next;
            return true;
        }

        int i = 1;
        Node p = list;//指向第一个节点
        //先找待插入节点之前的节点
        while (i<k-1&&p!=null){
            i++;
            p = p.next;
        }
        p.next= p.next.next;
        return true;
    }

    Node getNode(int k ){
        if(k<1) return null;

        int i =1;
        Node p = list;

        while (i<k&&p!=null){
            i++;
            p = p.next;
        }
        return p;
    }


    void printList(){
        Node p = list; //头指针
        while (p!=null){
            System.out.print(p.data+" ");
            p = p.next;
        }
        System.out.println();

    }

    public static void main(String[] args) {
        LinkList ll = new LinkList();

        ll.init();
        ll.printList();

        //之前插入
        ll.insertOld(4,new Node(4));
        ll.printList();
        //之前插入
        ll.insertOld(2,new Node(22));
        ll.printList();
        //如果是第一个位置，无法找到1前面的位置，会导致在后面插入了。。
        ll.insertOld(1,new Node(11));
        ll.printList();
        //1的前面插入
        ll.insert(1,new Node(111));
        ll.printList();

        System.out.println("删除第2个节点");
        ll.delete(2);
        ll.printList();

        System.out.println("删除第1个节点");
        ll.delete(1);
        ll.printList();

        System.out.println(ll.getNode(1).data);
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

带头节点

带头节点初始化

package dataStructure.LinkList2;

import dataStructure.LinkList.LinkList;

//带头节点
class Node{
    int data;
    Node next;

    Node(){
        System.out.println("调用了空构造");
    }
    Node(int data){
        this.data = data;
    }
}


public class LinkList2 {
    Node head;//头节点

    void init(){
        head = new Node();
        head.next=null;

        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        head.next = n1;
        n1.next = n2;
        n2.next = n3;
    }

    void printList(){
        Node p = head.next;//p是指向第一个元素的指针（头节点的下一个元素）
        while (p!=null){
            System.out.print(p.data+"  ");
            p = p.next;
        }
        System.out.println(" ");
    }


    public static void main(String[] args) {
        LinkList2 ll  =new LinkList2();
        ll.init();
        ll.printList();

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

带头节点插入(k之前插入)

插入代码如下：

额外引入 i（下标）

package dataStructure.LinkList2;

import dataStructure.LinkList.LinkList;

//带头节点
class Node{
    int data;
    Node next;

    Node(){
        System.out.println("调用了空构造");
    }
    Node(int data){
        this.data = data;
    }
}


public class LinkList2 {
    Node head;//头节点

    void init(){
        head = new Node();
        head.next=null;
    }

    void printList(){
        Node p = head.next;//p是指向第一个元素的指针（头节点的下一个元素）
        while (p!=null){
            System.out.print(p.data+"  ");
            p = p.next;
        }
        System.out.println(" ");
    }

    //k也是实际位置
    boolean insert(int k, Node node) {
        if (k<1) return false;

        int i =0;
        Node p = head;//初始化最开始的位置

        //将p指针移动到待插入的位置
        while (i<k-1&&p!=null){
            i++;
            p = p.next;
        }

        if (p==null) return false;

        node.next = p.next;
        p.next = node;
        return true;

    }

    public static void main(String[] args) {
        LinkList2 ll  =new LinkList2();
        ll.init();
        //开始插入节点
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        ll.insert(1,n1);
        ll.insert(2,n2);
        ll.insert(3,n3);
        ll.printList();

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

在位置K之后插入：

    public static void main(String[] args) {
        LinkList2 ll  =new LinkList2();
        ll.init();
        //开始插入节点
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(22);
        ll.insert(1,n1);
        ll.insert(2,n2);
        ll.insert(3,n3);
        //在2位置之后插入
        ll.insert(2+1,n4);

        ll.printList();

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

优化一下判断逻辑，在头节点里面存储单链表表长

---

时间复杂度

带头节点删除

先找第k-1个节点。。

指向后继的后继

package dataStructure.LinkList2;

import dataStructure.LinkList.LinkList;

//带头节点
class Node{
    int data;
    Node next;

    Node(){
        System.out.println("调用了空构造");
    }
    Node(int data){
        this.data = data;
    }
}


public class LinkList2 {
    Node head;//头节点

    void init(){
        head = new Node();
        head.next=null;
    }

    void printList(){
        Node p = head.next;//p是指向第一个元素的指针（头节点的下一个元素）
        while (p!=null){
            System.out.print(p.data+"  ");
            p = p.next;
        }
        System.out.println(" ");
    }

    //k也是实际位置
    boolean insert(int k, Node node) {
        if (k<1) return false;

        int i =0;
        Node p = head;//初始化最开始的位置

        //将p指针移动到待插入的位置
        while (i<k-1&&p!=null){
            i++;
            p = p.next;
        }

        if (p==null) return false;

        node.next = p.next;
        p.next = node;
        return true;
    }
    //k也是实际位置
    boolean delete(int k){
        if(k<1) return false;

        int i = 0;
        Node p = head;//指向头节点
        //先找待插入节点之前的节点
        while (i<k-1&&p!=null){
            i++;
            p = p.next;
        }
        p.next = p.next.next;
        return true;
    }

    public static void main(String[] args) {
        LinkList2 ll  =new LinkList2();
        ll.init();
        //开始插入节点
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(22);
        ll.insert(1,n1);
        ll.insert(2,n2);
        ll.insert(3,n3);
        //在2位置之后插入
        ll.insert(2+1,n4);

        ll.printList();

        System.out.println("删除第二个位置元素");
        ll.delete(2);
        ll.printList();
        System.out.println("删除第1个位置元素");
        ll.delete(1);
        ll.printList();

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

---

时间复杂度

带头节点查找

package dataStructure.LinkList2;

import dataStructure.LinkList.LinkList;

//带头节点
class Node{
    int data;
    Node next;

    Node(){
        System.out.println("调用了空构造");
    }
    Node(int data){
        this.data = data;
    }
}


public class LinkList2 {
    Node head;//头节点

    void init(){
        head = new Node();
        head.next=null;
    }

    void printList(){
        Node p = head.next;//p是指向第一个元素的指针（头节点的下一个元素）
        while (p!=null){
            System.out.print(p.data+"  ");
            p = p.next;
        }
        System.out.println(" ");
    }

    //k也是实际位置
    boolean insert(int k, Node node) {
        if (k<1) return false;

        int i =0;
        Node p = head;//初始化最开始的位置

        //将p指针移动到待插入的位置
        while (i<k-1&&p!=null){
            i++;
            p = p.next;
        }

        if (p==null) return false;

        node.next = p.next;
        p.next = node;
        return true;
    }
    //k也是实际位置
    boolean delete(int k){
        if(k<1) return false;

        int i = 0;
        Node p = head;//指向头节点
        //先找待插入节点之前的节点
        while (i<k-1&&p!=null){
            i++;
            p = p.next;
        }
        p.next = p.next.next;
        return true;
    }

    Node getNode(int k ){
        if(k<1) return null;

        int i =0;
        Node p = head;

        while (i<k&&p!=null){
            i++;
            p = p.next;
        }
        return p;
    }

    public static void main(String[] args) {
        LinkList2 ll  =new LinkList2();
        ll.init();
        //开始插入节点
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(22);
        ll.insert(1,n1);
        ll.insert(2,n2);
        ll.insert(3,n3);
        //在2位置之后插入
        ll.insert(2+1,n4);

        ll.printList();

        System.out.println("删除第二个位置元素");
        ll.delete(2);
        ll.printList();
        System.out.println("删除第1个位置元素");
        ll.delete(1);
        ll.printList();

        System.out.println(ll.getNode(1).data);

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

循环单链表

尾插

最后尾指针后移

双链表(考察很少)

先找第k-1个节点，然后执行插入操作。

注意非空判断

---

删除（中间节点）

真题

d
对于a

c
插入操作：(尾节点之后插入)

然后把尾节点加入进来

最后尾节点后移

删除操作：（删除尾节点，需要寻找尾节点之前的节点）


核心代码：

a

a

a

a

b
a

链式存储不用移动

a

栈

栈的顺序存储

top是指向栈顶的下一个位置。。

栈的链式存储

完成入栈操作。。

注意判空条件

完成出栈操作。。

真题

a

b

d
带入一些例子，一个一个去试一试就行。。。

a

a

a
入栈

出栈


栈只有打印所有元素的时候需要变量链表。。。

c

d
栈顶指针一直是指向栈顶元素的下一个元素。。
栈2不插入任何元素，栈1插入4个元素后，栈满。


栈2一直插入元素，栈1不插入任何元素。

也符合

队列

顺序存储队列

判断队列为空：

插入：

出队（删除）

读取队头元素

循环队列

取模运算

同样他，对头出队也是需要取模运算。

判空就得用size计数了。。

链式存储队列

入队

出队(返回出队的节点)

对于只有一个元素的出队。。（需要移动队尾指针了）

结合起来出队的完整代码就是：

获取对头元素

双端队列

真题

d

d

b

d

d

在对于B.D进一步的去验证。。

a

a

b

栈结合队列题目

队列的出对序列就是他的入队序列；同时也是栈的出栈序列。

D
对于B，插入


B删除

都是O1
对于D
2栈可以模拟队列，反之不行。。

d

c

b

b

c

串

真题

c

d


计算公式来源：

串的模式匹配

朴素算法

返回起始位置

进一步匹配

匹配成功

加上限制条件


完整代码如下：

时间复杂度

平均的时间复杂度：

KMP算法

前缀：

后缀：

计算不同位置的next值：

再一个例子：

真题

b

b
（之间有那个KMP前后缀的方法套就行。。）

a

b

数组

一维数组

带首地址的计算第i个元素的地址：

不带首地址的计算第i个元素的地址:

二维数组

行优先存储：
下标从0开始

下标从1开始：

列优先存储:
下标从0开始：

下标从1开始:

---

总结

当i==j的时候，按行存储和按列存储的偏移量是一样的。

真题

c

b

b

矩阵

对称矩阵

对称矩阵压缩为一维数组：

存储的元素个数：

下标从0开始，i>=j（下三角）

下标从0开始，j>=i（上三角）
交换i和J就行

总结

当下标从1开始：

三对角矩阵

按行存储

总结

稀疏矩阵

三元组表

十字链表

真题

a
也可代入一个数字去运算。。

a

a
带入一个值计算一下

c

d

b
注意：i小于j,是上三角

b

树

基本概念

树的度：树中节点度的最大值。

性质

第一个例子

第二个例子

带入每一层节点的数量，再等比求和。

例子：

例子：

例子2：

需要上取整。最小高度为3

真题

b

c

叶子节点的度为0
一共两种节点：度为0的节点和度为k的节点

二叉树的定义

性质

满二叉树和完全二叉树

关于二叉树性质4：

真题

b
带入具体的数值来计算（注意区分下取整符号和上取整的符号）

对于B的一个不成立的例子

d

d

d

c

C

如果有5个节点：

d
最高 1024

最低（完全二叉）
带入公式

或者用性质2求出区间

二叉树顺序存储

数组来存储

完全二叉树利用率高，非完全二叉树利用率低

二叉树链式存储

空指针的数量：

对于n个节点的二叉链表，一共有：
个空指针
对于三叉链表来说：
n个节点的三叉链表的空指针域为：

为n+2个空指针域

真题

a

d
b
三叉链表中，指针的数量是当前图片中的线段数乘以2
指针为10个
6个节点，每个节点的指针为3，一共为18个指针
空指针为18-10=8个空指针
或者直接用公式：n+2

c

d

二叉树遍历算法

先序遍历

中序遍历

后序遍历

层序遍历

---

一个小小的汇总：

根据遍历序列构造二叉树

中序是必不可少的

先序+中序构造二叉树

1：

2：

3：

4：

5：

6：

后序+中序构造二叉树

1：

2：

3：

4：

5：

6：

层序+中序构造二叉树

1：

2：

3：

4：

5：

6：

7：

真题

c
b

a

d
方法一：通过根节点的位置来判断

我的方法：
7开始，所以必然是右开头
然后根节点在中间
就是：右根左

b
1：

2：

3：

4：

5：

6：

b

c

平衡二叉树

对于a节点

对于C节点

对于B节点

因此，此二叉树为平衡二叉树：

同时也是完全二叉树

完全二叉树是平衡二叉树
平衡二叉树不一定是完全二叉树，例子如下：

二叉排序树

中序遍历二叉排序树就是有序序列

二叉排序树的构造

关键字序列的第一个元素为根节点：
1：

2：

3：

4：

5：

6：

7：

8：

9：

真题

c

c
找5

c

d对了

b

最优二叉树

路径长度：
节点的带权路径长度：
树的带权路径长度：

哈夫曼树：

其中，b为哈夫曼树

构造最优二叉树

1：

2：

3：

4：

5：

6：

树的带权路径长度为：

最优二叉树的概念

权值大的节点距离根节点进，权值小的节点距离根节点远

叶子节点是存在的节点，分支节点是构造出来的节点

根据之前的公式：

最优二叉树的构造规则

0：

1：

2：

3：

4：

结束：

---

一个例子：

两个例子：

哈夫曼编码

定义

等长编码：

编码方法如下：

左分支标0，右分支标1

编码为：

译码过程为：

一个例子如下：

压缩比

压缩比：
等长编码-哈夫曼编码/等长编码

真题

b

c

c

b
等长编码：


哈夫曼编码：



压缩比：

d(之前的性质里面讲了)

b
a

ac

a

等长编码为：


哈夫曼编码为:

压缩比为：

d
哈夫曼树的节点的度为0或者2（不存在只有一个子树的节点）

a
a

线索二叉树

c的直接前驱是b
c的直接后继是a

节点没有左右孩子就直接向直接前驱和后继
节点d:
d有右孩子，指向e，值为0
d没有左孩子，指向直接前驱a，值为1

线索二叉树就是普通二叉树的基础上，改变了一下存储结构

二叉树类别

真题

a


完全二叉树一定是平衡二叉树

c

最优二叉树只有度为0和度为1的节点

b

图

有向图和无向图

完全图

顶点的度

度：无向图
出度和入度：有向图

对于无向图来说:
度 为 边的数量乘以2

有向图同理：

路径

连通图和强连通图

最多和最少边的问题：

多的情况参照完全图

真题

d

b

图的存储

邻接矩阵

邻接表

---

关于无向图：

稠密图和稀疏图

邻接表适合存储稀疏图
邻接矩阵适合存储稠密图

真题

c

c

a

a
b

网

图的遍历

深度优先遍历(DFS)

关键是回溯操作，，

2.

4. (v5没有后续的节点了，回溯到v2)

6.(v4的后续节点也都被访问过了，继续回溯到v2)

7.(v2都后续节点也都被访问过了。继续回溯到v1)

8.

9.（v3的后续节点都被访问过了，回溯到v1）

结束遍历

---

递归调用的存储结构图如下：

时间复杂度

对于有向图：

采用递归的思想求解的

对于无向图：

广度优先遍历(BFS)

队列来实现的

2.

3.

4.

5.

6.

时间复杂度

真题

深度优先遍历和广度优先遍历的时间复杂度相同，只是和存储结构相关

c

a

a

b
a
强连通图：1是有向图 2任意两个节点之间存在路径

d
b

拓扑排序

aov网：有向无环图

真题

a

c

c

a

b

总结