对称矩阵压缩存储与算法解析

"本讲义主要讲解了对称矩阵算法，包括下标转换算法和输入对称矩阵的方法，以及数组和广义表的相关知识，如数组的定义、顺序表示、矩阵的压缩存储，同时还涉及了二维数组、数组操作、顺序存储方式、数组元素的存储地址等。此外，还提及了矩阵的压缩存储对于特殊矩阵如对称矩阵的重要性，以及对称矩阵的性质——aij等于aji。" 在数据结构中，对称矩阵是一种特殊的矩阵，其特点在于矩阵的主对角线两侧的元素相等，即aij等于aji。这种特性在处理特定问题时可以大大节省存储空间，因为只需要存储一半的非对角线元素即可完全确定整个矩阵。 下标转换算法ij_to_k(i, j)是用于将二维下标(i, j)转换为一维下标k，这是压缩存储对称矩阵的关键。当i小于0或j小于0时，返回-1表示无效下标；如果i大于等于j，公式(i*(i+1)/2+j)用于计算下标，这是基于行优先存储方式的计算；反之，如果i小于j，则使用(j*(j+1)/2+i)。这种转换使得可以按行优先顺序存储对称矩阵的一半元素。 输入对称矩阵的算法Input(a[], n)通过循环遍历从0到n*(n+1)/2，逐个读取输入的元素，并存储到一维数组a中。因为对称矩阵的下半部分可以通过对称关系得到，所以只需输入上三角或下三角部分。 数组是一种基本的数据结构，其维数是固定的，数据元素由值和下标组成。二维数组可以看作是一维数组的数组，也可以理解为线性表的行列向量形式。数组的基本操作主要包括存取和修改元素，通常采用顺序存储结构，因为它没有插入和删除操作。在顺序存储中，多维数组可以映射成一维数组，有行优先和列优先两种存储方式。数组元素的存储地址可以通过线性变换计算得出，对于二维数组，地址公式为Loc(i, j) = Loc(0, 0) + (i * n + j) * s，其中s是元素占用的存储空间大小。 矩阵的压缩存储是针对特殊矩阵的一种优化策略，例如对称矩阵、单位矩阵或稀疏矩阵。对于对称矩阵，只存储上三角或下三角元素，可以显著减少存储需求。矩阵运算如加法、乘法等在压缩存储结构下也能高效执行。 本讲义深入介绍了对称矩阵的存储和处理方法，以及数组和广义表的基础知识，对于理解和应用这些概念在实际编程和算法设计中具有重要意义。