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

image-20260601102647234

数组的常见操作

初始化数组

int arr[5];
int nums[5] = {1, 2, 3, 4, 5};
int* arr1 = new int[5];
int* nums1 = new int[5]{1, 2, 3, 4,5};

数组元素是否会被初始化为0，需要结合定义方式。

数组定义与初始化方式 元素是否初始化为 0 示例代码
全局 / 静态数组 ✅ 是 int arr[5]; (元素全为 0)
局部数组 (未初始化) ❌ 否 (随机垃圾值) void func() { int arr[5]; }
局部数组 (部分初始化) ✅ 是 (剩余元素自动补 0) int arr[5] = {1, 2}; (后三个为 0)
局部数组 (花括号清零) ✅ 是 (所有元素为 0) int arr[5] = {}; 或 int arr[5] = {0};

为了避免数组出现未初始化问题，推荐使用std::array 和 std::vector;

访问元素

image-20260601103136422

索引本质是内存地址的偏移。

int randomAccess(int* num, int size) {
  int randomIndex = rand()%size;
  int randomNum = nums[randomIndex];
  return randomNum;
}

插入元素

image-20260601103315101

插入会导致尾部元素的丢失。

void insert(int* nums, int size, int num, int index) {
	for (int i = size - 1; i > index; --i) {
    nums[i] = nums[i - 1];
  }
  nums[index] = num;
}

删除元素

image-20260601103524902

void remove(int* nums, int size, int index) {
	for (int i = index; i < size - 1; ++i) {
    nums[i] = nums[i + 1];
  }
}

遍历数组

void traverse(int* nums, int size) {
  int count = 0;
  for (int i = 0; i < size; ++i) {
    count += nums[i];
  }
}

查找元素

int find(int* nums, int size, int target) {
  for (int i = 0; i < size; ++i) {
    if (nums[i] == target) {
      return i;
    }
  }
  return -1;
}

数组的优点与局限

优点

  • 空间效率高：分配的连续内存块，无需额外结构开销。
  • 支持随机访问：可以在O(1)复杂度访问任意元素。
  • 缓存局部性：当访问数组元素时，计算机会缓存内存周围的区域，提高后续操作的执行速度。

局限

  • 插入和删除效率低：插入和删除需要移动大量的元素。
  • 长度不可变：扩容数组需要将数组全部元素复制到新数组，开销很大。
  • 空间浪费：如果数组分配的大小超过实际用途，则多余的空间被浪费。

Q&A

Q：如果连续空间不够，能申请数组吗

A：数组在内存中必须占用一块连续的、足够大的地址空间。如果系统当前找不到这样一块连续的内存，就会导致内存分配失败。