数据结构与算法：数组的基本原理

发表于 分类于 Disqus：

在讲解数据结构时，数组总是一个大家早期接触的主题。但你可能会发现，不同编程语言中“数组”这一概念的使用方式和 API 有所区别。其实我们可以把「数组」分为两大类：

静态数组

静态数组在创建时就已经确定了元素的个数以及连续的内存空间。我们可以通过下标索引访问数组中存储的元素，这正是数组最原始的形式，也是其 “随机访问” 能力得以实现的根本原因。

动态数组

动态数组是在静态数组基础上，为了方便编程引入的一层封装。动态数组在内部依然使用静态数组存储数据，但会自动进行扩容和提供一些常用的增删查改 API，如 ⁠push、⁠insert、⁠remove 等。了解动态数组的底层原理，有助于我们深入理解后续实现其他数据结构（例如队列、栈、哈希表等）的核心思想。

本文将围绕静态数组的基本原理，并用 C 语言代码手把手实现简单版本的动态数组，展示其增删查改操作。

静态数组的基本使用

在 C 语言中，我们可以直接通过如下方式定义一个大小为 10 的静态数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <string.h>

int main() {
    // 定义一个大小为 10 的静态数组
    int arr[10];
    
    // 用 memset 函数把数组的值初始化为 0
    memset(arr, 0, sizeof(arr));

    // 使用索引赋值
    arr[0] = 1;
    arr[1] = 2;

    // 使用索引取值
    int a = arr[0];
    printf("a = %d\n", a);

    return 0;
}

在上面的代码中：

  1. 数组 ⁠arr 在内存中占用了连续的 ⁠10 * sizeof(int) 字节空间（通常一个 ⁠int 占 4 字节，总共 40 字节）。

  2. 数组名 ⁠arr 就代表这块内存的首地址，因此 ⁠arr[0] 就是起始地址处的数据，而 ⁠arr[1] 则是偏移 4 字节后存储的数据。

这种连续内存的特性保证了数组的“随机访问”，即给定任何下标，都可以在 O(1) 时间内通过首地址和偏移量直接计算目标元素的内存位置。

数组的增删改查

对于静态数组来说，查改操作比较简单，需要给定下标直接访问数据，时间复杂度均为 O(1)。而增删操作则需要考虑两种情况：

  • 在数组末尾增加或删除元素

  • 在数组中间插入或删除元素（这就需要进行数据搬移）

数组的增删改查

假设我们有一个大小为 10 的数组，前 4 个位置存储数据，现在直接在末尾追加一个元素：

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
#include <stdio.h>

int main() {
    int arr[10] = {0};  // 数组初始化为 0
    int len = 4;        // 当前已存储 4 个元素

    // 对前 4 个位置赋值
    for (int i = 0; i < len; i++) {
        arr[i] = i;
    }

    // 在数组末尾追加一个元素 4
    if (len < 10) {
        arr[len] = 4;
        len++;
    }

    // 输出数组结果
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

在末尾追加数据时只需一次赋值操作，时间复杂度为 O(1)。

在中间插入元素

如果要在数组的某个中间位置插入一个新元素，就需要先将后面的元素向后搬移，为新元素腾出空间。例如，在下标 2（第三个位置）插入新数据 666：

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
#include <stdio.h>

int main() {
    int arr[10] = {0};  // 初始化数组
    int len = 4;        // 当前有 4 个元素

    // 赋初始值
    for (int i = 0; i < len; i++) {
        arr[i] = i;
    }

    int pos = 2;      // 插入位置
    int newVal = 666; // 要插入的新元素

    // 检测是否有足够空间
    if (len < 10) {
        // 从最后一个元素开始到插入位置，倒序搬移，避免覆盖
        for (int i = len; i > pos; i--) {
            arr[i] = arr[i - 1];
        }
        // 将新元素放入指定位置
        arr[pos] = newVal;
        len++;
    }

    // 输出数组结果
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

这里需要将位置 pos 之后的所有元素依次后移一位，因此时间复杂度为 O(N)。

删除元素

删除元素同样分两种情况：

  • 删除末尾元素时，只需要将数组长度减少一位，时间复杂度为 O(1)。

  • 删除数组中间的元素时，需要将目标元素后面的数据前移一位，时间复杂度为 O(N)。

删除末尾元素示例

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
#include <stdio.h>

int main() {
    int arr[10] = {0};
    int len = 5; // 假设数组中有 5 个元素

    // 赋初始值
    for (int i = 0; i < len; i++) {
        arr[i] = i;
    }

    // 删除末尾元素，简单将 len 减 1（此处用 -1 表示已删除，仅作示例）
    if (len > 0) {
        arr[len - 1] = -1;  // 标记为 -1
        len--;
    }

    // 输出数组结果
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

删除中间元素示例

例如删除下标 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
#include <stdio.h>

int main() {
    int arr[10] = {0};
    int len = 5; // 假设数组中有 5 个元素

    // 赋初始值
    for (int i = 0; i < len; i++) {
        arr[i] = i;
    }
    
    int pos = 1; // 删除位置

    // 将 pos 后面的元素依次前移
    for (int i = pos; i < len - 1; i++) {
        arr[i] = arr[i + 1];
    }
    // 最后一个位置标记为 -1，代表已删除（仅作示例）
    arr[len - 1] = -1;
    len--;

    // 输出数组结果（仅输出数组中有效的部分）
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

数组的扩容思想

静态数组的最大问题在于：在创建数组时就必须确定内存大小，一旦数组满了，无法直接在连续内存后面追加更多数据。我们只能重新开辟一块更大的内存，将原有数据复制到新数组中，然后插入新元素。这就是“扩容”操作，其时间复杂度为 O(N)。

以下示例展示如何扩容一个静态数组：

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
#include <stdio.h>
#include <stdlib.h>

int main() {
    // 初始数组大小为 10
    int initCapacity = 10;
    int *arr = (int *)malloc(initCapacity * sizeof(int));
    int len = initCapacity;

    // 假设数组已满，赋值 0 ~ 9
    for (int i = 0; i < len; i++) {
        arr[i] = i;
    }

    // 现在需要扩容，创建一个大小为 20 的新数组
    int newCapacity = 20;
    int *newArr = (int *)malloc(newCapacity * sizeof(int));

    // 把原来数组的数据复制到新数组中
    for (int i = 0; i < len; i++) {
        newArr[i] = arr[i];
    }

    // 释放旧数组内存
    free(arr);

    // 在新的大数组中追加新元素，比如新元素为 10
    newArr[len] = 10;
    len++;

    // 输出新数组中的数据
    for (int i = 0; i < len; i++) {
        printf("%d ", newArr[i]);
    }
    printf("\n");

    free(newArr);
    return 0;
}

在实际开发中，动态数组的扩容不会在每次添加元素时都发生，而是采用均摊时间复杂度（摊还分析）来评估其操作效率。正因为这种策略，使得在尾部追加元素的均摊时间复杂度依然是 O(1)。

动态数组的代码实现与关键点

动态数组是在静态数组基础上进行封装，以便更方便地进行增删查改操作。动态数组解决了静态数组大小固定的问题，最主要的改进包括：

  • 自动扩缩容：当数组元素个数达到容量上限时，扩容为原来的 2 倍；当元素个数减少到容量的 1/4 时，可以缩容为原来的 1/2。

  • 索引越界检查：在插入、查找和修改时分别进行检查，保证操作合法。

  • 防止内存泄漏：删除元素时清除相关数据，确保不再使用的数据能被正确释放。

下面我们通过一个完整的 C 语言示例来实现一个只存储整数的动态数组，该示例包含了自动扩容和缩容、插入、删除、查找以及修改等功能。

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

// 定义动态数组结构，用来存储整数数据
typedef struct {
    int *data;      // 指向存放数据的数组
    int size;       // 当前存储的元素个数
    int capacity;   // 底层数组的容量
} DynamicArray;

// 初始化动态数组，指定初始容量
DynamicArray* initDynamicArray(int initCapacity) {
    DynamicArray *arr = (DynamicArray*)malloc(sizeof(DynamicArray));
    if (initCapacity < 1) {
        initCapacity = 1;
    }
    arr->data = (int*)malloc(initCapacity * sizeof(int));
    arr->size = 0;
    arr->capacity = initCapacity;
    return arr;
}

// 释放动态数组内存
void freeDynamicArray(DynamicArray *arr) {
    if (arr) {
        free(arr->data);
        free(arr);
    }
}

// 根据新容量 newCap 重新分配内存
void resize(DynamicArray *arr, int newCap) {
    // 容量至少为 1
    if (newCap < 1) {
        newCap = 1;
    }
    int *newData = (int*)malloc(newCap * sizeof(int));
    // 搬移数据
    for (int i = 0; i < arr->size; i++) {
        newData[i] = arr->data[i];
    }
    // 释放旧数组内存
    free(arr->data);
    arr->data = newData;
    arr->capacity = newCap;
}

// 索引检查：用于返回已有元素的位置（查找、修改、删除）
void checkElementIndex(DynamicArray *arr, int index) {
    if (index < 0 || index >= arr->size) {
        fprintf(stderr, "IndexOutOfBoundsException: Index: %d, Size: %d\n", index, arr->size);
        exit(EXIT_FAILURE);
    }
}

// 索引检查：用于新增元素时，允许 index == size（插入至末尾）
void checkPositionIndex(DynamicArray *arr, int index) {
    if (index < 0 || index > arr->size) {
        fprintf(stderr, "IndexOutOfBoundsException: index: %d, Size: %d\n", index, arr->size);
        exit(EXIT_FAILURE);
    }
}

// 打印数组内部状态（调试函数）
void display(DynamicArray *arr) {
    printf("size = %d, capacity = %d\n", arr->size, arr->capacity);
    for (int i = 0; i < arr->size; i++) {
        printf("%d ", arr->data[i]);
    }
    printf("\n");
}

// --- 增 --- //

// 在数组末尾追加元素
void addLast(DynamicArray *arr, int val) {
    // 检查是否需要扩容
    if (arr->size == arr->capacity) {
        resize(arr, arr->capacity * 2);
    }
    arr->data[arr->size] = val;
    arr->size++;
}

// 在指定位置添加元素；允许 index == size（插入空隙）
void add(DynamicArray *arr, int index, int val) {
    checkPositionIndex(arr, index);
    if (arr->size == arr->capacity) {
        resize(arr, arr->capacity * 2);
    }
    // 将 index 后的所有元素向后搬移一位
    for (int i = arr->size - 1; i >= index; i--) {
        arr->data[i + 1] = arr->data[i];
    }
    arr->data[index] = val;
    arr->size++;
}

// 在数组首部添加元素，直接调用 add(index, val)
void addFirst(DynamicArray *arr, int val) {
    add(arr, 0, val);
}

// --- 删 --- //

// 删除数组最后一个元素，并返回该值
int removeLast(DynamicArray *arr) {
    if (arr->size == 0) {
        fprintf(stderr, "NoSuchElementException: Array is empty\n");
        exit(EXIT_FAILURE);
    }
    // 缩容判断
    if (arr->size == arr->capacity / 4 && arr->capacity > 1) {
        resize(arr, arr->capacity / 2);
    }
    int deletedVal = arr->data[arr->size - 1];
    // 清理数据，防止内存泄漏
    arr->data[arr->size - 1] = 0;
    arr->size--;
    return deletedVal;
}

// 删除指定位置的元素并返回该值
int removeAt(DynamicArray *arr, int index) {
    checkElementIndex(arr, index);
    // 缩容判断
    if (arr->size == arr->capacity / 4 && arr->capacity > 1) {
        resize(arr, arr->capacity / 2);
    }
    int deletedVal = arr->data[index];
    // 搬移数据，将 index+1 ... end 向前移动
    for (int i = index + 1; i < arr->size; i++) {
        arr->data[i - 1] = arr->data[i];
    }
    arr->data[arr->size - 1] = 0; // 清理数据
    arr->size--;
    return deletedVal;
}

// 删除数组首部元素
int removeFirst(DynamicArray *arr) {
    return removeAt(arr, 0);
}

// --- 查 --- //

// 获取指定索引处的元素
int get(DynamicArray *arr, int index) {
    checkElementIndex(arr, index);
    return arr->data[index];
}

// --- 改 --- //

// 修改指定索引处的元素，返回原值
int set(DynamicArray *arr, int index, int newVal) {
    checkElementIndex(arr, index);
    int oldVal = arr->data[index];
    arr->data[index] = newVal;
    return oldVal;
}

//
// 测试用例
//
int main() {
    // 初始容量设为 3
    DynamicArray *arr = initDynamicArray(3);

    // 添加 5 个元素：1 2 3 4 5
    for (int i = 1; i <= 5; i++) {
        addLast(arr, i);
    }
    // 此时数组元素为：[1, 2, 3, 4, 5]
    display(arr);

    // 删除下标 3 的元素（即第四个元素 4）
    int deleted = removeAt(arr, 3);
    printf("Removed value: %d\n", deleted);
    // 数组更新为：[1, 2, 3, 5]
    display(arr);

    // 在下标 1 的位置插入元素 9
    add(arr, 1, 9);
    // 数组更新为：[1, 9, 2, 3, 5]
    display(arr);

    // 在数组首部插入元素 100
    addFirst(arr, 100);
    // 更新为：[100, 1, 9, 2, 3, 5]
    display(arr);

    // 删除数组尾部元素
    int lastVal = removeLast(arr);
    printf("Removed last value: %d\n", lastVal);
    // 数组更新为：[100, 1, 9, 2, 3]
    display(arr);

    // 查、改示例
    int val = get(arr, 2);
    printf("Element at index 2: %d\n", val);
    set(arr, 2, 66);
    printf("After setting index 2 to 66:\n");
    display(arr);

    // 释放内存
    freeDynamicArray(arr);
    return 0;
}

代码说明

  1. 自动扩缩容

  • 在添加元素时，如果 ⁠size == capacity，调用 ⁠resize 扩容为原来的 2 倍。

  • 删除元素后，如果 ⁠size == capacity / 4（且容量不小于 1），进行缩容以节约内存。

  1. 索引越界检查

  • 使用 ⁠checkElementIndex 对已有元素的索引进行检查，确保查找、修改和删除操作在合法范围内。

  • 使用 ⁠checkPositionIndex 检查插入操作时允许 ⁠index == size 的情况，从而支持在末尾插入新元素。

  1. 防止内存泄漏
  • 删除元素后，将对应位置的数据置为 0（如果存放的是指针类型，则应调用适当的释放函数），以防止出现悬挂引用的问题。
  1. 其他细节优化
  • 数据搬移在示例中采用 for 循环实现，这有助于理解底层算法本质；但在生产环境中，可以考虑使用更高效的内存复制函数。

总结

本文融合了静态数组与动态数组的相关内容，主要介绍了：

  • 静态数组的内存连续性和基本增删改查操作，其中在中间插入和删除元素需要搬移数据。

  • 动态数组在静态数组之上封装了自动扩缩容、索引越界检查与内存清理等功能，使我们在实际开发中能够更灵活、更安全地操作数组。

  • 通过 C 语言完整示例展示了动态数组的实现细节，从而帮助大家深入理解其背后的工作原理和设计思路。

希望这篇博客能够帮助你全面理解数组的基本原理及动态数组的实现方法，并为你后续学习队列、栈、哈希表等更复杂的数据结构打下坚实基础！