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

第二节矩阵的压缩存储一、特殊矩阵特殊矩阵：是相同值的元素或者零元素在矩阵中的分布有一定规律的矩阵。1、对称矩阵若n阶方阵A中的元素满足下述性质：aij=aji

(0≤i，j≤n-1)则称A为n阶的对称矩阵。对于一个n阶对称矩阵，可只存储其下三角矩阵：将元素压缩存储到1+2+3+…+n=n（n＋1）/2个元素的存储空间中，假设以一维数组sa[n（n＋1）/2]作为n阶对称矩阵A的存储结构，以行序为主序存储其下三角（包括对角线）中的元素，数组M[k]和aij的对应关系：真题选解（例题·单选题）设有一个10阶的对称矩阵A，采用行优先压缩存储方式，a11为第一个元素，其存储地址为1，每个元素占一个字节空间，则a85的地址为()A．13B．18C．33D．40隐藏答案【答案】C【解析】a11为第一个元素，a85是第（1+2+3+4+5+6+7）+5=33个元素，则a85的地址为1+（33-1）*1=33。注意不要死记硬背公式。（例题·算法设计题）已知A和B是两个n×n阶的对称矩阵，因为是对称矩阵，所以仅需要输入下三角元素值存入一维数组。试写一算法，求对称矩阵A和B的乘积。隐藏答案【分析】对称矩阵的第i行和第j列的元素数据在一维数组中的位置：L=i(i+1)／2+j当i≥j时Aij，Bij处在下三角中)；L=j(j+1)／2+i当i<j时(Aij，Bij处在上三角中)；L代表Aij或Bij在对称矩阵存储的一维中的位置，而且0≤L<n(n+1)/2【算法描述】voidmatrlxmult(inta[]，intb[]，intc[][20]，intn){//n为A、B矩阵下三角元素个数，a，b分别为一维数组，//存放矩阵A和B的下三角元素值，c存放A和B的乘积for(i=0;i<20;i++)for(j=O;j<20；j++){s=0;for(k=0；k<n；k++){if(i>=k)//表示元素为下三角的元素，计算在a数组中的下标L1=i*(i+1)／2+k；else//表示元素为上三角的元素，计算下标L1=k*(k+1)／2+i;if(k>=j)//表示元素为下三角的元素，计算在b数组中的下标L2=k*(k+1)／2+j；e1seL2=j*(j+1)／2+k；s=s+a[L1]*b[L2]；//计算矩阵成绩}c[i][j]=s；}}2．三角矩阵下三角矩阵的主对角线上方均为常数c或零；上三角矩阵是指矩阵的下三角(不包括对角线)中的元素均为常数c或是零的n阶方阵。一般情况下，三角矩阵的常数c均为零。三角矩阵可压缩存储到数组M[n（n+1）/2+1]中。上三角矩阵中，主对角线上的第i行有n-i+1个元素，以行序为主序存放，M[k]和aij的对应关系是：下三角矩阵中，以行序为主序存放，与对称矩阵类是，M[k]和aij的对应关系是：真题选解（例题·填空题）1、假设一个10阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，若矩阵中的第一个元素a11在B中的存储位置k=0，则元素a55在B中的存储位置k=__________。隐藏答案【答案】34【解析】元素a55的前面存储了4行，每行存储的元素个数分别为：10、9、8、7，元素a55存储在第5行要存储的第1个元素，所以a55在B中的存储位置k=0+[(10+9+8+7)+1-1]=34二、稀疏矩阵1、稀疏矩阵的定义含有大量的零元素且零元素分布没有规律矩阵称为稀疏矩阵。2、三元组表（1）三元组表的含义：一个稀疏矩阵可用一个三元组线性表表示，每个三元组元素对应稀疏矩阵中的一个非零元素，包含有该元素的行号、列号和元素值。每个三元组元素在线性表中是按照行号值的升序为主序、列号值的升序为辅序（即行号值相同再按列号值顺序）排列的。【例】画出下列稀疏矩阵对应的三元组表【解析】根据前面三元组的含义很容易画出该矩阵的三元组表。【答案】（2）三元组表的类型定义#defineMaxsize1000//假设非零元素个数的最大为1000个typedefstruct｛inti，j；//非零元素的行号、列号(下标)DataTypev；//非零元素值}TriTupleNode；typedefstruct{TriTupleNodedata[Maxsize]；//存储三元组的数组intm，n，t;//矩阵的行数、列数和非零元素个数}TSMatrix；//稀疏矩阵类型【例】试写一个算法，建立顺序存储稀疏矩阵的三元组表。【分析】假设A为一个稀疏矩阵，其数据存储在二维数组a中，b为一个存放对应于A矩阵生成的三元组表。在这个算法中，要进行二重循环来判断每个矩阵元素是否为零，若不为零，则将其行、列下标及其值存入b中。【算法描述】voidCreateTriTable(TSMatrix*b，inta[][5]，intm，intn){//建立稀疏矩阵的三元组表inti，j，k=0；for(i=0；i<m；i++)for(j=0；j<n；j++)if(a[i][j]!=0)//找出非零元素{b->data[k]．i=i；//记录非零元素行下标b->data[k]．j=j;//记录非零元素列下标b->data[k]．v=a[i][j]；//保存非零值k++;//统计非零元素个数}b->m=m；b->n=n；//记录矩阵行列数b->t=k：//保存非零个数}【例】试写一个算法，实现以三元组表结构存储的稀疏矩阵的转置运算。【分析】对于一个m×n的矩阵M，它的转置矩阵T是一个n×m的矩阵，而且Mij=Tji

(0≤i<m，0≤j<n)，即M的行是T的列，M的列是T的行。稀疏矩阵M和它的转置矩阵T（1）一般的转置算法【算法思想】对M中的每一列col(0≤col≤a.n-1)从头至尾依次扫描三元组表，找出所有列号等col的那些三元组，并将它们的行号和列号互换后再依次存入b->data中，这样就可得到T的按行优先的三元组表。【算法描述】voidTransMatrix(TSMatrixa，TSMatrix*b){//a和*b是矩阵M、T的三元组表表示，求稀疏矩阵M的转置Tintp，q，col；b->m=a.n；b->n=a.m;//M和T行列数互换b->t=a.t；//赋值非零元素个数if(b->t<=0)printf("M中无非零元素!")；e1se{q=0;for(col=0;col<a.n;++col)for(p=0；p<a.t；++p)//扫描M的三元组表if(a.data[p].j==col)//找与col相等的三元组{b->data[q].i=a.data[p].j；b->data[q].j=a.data[p].i；b->data[q].v=a.data[p].v；++q;}}}【算法分析】该算法的时间复杂度为O(n×t)，即与稀疏矩阵M的列数和非零元素个数的乘积成正比。一般的矩阵转置算法的时间复杂度为O(m×n)。该算法仅适用于非零元素个数t远远小于矩阵元素个数m×n的情况。（2）快速转置算法【算法思想】创建两个数组num和rownext。num[j]存放矩阵第j列上非零元素个数，rownext[i]代表转置矩阵第i行的下一个非零元素在b中的位置。【算法描述】voidFaStTran(TSMatfixa，TSMatrix*b){intcol，p，t，q;int*num，*rownext;num=(int*)calloc(a.n+1，4);//分配n+1个长度为4的连续空间rownext=(int*)calloc(a.m+1，4)；//分配m+1个长度为4的连续空间b->m=a.n；b->n=a.m;b->t=a.t;if(b->t){for(col=0；col<a.n；++col)num[col]=0;//初始化for(t=0；t<a.t；++t)++num[a.data[t].j];//计算每列非零元素数rownext[0]=0；for(col=1;col<a.n;++col)//给出b中每一行的起始点rownext[col]=rownext[col-1]+num[col-1]；for(p=0；p<a.t;++p)//执行转置操作{col=a.data[p].j；q=rownext[col]；b->data[q].i=a．data[p].j；b->data[q].j=a．data[p].i；b->data[q].v=a．data[p].v；++rownext[col]；//下一次再有该行元素，起始点就比上一个加了1}}}【算法分析】算法的时间复杂度为O(t)3、带行表的三元组表带行表的三元组表：又称为行逻辑链接的顺序表。在按行优先存储的三元组表中，增加一个存储每一行的第一个非零元素在三元组表中位置的数组。【类型描述】typedefstruct{TriTupleNodedata[MaxSize]；intRowTab[MaxRow];//每行第一个非零元素的位置表intm，n，t；}RLSMatrix；带行表的三元组表的特点：①对于任给行号i(0≤i≤m-1)，能迅速地确定该行的第一个非零元在三元组表中的存储位置为RowTab[i]②RowTab[i](0≤i≤m-1)表示第i行之前的所有行的非零元数。③第i行上的非零元数目为RowTab[i+1]-RowT