6.稀疏矩阵
6.1定义&存储方式
稀疏矩阵：具有较多的零元素，且非零元素的分布无规律的矩阵。
稀疏因子：用于确定稀疏矩阵个数指标
常见的2种存放方式：三元组表存储、十字链表存储
6.2相关类及其操作
6.2.1概述
- 使用三元组唯一的标识一个非零元素
- 三元组组成：row行、column列、value值
- 三元组表：用于存放稀疏矩阵中的所有元素。
6.2.2相关类及其操作
三元组结点类
public class TripleNode { //三结点 public int row; //行号 public int column; //列号 public int value; //元素值 }
三元组顺序表类
public class SparseMatrix { //稀疏矩阵 public TripleNode[] data; //三元组表 public int rows; //行数n public int cols; //列数m public int nums; //非零元素的个数 }
三元组表初始化操作
6.3三元组表存储：矩阵转置
6.3.1定义
矩阵转置：一种简单的矩阵运算，将矩阵中每个元素的行列序号互换。
特点：矩阵N[m×n] 通过转置 矩阵M[n×m]
转置原则：转置前从左往右查看每一列的数据，转置后就是一行一行的数据。
6.3.2算法分析
6.3.3算法：转置
/** this转置前的对象，每一个对象中都有一个data数据 * tm 转置后的对象，每一个对象中都有一个data数据 * return 转置后的稀疏矩阵对象 */ public SparseMatrix transpose() { //转置 // 1 根据元素个数，创建稀疏矩阵 SparseMatrix tm = new SparseMatrix(nums); // 2 设置基本信息 tm.cols = rows; //2.1 行列交换 tm.rows = cols; //2.2 列行交换 tm.nums = nums; //2.3 元素个数 // 3 进行转置 int q = 0; //3.1 转置后数据的索引 for(int col = 0 ; col < cols; col ++) { //3.2 转置之前数据数组的每一个列号 for(int p = 0; p < nums; p ++) { //3.3 依次获得转置前数据数组的每一个数据 if (data[p].column == col) { //3.4 获得指定列的数据 tm.data[q].row = data[p].column; //3.5 行列交换，值不变 tm.data[q].column = data[p].row; tm.data[q].value = data[p].value; q++; //3.6 转置后的指针后移 } } } // 4 返回转置后的稀疏矩阵 return tm; }
矩阵转置时间复杂度：O(n×t) ，n列数，t非零个数
6.4三元组表存储：快速矩阵转置
6.4.1定义
假设：原稀疏矩阵为N、其三元组顺序表为TN，N的转置矩阵为M，其对应的三元组顺序表为TM。
快速转置算法：求出N的每一列的第一个非零元素在转置后的TM中的行号，然后扫描转置前的TN，把该列上的元素依次存放于TM的相应位置上。
基本思想：分析原稀疏矩阵的数据,得到与转置后数据关系
每一列第一个元素位置：上一列第一个元素的位置 + 上一列非零元素的个数
当前列，原第一个位置如果已经处理，第二个将更新成新的第一个位置。
6.4.2公式
- 需要提供两个数组：num[]、cpot[]
- num[] 表示N中第col列的非零元素个数
- cpot[] 初始值表示N中的第col列的第一个非零元素在TM中的位置
- 公式：
6.4.3算法：快速转置
public SparseMatrix fasttranspose() { // 1 根据元素个数，创建稀疏矩阵 SparseMatrix tm = new SparseMatrix(nums); // 2 设置基本信息 tm.cols = rows; //2.1 行列交换 tm.rows = cols; //2.2 列行交换 tm.nums = nums; //2.3 元素个数 // 3 校验 if(num <= 0) { return tm; } // 4 每一列的非零个数 int num = new int[cols]; //4.1 根据列数创建num数组 for(int i = 0; i<cols; i ++) { //4.2 初始数据（可省略） num[i] = 0; } for(int i = 0; i< nums; i ++) { //4.3 遍历转置的数据 int j = data[i].column; num[j]++; } // 5 转置后每一列第一个元素的位置数组 int cpot = new int[cols]; // 5.1 位置的数组 cpot[0] = 0; // 5.2 第一列第一个元素为0 for(int i = 1; i < cols ; i ++) { cpot[i] = cpot[i-1] + num[i-1]; // 5.3 当前列第一个元素位置 = 上一列位置+个数 } // 6 转置处理 for(int i = 0 ; i < nums ; i ++) { int j = data[i].column; //6.1 转置前，每一个元素的列数 int k = cpot[j]; //6.2 转置后的位置 tm.data[k].row = data[i].column; //6.3 原数据 转置后 数据 tm.data[k].column = data[i].row; tm.data[k].value = data[i].value; cpot[j]++; //6.4 下一个元素的位置 } }
时间复杂度：O(n+t) ，n列数，t非零个数
6.5十字链表存储
6.5.1定义
当稀疏矩阵中非零元素的位置或个数经常发生变化时，不宜采用三元组顺序表存储结构，而该用链式存储结构。
十字链表结点由5个域组成：
row：所在行
column：所在列
value：非零元素值
right：存放与该非零元素==同行==的下一个非零元素结点指针。
down：存放与该非零元素==同列==的下一个非零元素结点指针。
6.5.2相关类
结点类：
class OLNode { public int row, col; //行号、列号 public int value; //元素值 public OLNode right; //行链表指针 public OLNode down; //列链表指针 }
十字链表类：
class CrossList { public int mu, nu, tu; //行数、列数、非零元素个数 public OLNode[] rhead, chead; //行、列指针数组 }
