第5章数组和广义表 5.1数组的定义《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

第五章 数组和广义表 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构 数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数据元素本身也是一种线性表。 虽然数组不能吻合线性表的定义，但经过适当的转换，完全可以如同线性表的相关操作来处理数组。 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 5.1 数组的定义 由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组： ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 可以看成是由一个行向量组成的向量，也可以看成是由一个列向量组成的向量。 在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说， typedef elemtype array2[m][n]; 等价于： typedef elemtype array1[n]; typedef array1 array2[m]; 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 5.2 数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 通常有两种顺序存储方式： 以行序为主序 以列序为主序 a11 a12 …….. a1n a21 a22 …….. a2n am1 am2 …….. amn …………………. Loc( aij)=Loc(a11)+[(i-1)n+(j-1)]*l   按行序为主序存放 amn …….. am2 am1 ………. a2n …….. a22 a21 a1n ……. a12 a11 0 1 n-1 m*n-1 n   按列序为主序存放 0 1 m-1 m*n-1 m amn …….. a2n a1n ………. am2 …….. a22 a12 am1 ……. a21 a11 a11 a12 …….. a1n a21 a22 …….. a2n am1 am2 …….. amn …………………. Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l 计算二维数组元素地址的通式 设一般的二维数组是A[c1..d1, c2..d2]，这里c1,c2不一定是0。 无论规定行优先或列优先，只要知道以下三要素便可随时求出任一