第五章数组和矩阵

《第五章数组和矩阵》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章特殊矩阵的压缩存储1特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对无需存储的元素(如零元素或对称元素)，不再存储。对称矩阵三角矩阵对角矩阵5、2矩阵的压缩存储2对称矩阵3为节约存储空间，只存对角线及对角线以上的元素，或只存对角线及对角线以下的元素。前者称为上三角矩阵,后者称为下三角矩阵。把它按行存放于一维数组B中,称为对称矩阵A的压缩存储方式。4úúúûùêëé=3313AaaaaaaaaaaaaLLLLLLLn1an2an3aúêê323123222112111naLL2n3nnn在矩阵中，aij=aji数组B共

2、有n+(n-1)++1=n*(n+1)/2个元素对称矩阵5上三角阵下三角阵6下三角矩阵Ba11a21a22a31a32a33a41a42a42……an-1n-1012345678n(n+1)/2-1若ij,数组元素A[i][j]在数组B中的存放位置为1+2++i-1+j-1=(i-1)*i/2+j-1前i-1行元素数第i行第j个元素前元素个数7上三角若i

3、为同一个常数；(b)为上三角矩阵，主对角线以下均为同一个常数。存储时类似对称矩阵，另外存储c的数值11上三角矩阵Ba11a12a13a14a22a23a24a33a34a440123456789若ij，数组元素A[i][j]在数组B中的存放位置为n+(n-1)+(n-2)++(n-i+2)+j-i前i-1行元素数第i行第j个元素前元素个数n=412若ij，数组元素A[i][j]在数组B中的存放位置为n+(n-1)+(n-2)++(n-i+2)+j-i==(2*n-i+1)*(i-1)/2+j-i若i>j，数组元素A[i][j]在矩阵的下三角部分，在数组B中没有存放。因此，找它

4、的对称元素A[j][i]。1314对角矩阵15三对角矩阵的压缩存储Ba11a12a21a22a23a32a33a34…an,n-1an,n01234567891016三对角矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外，所有其它元素均为0。总共有3n-2个非零元素。将三对角矩阵A中三条对角线上的元素按行存放在一维数组B中，且a11存放于B[0]。在三条对角线上的元素aij满足1in,i-1ji+1在一维数组B中A[i][j]在第i-1行，它前面有3*(i-1)-1个非零元素,在本行中第j列前面有j-i+1个，所以元素A[i][j]在B中位置为k=2*i+j-3。1718

5、稀疏矩阵(SparseMatrix)随机稀疏矩阵：非零元素个数远少于矩阵元素个数，且分布没有一定规律.19如采用二维数组表示稀疏矩阵，那么它的弊病是什么？浪费空间，浪费时间。　前者是指存放了大量没有用的零值元素，后者是指在进行矩阵的运算中进行了很多与零元素的运算。解决稀疏矩阵压缩存储的目标是：1)尽可能减少或不存储零值元；2)尽可能不作和零值元进行的运算；3)便于进行矩阵运算，即易于从一对行列号找到矩阵的元，易于找到同一行或同一列的非零值元。20稀疏矩阵的存储行行((rrooww))列列((ccooll))值值((vvaalluuee))[1]01342222[2]0171155[3]12

6、121111[4]12561177[5]2334--66[6]34563399[7]45019911[8]5623228821稀疏矩阵的转置转置矩阵22转置矩阵23用三元组表表示的稀疏矩阵及其转置2425