数组与广义表：线性结构的扩展及压缩存储

"从分析a和b之间的差异可见只要做到-数据结构（清华大学版）——数组和广义表" 在数据结构的学习中，数组和广义表是两种重要的非线性数据结构，它们是对线性结构的扩展。数组，尤其是多维数组，广泛应用于数学计算和计算机科学的各个领域，而广义表则提供了更灵活的数据组织方式。 数组的定义： 数组是一种数据结构，它由n个相同类型的数据元素组成，这些元素在内存中是连续存储的。对于一维数组，它就像一个线性表，每个元素可以通过其索引直接访问。一维数组的存储地址可通过基础元素的地址和元素间的步长计算得出。例如，如果a0的地址是Loc(a0)，每个元素占L个存储单元，那么第i个元素ai的地址是Loc(ai)=Loc(a0)+i*L。这种可以直接通过索引访问任意元素的特性使得数组具有随机存取能力。 二维数组则是对一维数组的扩展，可以视为由m行n列的数据元素组成。每个元素可以用一对下标(i, j)来标识，其中i表示行，j表示列。二维数组可以按行或列理解，即它可以被视为由m个一维行向量或n个一维列向量组成。在二维数组中，除了边界情况外，每个元素都有两个直接前驱和两个直接后继。 多维数组进一步扩展了这一概念，可以有三个或更多的直接前驱和后继，适用于处理更高维度的数据。 广义表的定义与存储结构： 广义表是一种更通用的数据结构，它包含零个或多个元素，这些元素可以是基本数据类型，也可以是其他广义表。这种结构允许嵌套，即一个广义表的元素可以是另一个广义表。广义表的存储通常有两种方式：链式存储和顺序存储。链式存储利用链表结构，每个节点包含一个元素和指向下一个节点的指针；顺序存储则将所有元素紧凑地存储在连续的内存空间中，但需要额外的信息来指示元素间的结构关系。 矩阵转置： 在描述中提到的矩阵转置操作，涉及到对矩阵的行列值交换，以及调整三元组的次序。在实际操作中，矩阵的转置可以通过遍历原矩阵并创建一个新的矩阵来完成。对于非稀疏矩阵，这个过程相对直接，只需交换行和列即可。而对于稀疏矩阵（大部分元素为零的矩阵），为了节省存储空间，通常使用压缩存储。转置稀疏矩阵的关键在于保持非零元素的行（原矩阵的列）主序，这可能需要重新排列三元组的顺序。 教学重点难点： 在讲解数组和广义表时，矩阵的压缩存储是一个重要的话题。对于特殊矩阵和稀疏矩阵，采用压缩存储可以大大提高空间效率。例如，稀疏矩阵的压缩存储通常采用三元组或十字链表的形式，只存储非零元素及其对应的行号和列号。 总结： 数组和广义表是数据结构中的核心概念，它们为高效的数据操作提供了基础。数组提供了随机访问的便利，而广义表则支持复杂的数据组织。了解它们的定义、表示和实现方法，以及如何进行特定操作（如矩阵转置），对于理解和设计算法至关重要。