数组与广义表：三角矩阵及稀疏矩阵压缩存储

"本课件主要讲解了数据结构中的数组和广义表，特别是三角矩阵的存储方式以及数组和广义表的顺序表示和实现。" 在数据结构中，数组是一种基础且重要的数据组织形式，它允许我们以固定的时间复杂度访问任意位置的元素。数组的类型定义通常涉及其维度、每个维度的长度以及元素的下标范围。例如，二维数组的定义包括两个下标，分别对应行和列，且每个下标都有其最大和最小值。数组的基本操作包括初始化、销毁、获取元素值以及赋值，这些操作都需要确保下标的合法性以避免越界。 在处理特定类型的矩阵，如三角矩阵时，可以利用其特性进行优化存储。三角矩阵分为上三角矩阵和下三角矩阵，其中上三角矩阵包含主对角线以上的元素，下三角矩阵包含主对角线以下的元素。对于三角矩阵，当元素位于主对角线上或下方时（对于下三角），或上方时（对于上三角），它们按照行优先顺序存储。由于三角矩阵的非零元素远少于一般矩阵，因此在存储空间有限的情况下，可以使用压缩存储技术，如稀疏矩阵表示，来节省空间。 稀疏矩阵的压缩存储通常采用三元组（行号，列号，值）或链表的形式，只存储非零元素，大大减少了存储需求。对于三角矩阵，由于其非零元素分布的规律性，可以进一步优化存储结构，例如，只需要存储下三角或上三角的元素，而无需为对角线上的元素额外分配空间，因为它们与对应的上三角或下三角元素共享空间。 数组的顺序表示和实现涉及到如何在内存中以一维的形式存储多维的数据。这通常有两种方式：行序为主序和列序为主序。行序为主序意味着按照行优先的方式存储元素，适用于PASCAL和C等编程语言；而列序为主序则是按照列优先，常见于FORTRAN和VB。无论哪种方式，都可以通过计算公式确定数组中任意元素的存储位置，例如二维数组中元素`ai,j`的位置可以通过基地址加上行偏移和列偏移得到。 广义表是一种更通用的数据结构，它可以表示具有嵌套特性的数据。广义表的类型定义包括其元素可以是原子或子表，而表示方法通常有链式表示和顺序表示。链式表示利用指针链接元素，而顺序表示则是在一维数组中存储广义表的元素，根据元素类型决定是原子还是子表的起始位置。 这个课件涵盖了数组的定义、操作、顺序存储以及特殊矩阵的存储优化，同时介绍了广义表的基础知识，对于理解和应用数据结构有很重要的价值。学习这些内容有助于提升在数据结构和算法设计方面的技能，特别是在处理大规模数据时，如何有效地存储和访问数据是至关重要的。