特殊矩阵的压缩存储

矩阵：一个由m×n个元素排成的m行n列的表
矩阵的常规存储：将矩阵描述为一个二维数组
矩阵的常规存储的特点：
（1）可以对其元素进行随机存储
（2）矩阵运算非常简单，存储的密度为1
不适宜常规存储的矩阵：值相同的元素很多且呈某种规律分布，零元素多
矩阵的压缩存储：为多个相同的非零元素只分配一个存储空间，对零元素不分配空间，如对称矩阵、对角矩阵、三角矩阵、稀疏矩阵（矩阵中非零元素的个数较少，一般小于5%）等
（1）对称矩阵
特点：在n×n的矩阵a中，满足aij=aji（1≤i，j≤n）
存储方法：只存储下（或者上）三角（包括主对角线）的数据元素。共占用n(n+1)/2个元素空间
k=i×(i-1)/2+j-1
（2）三角矩阵
特点：对角线以下（或者以上）的数据元素（不包括对角线）全部为常数c
存储方法：重复元素c共享一个元素存储空间，共占用n(n+1)/2+1个元素空间


（3）对角矩阵
特点：在n×n的方阵中，所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵
（4）稀疏矩阵
特点：在m×n的矩阵中有t个非零元素，令δ=t/(m×n),当δ≤0.05时称为稀疏矩阵
顺序存储结构——三元组顺序表
三元组顺序表又称有序的双下标法
优点：非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算
缺点：不能随机存储，若按行号存取某一行中的非零元，则需从头开始进行查找
链式存储结构——十字链表
优点：它能够灵活地插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的各种运算
在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了（row,col,value）以外，还有两个域：
1）right:用于链接同一行中的下一个非零元素
2）down:用以链接同一列中的下一个非零元素
十字链表中结点的结构示意图：