矩阵压缩存储与广义表数据结构解析

"这篇资料主要介绍了数据结构中的数组和广义表相关知识，特别是矩阵的压缩存储技术。在清华大学版的数据结构课程中，这是一部分重要内容。内容包括数组的定义、顺序表示和实现，以及矩阵的压缩存储方法，如特殊矩阵和稀疏矩阵的处理。此外，还涉及到广义表的定义和存储结构。" 文章首先回顾了上节课的内容，即串的表示和模式匹配，然后引出本节课的重点——数组和广义表。数组作为一种线性数据结构的扩展，其数据元素本身也是数据结构。第五章详细讲解了数组和广义表： 1. 数组的定义：一维数组是一个有限序列，包含n个相同类型的数据元素，这些元素存储在连续的内存空间中。通过起始地址和元素大小，可以计算任意元素的地址，因此数组支持随机访问。 2. 一维数组的顺序表示和实现：每个元素的地址可以通过起始地址加上索引乘以元素大小来计算。这种存储方式使得数组具有随机存取的特性。 3. 二维数组：二维数组可以视为一维数组的扩展，每个数据元素对应于一对二维下标，可以按行或列看作一维数组。 4. 矩阵的压缩存储：对于特殊矩阵和稀疏矩阵，为了节省存储空间，可以采用压缩存储。文中提到的`num[col]`和`cpot[col]`两个数组用于存储非零元素的信息，其中`num[col]`表示第`col`列非零元素的个数，`cpot[col]`指示第`col`列第一个非零元素在压缩后的数组`mb`中的位置。 5. 广义表的定义：广义表是一种更通用的数据结构，其数据元素可以是单个元素或另一个广义表，从而形成嵌套结构。 6. 广义表的存储结构：广义表的存储通常采用链式结构，如链表或树形结构，以适应元素的复杂性。 这部分内容是数据结构学习的基础，对于理解和实现高效的算法至关重要，尤其是在处理大规模数据时，矩阵的压缩存储能够显著减少内存占用。广义表的概念则为处理复杂数据关系提供了可能。在实际编程中，数组和广义表是构建各种复杂数据结构和算法的基础。