文档介绍：数组的类型定义
稀疏矩阵的压缩存储
数组的顺序表示和实现
广义表的类型定义
广义表的表示方法
广义表操作的递归函数
本章小结
习题
数组的类型定义
由于数组中各元素具有统一的类型,并且数组元素的下标一般具有固定的上界和下界,因此,数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如,二维数组:
a01
a11
am-1,1
a0,n-1
a1 ,n-1
am-1 ,n-1
a00
a01
am-1,0
Am×n=
Am×n=((a00,a01,…,a0,n-1),(a10,a11,…,a1,n-1),…(am-1,0 , am-1,1,…,am-1,n-1))
(a)
(b)
(c)
typedef elemtype array2[m][n];
等价于:
typedef Elemtype array1[n];
typedef array1 array2[m];
一般地:多维数组的定义如下页所示:
ADT Array {
数据对象:
D={aj1,j2, ...,,ji,jn| ji =0,...,bi -1, i=1,2,..,n }
数据关系:
R={R1, R2, ..., Rn}
Ri={<aj1,... ji,... jn , aj1, ...ji +1, ...jn > | 0 jk bk -1,
1 k n 且k i, 0 ji bi -2, i=2,...,n }
基本操作:
} ADT Array
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。
数组一旦被定义,它的维数和维界就不再改变。因此,除了结构的初始化和销毁之外,数组只有存取元素和修改元素值的操作。
二维数组的抽象定义:
数据对象:
D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1}
数据关系:
R = { ROW, COL }
ROW = {<aij,ai+1j>| 0≤i≤b1-2, 0≤j≤b2-1}
COL = {<aij,aij+1>| 0≤i≤b1-1, 0≤ j≤b2-2}
数组的顺序表示和实现
类型特点:
1) 只有引用型操作,没有加工型操作;
2) 数组是多维的结构,而存储空间是一个一维的结构。
有两种顺序映象的方式:
1)以行序为主序(低下标优先);//我们所选择的
2)以列序为主序(高下标优先);
以“行序为主序”的存储映象
a0,1
a0,0
a0,2
a1,0
a1,1
a1,2
a0,1
a0,0
a0,2
a1,0
a1,1
a1,2
L
按行序为主序存放
0
1
n-1
m*n-1
n
am-1n-1
……..
am-11
am-10
……….
a1n-1
……..
a11
a10
a0n-1
…….
a01
a00
a00 a01 …….. a0n-1
a10 a11 …….. a1n-1
am-10 am-11 ……am-1n-1
………………….
Loc(i,j)=Loc(0,0)+[n*i+ j]*L
二维数组A中任一元素aij 的存储位置
LOC(i,j) = LOC(0,0) + (b2×i+j)× L
称为基地址或基址
每个元素占L个存储单元
已经存储的元素数