第五章数组 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