最新数组与广义表教学讲义ppt课件.ppt

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

1、数组与广义表数组定义相同类型的数据元素的集合。一维数组的示例352749186054778341020123456789一维数组数组的定义和初始化main(){inta1[3]={3,5,7},*elem;for(inti=0;i<3;i++)printf(“%d”,a1[i],“”);//静态数组elem=a1;for(inti=0;i<3;i++){printf(“%d”,*elem,“”);//动态数组elem++;}}三维数组各维元素个数为m1,m2,m3下标为i1,i2,i3的数组元素的存储地址：（

2、按页/行/列存放）LOC(i1,i2,i3)=a+(i1*m2*m3+i2*m3+i3)*l前i1页总元素个数第i1页的前i2行总元素个数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)*l二维数组三维数组行向量下标i页向量下标i列向量下标j行向量下标j列向量下标k特殊矩阵的压缩存储特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。特殊矩阵

3、的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。对称矩阵三对角矩阵对称矩阵的压缩存储设有一个nn的对称矩阵A。在矩阵中，aij=aji为节约存储空间，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。把它们按行存放于一个一维数组B中，称之为对称矩阵A的压缩存储方式。数组B共有n+(n-1)++1=n*(n+1)/2个元素。上三角矩阵下三角矩阵下三角矩阵Ba00a10a11a20a21a22a30a3

4、1a32……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

5、4/2=6k<4*5/2=10,取i=3。则j=8-3*4/2=2。上三角矩阵Ba00a01a02a03a11a12a13a22a23a330123456789若ij，数组元素A[i][j]在数组B中的存放位置为n+(n-1)+(n-2)++(n-i+1)+j-i前i行元素总数第i行第j个元素前元素个数n=4若ij，数组元素A[i][j]在数组B中的存放位置为n+(n-1)+(n-2)++(n-i+1)+j-i==(2*n-i+1)*i/2+j-i==(2*n-i-1)*i/2+j若i>j，数组元素

6、A[i][j]在矩阵的下三角部分，在数组B中没有存放。因此，找它的对称元素A[j][i]。A[j][i]在数组B的第(2*n-j-1)*j/2+i的位置中找到。三对角矩阵的压缩存储Ba00a01a10a11a12a21a22a23…an-1n-2an-1n-1012345678910三对角矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外，所有其它元素均为0。总共有3n-2个非零元素。将三对角矩阵A中三条对角线上的元素按行存放在一维数组B中，且a00存放于B[0]。在三条对角线上的元素aij满足0in-

7、1,i-1ji+1在一维数组B中A[i][j]在第i行，它前面有3*i-1个非零元素,在本行中第j列前面有j-i+1个，所以元素A[i][j]在B中位置为k=2*i+j。若已知三对角矩阵中某元素A[i][j]在数组B[]存放于第k个位置，则有i=(k+1)/3j=k-2*i例如，当k=8时，i=(8+1)/3=3,j=8-2*3=2当k=10时，i=(10+1)/3=3,j=10-2*3=4稀疏矩阵(SparseMatrix)非零元素个数远远少于矩阵元素个数在上图中,矩阵A是6*7的矩阵,它有42个元

8、素,但只有8个非零元素,且分布无规律可循,所以可以称之为稀疏矩阵。稀疏矩阵的抽象数据类型(三元组顺序表）#defineMAXSIZE12500typedefstruct{inti,j;//非零元素行号/列号ElemTypee;//非零元素的值}Triple;//三元组typedefunion{Tripledata[MAXSIZE+1];intm