数组与广义表：非零元素计数与特殊矩阵存储

第5章主要探讨了数组与广义表在数据结构中的应用，特别是关于数组的定义、特点以及特殊矩阵的存储优化。数组被定义为一种有序的元素集合，其中每个元素具有相同的数据类型，可以通过下标直接访问，如在一维数组中，Loc(ai) = Loc(a0) + i * k。二维数组则可以按照行主序或列主序存储，如行主序中，元素的存储位置由Loc(aij) = Loc(a00) + (i * n + j) * k计算。 章节中特别提到了特殊矩阵的压缩存储，因为某些矩阵可能包含大量相同的元素或零元素，这会影响存储效率。对于对称矩阵，它满足aij = aji (0 ≤ i, j ≤ n-1)的性质，通过存储上三角或下三角元素，可以大大节省空间，只需n(n+1)/2个元素就能表示整个矩阵。对称矩阵的存储通常是将主对角线及其下方的元素按行优先顺序存储，同时保留对称性。 此外，章节还介绍了其他两种特殊矩阵：三角矩阵，包括上三角矩阵和下三角矩阵，它们的特点分别是一行或一列的元素全为零；稀疏矩阵，这种矩阵大部分元素为零，但仍然具有特定的非零元素分布。这些特殊矩阵的存储方式旨在优化存储和计算效率，减少冗余，提高程序性能。 广义表作为另一种数据结构，虽然章节内容未详述，但通常用于表示非线性数据结构，与数组相比，它允许元素之间没有固定的关系。在实际编程中，理解数组和特殊矩阵的特性对于高效处理数据至关重要，尤其是在处理大规模数据集时，选择合适的存储结构能显著提升算法的执行效率。