数组和广义表解析：二维数组的定义与存储

"本资料主要涵盖了数据结构课程中的第五章——数组和广义表，特别是二维数组类型的定义及其等价表示方法，以及数组的顺序存储结构。此外，还涉及了矩阵的压缩存储、广义表的定义与存储结构，以及广义表的递归算法。" 在数据结构中，数组是一种基础且重要的数据组织形式，它允许我们以固定的位置存储和访问元素。数组通常分为一维、二维以及更高维度的形式。在本章中，重点讲解了二维数组。 二维数组类型定义是通过typedef关键字进行的，例如`Typedef ElemType Array2[m][n];`。这个声明意味着Array2是一个m行n列的二维数组，其中每个元素的类型是ElemType。这种定义方式等价于首先定义一个一维数组Array1[n]，其元素类型为ElemType，然后将Array1作为元素类型定义另一个一维数组Array2[m]。这样的结构意味着二维数组的每个元素实际上是一个一维数组，每个元素都有两个约束关系，即行索引和列索引。 数组的定义通常涉及到下标的限制，每个下标ji的取值范围是1到bi，其中bi表示第i维的长度。对于一维数组，它是一个线性表，元素间顺序关系由下标体现，所有元素具有相同的类型且为原子类型。而二维数组则可以看作是定长的线性表，每个元素本身也是一个定长线性表，即一维数组。 二维数组有两种展开方式：按行展开和按列展开。按行展开得到的是一个长度为m的线性表，而按列展开得到的是一个长度为n的线性表。这两种展开方式对于数组的操作和理解至关重要。 数组的基本操作相对简单，一旦定义，其维数和维界的值就不能改变。因此，数组的主要操作包括初始化、销毁、存取元素和修改元素。在实际存储中，二维数组常采用顺序存储结构，这分为以列序为主序和以行序为主序两种方式。列序存储方式常见于FORTRAN语言，而行序存储方式常见于BASIC、PL/1、COBOL、PASCAL和C语言。 在后续部分，章节还讨论了矩阵的压缩存储，这是一种节省空间的存储方法，尤其适用于稀疏矩阵。此外，广义表的概念也被引入，它是包含子表的数据结构，可以用来表示复杂的数据关系。广义表的存储结构通常采用链式存储，便于处理嵌套和空表的情况。最后，广义表的递归算法被探讨，递归是解决广义表问题的有效工具，能够简化代码并提高效率。 这一章深入探讨了数组的定义、表示和实现，以及如何利用这些知识去理解和操作二维数组，为后续学习更复杂的数据结构打下了坚实的基础。