矩阵压缩存储的概念 第五章数组和广义表 矩的压缩存:对于一些结构比较特殊的矩阵可 采用压缩存储方式,即只存储矩阵中的部分元素而不丢 失矩阵中任何信息的存储方式。同时,还需保证矩阵的 各种运算能有效地进行。 在矩阵阶数很高且矩阵中有许多值相同的元素或零 元素时,为多个值相同的元素分配一个存储空间,对零 元素不分配空间,从而可以大量节省存储空间 特殊矩阵:值相同的元素或零元素在矩阵中的分布 有一定规律。 硫矩阵:矩阵中非零元素较之零元素要少得多, 且非零元素的分布没有一定规律 第16页
第五章 数组和广义表 第16页 矩阵的压缩存储：对于一些结构比较特殊的矩阵可 采用压缩存储方式，即只存储矩阵中的部分元素而不丢 失矩阵中任何信息的存储方式。同时，还需保证矩阵的 各种运算能有效地进行。 在矩阵阶数很高且矩阵中有许多值相同的元素或零 元素时，为多个值相同的元素分配一个存储空间，对零 元素不分配空间，从而可以大量节省存储空间。 特殊矩阵：值相同的元素或零元素在矩阵中的分布 有一定规律。 稀疏矩阵：矩阵中非零元素较之零元素要少得多， 且非零元素的分布没有一定规律。 ⚫矩阵压缩存储的概念
特殊矩阵的压缩存储 第五章数组和广义表 研究对称矩阵、三角矩阵(上三角矩阵、下三角矩阵),对 角矩阵(三对角矩阵、带状矩阵)等特殊矩阵的压缩存储问题。 (1)对称矩阵的压缩存储 一定义若一个n阶矩阵(方阵)A中的元素满足下述性质一 ai=ai(1sl, sn) 则称A为n阶对称矩阵。 示例一个5阶对称矩阵 15137 50800 所谓共享存储空间 18926是指a与a经计算后都 3025 指向同一个存储单元 70613 对称矩阵中的元素关于主对角线对称,故仅需储矩阵中上 三角或下三角中的元素,让每一对对称的元素共享一个存储空间 第17页
第五章 数组和广义表 第17页 所谓共享存储空间 是指aij与 aji 经计算后都 指向同一个存储单元 研究对称矩阵、三角矩阵（上三角矩阵、下三角矩阵），对 角矩阵（三对角矩阵、带状矩阵）等特殊矩阵的压缩存储问题。 （1）对称矩阵的压缩存储 定义 若一个n阶矩阵（方阵）A中的元素满足下述性质 aij= aji (1≤i, j≤n) 则称A为n阶对称矩阵。 示例 一个5阶对称矩阵 1 5 1 3 7 5 0 8 0 0 1 8 9 2 6 3 0 2 5 1 7 0 6 1 3 对称矩阵中的元素关于主对角线对称，故仅需存储矩阵中上 三角或下三角中的元素，让每一对对称的元素共享一个存储空间 。 ⚫ 特殊矩阵的压缩存储
特殊矩阵的压缩存储 第五章数组和广义表 5137 a 11 50800 a21 as 8926 31a32a 33 3025 一a41a42a43a44 7061-3 a51a52a53a54a 对称矩阵以行为主序存 储下三角矩阵的元素 对于An×所对应的下 角矩阵中(见右下图) a11 第(1n)行恰有个元素, a21a22 故元素总数为 a31a32a33 an1an2an3…ann ∑i=1+2+…+n 对称矩阵An以行为主序 n2(n2+1) 存储下三角矩阵的元素 2 第18页
第五章 数组和广义表 第18页 1 5 1 3 7 5 0 8 0 0 1 8 9 2 6 3 0 2 5 1 7 0 6 1 3 a11 a21 a22 a31 a32 a33 a41 a42 a43 a44 a51 a52 a53 a54 a55 对称矩阵以行为主序存 储下三角矩阵的元素 a11 a21 a22 a31 a32 a33 … … … … … an1 an2 an3 …ann 对称矩阵Ann以行为主序 存储下三角矩阵的元素 . 2 ( 1) 1 2 1 + = = + + + = n n i n n i 对于An×n所对应的下 三角矩阵中（见右下图）， 第i(1≤i≤n)行恰有i个元素， 故元素总数为 aij ⚫ 特殊矩阵的压缩存储
0特殊矩阵的压缩存储 第五章数组和广义表 a a21a22 a31a32a33 an1an2an3…am 一设以一维数组a(n(n+1)2)作为n阶对称矩阵A的存一 储结构,令sa≌a,则有如下之一一对应关系 (-1 (s1) y=1+S+3+…+(!-J+ 第19页
第五章 数组和广义表 第19页 设以一维数组sa（1:n(n+1)/2）作为n阶对称矩阵A的存 储结构，令sa[k] a ij，则有如下之一一对应关系 ( ) 2 ( 1) 1 2 3 ( 1) j i j i i k i j + − = = + + ++ − + ⚫ 特殊矩阵的压缩存储 a11 a21 a22 a31 a32 a33 … … … … … an1 an2 an3 …amn aij
0特殊矩阵的压缩存储 第五章数组和广义表 由上述推导可得 a[k],则 k 十J 2 同理当7<令an=(则 k (-1) +(上式令,互换) 2 故有 ( k=2+j,当i≥下三角包括主对角线 (5-6) +i,当i<j上三角,不包括主对角线 第20页
第五章 数组和广义表 第20页 由上述推导可得 ( ) (5 6) , , 2 ( 1) , , 2 ( 1) . , 2 ( 1) , , [ ], . 2 ( 1) , [ ], − + − + − = + − = = + − = = 当 上三角 不包括主对角线 当 下三角 包括主对角线 故有 上式令 互换 同理 当 令 则 当 令 则 i i j j j j i j i i k i i j j j k i j a sa k j i i k i j a sa k i j i j ⚫ 特殊矩阵的压缩存储