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

1、数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社专题专题3：矩阵的压缩存储：矩阵的压缩存储123对称矩阵的压缩存储对称矩阵的压缩存储及寻址及寻址三角矩阵的压缩存储及寻址三角矩阵的压缩存储及寻址对角矩阵的压缩存储及寻址对角矩阵的压缩存储及寻址4稀疏矩阵的压缩存储稀疏矩阵的压缩存储5矩阵压缩存储的基本思想矩阵压缩存储的基本思想数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社4.3 矩阵的压缩存储矩阵的压缩存储p 特殊矩阵：特殊矩阵：矩阵中很多值相同的元素并且它们的矩阵中很多值相同的元素并且它们的分布有一定的规律。分布有一定的规律。p 稀疏矩阵：稀疏矩阵：

2、矩阵中有很多零元素。矩阵中有很多零元素。p 压缩存储的基本思想是：压缩存储的基本思想是： 为多个值为多个值相同相同的元素只分配的元素只分配一个一个存储空间；存储空间； 对对零零元素元素不分配不分配存储空间。存储空间。 特殊矩阵和稀疏矩阵特殊矩阵和稀疏矩阵数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社特殊矩阵的压缩存储特殊矩阵的压缩存储对称矩阵对称矩阵 3647862842481697460582957A对称矩阵特点：对称矩阵特点：aij=aji如何压缩存储？如何压缩存储？只存储下三角部分的元素。只存储下三角部分的元素。4.3 矩阵的压缩存储矩阵的压缩存储数据结构（数据结

3、构（C+版）第版）第2版版清华大学出版社清华大学出版社(a) 下三角矩阵下三角矩阵 (b) 存储说明存储说明 (c) 计算方法计算方法aij在一维数组中的序号在一维数组中的序号=阴影部分的面积阴影部分的面积= i( (i+1) )/2+ j一维数组下标从一维数组下标从0开始开始aij在一维数组中的下标在一维数组中的下标k= i( (i+1) )/2+ j-1 1 i n1 j n aij每行元素个数每行元素个数12i-1aij在本行中的序号在本行中的序号aij第第1行行第第2行行第第i-1行行对称矩阵的压缩存储对称矩阵的压缩存储 4.3 矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（C+版）

4、第版）第2版版清华大学出版社清华大学出版社对于下三角中的元素对于下三角中的元素aij（ij），在数组，在数组SA中的下标中的下标k与与i、j的关系为：的关系为：ki(i1)/2j -1。上三角中的元素上三角中的元素aij（ij），），因为因为aijaji，则访问和则访问和它对应的元素它对应的元素aji即可，即：即可，即：kj(j1)/2i -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-14.3 矩阵的压缩存储矩阵的压缩存储

5、数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社特殊矩阵的压缩存储特殊矩阵的压缩存储三角矩阵三角矩阵 3 cc c c6 2c c c4 81 c c7 46 0 c8 29 5 7(a)下三角矩阵下三角矩阵3 4 8 1 0c2 9 4 6cc 5 7cc c 0 8cc c c 7(b)上三角矩阵上三角矩阵如何压缩存储？如何压缩存储？只存储上三角（或下三角）部分的元素。只存储上三角（或下三角）部分的元素。4.3 矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社矩阵中任一元素矩阵中任一元素aij在在数组数组中的下标中的下

6、标k与与i、j的对应关系：的对应关系：i( (i1) )/2j-1 当当ijn( (n1) )/2 当当ijk=下三角矩阵的压缩存储下三角矩阵的压缩存储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 矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社矩阵中任一元素矩阵中任一元素aij在在数组数组中的下标中的下标k与与i、j的对应关系：的对应关系： (i-1)(2n-i+

7、2)/2+j-i 当当ijn( (n1) ) /2 当当ijk=上三角矩阵的压缩存储上三角矩阵的压缩存储存储存储上三角上三角元素元素对角线上方的常数对角线上方的常数只存一个只存一个4.3 矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社特殊矩阵的压缩存储特殊矩阵的压缩存储对角矩阵对角矩阵 对角矩阵：对角矩阵：所有非零元素都集中在以主对角线为中心所有非零元素都集中在以主对角线为中心的带状区域中，除了主的带状区域中，除了主对角线和它的上下方若干条对对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。角线的元素外，所有其他元素都为零。 a11

8、 a12 0 0 0a21 a22 a23 0 00 a32 a33a34 00 0 a43a44 a450 0 0 a54 a55A=4.3 矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社按行按行存储存储 元素元素aij在一维数组中的序号在一维数组中的序号=2 + 3( (i2) )+( ( ji + 2) )=2i+ j -2 一维数组下标从一维数组下标从0开始开始元素元素aij在一维数组中的下标在一维数组中的下标= 2i+ j -3(b) 寻址的计算方法寻址的计算方法(c) 压缩到一维数组中压缩到一维数组中a11 a12 a21 a22

9、 a23 a32 a33 a34 a43 a44 a45 a54 a550 1 2 3 4 5 6 7 8 9 10 11 12对角矩阵的压缩存储对角矩阵的压缩存储(a) 三对角矩阵三对角矩阵 0 0 0 0 00 00 0 0 0 0 A=a11 a12a21 a22 a23a32 a33 a34a43 a44 a45a54 a554.3 矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社稀疏矩阵的压缩存储稀疏矩阵的压缩存储 15 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 0 0 0 0

10、0A=如何只存储非零元素？如何只存储非零元素？注意：稀疏矩阵中的非零元素的分布没有规律。注意：稀疏矩阵中的非零元素的分布没有规律。4.3 矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社template struct element int row, col; /行号，列号行号，列号 DataType item /非零元素值非零元素值;将稀疏矩阵中的每个非零元素表示为将稀疏矩阵中的每个非零元素表示为：( (行号，列号，非零元素值行号，列号，非零元素值) )三元组三元组稀疏矩阵的压缩存储稀疏矩阵的压缩存储 定义三元组定义三元组：4.3 矩阵的压缩

11、存储矩阵的压缩存储数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社三元组表三元组表：将稀疏矩阵的非零元素对应的三元组所将稀疏矩阵的非零元素对应的三元组所构成的集合，构成的集合，按行优先的顺序排列成一个线性表。按行优先的顺序排列成一个线性表。稀疏矩阵的压缩存储稀疏矩阵的压缩存储 三元组表三元组表( (0,0,15), (1,1,11), (2,3,6), (4,0,9) )15 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 0 0 0 0 0A=如何存储三元组表？如何存储三元组表？4.3 矩阵的压缩存储矩阵的压缩存储数据结

12、构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组顺序表三元组顺序表采用顺序存储结构存储三元组表采用顺序存储结构存储三元组表15 0 0 22 0 - -15 0 11 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0 0 0A=三元组顺序表是否三元组顺序表是否需要预留存储空间？需要预留存储空间？稀疏矩阵的修改操作稀疏矩阵的修改操作三元组顺序表的插入三元组顺序表的插入/ /删除操作删除操作4.3 矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社稀疏矩阵的压缩

13、存储稀疏矩阵的压缩存储三元组顺序表三元组顺序表采用顺序存储结构存储三元组表采用顺序存储结构存储三元组表 1 1 15 1 4 22 1 6 - -15 2 2 11 2 3 3 3 4 6 5 1 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -115 0 0 22 0 - -15 0 11 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0 0 0A=7（非零元个数）（非零元个数）是否对应惟一的稀疏矩阵？是否对应惟一的稀疏矩阵？5（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）4.3 矩阵的压缩存储矩阵

14、的压缩存储数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社存储结构定义：存储结构定义： const int MaxTerm=100; template struct SparseMatrix DataType dataMaxTerm; /存储非零元素存储非零元素 int mu, nu, tu; /行数、列数、非零元个数行数、列数、非零元个数 ;稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组顺序表三元组顺序表4.3 矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社采用采用链接链接存储结构存储三元组表，每个非零元素对应存储结构存储

15、三元组表，每个非零元素对应的三元组存储为一个链表结点，结构为：的三元组存储为一个链表结点，结构为： rowcolitemdownrightrow：存储非零元素的行号存储非零元素的行号col：存储非零元素的列号存储非零元素的列号item：存储非零元素的值存储非零元素的值right：指针域，指向同一行中的下一个三元组指针域，指向同一行中的下一个三元组down：指针域，指向同一列中的下一个三元组指针域，指向同一列中的下一个三元组稀疏矩阵的压缩存储稀疏矩阵的压缩存储十字链表十字链表4.3 矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社 3 1 2M=3 0 0 50 1 0 02 0 0 0 1 1 3 1 4 5 2 2 1稀疏矩阵的压缩存储稀疏矩阵的压缩存储十字链表十字链表4.3 矩阵的压缩存储矩阵的压缩