《数组与广义表》PPT课件.ppt

《《数组与广义表》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章数组5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.3.1特殊矩阵5.3.2稀疏矩阵5.4广义表的定义与存储5.1数组的定义维数和维界二维数组的类型定义:等价于typedefElemTypeArray1[n];typedefArray1Array2[m];typedefElemTypeArray2[m][n];Array2A;二维的数组=定长的线性表a11a12a13...a1na21a22a23...a2nAmxn=......am1am2am3...amnAmxn=((a11,a12,a13,...a1n),(a21,a22,a23,...a2n),...,(a

2、m1,am2,am3,...amn))数组的抽象数据类型ADTArray{数据对象：D={aj1j2...jn

3、n(>0)称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标,aj1j2...jn∈Elemset}数据关系：R={R1,R2...Rn}Ri={＜aj1...ji...jn,aj1...ji+1...jn＞

4、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

5、,index2,...,indexn);Assign(&A,e,index1,index2,...,indexn)}ADTArray5.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,

6、LOC[1,1]=1000LOC[3,4]=LOC[1,1]+(5*(3-1)+4-1)*L=1000+13*2=1026LOC[0,0]为基地址:LOC[i,j]=LOC[0,0]+(n*i+j)*L(0<=i

7、是n维的维界,数组元素A(j1,j2,...,jn)的存储位置为LOC[j1,j2,...jn]=LOC[0,0,...,0]+(b2*b3*...*bn*j1+b3*...*bn*j2+......+bn*jn-1+jn)*Ln-1n=LOC[0,0,...,0]+(jibk+jn)*Li=1k=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+(100

8、8+224+40+4)*2=4552列序为主序:(FORTRAN)Amxn=((a11,a21,a31,...am1),(a12,a22,a32,...am2),...(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]=1000LOC[3,4]=LOC[1,1]+(4*(4-1)+3-1)*L=1000+14*2=1028LOC[0,0]为基地址:LOC[i,j]=LOC[0,0]+(m*j+i)*L(0<=i

9、<=m,0<=j<=n,每个数据元素占L个存储单元)LOC[i,j,k]=LOC[0,0,0]+(m*((n*k)+j)+i)*La11a12a13a14a15a21a22a23a24a25a31a32a33a34a35a41a42a43a44a45数组顺序存储的表示和实现InitArray(Array&A,intdim,...);//若维数dim和随后的维数合法,构造相应的数组,并返回OKDestroyArray(Ar