掌握多维数组的行主序和列主序地址计算，以及对称、三角、稀疏和三对角矩阵的压缩存储与下标映射。

# 一、多维数组的存储

多维数组在内存中仍是一段线性连续空间；二维下标只是逻辑视图。设二维数组 $A$ 有 $R$ 行、$C$ 列，元素大小为 $s$ 字节，首元素 $A[0][0]$ 的地址为 $\operatorname{LOC}(A[0][0])$。

# 1. 行主序与列主序

行主序先存完整的一行，再存下一行。第 $i$ 行、第 $j$ 列元素的线性下标为 $iC+j$：

$$\boxed{\operatorname{LOC}(A[i][j]) =\operatorname{LOC}(A[0][0])+(iC+j)s}.$$

C、C++ 通常采用行主序。列主序先存完整的一列，再存下一列，线性下标为 $jR+i$：

$$\boxed{\operatorname{LOC}(A[i][j]) =\operatorname{LOC}(A[0][0])+(jR+i)s}.$$

1
2
3
4
5
6
7

flowchart LR
    subgraph 行主序
        R0["A[0][0]  A[0][1]  A[0][2]"] --> R1["A[1][0]  A[1][1]  A[1][2]"]
    end
    subgraph 列主序
        C0["A[0][0]  A[1][0]"] --> C1["A[0][1]  A[1][1]"] --> C2["A[0][2]  A[1][2]"]
    end

# 二、对称矩阵与三角矩阵

# 1. 对称矩阵

$n$ 阶对称矩阵满足 $a_{ij}=a_{ji}$，只需保存主对角线及其下方或上方的一半元素，共

$$\frac{n(n+1)}2$$

个元素。

以下使用零基下标，并按行优先压缩保存下三角区。设一维数组为 B，则

$$k= \begin{cases} \dfrac{i(i+1)}2+j,&i\ge j,\\[6pt] \dfrac{j(j+1)}2+i,&i<j. \end{cases}$$

其中 $k$ 是 B 的下标。第二种情况利用 $a_{ij}=a_{ji}$ 转而查找下三角中的 $a_{ji}$。

# 2. 三角矩阵

上三角矩阵中主对角线及其上方元素有意义，下方元素往往均为同一个常量 $c$；下三角矩阵与之对称。压缩存储除保存有效三角区外，通常额外保留一个单元保存常量 $c$。

对零基 $n$ 阶上三角矩阵，按行优先存储上三角区时，$i\le j$ 的下标为

$$k=i n-\frac{i(i-1)}2+(j-i) =i n-\frac{i(i+1)}2+j.$$

若 $i>j$，则访问额外常量单元

$$B\left[\frac{n(n+1)}2\right].$$

# 三、稀疏矩阵

当 $m\times n$ 矩阵只有 $t$ 个非零元，且 $t\ll mn$ 时，完整数组会浪费大量空间。稀疏矩阵可只保存非零元及其行、列位置。

# 1. 三元组表

三元组表常按行序优先保存 $(row,col,value)$，并记录矩阵行数、列数和非零元数。空间复杂度为 $O(t)$，但按指定行列随机查询通常需要顺序扫描，最坏为 $O(t)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#define MAX_TERMS 100
typedef int ElemType;

typedef struct {
    int row;
    int col;
    ElemType value;
} Triple;

typedef struct {
    int rows;
    int cols;
    int terms;
    Triple data[MAX_TERMS];
} TSMatrix;

三元组表结构简单，适合顺序输出、转置和稀疏矩阵相加等按非零元扫描的任务。

# 2. 十字链表

若需要频繁按行和按列访问，可采用十字链表。每个非零结点同时属于一条行链和一条列链，结点包含行号、列号、值以及 right、down 两个链接；另有 rhead、chead 分别索引各行、各列的首结点。

1
2
3
4
5
6
7

flowchart LR
    R1[rhead 1] --> X11["(1,1,3)"]
    X11 --> X13["(1,3,5)"]
    C1[chead 1] --> X11
    C3[chead 3] --> X13
    X11 -.down.-> X31["(3,1,2)"]
    R3[rhead 3] --> X31

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

typedef struct CrossNode {
    int row;
    int col;
    ElemType value;
    struct CrossNode *right;
    struct CrossNode *down;
} CrossNode;

typedef struct {
    CrossNode **rhead;
    CrossNode **chead;
    int rows;
    int cols;
    int terms;
} CrossList;

十字链表只保存非零元并支持按行、按列遍历；插入或删除结点时需同时维护对应行链和列链。

# 四、三对角矩阵

$n$ 阶三对角矩阵仅主对角线、上对角线和下对角线可能非零，非零元总数为

$$3n-2.$$

若采用零基下标并逐行保存非零带状元素，则满足 $|i-j|\le1$ 的元素可映射为

$$\boxed{k=2i+j}.$$

例如第 0 行保存 $(0,0),(0,1)$，第 1 行保存 $(1,0),(1,1),(1,2)$；最后一行只保存 $(n-1,n-2),(n-1,n-1)$。若 $|i-j|>1$，元素为零或题设给定的默认值，不需要存入压缩数组。

另一种等价实现是分别使用下对角线、主对角线、上对角线三个数组；它们的有效长度分别为 $n-1,n,n-1$。

# 五、考场检查清单

1. 地址题先确认行主序或列主序，再确认下标从 0 还是从 1 开始。
2. 对称矩阵压缩只保存一半加主对角线，共 $n(n+1)/2$ 个元素。
3. 三角矩阵的另一半若为常量，应额外保存该常量或按题设直接返回。
4. 三元组表保存非零元，按位置查找一般不是 $O(1)$；十字链表以行链和列链支持双向组织。
5. 三对角矩阵非零元数量是 $3n-2$，不是 $3n$。