Olverae Assets

1 一句话定义

数组就是内存里一排紧挨着、大小相同的格子。正因为它们连续又等宽，知道首地址就能一步算出第 i 个格子的地址：address = base + i × 每格字节数——所以 a[i] 是 O(1) 直达，不用从头数。

像一排等宽的连号房间：知道 1 号房的位置和每间的宽度，要找第 i 间，不用挨个敲门，直接算"门牌 = 起点 + i×房宽"走过去。代价是房间数固定、且想在中间塞一间就得把后面所有房客整体往后挪（O(n)）——这正是后面链表要解决的痛点。

5 个 int 紧挨着排，每格 4 字节。第 i 格地址 = base + i×4——这条乘加公式就是「随机访问 O(1)」的全部秘密。

2 模型 · 地址怎么算，代价在哪

分两小步：第 1 步用寻址探索器弄懂"第 i 格地址 = base + i×size"这条核心公式（这就是 O(1) 的来源）；第 2 步看遍历 / 查找 / 插入的动画——访问单个是 O(1)，但扫一遍或往中间插就是 O(n)。

第 1 步 · 寻址探索器：第 i 格在哪？（点点看）

首地址 base = 0x1000，每格 4 字节（一个 int）。输入下标 i，看它的地址怎么一步算出来、是哪一格

访问 a[] →

关键：算地址只用一次乘法 + 加法，跟数组多长、i 多大都没关系 → 这就是随机访问 O(1)。代码里 a[i] 编译器就是按 *(base + i*sizeof(元素)) 来取的。

数组在代码里长什么样

声明时给定元素类型 + 个数，编译器就分配一整块连续内存；a[i] 与 *(a+i) 完全等价。

int a[8] = {10, 20, 35, 40, 55, 60}; // 8 格容量，先用 6 格
int n = 6;                  // 实际元素个数（容量≠个数！）

// 取第 i 个：下面三种写法等价，都是 base + i*4 那一格
a[i];   *(a + i);   i[a]; // （最后一种是 C 的冷知识）

数组名 a 在大多数场合退化成指向首元素的指针。所以传进函数后 sizeof(a) 量到的是指针大小、不再是整个数组——必须额外传长度 n。下面看三个操作的代价差别。

第 2 步 · 看三个操作。右边是真实 C 代码，随动画逐行高亮。重点感受：访问单格 O(1)，但遍历、查找、往中间插入都要碰 n 个格子 = O(n)。点例子，再点 ▶（建议 0.5×）。

数组操作演示

真实 C 代码（当前执行行高亮）

颜色说明

当前在看的格子命中 / 放入被搬动的格子

提示

点上方一个例子，再点 ▶ 看下标怎么逐格推进。

碰过的格子数（≈ 代价）

—

本次结果

3 核心要点 · 4 句人话看懂数组

每张卡片先用一句大白话说清"它到底在讲什么"，再配最小例子。

① 连续 + 等宽 = 能算地址

一句话：所有元素挨着放、每个一样大。这两条一成立，第 i 个的位置就能算出来，不用一个个找。

这是数组区别于链表的根：链表节点散落各处，只能顺着指针走；数组能跳着取。

addr(a[i]) = base + i × sizeof(元素)

② 随机访问 a[i] 是 O(1)

一句话：取任意一格都一步到位——一次乘加算出地址、直接读。和数组多长、i 多大都无关。

这是数组最强的地方。代价是它必须事先占好一整块连续内存，大小通常固定。

a[0]、a[7]、a[999] 取一个

都是同样的 1 次乘加 → O(1)

③ 插入 / 删除中间元素是 O(n)

一句话：想在中间塞一个或删一个，后面所有元素都得整体挪一格来补位/腾位——最坏要碰 n 个。

数组"取得快"，但"改结构慢"。需要频繁中间插删时，链表更合适（下一站）。

在 a[2] 插入：a[3..] 全部右移一格

删 a[2]：a[3..] 全部左移补上

④ 数组名会"退化"成指针

一句话：a[i] 其实是 *(a+i)。数组传进函数后只剩一个首地址指针，长度信息丢了。

所以 sizeof(a) 在函数里量到的是指针大小（8）、不是数组总字节——必须额外传 n。

void f(int a[]) // 等同 int *a

⟹ 想知道长度？再传一个 int n

4 错误实验室 · 点一下亲眼看 bug

下面 4 个是用数组最常翻车的坑——越界和「传参后 sizeof 失效」尤其爱考。点击卡片，控制台会模拟运行效果。

① 下标越界 a[n]

合法下标是 0~n−1；访问 a[n] 已经越过最后一格

② 循环写成 i <= n

最后一圈 i=n 越界；应是 i < n

③ 传参后用 sizeof 求长度

数组退化成指针，sizeof 量到的是 8，不是数组大小

④ 读没初始化的格子

局部数组不清零，里面是垃圾值

// 点击上方任一卡片，查看错误代码与运行效果

$ ./a.out （等待运行...）

5 即时小测 · 5 题 + 动手例题

这 5 题都卡在初学者最常错的点上——地址公式、合法下标范围、各操作复杂度、sizeof 陷阱。最后到练习系统亲手写一遍数组遍历。

去做例题：数组 · 最长严格递增连续子段

去做例题

读完这节，你应该明白：

数组 = 内存里连续、等宽的一排格子。正因连续等宽，第 i 格地址 = base + i×sizeof 一步可算，所以 随机访问 a[i] 是 O(1)——这是它最大的优点。但反过来，在中间插入 / 删除要把后面元素整体搬移，是 O(n)，而且容量通常固定。还有两个大坑：下标只能 0~n−1（越界即错），以及数组名传进函数会退化成指针、sizeof 失效，必须额外传长度 n。数组是排序、堆、哈希表、图邻接矩阵的底层地基；想要"中间插删也快"，就轮到链表出场了 ↓

数组

数组 Arrays