存储结构（物理结构）是数据在计算机中的实际存储方式，包括数据元素本身的存储和数据元素之间关系的表示。
四种基本存储结构：
顺序存储：元素 $a_i$ 的地址 $\text{Loc}(a_i) = \text{Loc}(a_0) + i \times \text{sizeof}(\text{elem})$，支持随机访问 $O(1)$。
链式存储：每个结点含数据域和指针域，逻辑相邻靠指针维持，插入删除 $O(1)$ 但无法随机访问。
索引存储：数据部分通常仍是顺序存储，索引表加速查找（如数据库索引、B+ 树）。
散列存储：根据关键字经散列函数算地址，查找平均 $O(1)$，但需处理冲突，且不能表示前后件关系。
| 存储结构 | 优点 | 缺点 | 典型应用 |
|---|---|---|---|
| 顺序存储 | 随机访问 $O(1)$，空间利用率高 | 插入删除 $O(n)$，需预分配 | 顺序表、数组 |
| 链式存储 | 插入删除 $O(1)$，动态分配 | 不能随机访问，有指针开销 | 链表、树、图 |
| 索引存储 | 查找效率高 $O(\log n)$ | 需额外索引表空间 | 数据库索引、B+ 树 |
| 散列存储 | 查找 $O(1)$ 平均 | 需处理冲突，不能顺序遍历 | 哈希表 |
| 考法 | 解题套路 |
|---|---|
| 判断存储结构 | 地址相邻→顺序，指针→链式，索引表→索引，哈希函数→散列 |
| 比较优劣 | 从访问方式、增删效率、空间开销三方面 |
| 选存储结构 | 频繁查找→索引/散列；频繁增删→链式；随机访问→顺序 |
↑ 以上为站内 HTML 相对链接（纯网页可浏览）；本页右上「在 Obsidian 中打开」跳回源笔记。