厦门大学：《数据结构》课程教学课件（PPT讲稿）第五章 数组和广义表

数据结构

数据结构

第五章数组和广义表 ■5.1数组的定义 ■5.2数组的顺序表示和实现 ■5.3矩阵的压缩存储 5.3.1特殊矩阵 5.3.2稀疏矩阵 5.4广义表的定义 5.5广义表的存储结构

第五章 数组和广义表 ◼ 5.1 数组的定义 ◼ 5.2 数组的顺序表示和实现 ◼ 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构

数组和广义表可看成是一种特殊的线性表，其 特殊在于，表中的数所元素本身也是一种线性 表。 5.1数组的定义 数组是我们最熟悉的数据类型，在早期的高 级语言中，数组是唯一可供使用的数据类型 由于数组中各元素具有统一的类型，并且数组 元素的下标一般具有固定的上界和下界，因此， 数组的处理比其它复杂的结构更为简单。多维 数组是向量的推广。例如，二维数组 a11a12a1n a21a22. a2n Amn Aml am2.amn

数组和广义表可看成是一种特殊的线性表，其 特殊在于，表中的数所元素本身也是一种线性 表。 5.1 数组的定义 数组是我们最熟悉的数据类型，在早期的高 级语言中，数组是唯一可供使用的数据类型。 由于数组中各元素具有统一的类型，并且数组 元素的下标一般具有固定的上界和下界，因此， 数组的处理比其它复杂的结构更为简单。多维 数组是向量的推广。例如，二维数组： a11 a12 . a1n a21 a22 . a2n . . . . am1 am2 . amn Amn =

可以看成是由个行向量组成的向量，也可以看成是 个列向量组成的向量。 在C语言中，一个二维数组类型可以定义为其分量 类型为一维数组类型的一维数组类型，也就是说 typedef elemtype array2[m][n]; 等价于： typedef elemtype array1[n]; typedef array1 array2[m]; 同理，一个n维数组类型可以定义为其数据元素为n 1维数组类型的一维序组类型。 数组一旦被定义，它的维数和维界就不再改变。因 此，除了结构的初始化和销毁之外，数组只有存取 元素和修改元素值的操作

可以看成是由个行向量组成的向量，也可以看成是 个列向量组成的向量。 在C语言中，一个二维数组类型可以定义为其分量 类型为一维数组类型的一维数组类型，也就是说， typedef elemtype array2[m][n]; 等价于： typedef elemtype array1[n]; typedef array1 array2[m]; 同理，一个n维数组类型可以定义为其数据元素为n- 1维数组类型的一维序组类型。 数组一旦被定义，它的维数和维界就不再改变。因 此，除了结构的初始化和销毁之外，数组只有存取 元素和修改元素值的操作

5.2数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用 一维内存来表示多维数组，就必须按某种 次序将数组元素排成一列序列，然后将这 个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作 也就是说，数组一旦建立，结构中的元素 个数和元素间的关系就不再发生变化。因 此，一般都是采用顺序存储的方法来表示 数组

5.2 数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用 一维内存来表示多维数组，就必须按某种 次序将数组元素排成一列序列，然后将这 个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作， 也就是说，数组一旦建立，结构中的元素 个数和元素间的关系就不再发生变化。因 此，一般都是采用顺序存储的方法来表示 数组

通常有两种顺序存储方式： (1)行优先顺序一将数组元素按行排列，第i+1个行 向量紧接在第个行向量后面。以二维数组为例，按 行优先顺序存储的线性序列为： a11,a12.a1n,a21,a22.a2n.am1,am2.amn 在PASCAL、C语言中，数组就是按行优先顺序存 储的。 (2)列优先顺序 一将数组元素按列向量排列，第+1 个列向量紧接在第j个列向量之后，A的m*n个元素 按列优先顺序存储的线性序列为： a11a21 .,am1,a12,a22,.am2.,an1an2,:.anm 在FORTRAN语言中，数组就是按列优先顺序存储的

通常有两种顺序存储方式： ⑴行优先顺序——将数组元素按行排列，第i+1个行 向量紧接在第i个行向量后面。以二维数组为例，按 行优先顺序存储的线性序列为： a11,a12,.,a1n,a21,a22,.a2n,.,am1,am2,.,amn 在PASCAL、C语言中，数组就是按行优先顺序存 储的。 ⑵列优先顺序——将数组元素按列向量排列，第j+1 个列向量紧接在第j个列向量之后，A的m*n个元素 按列优先顺序存储的线性序列为： a11,a21,.,am1,a12,a22,.am2,.,an1,an2,.,anm 在FORTRAN语言中，数组就是按列优先顺序存储的

以上规则可以推广到多维数组的情况：行优 先顺序可规定为先排最右的下标，从右到 左，最后排最左下标：列优先顺序与此相 反，先排最左下标，从左向右，最后排最 右下标。 按上述两种方式顺序存储的序组，只要 知道开始结点的存放地址（即基地址） 维数和每维的上、下界，以及每个数组元 素所占用的单元数，就可以将数组元素的 存放地址表示为其下标的线性函数。因此 数组中的任一元素可以在相同的时间内存 取，即顺序存储的数组是一个随机存取结 构

以上规则可以推广到多维数组的情况：行优 先顺序可规定为先排最右的下标，从右到 左，最后排最左下标：列优先顺序与此相 反，先排最左下标，从左向右，最后排最 右下标。 按上述两种方式顺序存储的序组，只要 知道开始结点的存放地址（即基地址）， 维数和每维的上、下界，以及每个数组元 素所占用的单元数，就可以将数组元素的 存放地址表示为其下标的线性函数。因此， 数组中的任一元素可以在相同的时间内存 取，即顺序存储的数组是一个随机存取结 构

例如，二维数组Amn按"行优先顺序”存储在内存 中，假设每个元素占用L个存储单元。 元素a的存储地址应是数组的基地址加上排在a 前面的元素所占用的单元数。因为a位于第i行、 第列，前面i-1行一共有(-1)×b2个元素，第行 上a前面又有j-1个元素，故它前面一共有i-1) ×b2+j1个元素，因此，a的地址计算函数为： LOC(a)=LOC(a11)+[(i-1)*b2+j-1]*L 同样，三维数组A按"行优先顺序”存储，其地址 计算函数为： LOC(ak)=LOC(a111)+[(i-1)*b2*b3+(j-1)*b3+(k 1)]*L

例如，二维数组Amn按“行优先顺序”存储在内存 中，假设每个元素占用L个存储单元。 元素aij的存储地址应是数组的基地址加上排在aij 前面的元素所占用的单元数。因为aij位于第i行、 第j列，前面i-1行一共有(i-1) ×b2个元素，第i行 上aij前面又有j-1个元素，故它前面一共有(i-1) ×b2+j-1个元素，因此，aij的地址计算函数为： LOC(aij)=LOC(a11)+[(i-1)*b2+j-1]*L 同样，三维数组Aijk按“行优先顺序”存储，其地址 计算函数为： LOC(aijk)=LOC(a111)+[(i-1)*b2*b3+(j-1)*b3+(k- 1)]*L

上述讨论均是假设数组各维的下界是1，更 般的二维数组是A[c1b1,c2b2],这里 c1c2不一定是1。a前一共有i-c1行，二维数 组一共有b2-c2+1列，故这i-c1行共有( c1)*(b2-c2+1)个元素，第i行上a前一共有j c2个元素，因此，a的地址计算数为： LOC(aj)=LOC(ac1c2)+[(i-C1)*(b2-C2+1)+j- C2]*L 例如，在C语言中，数组各维下标的下界是0 b长度的数组下标为0.b-1。因此在C语言中， 二 维数组a[b][b2]的地址计算公式为： LOC(ai)=LOC(aoo)+(i*b2+j)*L

上述讨论均是假设数组各维的下界是1，更 一般的二维数组是A[c1.b1,c2.b2]，这里 c1,c2不一定是1。aij前一共有i-c1行，二维数 组一共有b2-c2+1列，故这i-c1行共有(i￾c1)*(b2-c2+1)个元素，第i行上aij前一共有j￾c2个元素，因此，aij的地址计算函数为： LOC(aij)=LOC(ac1c2 )+[(i-c1)*(b2-c2+1)+j￾c2)]*L 例如，在C语言中，数组各维下标的下界是0， b长度的数组下标为0.b-1。因此在C语言中， 二维数组a[b1][b2]的地址计算公式为： LOC(aij)=LOC(a00)+(i*b2+j)*L

更一般地，可以得到n维数组存储位置的计 算公式，如书P93映像函数。 ■P93,数组的顺序表示和实现

◼ 更一般地，可以得到n维数组存储位置的计 算公式，如书P93映像函数。 ◼ P93，数组的顺序表示和实现