摘要矩阵压缩存储是数据结构与考研 408 的高频考点。本文系统梳理三角矩阵、三对角矩阵、稀疏矩阵的存储思想、下标计算公式与易错点并补充公式推导和边界说明适合期末复习与考研冲刺。关键词数据结构、矩阵压缩、三角矩阵、三对角矩阵、稀疏矩阵、408考研适合读者数据结构初学者、考研 408 备考同学、正在复习矩阵知识点的 CSer。阅读收获掌握三类特殊矩阵的压缩存储方式能独立推导下标对应公式避开下标起始规则带来的常见陷阱。目录一、三角矩阵1.1 分类1.2 解决方法1.3 三角矩阵中元素位置和数组下标的对应关系1.3.1 下三角矩阵1.3.2 上三角矩阵二、三对角矩阵2.1 概念2.2 特点2.3 存储方式2.4 由 k 反推 i 和 j2.5 和三角矩阵的区别三、稀疏矩阵3.1 稀疏矩阵定义3.2 存储方法3.2.1 顺序存储——三元组表3.2.2 十字链表表示法四、公式速查与易错点五、总结一、三角矩阵1.1 分类三角矩阵按主对角线划分分为两种类型定义压缩策略上三角矩阵下三角区存储相同的常量元素只存主对角线 上三角区常量单独存下三角矩阵上三角区存储相同的常量元素只存主对角线 下三角区常量单独存1.2 解决方法按照行优先只存储主对角线和下三角区的元素到一维数组中并在最后一个位置即数组下标为n(n1)/2上存储常量。共需n(n1)/2 1个存储单元相比原来的n²节约近一半空间。1.3 三角矩阵中元素位置和数组下标的对应关系约定矩阵下标从 1 开始一维数组下标从 0 开始。1.3.1 下三角矩阵当i ≥ j时元素aij在下三角区或主对角线上k i(i-1)/2 (j-1)当i j时元素属于上三角区常量k n(n1)/2推导过程前i-1行共有1 2 ... (i-1) i(i-1)/2个元素。在第i行中aij前面有j-1个元素。因此k i(i-1)/2 (j-1)1.3.2 上三角矩阵当i ≤ j时元素aij在上三角区或主对角线上k (i-1)(2n-i2)/2 (j-i)当i j时元素属于下三角区常量k n(n1)/2推导过程前i-1行共有n (n-1) ... (n-i2) (i-1)(2n-i2)/2个元素。在第i行中aij前面有j-i个元素。因此k (i-1)(2n-i2)/2 (j-i)边界说明如果一维数组下标从 1 开始则上述元素下标整体 1常量位置为n(n1)/2 1。二、三对角矩阵2.1 概念三对角矩阵只有对角三行有数据其他地方都是 0。2.2 特点对于三对角矩阵中的任意元素aij当i-j 1时有aij 0。2.3 存储方式共有3n-2个元素可以存储在数组a[3n-2]中。若按照行优先存储的方式来存则数组下标与元素在矩阵中的位置的关系为k 3i - 4 j - i 1 2i j - 3推导过程第 1 行有 2 个元素第 2 到第i-1行每行 3 个元素因此前i-1行共有2 3(i-2) 3i - 4个元素。第i行中aij的行内偏移为j - (i-1) j - i 1所以数组下标从 0 开始k (3i-4) (j-i1) 2i j - 3若已经k则可以根据不等式3i - 4 k 1 ≤ 3i - 1从而求出k。2.4 由 k 反推 i 和 j若数组下标从 0 开始已知k有3i-4 ≤ k ≤ 3i-2可解出i floor((k1)/3) 1j k - 2i 3408真题示例100 阶三对角矩阵按行优先存入下标从 0 开始的一维数组求a30,30的下标。代入k 2 × 30 30 - 3 87所以下标为 87。2.5 和三角矩阵的区别对比项三角矩阵三对角矩阵每行元素个数各不相同固定为 2 或 3 个能否由 k 反推 i,j不能能存储元素总数n(n1)/2 13n-2三对角矩阵每行元素个数固定因此可以通过k反推ij而三角矩阵每行元素个数不同无法通过k反推。三、稀疏矩阵3.1 稀疏矩阵定义矩阵中大部分元素为 0仅有少量非零元素。通常非零元素占比不超过 5% 时可视为稀疏矩阵。3.2 存储方法3.2.1 顺序存储——三元组表将非零元素和其对应的行和列构成一个三元组(行标列标值)所有三元组按一定顺序排列形成顺序表。typedef struct { int row; // 行标 int col; // 列标 int value; // 值 } Triple; typedef struct { Triple data[MAXSIZE 1]; int rows, cols, nums; } TSMatrix;3.2.2 十字链表表示法矩阵的每一行用一个带头结点的链表表示每一列也用一个带头结点的链表表示。typedef struct OLNode { int row, col; int value; struct OLNode *right; // 同行下一个非零元素 struct OLNode *down; // 同列下一个非零元素 } OLNode, *OLink; typedef struct { OLink *rhead; // 行头指针数组 OLink *chead; // 列头指针数组 int rows, cols, nums; } CrossList;408考点适用于压缩存储稀疏矩阵的两种存储结构是三元组表和十字链表。四、公式速查与易错点知识点公式备注下三角矩阵k i(i-1)/2 j - 1数组下标从 0i ≥ j上三角矩阵k (i-1)(2n-i2)/2 j - i数组下标从 0i ≤ j三对角矩阵k 2i j - 3数组下标从 0三对角矩阵k 2i j - 2数组下标从 1稀疏矩阵三元组(row, col, value)顺序存储稀疏矩阵十字链表right / down指针链式存储易错点提醒矩阵下标从 0 还是从 1 开始数组下标从 0 还是从 1 开始行优先还是列优先常量元素存在哪个位置考试时建议用特殊值代入验证例如取a11看公式结果是否为 0 或 1。五、总结矩阵压缩存储的关键在于理解存储顺序和下标映射关系三角矩阵每行元素个数不同按行优先存储常量单独存。三对角矩阵每行元素个数固定可由k反推i,j。稀疏矩阵三元组表适合顺序存储十字链表适合频繁访问行列。建议复习时手推一遍公式并用特殊值代入验证。如果觉得本文对你有帮助欢迎点赞 收藏 关注。