C++数组应用之特殊矩阵的压缩存储

矩阵：

矩阵是数值程序设计中经常用到的数学模型，它是由 m 行和 n 列的数值构成（m=n 时称为方阵）。在用高级语言编制的程序中，通常用二维 数组表示矩阵，它使矩阵中的每个元素都可在二维数组中找到相对应的存储位置 。然而在数值分析的计算中经常出现一些有下列特性的高阶矩阵，即矩阵中有很 多值相同的元或零值元，为了节省存储空间，需要对它们进行"压缩存储 "，即不存或少存这些值相同的元或零值元。

操作：可以对矩阵作 加、减、乘等运算。

存储压缩目标：

节约存储空间

压缩 的方法：

零元不存储

多个值相同的只存一个

压缩存储的 对象：

稀疏矩阵

特殊矩阵

特殊矩阵：

值相同元素 或者零元素分布有一定规律的矩阵称为特殊矩阵 例：对称矩阵、 上（下）三角 矩阵都是特殊矩阵

特殊矩阵压缩存储（以对称矩阵为例）

对称矩阵是满足下面条 件的n 阶矩阵： aij= aji　 1<= i，j<= n

k= 0　　 1　　　 2　　　　 3　　 4　　　　 5　　　 6　　　　　n（n+1）/2-1

对称矩阵元素可以只存储 下三角部分，共需 n（n+1）/2 个单元的空间（ 三角矩阵的存储方式类似）

以一维数组sa[0……n（n+1）/2-1]作为n 阶对称矩阵A的 存储结构A中任意一元素 aij与它的存储位置 sa[k] 之间关系：

k= 0　　 1　　　 2　　　　 3　　 4　　　　 5　　　 6　　　　　n（n+1）/2-1

例如：a42 在 sa[ ]中的 存储位置是：

k=4*（4+1）/2+2=12

sa[12]= a42

带状矩阵 所有非0元素都集中在以主对角线为中心的带状区域，半带宽为d时， 非0元素有 （2d+1）*n-（1+d）*d个（左上角与右下角补上0后，最后必须减掉），如下图 怕示：

为计算方便，认为每一行都有2d+1个非0元素，若少则0补足存放矩阵 的数组sa[ ]有：n（2d+1）个元素数组，元素sa[k]与矩阵元素aij 之间有关系 ：

k=i*（2d+1）+d+（j-i）（第一项i*（2d+1）表示前i行一共有几个元 素，d+（j-i）这一项是用来确定第i行中，第j列前有几个元素，以i=j时，这时 j-i=0，这个作为“分水岭”，左右两边的元素分别加上偏移量d.）

本例：d=1

K= 0　　　 1　　　　　　　　 2　　　　　　　 3　　　　　 4　　　 5　　　　 6　　　　　　　　　　 7　　　 8　　　　 　 9　　　　　 10　　 11　　　 12　　　 13　　　　　 14

（a0前以及a14处放一个0是用来表示在矩阵的左上角及右下角补上的0 ）

稀疏矩阵：

行数m = 6， 列数n = 7， 非零元素个数t = 6稀疏矩阵 （SparseMatrix）的抽象数据类型

　template <class Type>
　class SparseMatrix ...{
　　　　　 int Rows, Cols, Terms;　//行/列/非零元素数
　　　　　 Trituple<Type> smArray[MaxTerms];
　public:　//三元组表
　　　　　 SparseMatrix ( int MaxRow, int Maxcol );
　　　　　 SparseMatrix<Type> Transpose ( );　//转置
　　　　　 SparseMatrix<Type>　//相加
　　　　　　　　　　　　　　 Add ( SparseMatrix<Type> b );
　　　　　 SparseMatrix<Type>　//相乘
　　　　　　　　　　　 Multiply ( SparseMatrix<Type> b );
　}

A的三元组顺序表图示

三元组 （Trituple） 类的定义

　template<class Type> class SparseMatrix<Type>;
template<class Type>
　class Trituple ...{
　friend class SparseMatrix <Type>
　private:
　　　　　 int row, col;　//非零元素所在行号/列号
　　　　　 Type value;　//非零元素的值
　}

稀疏矩阵

转置矩阵

用三元组表表示的稀疏矩阵及其转置：

a.smArray　　　　　　　　　　　　　　　　　　　　　　　 　b.smArray

（a.Rows=6,a.Cols=7,a.Terms=8 ）

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!