【数据结构与算法】数组2

《【数据结构与算法】数组2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5.3矩阵的压缩存储矩阵:二维数组特殊矩阵:大量重复元素或大量0元素稀疏矩阵:大量0元素压缩存储:重复元素只分配一个存储空间,0元素不分配存储空间5.3.1特殊矩阵对称矩阵:aij=aji(1<=i,j<=n)下三角矩阵:当i

2、i-j

3、>1时,aij=0,(1<=i,j<=n)a11a12a13...a1na21a22a23...a2na31a32a33...a3n......an1an2an3...annAnxn=对称矩阵:aij=aji(1<=i,j<=n)存储元素数:1+2+...+n=n(n+1)/2一

4、维数组SA[1..n(n+1)/2]作为数组A下三角元素的存储结构:SA[k]=[a11,a21,a22,a31,...,an1,...,ann]k=1234n(n-1)/2+1n(n+1)/2SA[k]和A[i,j]的一一对应关系:i(i-1)/2+j当i>=jk={j(j-1)/2+i当i

5、28916795A=4520313252816795A=下三角矩阵:当i=j)0(当i

6、i-j

7、>1时,aij=0,(1<=i,j<=n)a11a1200...0a21a22a

8、230...0Anxn=0a32a33a34...0......000...ann-1ann一维数组SA[1..3*n-2]作为数组A下三角元素的存储结构:SA[k]=[a11,a12,a21,a22,a23,a32,a33,a34,...,ann-1,ann]k=123456783n-33n-2sa[k]和a[i,,j]的一一对应关系:sa[k],k=3*(i-1)+j-i+1,a[i,j]={当

9、i-j

10、<=10当

11、i-j

12、>1例5.5三对角矩阵4300052200A=010400028700095一维数组SA[1..3*5-2]作为数组A的存储结构:SA=(4

13、352210428795)如:a[5,4]=9k=3*(5-1)+4-5+1=12故:sa[12]=95.3.2稀疏矩阵通常稀疏因子<0.05时称为稀疏矩阵.例5.60129000000-30015000000012000180M=-30000140900240000240000T=00000-7018000000000001500-70000014000000000M:muxnu(6x7)T:nuxmu(7x6)M是T的转置稀疏矩阵的存储结构一.三元组顺序表M:ijeT:ije121213-3139161531-32112361425184324319521834

14、24611546-764-76314三元组顺序表结构定义#defineMAXSIZE12500typedefstruct{inti,j;Elemtypee;}Triple;typedefunion{Tripledata[MAXSIZE+1];intmu,nu,tu;}TSMatrix;TSMatrixM,T;M.data[p].i.j.e012........maxsize求稀疏矩阵M的转置矩阵TTSMatrixM,T;012345678012345678M.data[p].i.j.eT.data[q].i.j.e求稀疏矩阵M的转置矩阵TStatusTranspos

15、eSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;for(col=1;col<=M.nu;++col)for(p=1;p<=M.tu;++p)if(M.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++q;}}retrunOK;}//TransposeSMatrix求稀疏矩阵转置的算法复杂度其算法复杂度是O(nu*tu)而一般矩阵的转置算