数组和广义表——矩阵压缩存储详解

"该资源主要介绍了数组这一数据结构，包括其定义、特点、顺序存储结构以及矩阵的压缩存储方法，特别是针对对称矩阵和三角矩阵的存储优化。" 在计算机科学中，数组是一种基础且重要的数据结构，它代表了一种特殊形式的线性表，其中每个数据元素本身也是一个线性表。数组由固定大小的相同类型的数据元素组成，这些元素通过一个共同的名称（数组名）和各自的编号（下标）来访问。在二维数组或矩阵中，元素通常以行或列的顺序存储。 数组的特点包括： 1. 数据元素的结构固定，即所有元素都具有相同的类型。 2. 元素之间存在固定的线性关系，可以通过一组整数下标来确定每个元素的位置。 3. 存储紧凑，访问效率高，因为元素在内存中通常是连续存放的。 数组的顺序存储结构是将数组元素按照特定的顺序（如行优先或列优先）存储在内存中。例如，在行优先存储方式下，元素`a[i][j]`的存储位置可以通过公式`Loc(a[i][j]) = Loc(a[1][1]) + ((i-1) * n + (j-1)) * l`计算得出，其中`l`是每个元素占用的字节数，`n`是列数，`m`是行数。而在列优先存储方式下，公式变为`Loc(a[i][j]) = Loc(a[1][1]) + ((j-1) * m + (i-1)) * l`。 对于特殊的矩阵，如对称矩阵，只存储上三角或下三角部分就足以表示整个矩阵，因为对称矩阵的`a[i][j]`等于`a[j][i]`。这样可以显著减少存储空间的需求。例如，如果以行优先存储对称矩阵，只需要存储`k=0,1,2,...,n(n-1)/2`个元素，其中`k`是元素的索引。 同样，三角矩阵（如下三角或上三角）也可以进行压缩存储，只需存储非零元素。对于下三角矩阵，元素`a[i][j]`（`i <= j`）的存储位置可以用`Loc(a[i][j]) = Loc(a[1][1]) + k * l`计算，其中`k`是计算出来的下标，对于`i=1,2,...,n`和`j=1,2,...,i`。 这些算法和数据结构对于高效的数值计算、图形处理和其他领域非常重要，因为它们允许快速访问和操作大量数据，同时减少了不必要的内存占用。在编程中，理解和掌握数组的存储和操作技巧是至关重要的。