JAVA算法数据结构第一节稀疏矩阵

一、稀疏矩阵介绍：

稀疏矩阵是一种特殊类型的矩阵，其中大部分元素都是零。在处理这类矩阵时，如果仍然使用标准的矩阵存储方式（即传统的二维数组），则会浪费大量的存储空间来保存零值。为了提高存储效率以及在某些情况下提高计算效率，人们发明了稀疏矩阵的概念及其相应的存储方法。

稀疏矩阵的特点

• 高零值比例：矩阵中的零元素远多于非零元素。
• 节省空间：只存储非零元素，减少不必要的内存占用。
• 优化运算：在进行矩阵运算时，可以跳过与零相关的计算，从而加快计算速度。

二、稀疏矩阵代码实现：

1）原始二维代码： 

  //创建一个原始的二维数组9*9//0：表示没有棋子，1：表示黑子，2：表示白子int[][] ints = new int[9][9];ints[1][2]=1;ints[2][4]=2;//输出原始二维数组for (int[] row:ints){for (int data:row){System.out.print(data+"\t");}System.out.println();}

输出结果：

 

创建如图9*9的二维矩阵。

2）、将二维矩阵转化成稀疏矩阵：

  //创建对应稀疏矩阵int[][] xishu = new int[sum + 1][3];//给稀疏矩阵赋值xishu[0][0]=9;xishu[0][1]=9;xishu[0][2]=sum;//遍历二维数组，将非零值存放到xishu中int count=0;//用于记录是第几个非零数据for (int i=0;i<9;i++){for (int j=0;j<9;j++){if (ints[i][j]!=0){count++;xishu[count][0]=i;xishu[count][1]=j;xishu[count][2]=ints[i][j];}}}//输出稀疏数组的形式System.out.println("----------稀疏数组为---------");for (int i=0;i < xishu.length;i++){System.out.println(xishu[i][0]+"  "+xishu[i][1]+"  "+xishu[i][2]);}

输出结果：

 

3）、将稀疏矩阵转化为 二维矩阵：

   //读取稀疏数组第一行，根据第一行创建原始的二维数组int[][] huifus = new int[xishu[0][0]][xishu[0][1]];//读取稀疏数组后几行的数据并赋给原始二维数组即可//这里是要遍历稀疏矩阵的值而不是恢复矩阵for (int k=1;k< xishu.length;k++){huifus[xishu[k][0]][xishu[k][1]]=xishu[k][2];}System.out.println("---------恢复的二维矩阵-------");for (int[] row:huifus){for (int data:row){System.out.print(data+"\t");}System.out.println();}

输出结果：

 

三、完整代码：

//TIP 要<b>运行</b>代码，请按 <shortcut actionId="Run"/> 或
// 点击装订区域中的 <icon src="AllIcons.Actions.Execute"/> 图标。
public class Main {public static void main(String[] args) {//创建一个原始的二维数组9*9//0：表示没有棋子，1：表示黑子，2：表示白子int[][] ints = new int[9][9];ints[1][2]=1;ints[2][4]=2;//输出原始二维数组for (int[] row:ints){for (int data:row){System.out.print(data+"\t");}System.out.println();}
//将二维数组 转 稀疏数组的思想//1.先遍历二维数组 得到非零数据的个数int sum=0;for (int i=0;i<9;i++){for (int j=0;j<9;j++){if (ints[i][j]!=0){sum++;}}}//创建对应稀疏矩阵int[][] xishu = new int[sum + 1][3];//给稀疏矩阵赋值xishu[0][0]=9;xishu[0][1]=9;xishu[0][2]=sum;//遍历二维数组，将非零值存放到xishu中int count=0;//用于记录是第几个非零数据for (int i=0;i<9;i++){for (int j=0;j<9;j++){if (ints[i][j]!=0){count++;xishu[count][0]=i;xishu[count][1]=j;xishu[count][2]=ints[i][j];}}}//输出稀疏数组的形式System.out.println("----------稀疏数组为---------");for (int i=0;i < xishu.length;i++){System.out.println(xishu[i][0]+"  "+xishu[i][1]+"  "+xishu[i][2]);}//读取稀疏数组第一行，根据第一行创建原始的二维数组int[][] huifus = new int[xishu[0][0]][xishu[0][1]];//读取稀疏数组后几行的数据并赋给原始二维数组即可//这里是要遍历稀疏矩阵的值而不是恢复矩阵for (int k=1;k< xishu.length;k++){huifus[xishu[k][0]][xishu[k][1]]=xishu[k][2];}System.out.println("---------恢复的二维矩阵-------");for (int[] row:huifus){for (int data:row){System.out.print(data+"\t");}System.out.println();}}
}