数据结构：数组与广义表的存储优化

"数据结构-5-章课件，源自西南财经大学" 在数据结构的学习中，第五章主要探讨了数组和广义表的概念及其存储结构。数组作为一种基础且重要的数据结构，可以被视为一种特殊的线性表，其特殊之处在于数组的数据元素本身也是一个线性表。数组有以下三个显著特点： 1. 定义与特点： - 结构固定：数组的大小在创建时就已经确定，不可更改，这使得数组在内存中占用连续的空间。 - 数据元素同构：数组的所有元素都是同一类型，具有相同的结构和操作。 - 数组运算：主要包含两种基本操作，即通过下标存取数据元素和修改下标指定的数据元素值。 2. 顺序存储结构： - 次序约定：数组的存储方式有两种常见主序，一是以行序为主序，另一种是以列序为主序。在计算机内存中，通常以行序为主序存储，便于连续访问和处理。 3. 矩阵的压缩存储： - 对称矩阵、三角矩阵和三对角矩阵：这些特殊类型的矩阵可以通过特定的公式计算其非零元素的存储位置，如对称矩阵的Loc(aij) = Loc(a11) + 2(i-1) + (j-1)，从而节省存储空间。 - 稀疏矩阵：当非零元素远少于零元素时，可以采用压缩存储，只存储非零元素的行列下标和值。常见的压缩存储方法有两种：三元组表和伪地址表示法。 - 三元组表：定义为一个结构体数组，包含非零元素的行索引i、列索引j和值v。例如，若非零元素个数为t，则需要3(t+1)个存储单元。 - 伪地址表示法：根据矩阵元素在包括零元素在内的行优先顺序中的相对位置，用伪地址表示非零元素，需要2(t+1)个存储单元。 4. 稀疏矩阵转置： - 问题描述：给定一个稀疏矩阵的三元组表，需要求解其转置矩阵的三元组表。 - 解决方法：有两种策略，一种是按列序转置，另一种是快速转置。 - 按列序转置：遍历原矩阵的三元组表，按列顺序找到每个非零元素并转置，最后得到的结果按照原矩阵的行序排列。 - 快速转置：直接根据原矩阵三元组的顺序进行转置，并将结果放置在正确的位置。这种方法需要预先确定每一列的第一个非零元素的位置。 这些知识点在实际编程和算法设计中非常重要，特别是在处理大规模数据或优化内存使用时。例如，在图像处理、数值计算、科学计算等领域，高效地处理数组和矩阵是至关重要的。理解数组和矩阵的存储方式以及如何优化它们的运算，能帮助我们编写出更高效、更节省资源的代码。