数据结构的学习中，数组与特殊矩阵是基础且核心的内容。它们不仅是程序设计中最常用的线性结构，更是处理复杂矩阵运算的基础。本文将结合解析与真题，带你彻底搞懂数组的存储方式和特殊矩阵的压缩存储技巧。

一、一维数组与二维数组：存储是基础

1. 一维数组的存储

一维数组是最基础的线性结构，在内存中连续存储，每个元素占用相同大小的存储单元。

int main()
{
    int a[] = {16,47,89,42,38};
}

地址	101	105	109	113	117
元素	16	47	89	42	38
下标	a[0]	a[1]	a[2]	a[3]	a[4]

• 地址计算：若基地址为 LOC(a[0])，每个元素占 k 字节，则 a[i] 的地址为：LOC(a[i])=LOC(a[0])+i×k

2. 二维数组的存储：行优先 vs 列优先

二维数组在内存中本质是一维线性存储，有两种常见的存储顺序：

（1）行优先存储（C 语言默认）

地址	101	105	109	113	117	121
元素	1	2	3	4	5	6
下标	a[0][0]	a[0][1]	a[0][2]	a[1][0]	a[1][1]	a[1][2]

地址公式（m 行 n 列）：LOC(a[i][j])=LOC(a[0][0])+(i×n+j)×k

（2）列优先存储（Fortran、Matlab 等语言）

先存储第 0 列，再存储第 1 列，以此类推。

地址	101	105	109	113	117	121
元素	1	4	2	5	3	6
下标	a[0][0]	a[1][0]	a[0][1]	a[1][1]	a[0][2]	a[1][2]

地址公式（m 行 n 列）：LOC(a[i][j])=LOC(a[0][0])+(j×m+i)×k

---

3. 真题实战：二维数组地址计算

步骤解析：

1. 设数组为 m 行 n 列，行优先地址公式：LOC(A[i][j])=100+i×n+j
2. 代入 A[3][3] = 220：100+3n+3=220⟹3n=117⟹n=39
3. 计算 A[5][5]：LOC(A[5][5])=100+5×39+5=100+195+5=300 

答案：B

二、特殊矩阵：压缩存储是关键

特殊矩阵（如对称矩阵、三角矩阵、三对角矩阵、稀疏矩阵）存在大量重复或零元素，为了节省空间，需要对其进行压缩存储。

1. 对称矩阵

对称矩阵满足 a[i][j] = a[j][i]，因此只需存储上三角或下三角部分。

以 n×n 对称矩阵为例，下三角部分（i ≥ j）共有 n(n+1)/2 个元素。

存储映射：

• 行优先存储下三角元素到一维数组 B 中：k=2i(i+1)​+j(i≥j)
• 若 i < j，则 a[i][j] = a[j][i]，直接映射到 k = j(j+1)/2 + i。

真题实战：

步骤解析：

1. 上三角元素行优先存储，先存第 1 行（j=1~12），再存第 2 行（j=2~12）……
2. 前 5 行的元素总数：∑k=15​(12−k+1)=12+11+10+9+8=50
3. 第 6 行中，m_{6,6} 是第 1 个元素，因此下标为 50 + 1 - 1 = 50（C 语言下标从 0 开始）。

答案：A. 50

2. 三角矩阵

• 上三角矩阵：主对角线以下（i > j）的元素均为 0。
• 下三角矩阵：主对角线以上（i < j）的元素均为 0。

存储方式与对称矩阵类似，只存储非零部分，零元素不再重复存储。

数组从 0 开始计数

题目条件：

• 12×12 对称矩阵，只存上三角部分（含对角线），满足 1≤i≤j≤12
• 按行优先存入 C 语言一维数组（数组下标从 0 开始）
• 目标元素：m6,6​（第 6 行、第 6 列）

---

步骤 1：计算前 5 行（i=1 到 i=5）的元素总数

上三角第i行的元素个数为：12−i+1（从第i列到第 12 列）

• 第 1 行：12−1+1=12 个
• 第 2 行：12−2+1=11 个
• 第 3 行：12−3+1=10 个
• 第 4 行：12−4+1=9 个
• 第 5 行：12−5+1=8 个

前 5 行总元素数：12+11+10+9+8=50

---

步骤 2：确定m6,6​的下标

C 语言数组下标从 0 开始，所以：

• 前 5 行的元素，下标范围是：0∼49（共 50 个元素）
• 第 6 行的第一个元素是m6,6​，它的下标就是前 5 行的元素总数：50

所以m6,6​在数组N中的下标是 50，

答案：A. 50

步骤 1：明确 “列优先” 规则

对称矩阵上三角部分满足 1≤i≤j≤10，按列优先存储时，先存第 1 列的上三角元素，再存第 2 列，依此类推。

对于第 j 列，上三角元素的行号 i 范围是 1≤i≤j，共有 j 个元素。

---

步骤 2：计算前 1 列（j=1）的元素总数

第 1 列（j=1）的上三角元素只有 m1,1​，共 1 个。

---

步骤 3：计算第 2 列中 m7,2​ 的位置

注意：m7,2​ 属于上三角部分，根据对称矩阵性质 m7,2​=m2,7​，所以实际存储的是 m2,7​，对应列 j=7，行 i=2。

• 先计算前 6 列（j=1 到 j=6）的元素总数：1+2+3+4+5+6=21

• 第 7 列中，m2,7​ 是第 2 个元素（i=1,2），所以在数组中的下标为：21+2−1=22（C 语言数组下标从 0 开始，所以需要减 1）

  

答案：C. 22

3. 三对角矩阵

三对角矩阵是指除了主对角线及其上下两条对角线外，其余元素均为 0 的矩阵。

对于 n×n 三对角矩阵，非零元素总数为 3n - 2，可按行优先压缩存储到一维数组中。

地址映射公式：k=2i+j(∣i−j∣≤1)

步骤 1：理解三对角矩阵的结构

三对角矩阵中，只有当 ∣i−j∣≤1 时，元素 mi,j​ 非零（或需要存储）。行优先存储时，每行最多有 3 个元素：

• 第 1 行：j=1,2（2 个元素）
• 第 2~99 行：j=i−1,i,i+1（3 个元素）
• 第 100 行：j=99,100（2 个元素）

---

步骤 2：计算前 29 行的元素总数

• 第 1 行：2 个元素
• 第 2~29 行：共 29−1=28 行，每行 3 个元素
• 前 29 行总元素数：2+28×3=2+84=86

---

步骤 3：计算 m30,30​ 在第 30 行的位置

第 30 行的元素依次是 m30,29​、m30,30​、m30,31​。m30,30​ 是第 30 行的第 2 个元素。

所以它在数组中的下标为：86+2−1=87（数组下标从 0 开始，所以减 1）

---

答案：B. 87

4. 稀疏矩阵

稀疏矩阵是指零元素个数远多于非零元素个数的矩阵。常用的压缩存储方式有：

（1）三元组存储

用三元组 (i, j, value) 记录每个非零元素的行号、列号和值。

i   j   value
0   1   3
2   0   1
3   3   7

（2）十字链表

将每行和每列的非零元素分别用链表连接，便于快速访问行和列的元素。

三、总结与思考

结构类型	存储特点	核心公式 / 方法
一维数组	连续线性存储	LOC(a[i]) = LOC(a[0]) + i*k
二维数组（行优先）	按行展开存储	LOC(a[i][j]) = LOC(a[0][0]) + (i*n + j)*k
二维数组（列优先）	按列展开存储	LOC(a[i][j]) = LOC(a[0][0]) + (j*m + i)*k
对称矩阵	只存上 / 下三角部分	k = i(i+1)/2 + j（下三角）
三角矩阵	只存非零部分	同对称矩阵，零元素不存储
三对角矩阵	只存三条对角线元素	k = 2i + j
稀疏矩阵	三元组 / 十字链表存储	仅存储非零元素

数组与特殊矩阵的存储本质是空间与时间的权衡：通过压缩存储减少空间占用，同时保证高效的访问效率。在实际开发中，理解这些存储方式是优化算法和处理大规模数据的基础。