文档介绍：第五章数组
数组的定义
数组的顺序表示和实现
矩阵的压缩存储
特殊矩阵
稀疏矩阵
数组的定义
维数和维界
二维数组的类型定义:
等价于
typedef ElemType Array1[n];
typedef Array1 Array2[m];
typedef ElemType Array2[m][n];
Array2 A;
二维的数组= 定长的线性表
a11 a12 a13 ... a1n
a21 a22 a23 ... a2n
Amxn= ......
am1 am2 am3 ... amn
Amxn=
((a11,a12,a13,...a1n),(a21,a22,a23,...a2n),...,(am1,am2,am3,...amn))
数组的抽象数据类型
ADT Array {
数据对象:D = {aj1j2...jn |
n(>0)称为数组的维数,bi是数组第i维的长度,
ji是数组元素的第i维下标, aj1j2...jnElemset}
数据关系: R={R1 , R2 ... Rn}
Ri = {< aj1...ji...jn, aj1...ji+1...jn >|0  jk bk-1, 1  k  n,
aj1...ji...jn, aj1...ji+1...jn D}。
基本操作:
InitArray(&A,n,bound1,bound2,...,boundn);
DestroyArray (&A);
Value(A,&e,index1,index2,...,indexn);
Assign(&A,e, index1,index2,...,indexn)
}ADT Array
数组的顺序表示和实现
除了初始化和销毁之外,
数组一般只有存取操作和修改元素值的操作.
通常不作删除和插入.
行序为主序:(C语言,PASCAL, BASIC等)
Amxn=
(a11,a12,a13,...a1n,a21,a22,a23,...a2n,...am1,am2,am3,...amn)
LOC[1,1] 为基地址:
LOC[i,j] = LOC[1,1] + (n*(i-1)+j-1)*L
(1<=i<=m, 1<=j<=n, 每个数据元素占L个存储单元)
: 若 L=2, LOC[1,1] = 1000
LOC[3,4] = LOC[1,1] + (5*(3-1)+4-1)*L
= 1000 + 13 * 2
= 1026
LOC[0,0] 为基地址:
LOC[i,j] = LOC[0,0] + (n*i+j)*L
(0<=i<m, 0<=j<n, 每个数据元素占L个存储单元)
LOC[i,j,k] = LOC[0,0,0] + (n*h*i+ h*j + k)*L
(0<=i<m, 0<=j<n, 0<=k<h, 每个数据元素占L个存储单元)
a11 a12 a13 a14 a15
A4x5 = a21 a22 a23 a24 a25
a31 a32 a33 a34 a35
a41 a42 a43 a44 a45
一般n维数组的列主元存储地址计算公式
b1,b2,...,bn是n维的维界,数组元素A(j1,j2,...,jn)的存储位置为
LOC[j1,j2,...jn]= LOC[0,0,...,0] + (b2b3...bnj1
+ b3...bnj2
+ ......
+ bnjn-1
+ jn )L
n-1 n
= LOC[0,0,...,0] + (  ji  bk + jn)L
i=1 k=i+1
例: 在C语言中,设数组A[5][6][7][8]的首地址为 2000,
每个元素占2个字节; 求元素A[3][4][5][4]的地址.
LOC[3,4,5,4] = 2000 + (6*7*8*3 + 7*8*4 + 8*5 + 4)*2
= 2000 + ( 336*3 + 56*4 + 8*5 + 1*4)*2
= 2000 + (1008 + 224 + 40 + 4)*2 = 4552
列序为主序: (FORTRAN)
Amxn=
((a11,a21,a31,...am1),(a12,a22,a32,...am 2),...(a1n,a2n,a3n,...amn))
LOC[1,1] 为基地址:
LOC[i,j] = LOC[1,1] + (m*(j-1)+i-1)*L
(1<=i<=m, 1<=j<=n, 每个数据元素占L个存储单元)
: 若 L=2, LOC[1,1] = 100