数组与特殊矩阵

多维数组的存储

多维数组在内存中按行优先或列优先线性存储
元素地址计算公式

特殊矩阵的压缩存储

对称矩阵、三角矩阵、稀疏矩阵等可用一维数组压缩存储
节省空间，提高效率
稀疏矩阵常用三元组表、压缩行/列存储

典型应用

数组：数据存储、查找、排序、矩阵运算
稀疏矩阵：图的邻接矩阵、科学计算

习题

习题 1

多维数组在内存中的存储方式是什么？

答案与解析

按行优先或列优先线性存储，元素地址用公式计算。

习题 2

稀疏矩阵如何压缩存储？

答案与解析

只存非零元素及其位置，常用三元组表或压缩行/列存储。

考研真题

真题 1

【2021·数据结构】简述稀疏矩阵的压缩存储方法及其优缺点。

答案与解析

稀疏矩阵压缩存储方法主要有： 1. 三元组表示法：只存储非零元素的行号、列号和值。 2. 十字链表法：用链表存储非零元素，便于矩阵运算。 3. 压缩行/列存储：适合行/列分布稀疏的矩阵。优点：节省存储空间，减少无效运算。缺点：随机访问效率低，算法实现复杂。