第4章专题3矩阵的压缩存储.ppt

* 数据结构（C++版）第2版 清华大学出版社 专题3：矩阵的压缩存储 1 2 3 对称矩阵的压缩存储及寻址 三角矩阵的压缩存储及寻址 对角矩阵的压缩存储及寻址 4 稀疏矩阵的压缩存储 5 矩阵压缩存储的基本思想　 4.3 矩阵的压缩存储 特殊矩阵：矩阵中很多值相同的元素并且它们的分布有一定的规律。 稀疏矩阵：矩阵中有很多零元素。 压缩存储的基本思想是： ⑴ 为多个值相同的元素只分配一个存储空间； ⑵ 对零元素不分配存储空间。 特殊矩阵和稀疏矩阵 特殊矩阵的压缩存储——对称矩阵 3　6　4　7　8 6　2　8　4　2 4　8　1　6　9 7　4　6　0　5 8　2　9　5　7 A＝ 对称矩阵特点：aij=aji 如何压缩存储？ 只存储下三角部分的元素。 4.3 矩阵的压缩存储 (a) 下三角矩阵 (b) 存储说明 (c) 计算方法 aij在一维数组中的序号 =阴影部分的面积 = i×(i+1)/2+ j ∵一维数组下标从0开始 ∴aij在一维数组中的下标 k= i×(i+1)/2+ j-1 1 … i n 1 … j … n aij 每行元素个数 1 2 … i-1 aij在本行中的序号 aij 第1行 第2行 … 第i-1行 对称矩阵的压缩存储 4.3 矩阵的压缩存储 对于下三角中的元素aij（i≥j），在数组SA中的下标k与i、j的关系为：k＝i×(i＋1)/2＋j -1。 上三角中的元素aij（i＜j），因为aij＝aji，则访问和它对应的元素aji即可，即：k＝j×(j＋1)/2＋i -1 。 对称矩阵的压缩存储 第1行 第n-1行 第0行 a11 a21 a22 a31 a32 a33 aij … a n1 an2 … ann … 第2行 0 1 2 3 4 5 k n(n+1)/2-1 4.3 矩阵的压缩存储 特殊矩阵的压缩存储——三角矩阵 3 c　c　 c　 c 6 　2　c　 c　 c 4 8　1　 c c 7　 4　6 　0　 c 8　 2　9 　5 　7 (a)　下三角矩阵 3 4　 8　 1 0 c　2 　9　 4　 6 c　c　１ 5 7 c　c　 c　 0 　8 c　c　 c　 c 7 (b)　上三角矩阵 如何压缩存储？ 只存储上三角（或下三角）部分的元素。 4.3 矩阵的压缩存储 矩阵中任一元素aij在数组中的下标k与i、j的对应关系： i×(i＋1)/2＋j-1 当i≥j n×(n＋1)/2 当i＜j k= 下三角矩阵的压缩存储 0 1 2 3 4 5 k n(n+1)/2 第1行 第0行 a11 a21 a22 a31 a32 aij … ann … 第2行 c a33 存储 下三角元素 对角线上方的常数——只存一个 4.3 矩阵的压缩存储 矩阵中任一元素aij在数组中的下标k与i、j的对应关系： (i-1)×(2n-i+2)/2+j-i 当i≤j n×(n＋1) /2 当i＞j k= 上三角矩阵的压缩存储 存储 上三角元素 对角线上方的常数——只存一个 4.3 矩阵的压缩存储 特殊矩阵的压缩存储——对角矩阵 对角矩阵：所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。 a11 a12 0　 0　 0 a21 a22 a23 0　 0 0 a32 a33　a34 0 0 0 a43　a44 a45 0　 0　 0　 a54 a55 A= 4.3 矩阵的压缩存储 按行 存储 元素aij在一维数组中的序号 =2 + 3(i－2)+( j－i + 2) =2i+ j