第4章 矩阵的压缩存储

1、 数据结构数据结构 主讲教师：杨华莉主讲教师：杨华莉 2 第四章第四章 矩阵的压缩存储矩阵的压缩存储 3 4.1 数组的定义及其基本操作数组的定义及其基本操作 1) 数组的定义数组的定义 n 数组是数组是n(n=0)n(n=0)个个相同相同数据类型数据元素数据类型数据元素 构成的构成的有限有限序列。序列。 n 数组可以看成是一种特殊的线性表，即线数组可以看成是一种特殊的线性表，即线 性表中数据元素本身也是一个线性表。性表中数据元素本身也是一个线性表。 4 二维数组同样满足数组的定义。一个二维二维数组同样满足数组的定义。一个二维 数组可以被看成是特殊的一维数组，其中，数组可以被看成是特殊的一维数

2、组，其中， 每个元素又是一个一维数组。多维数组可以每个元素又是一个一维数组。多维数组可以 按同样的方法类推。按同样的方法类推。 mnmm n n nm aaa aaa aaa A . . . . 21 22221 11211( ( ) ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 5 2) 数组的特点数组的特点 数组中的数据元素数目固定数组中的数据元素数目固定( (结构固定结构固定) ) 数组中的数据元素具有相同的数据类型数组中的数据元素具有相同的数据类型 ( (元素同构元素同构) ) 数组中的每个数据元素都与一组唯一的数组中的每个数据元素都与一组唯一的 下标值相对应；下

3、标值相对应； 数组是一种数组是一种随机存储结构随机存储结构。 6 3) 数组的基本运算数组的基本运算 构造构造 n n 维数组维数组 销毁销毁 n n 维数组维数组 存取数组元素值存取数组元素值( (给定一组下标，存取相给定一组下标，存取相 应数据元素值应数据元素值) ) 修改数组元素值修改数组元素值( (给定一组下标，修改相给定一组下标，修改相 应数据元素值应数据元素值) ) 7 4.1.2 数组的顺序存储数组的顺序存储 一个一维数组，一旦第一个元素一个一维数组，一旦第一个元素a a0 0的存储地址的存储地址 Loc(aLoc(a0 0) )确定，而每个元素所占用的存储空间大小确定，而每个元

4、素所占用的存储空间大小 为为则元素则元素a ai i的地址可以由以下公式计算：的地址可以由以下公式计算： 时时 0 0, ,) )( ( 时时 0 0a a, , ) )( ( iliLOC i iLOC 1 LOC ( i ) = LOC ( i - -1 ) + l =a+ i*l 8 mnm3m2m1 3n33231 2n232221 1n13211 aaaa aaaa aaaa aaaa A 3 1 9 10 limiLOC limimmmi mmmiLOCiiiLOC n j n jk nkj nnnn nn *)0,.0 , 0( *) ()0,.0 , 0(),( 1 11 14

5、32 32121 m1, m2, m3, , mn， 11 4.2 特殊矩阵的压缩存储特殊矩阵的压缩存储 高级语言中一般用二维数组存储矩阵，当矩高级语言中一般用二维数组存储矩阵，当矩 阵中存在大量相同的元素或零元素时，浪费空阵中存在大量相同的元素或零元素时，浪费空 间。间。 矩阵的压缩存储矩阵的压缩存储: :为多个值相同的元素只分为多个值相同的元素只分 配一个存储空间配一个存储空间, ,对零元素不分配空间。对零元素不分配空间。 u 特殊矩阵特殊矩阵：值相同的元素或零元素在矩阵中分：值相同的元素或零元素在矩阵中分 布有一定规律。布有一定规律。 u 稀疏矩阵稀疏矩阵：零元素较多，分布无规律。：零元

6、素较多，分布无规律。 12 4.2.1 对称矩阵对称矩阵 在一个在一个n阶方阵阶方阵A中，若元素满足下述性质：中，若元素满足下述性质： 则称则称A为为对称矩阵对称矩阵。对称矩阵中的元素关于主。对称矩阵中的元素关于主 对角线对称，故只需要存储矩阵的上三角或下对角线对称，故只需要存储矩阵的上三角或下 三角矩阵，这样可以节约大约一半的空间。三角矩阵，这样可以节约大约一半的空间。 jiij AA 13 31607 15203 62981 00805 73151 a a11 11 a a21 21 a a22 22 a a31 31 a a32 32 a a33 33 . a an,1 n,1 . a

7、. an,n n,n 在此下三角阵中在此下三角阵中,第第i行恰有行恰有i个元素个元素,元素总数为元素总数为 n i nni 1 2/)1( a11 a21 a22 a31 a32 an1 ann . k= 0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 因此可将这些元素存放在一个向量因此可将这些元素存放在一个向量Sn(n+1)/2中中 14 为了便于访问方阵为了便于访问方阵A中的元素，必须在中的元素，必须在aij 和和Sk之间建立一个对应关系。若之间建立一个对应关系。若aij在下三在下三 角矩阵中角矩阵中(ij)，则有：，则有： 若若aij在上三角矩阵中在上三角矩阵中(ij)，则有

8、：，则有： k 和和 i、j的对应关系为：的对应关系为： )1(2/)1(jiik )1(2/)1(ijjk jiijj jijii k ),1(2/ ) 1( ) 1(2/ ) 1(， 15 4.2.2 三角矩阵三角矩阵 以主对角线划分，下三角矩阵：以主对角线划分，下三角矩阵： 在多数情况下，三角矩阵的常数在多数情况下，三角矩阵的常数c为为0。 nnnn aaa caa cca ,2,1 , 2221 11 . . . . jinn jijii k , , , , , , , , ,2/)1(* )1(2/)1(， 16 4.3 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 如果一个矩阵的非如果一个

9、矩阵的非 0 元素个数远远小于矩元素个数远远小于矩 阵阵 元素的总数，则称这个矩阵为稀疏矩阵。元素的总数，则称这个矩阵为稀疏矩阵。 一般来说，稀疏矩阵非一般来说，稀疏矩阵非0元素的分布是无规元素的分布是无规 律的。因此，在存储非律的。因此，在存储非0元素的同时，还要存元素的同时，还要存 储适当的辅助信息。储适当的辅助信息。 稀疏矩阵常用的压缩存储方式：稀疏矩阵常用的压缩存储方式： 三元组表三元组表 十字链表十字链表 17 4.3.1 三元组表三元组表 存储特点：存储特点： u 对于矩阵中每个非对于矩阵中每个非0元素，用它的行号元素，用它的行号 、列号、元素值，即、列号、元素值，即（i, j,

10、a ）表示。表示。 u 将表示稀疏矩阵的所有非将表示稀疏矩阵的所有非0元素的三元元素的三元 组按行优先（列优先）顺序排列，则可得组按行优先（列优先）顺序排列，则可得 到一个其结点均是三元组的线性表，称为到一个其结点均是三元组的线性表，称为 三元组表三元组表。 u 要唯一确定一个稀疏矩阵，还必须存储要唯一确定一个稀疏矩阵，还必须存储 该矩阵的该矩阵的行数和列数行数和列数。 18 数据类型定义：数据类型定义： # define SMax 1024 三元组结点三元组结点： typedef int datatype typedef struct int i, j; datatype v; SPNode

11、; 稀疏矩阵稀疏矩阵： typedef struct SPNode dataSMax+1 ; int mu, nu, tu; /*行、列、非零元素个数行、列、非零元素个数*/ SPMatrix ; 19 三元组表所需存储单元个数为三元组表所需存储单元个数为3(t+1) 其中其中t为非零元个数为非零元个数 6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 A.data i j v 0 1 2 3 4 5 6 7 8 data0.i, data0.j, data0.v可分别可分别 存放矩阵行数、列数和非零元个数存放矩阵行数、列

12、数和非零元个数 行列下标行列下标 非零元值非零元值 76 00070015 00000180 00002400 01400003 0000000 00009120 M 例：例： 20 基本运算举例：基本运算举例： 以矩阵的转置为例说明这种压缩存储结构是如何以矩阵的转置为例说明这种压缩存储结构是如何 实现矩阵运算的。实现矩阵运算的。 问题描述：已知一个稀疏矩阵的三元组表，求该问题描述：已知一个稀疏矩阵的三元组表，求该 矩阵转置矩阵的三元组表。矩阵转置矩阵的三元组表。( (一个一个m mn n矩阵矩阵A A，它的，它的 转置矩阵是一个转置矩阵是一个n nm m 矩阵矩阵B B，且，且Aij=Bji

13、Aij=Bji） 一般矩阵转置算法：一般矩阵转置算法： for(j=0;jn;j+) for(i=0;im;i+) Bji=Aij; T(n)=O(m n) 21 从从a.data的第一列开始转置的第一列开始转置(b.data的第一行）的第一行） ， 在转置完毕后，第二列的转置开始，程序的遍历同在转置完毕后，第二列的转置开始，程序的遍历同 第一列相同，在此就不演示，仅把结果写出。第一列相同，在此就不演示，仅把结果写出。 i j v i j v col=8 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 7 1 3 3 1 6 15 2 1

14、12 2 5 18 3 1 9 3 4 24 4 6 7 6 3 14 p=8 q=9 a.data b.data 方法一：方法一： 按按b中三元组的次序依次在中三元组的次序依次在a中找到相应中找到相应 的三元组，即按的三元组，即按M的列序转置。的列序转置。 22 方法一程序实现如下：方法一程序实现如下： void TransposeSMtrix(TSMatrix a，TSMatrix b.mu=a.nu; b.nu=a.mu;/* 行、列数互换行、列数互换*/ b.tu=a.tu; /* 非零元数不变非零元数不变*/ if（b.tu!=0） /* 若非零元不为零若非零元不为零*/ q=1;

15、/* b.data中元素的下标中元素的下标*/ 23 for（col=1;col=a.nu;col+） for（p=1;p=a.tu;p+） if（a.datap.j= =col） /*查找查找a中第中第1col列的元素列的元素*/ b.dataq.i=a.datap.j; /*行值列值互换行值列值互换*/ b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; /*值不变值不变*/ q+; /*处理下一个非零元处理下一个非零元*/ 24 方法二：方法二： 25 1357889 col numcol cpotcol 1 2 2 2 3 2 4 1 5 0 6 1 7

16、 0 76 00070015 00000180 00002400 01400003 0000000 00009120 M 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 7 1 3 3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 7 6 3 14 a.datab.data i j v i j v 26 算法：算法：P.84 P.84 算法算法4.24.2 SPMatrix Fast_TransMatrix(SPMatrix A)SPMatrix Fast_TransMatrix(SPMatrix A) SPM

17、atrix B; SPMatrix B; int p,q,col,k; int p,q,col,k; int numn+1,cpotn+1; int numn+1,cpotn+1; B.mu=A.nu; B.mu=A.nu; /行数行数 B.nu=A.mu; B.nu=A.mu; /列数列数 B.tu=A.tu; /B.tu=A.tu; /元素个数元素个数 27 算法：算法：P.84 P.84 算法算法4.24.2 if(B.tu)/if(B.tu)/有非零元则转置有非零元则转置 for(col=1;col=A.nu;col+) for(col=1;col=A.nu;col+) numcol=

18、0; / numcol=0; /初始化每列非初始化每列非0 0元个数元个数 for(k=1;k=A.tu;k+)for(k=1;k=A.tu;k+) numA.datak.j+;/numA.datak.j+;/求求A A中每列非中每列非0 0元个数元个数 /求求A A中每一列第中每一列第1 1个非个非0 0元素在元素在B.dataB.data中的位置中的位置 cpot1=1;cpot1=1; for(col=2;col=A.nu;col+) for(col=2;col=A.nu;col+) cpotcol=cpotcol-1+numcol-1;cpotcol=cpotcol-1+numcol-

19、1; 28 算法：算法：(P.84 (P.84 算法算法4.2)4.2) for(p=1;p=A.tu;p+)/for(p=1;pmu-mu* *nunu时，接近时，接近O(muO(mu* *nu)nu) 29 2) 2) 十字链表十字链表 十字链表是稀疏矩阵链接形式存储结构的一十字链表是稀疏矩阵链接形式存储结构的一 种（当然还有其它形式）。种（当然还有其它形式）。 在该方法中每一个非在该方法中每一个非0元素用一个结点表示元素用一个结点表示 ，结点中除了表示非，结点中除了表示非0元素的元素的行、列和值行、列和值的三元组的三元组 外，还增加了两个链域：外，还增加了两个链域： 行指针域行指针域：用

20、来指向本行中下一个非：用来指向本行中下一个非0元素；元素； 列指针域列指针域：用来指向本列中下一个非：用来指向本列中下一个非0元素。元素。 30 ijv/next 行指针行指针列指针列指针 在每一个在每一个行链表行链表和每一个和每一个列链表列链表增加一个增加一个 和表结点相同的表头结点，表头结点中的行、列域和表结点相同的表头结点，表头结点中的行、列域 置为置为0，并且将所有的行、列链表和他们的头结点，并且将所有的行、列链表和他们的头结点 一起链成一个循环链表。一起链成一个循环链表。 实际实现时，两组头结点可以合用，即第实际实现时，两组头结点可以合用，即第i行链行链 表和第表和第i 列链表共享一

21、个表头结点。因为表头结点中列链表共享一个表头结点。因为表头结点中 值域值域v无用，所以可以将它作为指针域，用来存储指无用，所以可以将它作为指针域，用来存储指 向下一个表头结点的指针。向下一个表头结点的指针。 31 十字链表用十字链表用C语言描述如下：语言描述如下： typedef struct OLNode int i, j; /*矩阵非零元素的行、列值矩阵非零元素的行、列值*/ ElemType e; /*非零元素的值非零元素的值*/ struct OLNode *right, *down; /*该非零元所在行、列的后继链域该非零元所在行、列的后继链域*/ OLNode, *Olink; t

22、ypedef struct Olink *rhead, *chead; /*行、列表指针向量基行、列表指针向量基 址址*/ int mu,nu,tu; /*矩阵的行、列数及非零元数矩阵的行、列数及非零元数 个数个数*/ CrossList; 32 例：用十字链表表示下面的矩阵。例：用十字链表表示下面的矩阵。 0002 0010 5003 M 1 1 31 4 5 2 2 -1 3 1 2 M.chead M.rhead 33 十字链表的程序实现十字链表的程序实现 int CreatLinkMatrix(CrossList scanf（ /输入矩阵行、列值和非零元个数输入矩阵行、列值和非零元个数

23、 M.mu=m; M.nu=n; M.tu=t; if(!M.rhead=(Olink*)malloc(m+1)*sizeof(Olink) return OVERFLOW; /*内存分配失败，返回溢出信息内存分配失败，返回溢出信息*/ if(!M.chead=(Olink*)malloc(n+1)*sizeof(Olink) return OVERFLOW; M.rhead=M.chead=NULL;/初始化行列头指针向量初始化行列头指针向量 34 for( scanf( i!=0;scanf( p-i=i; p-j=j; p-e=e; /生成结点生成结点 if(M.rheadi = =NULL|M.rheadi-jj) p-right=M.rheadi; M.rheadi=p; /生成第一个结点生成第一个结点 else for(q=M.rheadi; (q-right) /寻找插入位置寻找插入位