数组与特殊矩阵

数组是程序设计中最基础的存储结构，几乎所有数据结构的底层都离不开数组。对于具有大量重复元素或大量零元素的特殊矩阵与稀疏矩阵，压缩存储能大幅节省空间，是考研的常考考点。本章围绕”如何用更少的空间存储矩阵”这一核心问题，介绍多维数组的地址计算、特殊矩阵的压缩存储方法与稀疏矩阵的两种表示法。读完本节，你将能够掌握一维、二维数组的存储结构，能计算元素地址、理解行优先与列优先存储的地址公式及区别、掌握对称矩阵、下三角矩阵、三对角矩阵的压缩存储公式、掌握稀疏矩阵的三元组表示法与十字链表法、运用压缩存储解决矩阵的存取与运算问题。

本章要解决的问题

一个 10×10 的矩阵需要 100 个存储单元，但对称矩阵其实只需存一半，稀疏矩阵甚至只需存几十个非零元素。如何在保持”能访问任意元素”的前提下，把矩阵压缩到最小空间？这需要掌握多维数组的行优先/列优先地址计算公式，理解对称矩阵、三角矩阵、三对角矩阵的压缩规律，以及稀疏矩阵的三元组与十字链表表示。

基础路线：多维数组的存储 → 特殊矩阵的压缩存储，先掌握地址计算公式。

进阶路线：稀疏矩阵 → 典型应用 → 总结，理解三元组与十字链表的适用场景。