第五章数组 5.1数组的定义 5.2数组的顺序表示和实现 5.3矩阵的压缩存储 5.3.1特殊矩阵 5.3.2稀疏矩阵
第五章 数组 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵
5.1数组的定义 维数和维界 二维数组的类型定义: 等价于 typedef ElemType Arrayl[n] typedef Array1 Array2[m] typedef ElemType Array2[m][n Array2 A 维的数组=定长的线性表 a11a12a13..a1n 22 m2 Amxn (al1,a12,a13,aln),(a21,a22,a23, 2n) (aml, am2, am3, .. amn))
5.1 数组的定义 维数和维界 二维数组的类型定义: 等价于 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))
数组的抽象数据类型 ADTArray i 数据对象:D={a1 n(>0)称为数组的维数b是数组第i维的长度 是数组元素的第维下标,a1. Elemnet 数据关系:R={R1,R2.1Rn} Ri=.jn, a, jit+ljn >10 Jk bx-1,1 k n, ajr J1.Ji.Jn? 11.JitI.n 基本操作: InitArray(&A, n, bound1, bound,,, bound); DestroyArray (&A); Value(A, &e, indexI, index2,,index); Assign(&A, e, index, index2,., index) ADT Array
数组的抽象数据类型 ADT Array { 数据对象：D = {aj1j2...jn | • n(>0)称为数组的维数,bi是数组第i维的长度, • j i是数组元素的第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
5.2数组的顺序表示和实现 除了初始化和销毁之外 数组一般只有存取操作和修改元素值的操作. 通常不作删除和插入 行序为主序:C语言, PASCAL, BASIC等) Amxn= a11, a1o, a ain, ao1, a2, a amI, am2, a LOC[1,1]为基地址 LOCLi, j]= LOC[1, 1]+(n*(i-1)+j-1)*L (1<=i<=m,1<=j=n,每个数据元素占L个存储单元
5.2 数组的顺序表示和实现 除了初始化和销毁之外, 数组一般只有存取操作和修改元素值的操作. 通常不作删除和插入. 行序为主序:(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个存储单元)
例5.1:若L=2,L0C[1,1]=1000 a11a12a13a14a15 21a22a23a24a25 a a a 34a35 44a45 LOC[3,4]=L0C[1,1]+(5*(3-1)+4-1)*L 1000+13米2 1026 LC[0,0]为基地址: LOCLi, j]= LoC[0, 0]+(n*i+j)*L (0<=i<m,0<=jn,每个数据元素占L个存储单元) LOC[i,j,k]=LOC[0,0,0]+(n*h*十h*j+k)米L (0<=i<m,0<=jn,0<=k<h,每个数据元素占L个存储单元)
例5.1: 若 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)的存储位置为 C[j1,j2,,jin]=LOC[0,0,,0]+(b2b b3 On Jn-1 in) L LOC[0,0,..,0]+(∑j∏bk+jn)L 例:在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
一般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 mxn (a1a21,1a31,…,am),(a12,a22a32,am2),,(a1n,a2na3n…,am) LOC[1,1]为基地址 LOC[i,j=L0C[1,1]+(m*(j1)+-1)米 (1<=<-m,1<=<n,每个数据元素占L个存储单元) 例5.2:若L=2,LOC[1,1]=1000 0C[3,4]=LOC[1,1]+(4*(4-1)+3-1)米 a11a12a13a14a15 22a23a24a25 1000+14*2 1028 a21 a32 a33 a24 a 41(424344045 LOC[0,O]为基地址 LOCLi, j]= LOC[0, 0]+(m*j+i)* (0<=i<=m,0<=j<=n,每个数据元素占L个存储单元 LOC[i,j,k]=LOC[0,0,0]+(m*(n米k)+j)+i1)米L
列序为主序: (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个存储单元) 例5.2: 若 L=2, LOC[1,1] = 1000 LOC[3,4] = LOC[1,1] + (4*(4-1)+3-1)*L = 1000 + 14 * 2 = 1028 LOC[0,0] 为基地址: LOC[i,j] = LOC[0,0] + (m*j+i)*L (0<=i<=m, 0<=j<=n, 每个数据元素占L个存储单元) LOC[i,j,k] = LOC[0,0,0] + (m*((n*k)+j)+i) *L a11 a12 a13 a14 a15 a21 a22 a23 a24 a25 a31 a32 a33 a34 a35 a41 a42 a43 a44 a45
数组顺序存储的表示和实现 *incluse base a0 #define maX array dim 8 dim typedef struct bounds a ElemType米base; int dim constants int * bounds dim-1 al int constants f Array at InitArray(Array &A, int dim,.) ∥若维数dm和随后的维数合法,构造相应的数组,并返回OK DestroyArray( Array&A);/销毁数组A Value(Array A, Elem Type &e,.) 若各下标不超界,则e赋值为所指定的A的元素值,并返回OK Assign(Array &A, Elem Type e,...) 若各下标不超界,则将e的值赋给所指定的A的元素,并返回OK
数组顺序存储的表示和实现 InitArray(Array &A, int dim, ...); • // 若维数dim和随后的维数合法,构造相应的数组,并返回OK DestroyArray (Array &A);//销毁数组A Value(Array A, ElemType &e, ...); • 若各下标不超界,则e赋值为所指定的A的元素值,并返回OK Assign(Array &A, ElemType e, ...) • 若各下标不超界,则将e的值赋给所指定的A的元素,并返回OK base dim bounds constants a0 a1 ai at ... ... ... 0 1 ... dim-1 ... #incluse #define MAX_ARRAY_DIM 8 typedef struct { ElemType *base; int dim; int *bounds; int *constants; }Array;
Status InitArray (Array &A, int dim va list ap if(dimMAX ARRAY DIM) return ERROR A dim= dim A bounds=(int * malloc(dim*sizeof (int)) if(!A bounds) exit(OVERFLOW elemtotal= 1 va start(ap, dim for(i =0, i=0 A constants[]= A bounds [i+1 A constants[i+1l return OK
Status InitArray(Array &A, int dim, ...) { va_list ap; if(dim MAX_ARRAY_DIM) return ERROR; A.dim = dim; A.bounds = (int * ) malloc(dim*sizeof(int)); if(!A.bounds) exit(OVERFLOW); elemtotal = 1; va_start(ap, dim); for(i =0 ; i=0; --i) A.constants[i] = A.bounds[i+1] * A.constants[i+1]; return OK; }
Array a[5][6][7][8]; base bounds constants 5x6x7x8 3365681 elemtatol-1
base dim (4) bounds constants elemtatol-1 7 0 1 2 3 8 5 6 336 1 Array A[5][6][7][8]; 8 56 0 5x6x7x8