『数据结构与算法』—— 数组

字数统计: 1,619 字   |   阅读时长: 9 分   |   本文总阅读量: 次


数据结构与算法

定义

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

线性表

顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。

连续内存，类型相同

我们知道，计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：

1
a[i]_address = base_address + i * data_type_size

优劣

优点显而易见，其时间复杂度仅仅为 $O(1)$，但是对于插入或者删除，都需要通过平移数组来完成操作，这就意味着最坏时间复杂度为 $O(n)$，如果容量还需要进行扩容，这是相当耗时的。

个人总结

  1. Java List 无法存储基本类型，都需要封住成 Integer 或者 Long 类，而装箱和拆箱是有很大的性能消耗的。
  2. 如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。

例子

  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
class Array {
    int data[];
    int count;
    int n;

    Array(int capacity) {
        data = new int[capacity];
        count = 0;
        n = capacity;
    }

    boolean add(int index, int value) {
        if (count >= n) {
            System.out.println("容量达到最大值");
            return false;
        }
        if (index > count) {
            System.out.println("下标越界");
            return false;
        }
        // 从屁股开始，往后移动，将 index 位置空出来
        for (int i = count; i > index; i--) {
            data[i] = data[i - 1];
        }
        data[index] = value;
        count++;
        System.out.println("插入成功:\tvalue:\t" + value + ":\tindex:\t" + index);
        System.out.println("data:\t" + toString());
        return true;
    }

    int get(int index) {
        if (index >= count) {
            return -1;
        }
        System.out.println("value:\t" + data[index]);
        return data[index];
    }

    boolean delete(int index) {
        if (index >= count) {
            System.out.println("下标越界");
            return false;
        }
        for (int i = index; i < count - 1; i++) {
            data[i] = data[i + 1];
        }
        data[count - 1] = 0;
        count--;
        System.out.println("删除成功 data:\t" + toString());
        return true;
    }

    @Override
    public String toString() {
        return Arrays.toString(data);
    }

    public static void main(String[] args) {
        Array array = new Array(10);
        array.add(0, 1);
        array.add(1, 2);
        array.add(2, 3);
        array.add(3, 4);
        array.add(4, 5);
        array.add(5, 6);
        array.add(6, 7);
        array.add(7, 8);
        array.add(8,9);
        array.add(9,10);
        array.delete(9);
        System.out.println("get value:\t" + array.get(3));
    }
}

输出结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
插入成功:	value:	1:	index:	0
data:	[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
插入成功:	value:	2:	index:	1
data:	[1, 2, 0, 0, 0, 0, 0, 0, 0, 0]
插入成功:	value:	3:	index:	2
data:	[1, 2, 3, 0, 0, 0, 0, 0, 0, 0]
插入成功:	value:	4:	index:	3
data:	[1, 2, 3, 4, 0, 0, 0, 0, 0, 0]
插入成功:	value:	5:	index:	4
data:	[1, 2, 3, 4, 5, 0, 0, 0, 0, 0]
插入成功:	value:	6:	index:	5
data:	[1, 2, 3, 4, 5, 6, 0, 0, 0, 0]
插入成功:	value:	7:	index:	6
data:	[1, 2, 3, 4, 5, 6, 7, 0, 0, 0]
插入成功:	value:	8:	index:	7
data:	[1, 2, 3, 4, 5, 6, 7, 8, 0, 0]
插入成功:	value:	9:	index:	8
data:	[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
插入成功:	value:	10:	index:	9
data:	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
删除成功 data:	[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
value:	4
get value:	4
  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
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
class GenericArray<T> {
    T[] data;
    int size;

    GenericArray(int capacity) {
        data = (T[]) new Object[capacity];
        size = 0;
    }

    GenericArray() {
        this(10);
    }

    void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("下标越界");
        }
    }

    void resize(int newSize) {
        T[] newData = (T[]) new Object[newSize];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        System.out.println("扩容 capacity:\t" + newSize);
        data = newData;
    }

    T get(int index) {
        checkIndex(index);
        return data[index];
    }

    boolean isEmpty() {
        return size == 0;
    }

    void set(int index, T t) {
        checkIndex(index);
        data[index] = t;
        System.out.println("set value:" + " index: " + index + " value: " + t);
        System.out.println("data: " + toString());
    }

    int getCapacity() {
        return data.length;
    }

    int getCount() {
        return size;
    }

    boolean contains(T t) {
        for (int i = 0; i < size; i++) {
            if (data[i] == t) {
                return true;
            }
        }
        return false;
    }

    int find(T t) {
        for (int i = 0; i < size; i++) {
            if (data[i] == t) {
                return i;
            }
        }
        return -1;
    }

    void add(int index, T t) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("下标越界");
        }
        if (size == data.length) {
            resize(2 * size);
        }
        for (int i = size; i > index; i--) {
            data[i] = data[i-1];
        }
        data[index] = t;
        size ++;
        System.out.println("add data: " + " index: " + index + " value: " + t);
        System.out.println("data: " + toString());
    }

    void addFirst(T t) {
        add(0, t);
    }

    void addLast(T t) {
        add(size, t);
    }

    T remove(int index) {
        checkIndex(index);
        T t = data[index];
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        data[size-1] = null;
        size--;
        if (size == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }
        System.out.println("remove data: " + " index: " + index + " value: " + t);
        System.out.println("data: " + toString());
        return t;
    }

    @Override
    public String toString() {
        return Arrays.toString(data);
    }

    public static void main(String[] args) {
        GenericArray<String> data = new GenericArray<String>(6);
        data.addLast("1");
        data.addLast("2");
        data.addLast("3");
        data.addLast("4");
        data.addLast("5");
        data.addLast("6");
        data.addLast("7");

        data.remove(data.getCount()-1);
        data.remove(data.getCount()-1);
        data.remove(data.getCount()-1);
        data.remove(data.getCount()-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
add data:  index: 0 value: 1
data: [1, null, null, null, null, null]
add data:  index: 1 value: 2
data: [1, 2, null, null, null, null]
add data:  index: 2 value: 3
data: [1, 2, 3, null, null, null]
add data:  index: 3 value: 4
data: [1, 2, 3, 4, null, null]
add data:  index: 4 value: 5
data: [1, 2, 3, 4, 5, null]
add data:  index: 5 value: 6
data: [1, 2, 3, 4, 5, 6]
扩容 capacity:	12
add data:  index: 6 value: 7
data: [1, 2, 3, 4, 5, 6, 7, null, null, null, null, null]
remove data:  index: 6 value: 7
data: [1, 2, 3, 4, 5, 6, null, null, null, null, null, null]
remove data:  index: 5 value: 6
data: [1, 2, 3, 4, 5, null, null, null, null, null, null, null]
remove data:  index: 4 value: 5
data: [1, 2, 3, 4, null, null, null, null, null, null, null, null]
扩容 capacity:	6
remove data:  index: 3 value: 4
data: [1, 2, 3, null, null, null]

参考自极客时间

本文标题:『数据结构与算法』—— 数组

文章作者:下位子

发布时间:2018-09-25, 15:10:00

最后更新:2018-11-01, 09:35:36

原始链接:http://xiaweizi.cn/article/af0f/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

#rewardButton { background-color: #ea6f5a; } .btn-pay { margin-bottom: 20px; padding: 8px 25px; font-size: 16px; color: #fff; background-color: #ea6f5a; } .btn { display: inline-block; margin-bottom: 0; font-weight: 400; text-align: center; vertical-align: middle; touch-action: manipulation; cursor: pointer; background-image: none; border: 1px solid transparent; white-space: nowrap; padding: 6px 12px; font-size: 14px; line-height: 1.42857; border-radius: 4px; -webkit-user-select: none; -moz-user-select: none; -ms-user-select: none; user-select: none; } #QR img{ height: 200px; height: 200px; margin: 20px; }
文章目录
  1. 1. 定义
  2. 2. 优劣
  3. 3. 个人总结
  4. 4. 例子
您是第 位小伙伴 | 本站总访问量 次 | 已经写了 120.4k 字啦

载入天数...载入时分秒...