你知道稀疏矩阵吗？
🌲🌲🌲定义&存储方式
🎃🎃🎃🎃稀疏矩阵：具有较多的零元素，且非零元素的分布无规律的矩阵。
❤️ 💚 💙 稀疏因子：用于确定稀疏矩阵个数指标。
🎃🎃🎃🎃 常见的2种存放方式：三元组表存储、十字链表存储。
🌲🌲🌲 三元组表存储
🐋🐋🐋🐋 概述
❤️ 💚 💙 使用三元组唯一标识一个非零元素。
❤️ 💚 💙 三元组组成：row行、column列、value值。
❤️ 💚 💙 三元组表：用于存放稀疏矩阵中的所有元素。
🐋🐋🐋🐋 相关类及其操作
🍀🍀🍀🍀三元组结点类 ：
public class TripleNode { //三结点 public int row; //行号 public int column; //列号 public int value; //元素值 }
🍀🍀🍀🍀三元组顺序表类 ：
// 稀疏矩阵三元组·顺序表类定义 public class SparseMatrix { public TripleNode data[] ; //三元组表 public int rows ; //行数 public int cols ; //列数 public int nums ; //非零元素的个数 //构造方法 public SparseMatrix(int maxSize) { //为顺序表分配maxSize个存储单元 data = new TripleNode[maxSize] ; for (int i = 0; i < data.length; i++) { data[i] = new TripleNode(); } rows = 0 ; cols = 0 ; nums = 0 ; } //打印输出稀疏矩阵 public void printMatrix () { System.out.println("稀疏矩阵的三元组存储结构："); System.out.println("行数："+rows+"，列数："+cols+"，非零元素个数："+nums); System.out.println("行下标 列下标 元素值"); for (int i = 0; i < nums; i++) { System.out.println(data[i].row+"\t"+data[i].column+"\t"+data[i].value); } }
🍀🍀🍀🍀三元组表初始化操作：
//从一个稀疏矩阵创建三元组表，mat我稀疏矩阵 public SparseMatrix(int mat[][]) { int i ,j , k=0, count = 0 ; rows = mat.length ; //行数 cols = mat[0].length; //列数 //统计非零元素的个数 for ( i = 0; i < mat.length; i++) { for ( j = 0; j < mat[i].length; j++) { if (mat[i][j] != 0 ){ count++ ; } } } nums = count ; //非零元素的个数 data = new TripleNode[nums]; //申请三元组结点空间 for ( i = 0; i < mat.length; i++) { for ( j = 0; j < mat[i].length; j++) { if (mat[i][j] != 0 ){ data[k] = new TripleNode(i,j,mat[i][j]); //建立三元组 k++ ; } } } }
🌲🌲🌲 三元组表存储：矩阵转置
🎃🎃🎃🎃 定义 ：
❄️❄️❄️ 矩阵转置：一种简单的矩阵运算，将矩阵中每个元素的行列序号互换。
❤️ 💚 💙 特点：矩阵N[m×n] 通过转置 矩阵M[n×m]
❤️ 💚 💙 转置原则：转置前从左往右查看每一列的数据，转置后就是一行一行的数据。
🎃🎃🎃🎃 算法分析：
🎃🎃🎃🎃 算法：转置
/** 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非零个数。
🌲🌲🌲 三元组表存储：快速矩阵转置
🐋🐋🐋🐋定义 ：
🎃🎃🎃 假设：原稀疏矩阵为N、其三元组顺序表为TN，N的转置矩阵为M，其对应的三元组顺序表为TM。
🎃🎃🎃 快速转置算法：求出N的每一列的第一个非零元素，在转置后的TM中的行号，然后扫描转置前的三元组顺序表TN，把该列上的元素依次存放于TM的相应位置上。
🎃🎃🎃 基本思想：分析原稀疏矩阵的数据,得到与转置后数据关系：
❤️ 💚💙 每一列第一个元素位置：上一列第一个元素的位置 + 上一列非零元素的个数
❤️ 💚💙 当前列，原第一个位置如果已经处理，第二个将更新+1成新的第一个位置。
🐋🐋🐋🐋公式：
🎃🎃🎃 需要提供两个数组：num[]、cpot[]
❤️ 💚💙 num[] ：表示原稀疏矩阵N中第col[]列的非零元素个数
❤️ 💚💙 cpot[] ：初始值表示原稀疏矩阵N中的第col[]列的第一个非零元素在TM中的位置
🎃🎃🎃 公式：
🐋🐋🐋🐋算法：快速转置
//矩阵快速转置算法 public SparseMatrix fasttranspose () { // 1 根据元素个数，创建稀疏矩阵 SparseMatrix tm = new SparseMatrix(nums); tm.cols = rows ; //行数变列数 tm.rows = cols ; //列数变行数 tm.nums = nums ; //非零元素个数不变 //校验 if (nums <= 0 ){ return tm ; } //每一列的非零个数 int[] num = new int[cols] ; //根据列数创建num数组 for (int i = 0; i < cols; i++) { num[i] = 0 ; //初始化数据（可省略） } for (int i = 0; i < nums; i++) { //变量转置的数据 int j = data[i].column ; num[j] ++ ; } //转置后每一列第一个元素的位置数组 int[] cpot = new int[cols]; //位置数组 cpot[0] = 0 ; //第一列的第一个元素为0 for (int i = 1; i < cols; i++) { cpot[i] = cpot[i-1] + num[i-1] ; //当前列第一个元素位置 = 上一列元素位置 + 上一列非零元素个数 } //转置处理 for (int i = 0; i < nums; i++) { int j = data[i].column ; //转置前，每一个元素的列数 int k = cpot[j]; //转置后的位置 tm.data[k].row = data[i].column ; //原数据转置后数据 tm.data[k].column = data[i].row; tm.data[k].value = data[i].value; cpot[j]++ ; //下一个元素的位置 } return tm; }
时间复杂度：O(n+t) ，n列数，t非零个数
🌲🌲🌲 十字链表存储
🐋🐋🐋🐋定义：
🎃🎃🎃 当稀疏矩阵中非零元素的位置或个数经常发生变化时，不宜采用三元组顺序表存储结构，而该用链式存储结构。
🎃🎃🎃 十字链表结点由5个域组成：
❤💜 row：所在行
❤💚 column：所在列
❤❤️ value：非零元素值
❤💜 right：存放与该非零元素==同行==的下一个非零元素结点指针。
❤💚 down：存放与该非零元素==同列==的下一个非零元素结点指针。
🐋🐋🐋🐋 相关类 ：
❤💚 结点类：
package data.strings_arrays.arrays; //十字链接结点类 public class OLNode { public int row,col ; //元素的行号和列号 public int e ; //元素值 public OLNode right ; // 行链表指针 public OLNode down ; //列链表指针 //无参构造 public OLNode() { } //有参构造 public OLNode(int row, int col, int e, OLNode right, OLNode down) { this.row = row; this.col = col; this.e = e; this.right = right; this.down = down; } }
❤❤️十字链表类定义初始化：
package data.strings_arrays.arrays; //稀疏矩阵的十字链表类定义: public class CrossList { public int mu, nu, tu; //行数、列数、非零元素个数 public OLNode[] rhead, chead; //行、列指针数组 //构造方法，初始化 public CrossList (int m ,int n ) { mu = m ; nu = n ; rhead = new OLNode[m] ; //初始化行指针数组 chead = new OLNode[n] ; //初始化列指针数组 tu = 0 ; for (int i = 0; i < m; i++) { rhead[i] = new OLNode(); } for (int i = 0; i < n; i++) { chead[i] = new OLNode(); } } }
