核心内容摘要
星野璀璨，情深意长：一个关于梦想与传承的温暖故事
目录
数组从逻辑维度到物理地址
行优先 (Row-major) 与 列优先 (Column-major)
特殊矩阵的压缩存储
对称矩阵 ()
三角矩阵
稀疏矩阵 (Sparse Matrix)变废为宝
三元组顺序表 (Triple Oracle)
十字链表 (Cross List) —— 终极优化
广义表 (Generalized Lists)递归的线性表
核心操作GetHead 与 GetTail
今日深度
总结表避坑指南
数组从逻辑维度到物理地址数组是随机存取结构。
在内存中多维数组必须映射为一维线性地址。
行优先 (Row-major) 与 列优先 (Column-major)行优先C语言、严版教材默认先存第一行再存第二行。
二维数组地址计算公式以的二维数组为例下标从 0 开始详细注释代表跳过了前行的所有元素代表在当前行偏移的位置是每个元素占用的字节数。
特殊矩阵的压缩存储对于有规律的矩阵我们只存“有效”部分其余部分通过数学公式计算得出。
对称矩阵 ()只需存储下三角含对角线的个元素。
映射公式将二维下标映射到一维数组。
(当时)
三角矩阵上下三角全是常数。
同样只存有效的一半加一个位置存常数。
稀疏矩阵 (Sparse Matrix)变废为宝当矩阵中绝大多数元素为 0 时非零元素占比通常 5%直接存储会造成内存极大浪费。
三元组顺序表 (Triple Oracle)原理每个非零元素存为一个三元组(行下标, 列下标, 值)。
缺点失去了随机存取特性。
高频考点快速转置算法。
传统的行列互换后为了保持三元组按行序排列需要预先统计每列非零个数计算出转置后每行应放的起始位置。
十字链表 (Cross List) —— 终极优化结构每个非零元素是一个节点包含五个域行、列、值、行指针(right)、列指针(down)。
优势在进行矩阵加法、乘法等动态运算时十字链表无需像三元组那样频繁移动元素效率极高。
广义表 (Generalized Lists)递归的线性表广义表是线性表的推广它的元素可以是原子单个数据也可以是子表。
核心操作GetHead 与 GetTail这是考试中最容易丢分的地方GetHead(L)取出的第一个元素。
可以是原子也可以是子表。
GetTail(L)除去第一个元素外剩下的元素组成的表。
⚠️ 必考例题——注意尾部一定带括号是一个表
今日深度
总结表存储对象核心挑战解决方案适用场景稠密矩阵快速存取顺序存储行优先基础科学计算对称/对角矩阵冗余数据多下三角/对角压缩物理模拟、结构分析稀疏矩阵0 元素极多三元组、十字链表社交网络邻接矩阵、推荐算法广义表结构不规则链式存储头尾链Lisp 语言、递归逻辑表示避坑指南公式偏移一定要看清题目下标是从 0 还是 1 开始。
如果是从 1 开始地址公式变为。
转置细节三元组转置时如果不使用“快速转置”时间复杂度会升至 $O(n \times t)$$t$ 为非零元素个数这在考研大题中是扣分项。
广义表空表。
空表也是表不能写“无”。