本文介绍对称矩阵、三角矩阵、对角矩阵和稀疏矩阵的压缩存储方法。
对称矩阵
在一个n阶矩阵A中，若元素满足aij=aji,0<=i,j<=n-1，则称矩阵A为对称矩阵。
按行优先顺序将这些元素存放在一个一维数组s[n(n+1)/2]中，元素aij在s中对应的下标为k：
三角矩阵
以主对角线划分，三角矩阵分为上三角和下三角两种，上三角矩阵的下三角所有元素均为常数c，下三角矩阵正好相反。
按行优先顺序将三角矩阵存放在一维数组s[n(n+1)/2+1]，其中常数c存放在数组的最后一个分量中。
上三角矩阵元素aij在s中对应的下标为k：
下三角矩阵元素aij在s中对应的下标为k：
对角矩阵
对角矩阵是指矩阵中所有的非零元素集中在以主对角线为中心的带状区域中。一个k对角矩阵（k为奇数）A满足若|i-j|>(k-1)/2则元素aij=0。
将三对角矩阵A中的非零元素按行优先顺序存放到数组s[3n-2]中，在三对角矩阵A中，除第一行和最后一行只有两个非零元素外，其他每行中均有三个非零元素。三对角矩阵中的元素aij在s中对应的下标为k=3×i-1+j-(i-1)=2×i+j.
稀疏矩阵
设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数，即s<<mxn，则称A为稀疏矩阵。
对于稀疏矩阵的压缩存储方法通常有两种，分别是三元组顺序表和十字链表。
1. 三元组顺序表
每个元素是一个结构体，包括该元素在矩阵中的行数、列数和数值，所有元素存在一个向量vector中，并同时记录矩阵的行数、列数及非零元素个数等信息。
2. 十字链表
为了克服顺序表中对非零元素插入和删除操作带来的不便，采用链接存储结构存储稀疏矩阵。
十字链表将每个元素存储为一个结构体，除了包括元素的行号、列号、数值外，还包括一个向右指针域用于指向同一行中的下一个非零元素和一个向下指针域用于指向同一列中的下一个非零元素。所有结构体通过两个一维指针数组分别存储各个行链表的头指针和各个列链表的头指针组织成一个整体。
三元组顺序表中矩阵的转置
目标是将每个元素的行号列号交换，并按照新的行列号按序存放。关键在于如何高效地进行按序存放。
方法一：朴素转置算法
按照原列号分别从头至尾扫描，依次放入新的矩阵中。对于一个m行n列且非零元素个数为t的稀疏矩阵而言，该算法的时间复杂度为O(t×n)。
方法二：快速转置算法
采用一个数组cnum[cols]记录每一列中的元素个数，一个数组cpot[cols]记录每一列的第一个非零元素在转置矩阵顺序表中的下标。cnum和cpot各采用一次遍历得到，其中cpot[0]=0，cpot[col]=cpot[col-1]+cnum[col-1]。
网友评论