数据结构CH5 数组和广义表

时间：2026-01-20

CH5 数组和广义表5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构

数组和广义表可以视为是线性表的扩展，即线性表中的数据元素本身也是一个数据结构。一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。 ⒈ 二维数组定义 ┌ a11 a12 … a1n ┐ Am×n= │ a21 a22 … a2n │ │· · │ │· · │ └ am1 am2 … amn ┘ Am×n可定义为一个线性表 A=(a1,a2,…,an), 其中：每个数据元素aj(j=1,2,…n)又是一个列向量的线性表，即：aj=( 1j,a2j,…,amj), 1≤j≤n a

或者二维数组Amxn可定义为一个线性表： A=(B1,B2,…,Bm) 其中：每个数据元素Bj又是一个行向量的线性表，即： Bj=(aj1,aj2,…,ajn), 1≤j≤m 即A =(B1,B2,…,Bm) =((a11,a12,…,a1n),(a21,a22,…,a2n),…,(am1,am2,…,amn)) ┌ a11 a12 … a1n ┐ Amxn= │ a21 a22 … a2n │ │ · · │ │ · · │ am2 … amn ┘ └ am1 类似地，可以定义n维数组。

5.1 数组的类型定义ADT Array { 数据对象： D={aj ,j , ...,,j ,j | ji =0,...,bi -1, i=1,2,..,n } 数据关系： R={R1, R2, ..., Rn} Ri={<aj ,... j ,... j , aj , ...j +1, ...j > | 0 jk bk -1, 1 k n 且k i, 0 ji bi -2, i=2,...,n }1 2 i n 1 i n 1 i n

基本操作: } ADT Array

二维数组的定义: 数据对象:

D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1}数据关系:R = { ROW, COL } ROW = {<ai,j,ai+1,j>| 0≤i≤b1-2, 0≤j≤b2-1} COL = {<ai,j,ai,j+1>| 0≤i≤b1-1, 0≤ j≤b2-2}

基本操作：InitArray(&A, n, bound1, ..., boundn)DestroyArray(&A) Value(A, &e, index1, ..., indexn) Assign(&A, e, index1, ..., indexn)

InitArray(&A, n, bound1, ..., boundn) 操作结果：若维数 n 和各维长度合法，

则构造相应的数组A,并返回OK。

DestroyArray(&A) 操作结果：销毁数组A。

Value(A, &e, index1, ..., indexn) 初始条件：A是n维数组，e为元素变量，随后是n 个下标值。操作结果：若各下标不超界，则e赋值为

所指定的A 的元素值，并返回OK。

Assign(&A, e, index1, ..., indexn) 初始条件：A是n维数组，e为元素变量，随后是n 个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回 OK。

5.2 数组的顺序表示和实现

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