3.4.4 稀疏矩阵

教材导航 · 第3章

原书定位

印刷页P104起,对应PDF第116页。下文为目视整理的知识提要;完整内容见原书对照。

非零元素远少于全部元素,且位置一般没有固定规律。为每个非零项保存 (行号, 列号, 值),还需保存矩阵总行数、总列数和非零项数。

三元组表可顺序存储,也可通过十字链表同时组织行链与列链。压缩后通常不能像完整二维数组一样按下标在 O(1)O(1) 时间直接定位任意元素。不能仅由三元组中出现的最大下标恢复矩阵大小,因为可能有全零末行或末列。

图3.26 稀疏矩阵与对应三元组

图3.26 稀疏矩阵与对应三元组,原书P104。

对应练习

3.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P104,PDF第116页