数组与广义表详解：压缩存储、稀疏矩阵与地址变换

"本章主要介绍了数组和广义表的概念，特别是二维数组的存储结构、特殊矩阵的压缩存储以及稀疏矩阵的两种表示方法。同时，提到了广义表的存储结构与算法，强调了数组作为线性表的推广，不能进行插入和删除操作，但支持取值和赋值操作。在高级语言中，数组的大小和下标范围在定义后不可变。此外，本章还探讨了n维数组的抽象数据类型（ADT）及其基本操作。" 本章的知识点详述如下： 1. **二维数组**：二维数组是由多个一维数组排列而成，每个元素可以通过一对下标（i，j）来标识。在内存中，二维数组通常采用行优先或列优先的顺序存储，地址变换公式可以根据存储方式来计算。 2. **特殊矩阵的压缩存储**：对于对角矩阵、三角矩阵和对称矩阵等特殊矩阵，可以采用压缩存储节省空间，例如仅存储非零元素，地址变换公式需考虑特殊结构。 3. **稀疏矩阵**：当矩阵中非零元素较少时，使用三元组表示法（行号，列号，值）或十字链表表示，可以减少存储空间。三元组表示适合随机访问，十字链表表示则便于矩阵运算如加法和乘法。 4. **广义表**：广义表是一种更通用的数据结构，可以包含其他列表作为元素，即支持嵌套。它的存储结构通常用链表实现，支持头尾插入、删除等操作，可以用于表示复杂的逻辑结构。 5. **数组的存储结构与地址变换**：数组在内存中连续存储，地址变换公式通常基于元素的下标和数组的起始地址。数组的下标范围在定义时固定，因此插入和删除操作效率低，但取值和赋值操作高效。 6. **n维数组的ADT**：n维数组是一个有序集合，由n个下标标识。初始化、撤销、取值和赋值是其基本操作。在实际编程中，需要考虑下标的范围限制。 本章内容涵盖了数据结构中的基本数据组织形式，这些知识对于理解和实现各种算法至关重要，尤其是在解决线性代数问题和处理复杂数据结构时。通过掌握这些知识点，可以有效提高程序设计和数据处理的效率。