一维数组多维数组特殊矩阵的压缩存储 稀疏矩阵广义表.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,“”)

2、;//动态数组elem++;}}数组溢出的处理一维数组的问题在于：如果其空间大小已经分配，一旦空间占满，再加入新元素将产生溢出。已知一维数组的大小为MaxSize，其定义和分配如下：typedefintElemType;ElemType*data=newElemType[MaxSize];现已产生溢出，那么处理溢出的方法为：constintNewSize=100;ElemType*newArray=newElemType[NewSize];if(newArray==NULL){printf(“存储分配错!”)

3、;exit(1);}intn=(NewSize<=MaxSize)?NewSize:MaxSize;ElemType*srcptr=data;ElemType*destptr=newArray;while(n--)*destptr++=*srcptr++;free(data);data=newArray;多维数组多维数组是一维数组的推广多维数组是一种非线性结构。其特点是每一个数据元素可以有多个直接前驱和多个直接后继。数组元素的下标一般具有固定的下界和上界，因此它比其他复杂的非线性结构简单。二维数组三维数组行向量下

4、标i页向量下标i列向量下标j行向量下标j列向量下标k二维数组行优先存放：设数组开始存放位置LOC(a[0][0])=a,每个元素占用l个存储单元LOC(a[j][k])=a+(j*m+k)*l列优先存放：设数组开始存放位置LOC(a[0][0])=a,每个元素占用l个存储单元LOC(a[j][k])=a+(k*n+j)*l三维数组各维元素个数为m1,m2,m3下标为i1,i2,i3的数组元素的存储地址：（按页/行/列存放）LOC(a[i1][i2][i3])=a+(i1*m2*m3+i2*m3+i3)*l前i1页

5、总元素个数第i1页的前i2行总元素个数第i2行前i3列元素个数n维数组各维元素个数为m1,m2,m3,…,mn下标为i1,i2,i3,…,in的数组元素的存储地址：LOC(a[i1][i2]…,[in])=a+(i1*m2*m3*…*mn+i2*m3*m4*…*mn++……+in-1*mn+in)*l特殊矩阵的压缩存储特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。对称矩阵三对角矩阵对称矩阵的压缩

6、存储设有一个nn的对称矩阵A。在矩阵中，aij=aji为节约存储，只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。下三角矩阵上三角矩阵把它们按行存放于一个一维数组B中，称之为对称矩阵A的压缩存储方式。数组B共有n+(n-1)++1=n*(n+1)/2个元素。下三角矩阵Ba00a10a11a20a21a22a30a31a32……an-1n-1012345678n(n+1)/2-1若ij,数组元素A[i][j]在数组B中的存放位置为1+2++i+

7、j=(i+1)*i/2+j前i行元素总数第i行第j个元素前元素个数若i

8、3a330123456789若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