数组与特殊矩阵压缩

概念

数组是线性表的推广：一维数组就是线性表，二维数组是"元素为一维数组的线性表"。与一般线性表不同，数组的维数和维界（每维长度）一旦确定就不再改变，所以数组上只有"取元素"和"改元素"两种操作，不做插入删除。

特殊矩阵压缩（compressed storage）指：为多个值相同的元素只分配一个存储空间，对零元素不分配空间，从而节省内存。核心是建立矩阵下标 (i, j) → 一维数组下标 k 的映射公式。

一句话理解：压缩不是把数据变小，而是"把重复的和为零的裁掉"，代价是访问时要先算一遍下标。

原理

行优先与列优先

二维数组 A[n][m]（n 行 m 列）在内存中仍是一维的，两种存放方式：

行优先（C 语言采用）：A[0][0] A[0][1] ... A[0][m-1] A[1][0] A[1][1] ...
列优先（FORTRAN）：  A[0][0] A[1][0] ... A[n-1][0] A[0][1] A[1][1] ...

设每个元素占 L 个字节，基地址为 Loc(a₀₀)，下标从 0 开始：

方式	a[i][j] 的地址（下标从 0）	下标从 1 起
行优先	Loc = base + (i × m + j) × L	base + ((i-1) × m + (j-1)) × L
列优先	Loc = base + (j × n + i) × L	base + ((j-1) × n + (i-1)) × L

记忆法：行优先时行号乘"每行多少个元素"，列优先时列号乘"每列多少个元素"。

对称矩阵

n 阶对称矩阵满足 a[i][j] = a[j][i]，只需存主对角线及下三角（或上三角），共 n(n+1)/2 个元素。

存下三角（含对角线），下标从 0 起，一维数组 B[0..n(n+1)/2-1]：

$$k=\{\begin{array}{ll}{\displaystyle \frac{i(i+1)}{2}}+j,& i\ge j(\text{下三角})\\ {\displaystyle \frac{j(j+1)}{2}}+i,& i<j(\text{上三角，对称到 }j,i)\end{array}$$

前面 i 行共有 1+2+...+i = i(i+1)/2 个元素（第 0 行 1 个，第 1 行 2 个 …）。

三角矩阵

下三角矩阵（上三角全是同一个常数 C）比对称矩阵多存一个常数，总空间 n(n+1)/2 + 1，常数放在最后一个位置。

$$k=\{\begin{array}{ll}{\displaystyle \frac{i(i+1)}{2}}+j,& i\ge j\\ {\displaystyle \frac{n(n+1)}{2}},& i<j(\text{常数区})\end{array}$$

三对角矩阵（带状矩阵）

只有主对角线及其上下各一条对角线上有非零元素，其余为零。按行优先存放非零元素，n 阶共 3n - 2 个元素。

下标从 0 起，第 i 行之前共有 3i - 1 个非零元素（第 0 行 2 个，其余行每行 3 个），本行内偏移为 j - (i - 1)：

$$k=2i+j(\text{下标从 0 起，且 }|i-j|\le 1)$$

反推：i = ⌊(k + 1) / 3⌋，j = k - 2i。

稀疏矩阵

非零元素个数远少于零元素（一般认为非零元占比 < 5%）时，只存非零元。

方法	结构	适用
三元组顺序表	(row, col, value) 数组	最常考，适合矩阵转置
十字链表	每个非零元既是行链又是列链结点	适合矩阵频繁做加减（非零元位置会变）

转置的两种算法：普通转置 O(cols × 非零元数)，快速转置（先统计每列非零元个数，算出每列首个元素的存放位置）O(cols + 非零元数)。

示例

例 1：二维数组地址计算

数组 A[0..9][0..19]（10 行 20 列），每个元素占 4 字节，基地址 base = 1000。按行优先存储，求 A[5][8] 的地址。

完整计算过程：

第一步，确认每行列数与元素大小：m = 20，L = 4。

第二步，算 A[5][8] 之前有多少个元素：

$$5\times 20+8=100+8=108$$

即第 0~4 行共 100 个元素，第 5 行前面还有 8 个。

第三步，算地址：

$$Loc=1000+108\times 4=1000+432=1432$$

结论：A[5][8] 的地址为 1432。若改为列优先，则前面有 8 × 10 + 5 = 85 个元素，地址 = 1000 + 85 × 4 = 1340。

例 2：对称矩阵压缩

10 阶对称矩阵按行优先存下三角到一维数组 B（下标从 0），求 a[7][3] 与 a[3][7] 在 B 中的下标。

完整计算过程：

第一步，判断位置：a[7][3] 有 i = 7 ≥ j = 3，落在下三角，直接用下三角公式：

$$k=\frac{7\times 8}{2}+3=28+3=31$$

第二步，a[3][7] 有 i = 3 < j = 7，落在上三角，由对称性取其转置位置 (7, 3)：

$$k=\frac{7\times 8}{2}+3=31$$

结论：两者下标都是 31 —— 这正是对称矩阵压缩能省一半空间的直接体现。

第三步，验算容量：总空间 n(n+1)/2 = 10 × 11 / 2 = 55，31 < 55，合理。

C 语言：三元组顺序表与快速转置

#include <stdio.h>

#define MAXTERM 100

typedef struct {
    int row, col, val;
} Triple;

typedef struct {
    Triple data[MAXTERM];
    int rows, cols, nums;      /* 行数、列数、非零元个数 */
} TSMatrix;

/* 快速转置：O(cols + nums) */
void fastTranspose(const TSMatrix *M, TSMatrix *T) {
    int num[MAXTERM] = {0};    /* 每列非零元个数 */
    int pos[MAXTERM];          /* 每列首个元素在 T 中的下标 */

    T->rows = M->cols; T->cols = M->rows; T->nums = M->nums;
    if (M->nums == 0) return;

    for (int i = 0; i < M->nums; i++) num[M->data[i].col]++;
    pos[0] = 0;
    for (int c = 1; c < M->cols; c++) pos[c] = pos[c - 1] + num[c - 1];

    for (int i = 0; i < M->nums; i++) {
        int c = M->data[i].col;
        int p = pos[c]++;
        T->data[p].row = M->data[i].col;    /* 行列互换 */
        T->data[p].col = M->data[i].row;
        T->data[p].val = M->data[i].val;
    }
}

int main(void) {
    TSMatrix M = {{{0, 2, 5}, {1, 0, 8}, {2, 1, 3}}, 3, 3, 3};
    TSMatrix T;
    fastTranspose(&M, &T);
    for (int i = 0; i < T.nums; i++)
        printf("(%d,%d,%d) ", T.data[i].row, T.data[i].col, T.data[i].val);
    printf("\n");   /* (2,0,5) (0,1,8) (1,2,3) */
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

Python 对照

# 二维数组地址计算（行优先）
def addr(i, j, base, rows, cols, L, one_based=False):
    if one_based:
        i, j = i - 1, j - 1
    return base + (i * cols + j) * L

print(addr(5, 8, 1000, 10, 20, 4))      # 1432，行优先
print(addr(5, 8, 1000, 10, 20, 4, one_based=True))

# 对称矩阵下三角压缩的下标映射
def k_sym(i, j, zero_based=True):
    if not zero_based:
        i, j = i - 1, j - 1
    if i >= j:
        return i * (i + 1) // 2 + j
    return j * (j + 1) // 2 + i

print(k_sym(7, 3), k_sym(3, 7))         # 31 31

# 稀疏矩阵用字典表示，转置就是键互换
sparse = {(0, 2): 5, (1, 0): 8, (2, 1): 3}
print({(c, r): v for (r, c), v in sparse.items()})

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

考点

考点

1. 地址计算三步走（送分题，别丢）

① 确认行优先还是列优先 → ② 算出目标元素之前有多少个元素 → ③ 乘 L 加基址。

陷阱：下标从 0 还是从 1 开始。题目写 A[1..10][1..20] 就是 1 起，公式里要减 1。

2. 压缩映射公式（要会推，不要背）

矩阵	空间	关键公式（下标从 0 起）
对称（下三角）	n(n+1)/2	k = i(i+1)/2 + j（i ≥ j）
下三角矩阵	n(n+1)/2 + 1	同上，上三角统一映射到 n(n+1)/2
三对角	3n − 2	k = 2i + j
稀疏	3(t+1) 个单元	三元组 (i, j, v)

3. 易错点

• 对称矩阵压缩后，上三角元素要对称到 (j, i) 再套公式，不是套 i < j 的另一条公式。
• 三对角矩阵的行优先公式 k = 2i + j 只在下标从 0 起时成立；1 起时是 k = 2i + j - 3。
• 稀疏矩阵三元组通常按行优先有序存放，若题目没说有序，转置前不能假定。
• 快速转置的复杂度是 O(cols + nums)，不要误写成 O(rows × cols)。
• 数组是随机存取结构，取元素 O(1)；这与"数组插入删除要搬元素"是两件事，别混。

小结

• 数组一旦定维就不再改变，存取靠地址公式：行优先 i×m+j，列优先 j×n+i。
• 特殊矩阵压缩的本质是"建立 (i,j) → k 的映射"，公式要会推不要死背。
• 三对角矩阵只需 3n-2 个单元，是压缩率最直观的例子。
• 稀疏矩阵考的是快速转置的复杂度与 num[]/pos[] 两个辅助数组的构造。

下一篇：串与 KMP 模式匹配