矩阵的基础知识

一、矩阵的定义

•  矩阵：一个由m×n个元素排成的m行n列的表。
• 矩阵的常规存储：将矩阵描述成一个二维数组。
• 矩阵的常规存储的特点：1.可以对其元素进行随机存取 2.矩阵的运算非常简单 3.存储密度为1 
• 矩阵的压缩存储：1.为多个相同的非零元素只分配一个存储空间 2.对零元素不分配空间
• 什么是压缩存储：若多个数据元素的值相同，则只分配一个元素值的存储空间，且零元素不占存储空间
• 什么样的矩阵能够压缩：一些特殊矩阵（比如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等）
• 什么叫稀疏矩阵：矩阵中的非零元素个数较少（一般小于5%） 

二、怎么压缩 

1. 对称矩阵 

• 本身特点：在n×n的矩阵a中，满足如下性质：aij=aji(1<=i,j<=n)
• 存储方法：只存储下（或者上）三角（包括主对角线）的数据元素。共占用n(n+1)/2个元素空间。 
• 存储结构：1.对称矩阵上下三角中的元素均为：n×(n+1)/2可以以行序为主序将元素存放在一维数组a[n×(n + 1) / 2]中。 

可以以行序为主序将元素存放在一维数组a[n×(n + 1) / 2]中。
aij前面有i-1行，前面i-1行一共有1+2+...i-1个元素，也就是(i-1)i/2
    只看第i行，前面有j-1个元素
    所以aij的地址=a11的地址+【(i - 1)i / 2】*sizeof(a11)+(j-1)*sizeof(a11)

 

 

   2. 三角矩阵

 

 

• 本身特点：对角线以下（或者以上）的数据元素（不包括对角线）全部为常数c。
• 存储方法：重复元素c共享一个元素存储空间，共占用n(n+1)/2个元素
•  对于上三角：

第一种以行序为主序存储
第1行存放n个元素-----1
第2行存放n-1个元素-----2
...
第i-1行存放n-(i-1-1)=n-i+2个元素-----i-1
第i行存放n-(i-1)=n-i+1个元素
aij前面有i-1行，前面i-1行有n+n-1+.....n-i+2个元素，也就是(i-1)(2n-i+2)/2
   只看第i行，第i行的第一个元素为aii,所以aij前面有j - i个元素
   所以aij的地址 = a11的地址 + 【(i - 1)(2n - i + 2) / 2】 * sizeof(a11) + (j - i) * sizeof(a11)
 
第二种以列序为主序存储
aij前面有j-1列一共有1+2....+j-1个元素，也就是(j-1)j/2
   只看第j列，前面有i-1个元素
    所以aij的地址 = a11的地址 + 【(j - 1)j / 2】 * sizeof(a11) + (i - 1) * sizeof(a11)

•  对于下三角：

以行为主序存储：
aij前面有i - 1行，前面i - 1行一共有1 + 2 + ...i - 1个元素，也就是(i - 1)i / 2
只看第i行，前面有j - 1个元素
所以aij的地址 = a11的地址 + 【(i - 1)i / 2】 * sizeof(a11) + (j - 1) * sizeof(a11)
3.对角矩阵（带状矩阵）
特点：在n×n的方阵中，所有非零元素都集中自爱以主对角线为中心的带状区域，区域外的值全是0，则陈伟对角矩阵。
常见的有三对矩阵，五对角矩阵，七对角矩阵。
存储方法：以对角线的顺序存储

3.对角矩阵（带状矩阵）

• 特点：在n×n的方阵中，所有非零元素都集中自爱以主对角线为中心的带状区域，区域外的值全是0，则陈伟对角矩阵。常见的有三对矩阵，五对角矩阵，七对角矩阵。
• 存储方法：以对角线的顺序存储 

 

  

4.稀疏矩阵

• 设在m×n矩阵中有t个非零元素。令ss=t/(m×n)  当ss<=5%的时候称为稀疏矩阵。
• 三元组（i，j，aij）唯一确定矩阵的一个非零元（i，j分别表示aij的位于第i行，第j列）。
• 压缩原则：存各非零元的值、行列的位置和矩阵的行列数。
• 注意：为更可靠描述，通常再加一个“总体信息”：即总行数，总列数，非零元素总个数。 
• 三元组顺序表又称有序的双下标法。
• 三元组顺序表的优点：非零元在表中按行序有序存储，因此便于进行依次顺序处理的矩阵运算。
• 三元组顺序表的缺点：不能随机存取。若按行号存取某一行的非零元，则需从头开始进行查找。
• 优点：它能够灵活的插入因运算而产生的新的非零元素，删除因运算而产生的新的非零元素，实现矩阵的各种运算。