特殊矩阵的压缩存储

一、对称矩阵

定义

n 阶方阵 A 满足 $ a_{ij} = a_{ji} $（$ 1 \le i, j \le n $）。

特点

• 关于主对角线对称
• 只需存储下三角（或上三角）部分

压缩存储

用一维数组存储下三角（含对角线）元素：

• 元素个数：$ n(n+1)/2 $
• 存储空间：$ n(n+1)/2 $ 个存储单元

地址映射公式（按行优先存下三角）

当 $ i \ge j $（下三角）：

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

当 $ i < j $（上三角），利用 $ a_{ij} = a_{ji} $：

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

地址计算：$ LOC(a_{ij}) = LOC(a_{11}) + k \times sizeof(ElemType) $。

二、三角矩阵

1. 上三角矩阵

下三角全为常数 c（或 0）。压缩存储上三角 + 一个常数 c，元素个数 $ n(n+1)/2 + 1 $。

上三角元素 $ a_{ij} $（$ i \le j $）下标：

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

2. 下三角矩阵

上三角全为常数 c。下三角元素 $ a_{ij} $（$ i \ge j $）：

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

与对称矩阵下三角公式相同；常数统一映射到最后一个位置。

三、三对角矩阵（带状矩阵）

定义

只有主对角线及其上下各一条对角线有非零元素。

特点

• 每行最多 3 个非零元素（第 1 行和第 n 行 2 个）
• 非零元素总数：$ 3n - 2 $

地址映射

当 $ |i-j| \le 1 $ 时：

$$k = 2(i-1) + (j-1) = 2i + j - 3$$

反向映射（已知 k 求 i,j）：

$$i = \left\lfloor \frac{k+1}{3} \right\rfloor + 1,\quad j = k - 2(i-1) + 1 = k - 2i + 3$$

四、稀疏矩阵

定义

非零元素个数远小于元素总数（通常 $ t < 0.05 \times m \times n $）。

1. 三元组表

typedef struct {
    int i, j;       // 行号、列号
    ElemType val;   // 元素值
} Triple;

typedef struct {
    Triple data[MAXSIZE+1];  // data[0]未用或存矩阵信息
    int mu, nu, tu;          // 行数、列数、非零元素个数
} TSMatrix;

2. 十字链表

typedef struct OLNode {
    int i, j;
    ElemType val;
    struct OLNode *right, *down;  // 行链、列链
} OLNode, *OLink;

typedef struct {
    OLink *rhead, *chead;  // 行头、列头指针数组
    int mu, nu, tu;
} CrossList;