清华大学严蔚敏数据结构：对称矩阵的压缩存储

在清华大学严蔚敏的数据结构课程中，5.3.1节专门探讨了特殊矩阵，这是一种非零元素或零元素分布具有特定规律的矩阵。对称矩阵是一个重要的特殊矩阵类型，它在下述条件下的n阶方阵A被称为对称矩阵：元素满足aij=aji，即矩阵的对角线上下元素相等，0≤i,j≤n-1。对称矩阵的特点是其元素关于主对角线对称，因此，可以通过存储上三角或下三角的元素来节省存储空间，因为对称的元素只需存储一次，另一半可以通过对称性得出。这种存储策略可以显著减少存储需求，通常达到约50%的空间效率。 "行优先"策略是常采用的方法，它按照矩阵的行顺序存储非对角线上的元素，这样在查找或修改元素时，只需要访问到对角线以下的部分，而对称部分无需独立存储。对称矩阵在实际应用中广泛存在，例如在物理学中的哈密顿矩阵、工程中的振动系统模型等，都是对称矩阵的典型例子。 除了对称矩阵，还有其他特殊矩阵如稀疏矩阵（主要由少量非零元素组成）、单位矩阵（所有主对角线元素为1，其余为0）、三角矩阵（分为上三角矩阵和下三角矩阵，只有对角线及其上方或下方的元素非零）等。这些特殊矩阵的高效存储和操作对于优化计算性能至关重要，尤其是在大规模数据处理和科学计算中。 数据结构课程中提到，数据结构是计算机科学的基础，它研究如何组织和存储数据以及如何有效地执行与数据相关的操作。通过对称矩阵的讨论，展示了如何根据数据的内在结构设计算法，提高程序的效率。例如，电话号码查询系统和图书馆书目检索系统的实现，就需要根据数据的逻辑结构（如二维数组、表结构或向量）来设计查询算法，确保查找速度和存储空间的有效利用。 此外，课程还涉及到了基本概念和术语，如数据（Data）的定义，它指的是信息的基本单元；数据结构则是对数据的组织方式，包括逻辑结构（数据元素之间的关系）和物理结构（数据在计算机内存中的存储方式）。数据结构还包含了对这些结构的操作，如搜索、排序、插入和删除等，以及这些操作的时间复杂度和空间复杂度分析。 通过以上内容，我们可以看到数据结构课程的核心在于理解不同数据结构的特点和适用场景，以便在实际问题中选择最合适的存储和处理方法，从而提升程序的性能和效率。