对称矩阵压缩存储技巧

"本讲义主要讲解了数据结构中的对称矩阵分配方法，以及数组和广义表的相关概念。在对称矩阵的存储中，通常只存储下三角部分（包括主对角线），并以此节省空间。此外，还介绍了数组的定义、顺序表示和实现，包括二维数组的行优先和列优先存储方式，以及数组元素的存储地址计算方法。对于矩阵，特别是对称矩阵的压缩存储是提高存储效率的关键。同时，提到了广义表的定义和存储结构，以及m元多项式的表示和广义表的递归算法。" 对称矩阵是一种特殊的矩阵，其特点在于矩阵的对角线两侧的元素相等，即aij等于aji。在存储对称矩阵时，可以利用这一特性来节省空间。通常，我们可以只存储对角线以下或以上的元素，因为另一半可以通过对称关系得到。如果以一维数组来存储n阶对称矩阵，并且以行序为主序，那么数组中的元素位置与矩阵中的元素存在一一对应关系。例如，数组下标k对应矩阵中的元素aij，可以通过公式计算得出，如在二维情况下，Loc(i,j) = Loc(0,0) + (i*n+j)*s。 数组是数据结构的基础，它由固定大小的同类型元素集合构成。数组的维数是固定的，一旦定义就不能更改。数据元素可以看作是值和下标的偶对，每个元素都可以视为一个线性表。在二维数组中，可以将其视为元素类型为一维数组的一维数组。数组的基本操作主要包括存取和修改指定下标处的元素。在实际应用中，多维数组通常通过映射到一维数组来实现，有行优先和列优先两种存储方式，分别按照行或列的顺序存放元素。行优先存储是C语言的默认方式。 数组的顺序存储方式因其没有插入和删除操作而非常适用。数组元素的存储地址可以通过一定的公式计算，例如对于二维数组， Loc(i,j) = Loc(0,0) + (i*n+j)*s，其中s是元素的大小。 矩阵的压缩存储对于优化存储空间至关重要，特别是对于特殊矩阵，如对称矩阵，可以通过只存储非重复元素来节省空间。零矩阵或具有大量重复元素的矩阵也可以通过类似的方法压缩存储。在处理这类矩阵时，可以减少不必要的内存开销，从而提高程序效率。 广义表是数据结构中的一种抽象概念，它可以表示多种数据结构，包括线性表、树形结构等。广义表的存储结构可以采用链式存储，便于处理复杂的结构。此外，广义表的递归算法可以用于解决多种复杂问题。 这份讲义涵盖了数据结构中的核心概念，从基本的数组操作到矩阵的高效存储，再到广义表的定义和算法，都是理解数据结构和算法设计的重要内容。