算法与数据结构之稀疏矩阵

稀疏 sparsearray 数组

1. 实际的需求：
   • 五子棋程序中，有存盘退出和续上盘的功能
   • 因为该二维数组的很多值是默认值 0, 因此记录了很多没有意义的数据.->稀疏数组.
   • 当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组
2. 基本介绍之稀疏数组的处理方法是：
   • 记录数组一共有几行几列，有多少个不同的值
   • 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
3. 应用实例:
   • 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
   • 把稀疏数组存盘，并且可以从新恢复原来的二维数组数

整体思路分析

java代码实现

package com.atguigu.sparsearray;

public class SparseArray {

    public static void main(String[] args) {
    int chessArr1[][]=new int[11][11];
    chessArr1[1][2]=1;
    chessArr1[2][3]=2;
    System.out.println("原始的二维数组");
    for (int[] row : chessArr1) {
        for (int data : row) {
            System.out.printf("%d\t",data);
        }
        System.out.println();
    }
    System.out.println("二维数组转化为稀疏数组");
    int sum=0;
    for (int i = 0; i < 11; i++) {
        for (int j = 0; j < 11; j++) {
            if (chessArr1[i][j]!=0) {
                sum++;
            }
        }
    }
    System.out.println("非零元素的个数："+sum);
    int sparseArr[][]=new int[sum+1][3];
    sparseArr[0][0]=11;
    sparseArr[0][1]=11;
    sparseArr[0][2]=sum;
    
    int count=0;
    
    for (int i = 0; i < 11; i++) {
        for (int j = 0; j < 11; j++) {
            if (chessArr1[i][j]!=0) {
                count++;
                sparseArr[count][0]=i;
                sparseArr[count][1]=j;
                sparseArr[count][2]=chessArr1[i][j];
                
            }
        }
    }
    System.out.println("得到的稀疏数组");
    for (int i = 0; i < sparseArr.length; i++) {
        System.out.printf("%d\t%d\t%d\t\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
    }
    System.out.println();
    System.out.println("稀疏数组恢复为二维数组");
    
    int chessArr2[][] =new int[sparseArr[0][0]][sparseArr[0][1]];
    for (int i = 1; i <sparseArr.length; i++) {
        chessArr2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];
    }
    System.out.println();
    
    System.out.println("恢复后的二维数组");
//    for (int[] row : chessArr2) {
//        for (int data : row) {
//            System.out.printf("%d\t",data);
//        }
//        System.out.println();
//    }
    for (int i = 0; i < chessArr2.length; i++) {
        for (int j = 0; j < chessArr2.length; j++) {
            System.out.printf("%d\t",chessArr2[i][j]);
        }
        System.out.println();
    }
    }
}

scala代码实现

package com.atguigu.sparseArr

import scala.collection.mutable.ArrayBuffer
/**
  * @author shkstart
  * @create 2022-03-11 17:35
  */
object SparseArr {
  def main(args: Array[String]): Unit = {
    val rowSize=11
    val colSize=11
val chessMap: Array[Array[Int]] = Array.ofDim[Int](rowSize,colSize)
    chessMap(1)(2)=1 //1代表黑子
    chessMap(2)(3)=2 // 2 表示白子
    //输出原始的地图
    for(item <- chessMap){
      for(item2 <- item){
        printf("%d\t",item2)
      }
      println()
    }
    //将 chessmap 转成稀疏数组
    // 思路 =》 效果是达到对数据的压缩
    // class Node (row, col, value)
    // ArrayBuffer

val sparseArr: ArrayBuffer[Node] = ArrayBuffer[Node]()
    val node = new Node(rowSize, colSize, 0)
    sparseArr.append(node)

    for(i<-0 until chessMap.length){
      for(j<-0 until chessMap(i).length){
        if(chessMap(i)(j)!=0) {
          val node = new Node(i, j, chessMap(i)(j))
          sparseArr.append(node)
        }
      }
    }
    println("---------稀疏数组----------")
   for(node<-sparseArr){
     printf("%d\t%d\t%d\n",node.row,node.col,node.value)
   }
    //存盘
    //读盘 -> 稀疏数组
    //稀疏数组-> 原始数组
    //读取稀疏数组的第一个节点
    val newNode: Node = sparseArr(0)
    val rowSize2: Int = newNode.row
    val colSize2: Int = newNode.col
    val chessMap2: Array[Array[Int]] = Array.ofDim[Int](rowSize2,colSize2)
    for(i<-1 until sparseArr.length){
      val node= sparseArr(i)
      chessMap2(node.row)(node.col)=node.value
    }
    println("-------从稀疏数组恢复后的地图--------")
    for(item <- chessMap){
      for(item2 <- item){
        printf("%d\t",item2)
      }
      println()
    }

  }
}
class Node(val row:Int,val col:Int,val value:Int){
}