数据结构数组备课讲稿.ppt

《数据结构数组备课讲稿.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构数组一维数组存储方式352749186054778341020123456789llllllllllLOC(i)=LOC(i-1)+l=a+i*lLOC(i)=LOC(i-1)+l=a+i*l,i>0a,i=0a+i*la2.4.1数组的定义二维数组：类似于线性表，一个二维数组的逻辑结构可形式地表示为：2_Array=(D,R)D={aij(i=0,1,…,m-1,j=0,1,…,n-1)},aij是同类型数据元素的集合。R={ROW,COL}是数据元素上关系的集合。2.4.1数组的定义a11a12a13…a1na21a22a23…a2nam

2、1am2am3…amn…ai,j-1aijai,j+1………ai-1,jai+1,jAm,n=aij受行列两个关系的约束：第i行的行向量，第j列的列向量。ROW={

3、0im-1,0jn-2}每一行上的列关系。aij的行前趋ai,j-1，aij的行后继ai,j+1COL={

4、0im-2,0jn-1}每一列上的行关系。aij的列前趋ai-1,j，aij的列后继ai+1,j2.4.1数组的定义行优先存放(例：pascal、C语言)：设数组开始存放位置LOC(0,0)=a,每个元素占用l个存

5、储单元LOC(i,j)=a+(in+j)l2.4.2数组的顺序存储结构约定存放次序：因为计算机的存储单元是一维的，数组可以是多维的，所以必须约定存放次序。列优先存放(例：Fortran语言)：设数组开始存放位置LOC(0,0)=a,每个元素占用l个存储单元LOC(i,j)=a+(jm+i)l2.4.2数组的顺序存储结构三维数组：各维元素个数为m1,m2,m3下标为i1,i2,i3的数组元素的存储地址：(按页/行/列存放)LOC(i1,i2,i3)=a+(i1m2m3+i2m3+i3)*l前i1页总元素个数第i1页的前i2行总元素个数2.

6、4.2数组的顺序存储结构第i1页的第i2行i3列前元素个数下标为i1,i2,i3的数组元素的存储地址：(按列/行/页存放)LOC(i1,i2,i3)=a+(i3m1m2+i2m1+i1)*l前i3列总元素个数第i3列的前i2行总元素个数2.4.2数组的顺序存储结构第i3列的第i2行i1页前元素个数n维数组：各维元素个数为m1,m2,m3,…,mn下标为i1,i2,i3,…,in的数组元素的存储地址：LOC(i1,i2,…,in)=a+(i1m2m3…mn+i2m3m4…mn++……+in-1mn+in)l2.4.2数组的顺序

7、存储结构二维数组三维数组行向量下标i1页向量下标i1列向量下标i2行向量下标i2列向量下标i3特殊矩阵的压缩存储特殊矩阵：是指非零元素的分布有一定规律/大量零元素的矩阵。压缩存储：针对阶数很高的特殊矩阵。为节省存储空间，可以不存储零元素或对称元素。对称矩阵三对角矩阵2.4.2数组的顺序存储结构对称矩阵的压缩存储设有一个nn的对称矩阵A。在矩阵中，aij=aji2.4.2数组的顺序存储结构为节约存储空间，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。把它们按行存放于一个一维数组B中，称之为对称

8、矩阵A的压缩存储方式。数组B共有n+(n-1)++1=n(n+1)/2个元素。2.4.2数组的顺序存储结构上三角矩阵下三角矩阵下三角矩阵Ba00a10a11a20a21a22a30a31a32……an-1n-1012345678n(n+1)/2-1若ij,数组元素A[i][j]在数组B中的存放位置为1+2++i+j=(i+1)i/2+j前i行元素总数第i行第j个元素前元素个数若i

9、第k个位置，可寻找满足i(i+1)/2k<(i+1)(i+2)/2的i(行号),j=k-i(i+1)/2(列号)例:当k=8,34/2=6k<4*5/2=10,取i=3。则j=8-34/2=2。2.4.2数组的顺序存储结构上三角矩阵Ba00a01a02a03a11a12a13a22a23a330123456789若ij，数组元素A[i][j]在数组B中的存放位置为n+(n-1)+(n-2)++(n-i+1)+j-i=(2n-i-1)i/2+j前i行元素总数第i行第j个元素前元素个数n=4若i>j，数组元素A[i][j]在矩阵的

10、下三角部分，在数组B中没有存放。因此，找它的对称元素A[j][i]。A[j][i]在数组B的第(2n-j-