数据结构-数组

发表于 | 分类于 | | 阅读次数: |
字数统计: 3,852 字 | 阅读时长 ≈ 18 分钟

这篇笔记开始 将系统学习一遍数据结构，编程的技术内功。💪💪💪

我们先看下在Java中如何使用数组

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
public class Main {

    public static void main(String[] args) {
        // write your code here
		
        // 创建数组
        int[] arr = new int[20];
        // 遍历数组
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }
	
        int[] scores = new int[]{100, 12, 34};
        for (int i = 0; i < scores.length; i++) {
            System.out.println(scores[i]);
        }
        
        // 修改数组的值
        scores[1] = 68;

        for(int score:scores)
            System.out.println(score);
    }
}

// 输出结果
100
12
34
100
12
34
二次封装动态数组

数组最大的优点：快速查询。scores[2]

数组最好应用于”索引有语义”的情况。（即索引下标最好有实际意义）

但是并非所有有语义的索引都适用于数组。（如身份证号码）

下面我们主要探索索引没有语义的情况数组的使用。

索引没有语义，如何表示没有的元素？

如何添加元素，删除元素？

我们自己设计一个数组，能够实现索引没有语义的情况解决上面的问题

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
public class Array {

    private int[] data; //
    private int size;  // 这个size表示在data数组中有多少有效元素

    // 构造函数，传入数组的容量capacity构造Array
    public Array(int capacity) {
        data = new int[capacity];
        size = 0;
    }

    // 无参的构造函数，默认数组的capacity=10
    public Array() {
        this(10);
    }

    // 获取数组中的元素个数
    public int getSize() {
        return size;
    }

    // 获取数组的容量
    public int getCapacity() {
        return data.length;
    }

    // 返回数组是否为空
    public boolean isEmpty() {
        return size == 0;
    }
}

下面我们逐渐完善这个类。

向数组中添加元素

image-20181226201803092

上面代码写了这个size就是数组data的实际有效元素个数，指向的是数组中第一个没有元素的位置。我们要向数组末尾添加元素，直接向size指向的位置添加元素。同时size要向后挪移位。

1
2
3
4
5
6
7
8
9
10
// 向所有元素后添加一个新元素
public void addLast(int e){

    // 暂时不支持超过数组容量之后新增数组
    if (size == data.length){
        throw new IllegalArgumentException("AddLast failed, Array is full!");
    }
    data[size] = e;
    size++;
}

向指定位置添加元素

对于一个有序的数组，我们可以指定插入数据的位置。

image-20181226203709283

在指定位置添加新的元素，我们需要将指定位置后面的元素都往后挪一位，然后将要添加的元素放到对应的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 在第index个位置插入一个新元素e
public void add(int index, int e) {
    if (size == data.length)
        throw new IllegalArgumentException("add failed, Array is full!");

    if (index < 0 || index > size)
        throw new IllegalArgumentException("add failed, Require >= 0 and <=size");

    for (int i = size - 1; i >= index; i--)
        data[i + 1] = data[i];

    data[index] = e;
    size++;

}

了上面的方法我们可以简化添加最后和最开始两个函数

1
2
3
4
5
6
7
8
9
// 向所有元素后添加一个新元素
public void addLast(int e) {
    add(size, e);
}

// 在所有元素前添加一个新的元素
public void addFirst(int e) {
    add(0, e);
}

在数组中查询元素和修改元素

我们重写一下toString方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@Override
public String toString(){
    StringBuilder res = new StringBuilder();
    res.append(String.format("Array: size = %d, capacity = %d \n", size, data.length));
    res.append('[');
    for (int i = 0; i < size; i++) {
        res.append(data[i]);
        if (i != size - 1)
            res.append(",");

    }
    res.append("]");

    return res.toString();

}

新增一个数组，打印输出下

1
2
3
4
5
6
7
8
9
10
11
Array arr = new Array(20);

for (int i = 0; i < 10; i++) {
    arr.addLast(i);
}

System.out.println(arr);

// 输出
Array: size = 10, capacity = 20 
[0,1,2,3,4,5,6,7,8,9]
1
2
3
// 在 1 位置添加 100
arr.add(1, 100);
System.out.println(arr);
1
2
3
// 开始位置添加 -1
arr.addFirst(-1);
System.out.println(arr);
1
2
3
4
5
6
// 获取 index 索引位置的元素 
public int get(int index){
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("Get failed, Index is Illegal");
    return data[index];
}

增加一个get方法使用户只能访问有数据的空间。

1
2
3
4
5
6
7
// 修改 index 索引位置的元素为e
public void set(int index, int e) {
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("Get failed, Index is Illegal");
    data[index] = e;

}

增加set方法设置指定索引的值。

增加包含，搜索，删除方法

遍历查找元素

1
2
3
4
5
6
7
8
// 查找数组中是否有元素
public boolean contains(int e) {
    for (int i = 0; i < size; i++) {
        if (data[i] == e)
            return true;
    }
    return false;
}

遍历查找元素，返回对应的索引

1
2
3
4
5
6
7
8
9
// 查找数组中元素 e 所在的索引 如果不存在元素 e 则返回 -1
public int find(int e) {
    for (int i = 0; i < size; i++) {
        if (data[i] == e)
            return i;
    }
    return -1;

}

删除指定位置的元素

image-20181227095714812

类比于插入元素，我们在删除元素的时候，需要将对应位置后面的元素都往前挪一位。最后需要将size加一。不过，因为我们将size指向的是第一个为空的位置，最后一个元素我们可以不删，因为我们将它看为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 从数组中删除index位置的元素 返回删除的元素
public int remove(int index) {
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("Get failed, Index is Illegal");

    int ret = data[index];
    for (int i = index + 1; i < size; i++) {
        data[i - 1] = data[i];

    }
    size--;
    return ret;
}

由上面方法我们可以创造两个简化的方法

1
2
3
4
5
6
7
8
9
// 从数组中删除第一个元素 返回删除的元素
public int removeFirst() {
    return remove(0);
}

// 从数组中删除最后一个元素 返回删除的元素
public int removeLast() {
    return remove(size - 1);
}

删除指定元素

1
2
3
4
5
6
// 删除数组中元素 e
public void removeElement(int e){
    int index = find(e);
    if(index != -1)
        remove(index);
}
使用泛型

我们上面的数组只能承载int类型的元素。一个数组应该能够存放任意类型的数据。

解决这个问题的方式就是使用泛型。

使用泛型可以让我们的数据结构放置”任何”（不可以是基本数据类型，只能是类对象）数据类型。

基本数据类型（boolean byte char short int long float double）

每个基本数据类型都有对应的包装类。因此使用泛型的时候，我们存放的是基本类型的包装类。

基本数据类型对应的包装类（Boolean Byte Char Short Int Long Float Double）

我们使用泛型修改上面写的数组类，使其能够承载任意类型数据。

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
public class Array<E> {
    // 这里使用泛型 类型 E 指代要存入数据类型

    private E[] data;
    private int size;

    // 构造函数，传入数组的容量capacity构造Array
    public Array(int capacity){
        data = (E[])new Object[capacity];
        // 不支持直接创建泛型的数组 需要进行小技巧转化下
        size = 0;
    }

    // 无参数的构造函数，默认数组的容量capacity=10
    public Array(){
        this(10);
    }

    // 获取数组的容量
    public int getCapacity(){
        return data.length;
    }

    // 获取数组中的元素个数
    public int getSize(){
        return size;
    }

    // 返回数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    // 在index索引的位置插入一个新元素e
    public void add(int index, E e){

        if(size == data.length)
            throw new IllegalArgumentException("Add failed. Array is full.");

        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");

        for(int i = size - 1; i >= index ; i --)
            data[i + 1] = data[i];

        data[index] = e;

        size ++;
    }

    // 向所有元素后添加一个新元素
    public void addLast(E e){
        add(size, e);
    }

    // 在所有元素前添加一个新元素
    public void addFirst(E e){
        add(0, e);
    }

    // 获取index索引位置的元素
    public E get(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Index is illegal.");
        return data[index];
    }

    // 修改index索引位置的元素为e
    public void set(int index, E e){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Index is illegal.");
        data[index] = e;
    }

    // 查找数组中是否有元素e
    public boolean contains(E e){
        for(int i = 0 ; i < size ; i ++){
            if(data[i].equals(e)) // 对象间的比较不再支持 == 
                return true;
        }
        return false;
    }

    // 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
    public int find(E e){
        for(int i = 0 ; i < size ; i ++){
            if(data[i].equals(e))
                return i;
        }
        return -1;
    }

    // 从数组中删除index位置的元素, 返回删除的元素
    public E remove(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        E ret = data[index];
        for(int i = index + 1 ; i < size ; i ++)
            data[i - 1] = data[i];
        size --;
        data[size] = null; // loitering objects != memory leak
        return ret;
    }

    // 从数组中删除第一个元素, 返回删除的元素
    public E removeFirst(){
        return remove(0);
    }

    // 从数组中删除最后一个元素, 返回删除的元素
    public E removeLast(){
        return remove(size - 1);
    }

    // 从数组中删除元素e
    public void removeElement(E e){
        int index = find(e);
        if(index != -1)
            remove(index);
    }

    @Override
    public String toString(){

        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
        res.append('[');
        for(int i = 0 ; i < size ; i ++){
            res.append(data[i]);
            if(i != size - 1)
                res.append(", ");
        }
        res.append(']');
        return res.toString();
    }
}

我们在使用Array的时候只要指定泛型类型即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Main {

    public static void main(String[] args) {
        // write your code here

        Array<Integer> arr = new Array<>(20);

        for (int i = 0; i < 10; i++) {
            arr.addLast(i);
        }

        System.out.println(arr);

        arr.add(1, 100);
        System.out.println(arr);
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Main {

    public static void main(String[] args) {
        // write your code here

        Array<String> arr = new Array<>(20);

        for (int i = 0; i < 10; i++) {
            arr.addLast(String.valueOf(i));
        }

        System.out.println(arr);

        arr.add(1, "测试字符串");
        System.out.println(arr);

    }
}

我们还可以使用自己定义的类型

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
public class Student {

    private String name;
    private int score;

    public Student(String studentName, int studentScore) {
        name = studentName;
        score = studentScore;
    }

    @Override
    public String toString() {
        return String.format("Student(name: %s, score: %d)", name, score);
    }

    public static void main(String[] args) {

        Array<Student> arr = new Array<>();
        arr.addLast(new Student("Alice", 100));
        arr.addLast(new Student("Bob", 66));
        arr.addLast(new Student("Charlie", 88));
        System.out.println(arr);
    }
}

// 结果
Array: size = 3 , capacity = 10
[Student(name: Alice, score: 100), Student(name: Bob, score: 66), Student(name: Charlie, score: 88)]
动态数组

上面我们使用的数组data还是Java内置的静态数组，具有一些局限性（容量有限）。

image-20181227110907114

当我们的数组已满 继续想添加元素的时候，可以先新建一个容量长一点的数组，然后将旧的数组元素拷贝到新的数组中，并将之前的data指向新的数组。旧的数组会被垃圾回收机制自动回收。这样我们就得到了一个新的数组。

1
2
3
4
5
6
7
// 将数组的容量扩容到之前的两倍
private void resize(int newCapacity){
    E[] newData = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++)
        newData[i] = data[i];
    data = newData; // 将 data 指向新建的数组
}
1
2
3
4
5
6
7
8
9
10
11
// 在index索引的位置插入一个新元素e
public void add(int index, E e) {
    if (index < 0 || index > size)
        throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
    if (size == data.length)
        resize(2*data.length); // 当数组满的时候 直接扩容
    for (int i = size - 1; i >= index; i--)
        data[i + 1] = data[i];
    data[index] = e;
    size++;
}

经过上面的改造 我们的数组就是动态数组了

我们测试下 当数组满了的时候 再次新增元素将会发生什么

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Main {

    public static void main(String[] args) {
        // write your code here

        Array<String> arr = new Array<>(10);

        for (int i = 0; i < 10; i++) {
            arr.addLast(String.valueOf(i));
        }

        System.out.println(arr);

        arr.addLast("测试字符串");
        System.out.println(arr);

    }
}
// 输出
Array: size = 10 , capacity = 10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 11 , capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 测试字符串]

我们看到在数组满的时候，将会扩容然后新增数据。

同理 我们可以在删除数组的时候当存储数据只有容量的一半的时候，可以将容量减少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 从数组中删除index位置的元素, 返回删除的元素
public E remove(int index) {
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("Remove failed. Index is illegal.");

    E ret = data[index];
    for (int i = index + 1; i < size; i++)
        data[i - 1] = data[i];
    size--;
    data[size] = null; // loitering objects != memory leak
    if(size == data.length / 2)
        resize(data.length / 2);
    return ret;
}

测试一下当数据量为容量一半的时候

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Main {

    public static void main(String[] args) {
        // write your code here

        Array<String> arr = new Array<>(10);

        for (int i = 0; i < 6; i++) {
            arr.addLast(String.valueOf(i));
        }

        System.out.println(arr);

        arr.removeLast();
        System.out.println(arr);

    }
}
// 输出
Array: size = 6 , capacity = 10
[0, 1, 2, 3, 4, 5]
Array: size = 5 , capacity = 5
[0, 1, 2, 3, 4]

我们看到 当数据量减少到容量一半的时候 将会自动缩减容量。

简单的时间复杂度分析

我们在讨论时间复杂度的时候经常遇见O(1), O(n), O(lgn), O(nlogn), O(n^2)。

大O描述的是算法的运行时间和输入数据之间的关系。

image-20181227132514245

不过这个大O表示的是渐进时间复杂度，描述n趋近于无穷的情况。

现在我们看下之前写的Array各个函数的时间复杂度

image-20181227140022119

image-20181227140044712

image-20181227140059669

image-20181227140135820

image-20181227140222921

当索引具有语义的时候，时间复杂度就会很小。

均摊复杂度

我们以上考虑都是基于最坏考虑的，但是在新增的时候只有新增到最后需要扩容的时候resize才会有O(n)。

image-20181227140522368

这种最坏的考虑是不适合addLast的时间复杂度计算的。

当我们使用均摊复杂度（amortized time complexity）的时候 addLast的时间复杂度则为O(1)

因为扩容的触发是在2n+1次addLast之后才触发一次。

复杂度震荡

image-20181227141222561

在刚好到容量长度的时候每次新增删除都是触发O(n)。理论上这两个方法的时间复杂度都是O(1)。

出现问题原因：removeLast时resize过于着急(Eager)

解决方案：Lazy的方式resize

image-20181227141818164

即当使用removeLast删除元素的时候，并不着急的缩容，而是继续可以进行数据删除，当数据量为扩容后的1/4（即原来容量的1/2）的时候再进行缩容。

这样我们可以修改下我们的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 从数组中删除index位置的元素, 返回删除的元素
public E remove(int index) {
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("Remove failed. Index is illegal.");

    E ret = data[index];
    for (int i = index + 1; i < size; i++)
        data[i - 1] = data[i];
    size--;
    data[size] = null; // loitering objects != memory leak
    if(size == data.length / 4 && data.length / 2 != 0)
        resize(data.length / 2);
    return ret;
}
知识就是财富
如果您觉得文章对您有帮助, 欢迎请我喝杯水！