大学《数据结构》第四章：多维数组和广义表-第二节-矩阵的压缩存储

1、第二节矩阵的压缩存储一、特殊矩阵特殊矩阵：是相同值的元素或者零元素在矩阵中的分布有一定规律 的矩阵。.对称矩阵假设n阶方阵A中的元素满足下述性质：aij=aji (0i , jn-l)那么称A为n阶的对称矩阵。对于一个n阶对称矩阵，可只存储其下三角矩阵：aio an20a21a22an-ll an-ln-l J 将元素压缩存储到l+2+3+. + n=n (n + l)/2个元素的存储空间中，假设以一维数组san ( n +1) /2作为n阶对称矩阵A的存储结构，以行序为主序存储其下三角(包括对角线)中的元素，数组Mk 和ag的对应关系:1+2+3+*(i+1) J2旬 当 Ijj (j+1)

2、 /2+i当 im=a.n ; b-n=a.m;b-t=a.t;if(b-t)for(col=0 ; cola.n ; +col) numcol=0;for(t=0 ; ta.t; +t)+ + numa.datat.j;素数rownext0=0 ;for(col = l; cola.n;+col)一行的起始点rownextcol = rownextcol-l + numcol-l;for(p=0 ; pdataq.i=a . datap.j ;b-dataq.j=a . datap.i ;b-dataq.v=a . datap.v ;+ + rownextcol;下一次再有b-dataq.j

3、=a . datap.i ;b-dataq.v=a . datap.v ;+ + rownextcol;)【算法分析】算法的时间复杂度为03、带行表的三元组表带行表的三元组表：又称为行逻辑链接的顺序表。在按行优先存储 的三元组表中，增加一个存储每一行的第一个非零元素在三元组表中 位置的数组。【类型描述】typedef structTriTupleNode dataMaxSize;int RowTabMaxRow;每行第一个非零元素的位置表int m , n , t;JRLSMatrix ;带行表的三元组表的特点：对于任给行号i(Owiwm-l),能迅速地确定该行的第一个非零元 在三元组表中的存

4、储位置为RowTabiRowTabi（043m-l）表示第i行之前的所有行的非零元数。 第i行上的非零元数目为RowTabi+l-RowTabi（0im ）会更方便些, 且t可省略。带行表的三元组表可改进矩阵的转置算法，具体【参阅其它参考 书】。当前讲授真题选解（例题算法设计题）1、对于以下稀疏矩阵（注：矩阵元素的行列下标均从1开始） TOC o 1-5 h z 00000-07-10 0-8050000000006-29（1）画出三元组表；（2 ）画出三元组表的行表。隐藏答案【答案】（1）三元组表27?3-131-833553654559(2)三元组表的行表00224（例题单项选择题）设有一

5、个10阶的对称矩阵A ,采用行优先压缩存 储方式，aii为第一个元素，其存储地址为1 ,每个元素占一个字节空 间，那么385的地址为（）A . 13B . 18C . 33D . 40隐藏答案【答案】C【解析】aii为第一个元素，a85是第（1+2+3+4+5+6+7 ）+ 5=33个元素，那么a85的地址为1+ （ 33-1 ） *1=33。注意不要死记 硬背公式。（例题算法设计题）A和B是两个n x n阶的对称矩阵，因 为是对称矩阵，所以仅需要输入下三角元素值存入一维数组。试写一 算法，求对称矩阵A和B的乘积。隐藏答案【分析】对称矩阵的第i行和第j列的元素数据在一维数组中的位 置：L=i（

6、i+l）/2+j当 iNj 时 Aij, Bij 处在下三角中）；L 司L 司(j + l)/2 + i当ij时(Aij, Bij处在上三角中）；L代表Aij或By在对称矩阵存储的一维中的位置，而且04Ln(n + l)/2【算法描述】void matrlxmult(int a , int b , int c20 , int n) /n为A、B矩阵下三角元素个数，a , b分别为一维数组，存放矩阵A和B的下三角元素值，c存放A和B的乘积for(i=0; i20;i+)for(j=O; j20 ; j+)s=0;for(k=0 ; k = k)表示元素为下三角的元素，计算在a数组中的下标Ll=i

7、*(i + l)/2 + k ;else表示元素为上三角的元素，计算下标Ll=k*(k+l)/2+i;if(k=j)表示元素为下三角的元素，计算在b数组中的下标L2=k*(k+l)/2+j ;elseL2=j*0+l)/2+k;s=s+aLl*bL2;s=s+aLl*bL2;s=s+aLl*bL2;计算矩阵成绩s=s+aLl*bL2;计算矩阵成绩/3Q0a10a20cana21CC/3Q0a10a20cana21CCa22Goa10ailca20a21a22TOa2n-l%-10%-12%Tn-lJ上三角矩阵上三角矩阵下三角矩阵上三角矩阵F三角矩阵的主对角线上方均为常数c或零；上三角矩阵是指矩

8、阵的下三角(不包括对角线)中的元素均为常数c或是零的n阶方阵。一 般情况下，三角矩阵的常数c均为零。三角矩阵可压缩存储到数组Mn ( n + 1) /2+1中。上三角矩阵中，主对角线上的第i行有n-i+l个元素，以行序为主序存放，Mk和a。的对应关系是:r nYnr nYnl)Yn2)+Yni+lT(ji*l)-l=i (2ni+2)2tH 当 iWj当的F三角矩阵中，以行序为主序存放，与对称矩阵类是，Mk和ay的对应关系是：r i (i+1) /2旬当诊 jk= 、，L n (n+1) /2 当 ij真题选解(例题填空题)1、假设一个10阶的上三角矩阵A按行优先顺序 压缩存储在一维数组B中，

9、假设矩阵中的第一个元素an在B中的存储 位置k=0 ,那么元素朋5在B中的存储位置k= 隐藏答案【答案】34【解析】元素a55的前面存储了 4行，每行存储的元素个数分别为：10、9、8、7 ,元素a55存储在第5行要存储的第1个元素，所以 a55在 B 中的存储位置 k=0+(10+9+8+7)+l-l = 34二、稀疏矩阵1、稀疏矩阵的定义含有大量的零元素且零元素分布没有规律矩阵称为稀疏矩阵。2、三元组表(1 )三元组表的含义：一个稀疏矩阵可用一个三元组线性表表 示，每个三元组元素对应稀疏矩阵中的一个非零元素，包含有该元素 的行号、列号和元素值。每个三元组元素在线性表中是按照行号值的 升序为

10、主序、列号值的升序为辅序(即行号值相同再按列号值顺序) 排列的。【例】画出以下稀疏矩阵对应的三元组表e o I。、 TOC o 1-5 h z 05000000Q00-7【解析】根据前面三元组的含义很容易画出该矩阵的三元组表。【答案】jV0211130-433-7(2 )三元组表的类型定义#define Maxsize 1000 假设非零元素个数的最大为1000个typedef struct inti J; 非零元素的行号、列号(下标)DataType v ; 非零元素值TriTupleNode ;typedef struct TriTupleNode dataMaxsize; 存储三元组的数

11、组int m , n , t; 矩阵的行数、列数和非零元素个数TSMatrix ; 稀疏矩阵类型【例】试写一个算法，建立顺序存储稀疏矩阵的三元组表。【分析】假设A为一个稀疏矩阵，其数据存储在二维数组a中，b 为一个存放对应于A矩阵生成的三元组表。在这个算法中，要进行二 重循环来判断每个矩阵元素是否为零，假设不为零，那么将其行、列下标 及其值存入b中。【算法描述】void CreateTriTable(TSMatrix *b , int a5 , int m , int n)(建立稀疏矩阵的三元组表int i , j , k=0 ;for(i=0 ; im ; i + +)for(j=0 ; j

12、datak . i=i ;b-datak . j=j;b-datak . v=aiQ; k+;)b-m = m ; b-n=n ;b-t=k:找出非零元素记录非零元素行下标记录非零元素列下标保存非零值统计非零元素个数找出非零元素记录非零元素行下标记录非零元素列下标保存非零值统计非零元素个数记录矩阵行列数保存非零个数【分析】对于一个mxn的矩阵M ,它的转置矩阵T是一个nxm的矩阵，而且Mij-Tji (0im , 0jn),即M的行是T的列,M的M=/0 3 0 50 0-2010 0 0g 0 8 006 ojT=03M=/0 3 0 50 0-2010 0 0g 0 8 006 ojT=030data中，这样就可得到T的按行优先的三 元组表。【算法描述】void TransMatrix(TSMatrix a , TSMatrix*b)/a和*b是矩阵M、T的三元组表表示，求稀疏矩阵M的转置Tint p , q , col ;b-m=a.n ; b-n=a.m;换b-t=a.t;if(b-t=0)printf(M中无零元素!。;elseq=0;for(col=0;coldataq.i=a.datap.j ; b-dataq.j=a.datap.i ; b-dataq.v=a.datap.v ;+