特殊矩阵的压缩存储（数组下标从0开始存储）

用一维数组压缩存储对称矩阵

对称矩阵的特点：

a[i][j] = a[j][i]

a[i][j] 是 第 i+1 行、第 j+1列 的元素

如何压缩存储？

只存储下三角部分的元素

从a[0][0] 开始，把每行元素都依次存储进一维数组

存储时：a[i][j] 在一维数组 A[ ]中的下标就是该元素前面元素的个数：
k= i×(i+1)/2+ j

输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值

对于下三角中的元素：a[i][j]在数组A[ ]中的下标k与i、j的关系为：k＝i×(i＋1)/2＋j

对于上三角中的元素：访问和它对应的元素a[j][i]即可 k＝j×(j＋1)/2＋i

运行结果

下三角矩阵

如何压缩存储？

存储下三角部分的元素和一个常数

输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值

i>=j 时：a[ i ][ j ]对应下三角的元素，包括对角线

i < j 时：a[ i ][ j ]对应上三角的元素

运行结果

上三角矩阵

如何压缩存储？

存储上三角部分的元素和一个常数

输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值

i>=j 时：a[ i ][ j ]对应下三角的元素，包括对角线

i < j 时：a[ i ][ j ]对应上三角的元素

运行结果

对角矩阵

所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零：

如何压缩存储？

元素a[ i ][ j ] 在一维数组中的下标 k=2+（i-1）*3+j-i+1= 2i+ j

输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值

i>=j 时：a[ i ][ j ]对应下三角的元素，包括对角线

i < j 时：a[ i ][ j ]对应上三角的元素

运行结果

用三元组顺序表存储稀疏矩阵

当矩阵中只有极少的非零元素，而且分布也不规律，如果非零元素个数只占矩阵元素总数的25%~30%或低于这个百分数时，这样的矩阵称为稀疏矩阵。

如何压缩存储？

将稀疏矩阵中的每个非零元素表示为：三元组——(行号，列号，非零元素值)
三元组顺序表——以顺序存储结构表示三元组表，是稀疏矩阵的一种压缩存储方式：

三元组顺序表操作——用三元组顺序表 实现稀疏矩阵的转置操作

方法一

简单的一种办法是直接交换原三元组顺序表中行号和列号并存在一个新的三元组顺序表中，

但顺序表要求按行排好序确定对一个的矩阵唯一，所以在交换的时候要先找到所有列号为0的元素，

再找到所有列号为1的......直到结束，但是这种办法一次又一次地遍历三元组顺序表，查找每列所有的元素都要遍历一次，

那么转置一个三元组顺序表需要遍历 列数*非零元素个数 次的三元组顺序表，效率较低。

方法二

原顺序表的存储是有序且按行排列的，现在可以利用这一特性，对被转置矩阵的三元组表只扫描一次，使得所有的非零元素一次性存放到转置后的三元组表中：

原表中A中第0列共有元素（0,0）和（4,0）两个，所以转置后的新表B中第0行应该有2个元素（0,0）（0,4）

那么B中第1行的第一个元素的位置应该是在B表的第2位上：0+2=2

即B表中：第 i 列的第一个非零元素的位置 = 第 i-1 列的第一个非零元素的位置 + 第 i-1 列的非零元素的个数

cpot[col] = cpot[col-1] + cnum[col-1]

右边的表格可以确定下面这个顺序表：

很明显，由新加入的两个数组可以确定每一行的第一个元素要插入的位置。

运行结果

用三元组顺序表实现稀疏矩阵的相加、相减