数组和广义表：矩阵压缩存储与广义表定义

"三角矩阵是数据结构中的一种特殊形式，尤其在处理特定问题时能有效节省存储空间。在清华大学版的数据结构课程中，数组和广义表是重要的章节，讲解了如何定义、表示和实现这些数据结构。三角矩阵分为上三角矩阵和下三角矩阵，主要特点是矩阵主对角线以下或以上的元素要么是常数c，要么为零。通常情况下，这个常数是零，这样的矩阵称为稀疏矩阵。 数组，尤其是线性结构的扩展——一维、二维和多维数组，是数据结构的基础。一维数组可以被视为具有连续存储地址的线性序列，通过简单的公式可以直接计算任一元素的存储位置。二维数组则进一步扩展了这一概念，形成了一种矩阵结构，其中每个元素都有行和列的索引，可以视为由行向量或列向量组成的结构。多维数组则是在更多维度上的扩展，数据元素可能有多个直接前驱和后继。 在数组中，特别是对于大矩阵，当非零元素很少时，使用压缩存储技术是必要的。对于特殊矩阵，如三角矩阵，可以通过只存储非零元素来减少存储需求。这种技术在处理稀疏矩阵时特别有用，因为稀疏矩阵中大部分元素为零。稀疏矩阵的压缩存储通常有两种方式：三元组表示法和压缩存储的链接列表。三元组表示法记录每个非零元素的行号、列号和值；压缩存储的链接列表则通过链接结构仅存储非零元素，进一步节省空间。 在讲解完数组后，课程会引入广义表这一概念，它是一种更通用的数据结构，数据元素本身也可以是复杂的数据结构，例如可以是其他列表或组合。广义表的存储结构通常采用链表实现，允许灵活的结构和操作，可以处理递归定义的数据。 数组和广义表是数据结构中不可或缺的部分，它们提供了解决问题的不同视角和方法，特别是在处理大量数据时，理解和掌握这些数据结构的表示和优化技术至关重要。"