数组是一种常见的线性数据结构，其将相同类型的元素存储在连续的内存空间中，我们将元素在数组中的位置称为该元素的索引。

1. 数组的常用操作

1.1 初始化数组

初始化数组时，我们可以根据需求选用数组的两种初始化方式：无初始值、给定初始值。在未指定初始值的情况下，大多数编程语言会将数组元素初始化为0，但是经过实测，C++和C在数组为初始化时，大多数情况下不会将数组初始化为0，特别是使用new或malloc创建动态数组时数组元素都是随机值，因此在C++和C中建议创建完数组后就立刻将其初始化：

/* 初始化数组arr */
// 将数组存储在栈上
int size = 5;
int arr[5] = {0};
printf("数组 arr = ");
printArray(arr, 5);

/* 初始化数组nums */
// 将数组存储在栈上
int nums[5] = {1, 2, 3, 4, 5};
printf("数组 nums = ");
printArray(nums, 5);

/* 初始化数组arr */
// 将数组存储在堆上
int size = 5;
int *arr = new int[size];
fill_n(arr, size, 0); // 将数组 arr 的前 size 个元素初始化为 0
cout << "数组 arr = ";
printArray(arr, size);

/* 初始化数组nums */
// 将数组存储在堆上
int *nums = new int[size]{1, 3, 2, 5, 4};
cout << "数组 nums = ";
printArray(nums, size);

1.2 访问数组元素

数组元素被存储在连续的内存空间中，这意味着计算数组元素的内存地址非常容易。给定数组内存地址（首元素内存地址）和某个元素的索引，就能够直接访问该元素。

在数组中访问元素非常高效，我们可以在$O(1)$时间内随机访问数组中的任意一个元素。

/* 随机访问元素 */
int randomAccess(int *nums, int size) {
    // 在区间 [0, size) 中随机抽取一个数字
    int randomIndex = rand() % size;
    // 获取并返回随机元素
    int randomNum = nums[randomIndex];
    return randomNum;
}

/* 随机访问元素 */
int randomAccess(int *nums, int size) {
    // 在区间 [0, size) 中随机抽取一个数字
    int randomIndex = rand() % size;
    // 获取并返回随机元素
    int randomNum = nums[randomIndex];
    return randomNum;
}

1.3 插入元素

数组元素在内存中是连续的，它们之间没有空间再存放任何数据。如果想在数组中间插入一个元素，则需要将该元素之后的所有元素都向后移动一位，之后再把元素赋值给该索引。

/* 在数组的索引 index 处插入元素 num */
void insert(int *nums, int size, int num, int index) {
    // 把索引 index 以及之后的所有元素向后移动一位
    for (int i = size - 1; i > index; i--) {
        nums[i] = nums[i - 1];
    }
    // 将 num 赋给 index 处的元素
    nums[index] = num;
}

/* 在数组的索引 index 处插入元素 num */
void insert(int *nums, int size, int num, int index) {
    // 把索引 index 以及之后的所有元素向后移动一位
    for (int i = size - 1; i > index; i--) {
        nums[i] = nums[i - 1];
    }
    // 将 num 赋给 index 处的元素
    nums[index] = num;
}

1.4 删除元素

同理，若想删除索引 $i$ 处的元素，则需要把索引 $i$ 之后的元素都向前移动一位。

/* 删除索引 index 处的元素 */
// 注意：stdio.h 占用了 remove 关键词
void removeItem(int *nums, int size, int index) {
    // 把索引 index 之后的所有元素向前移动一位
    for (int i = index; i < size - 1; i++) {
        nums[i] = nums[i + 1];
    }
}

/* 删除索引 index 处的元素 */
void remove(int *nums, int size, int index) {
    // 把索引 index 之后的所有元素向前移动一位
    for (int i = index; i < size - 1; i++) {
        nums[i] = nums[i + 1];
    }
}

总的来看，数组的插入和删除操作有以下缺点：

时间复杂度高：数组的插入和删除的平均时间复杂度均为$O(n)$，其中n为数组长度。
丢失元素：由于数组的长度不可变，因此在插入元素后，超出数组长度范围的元素会丢失。
内存浪费：我们可以初始化一个比较长的数组，只用前面一部分，这样在插入数据时，丢失的末尾元素都是无意义的，但这样做会造成部分内存空间浪费。

1.5 遍历数组

在大多数编程语言中，我们既可以通过索引遍历数组，也可以直接遍历获取数组中的每个元素：

/* 遍历数组 */
void traverse(int *nums, int size) {
    int count = 0;
    // 通过索引遍历数组
    for (int i = 0; i < size; i++) {
        count += nums[i];
    }
}

/* 遍历数组 */
void traverse(int *nums, int size) {
    int count = 0;
    // 通过索引遍历数组
    for (int i = 0; i < size; i++) {
        count += nums[i];
    }
}

1.6 查找元素

在数组中查找指定元素需要遍历数组，每轮判断元素值是否匹配，若匹配则输出对应索引。

/* 在数组中查找指定元素 */
int find(int *nums, int size, int target) {
    for (int i = 0; i < size; i++) {
        if (nums[i] == target)
            return i;
    }
    return -1;
}

/* 在数组中查找指定元素 */
int find(int *nums, int size, int target) {
    for (int i = 0; i < size; i++) {
        if (nums[i] == target)
            return i;
    }
    return -1;
}

1.7 扩容数组

当需要扩容数组时，需要重新建立一个更大的数组，然后把原数组元素依次复制到新数组。这是操作的时间复杂度时$O(n)$,因此在数组很大时非常耗时。

/* 扩展数组长度 */
int *extend(int *nums, int size, int enlarge) {
    // 初始化一个扩展长度后的数组
    int *res = (int *)malloc(sizeof(int) * (size + enlarge));
    // 将原数组中的所有元素复制到新数组
    for (int i = 0; i < size; i++) {
        res[i] = nums[i];
    }
    // 初始化扩展后的空间
    for (int i = size; i < size + enlarge; i++) {
        res[i] = 0;
    }
    // 返回扩展后的新数组
    return res;
}

/* 扩展数组长度 */
int *extend(int *nums, int size, int enlarge) {
    // 初始化一个扩展长度后的数组
    int *res = new int[size + enlarge];
    // 将原数组中的所有元素复制到新数组
    for (int i = 0; i < size; i++) {
        res[i] = nums[i];
    }
    // 初始化扩展后的新元素为 0
    fill_n(res + size, enlarge, 0);
    // 释放内存
    delete[] nums;
    // 返回扩展后的新数组
    return res;
}