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();
        }

    }
}