您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

稀疏数组(图文)

第十三双眼睛2022-05-28【数据结构与算法】人已围观

简介稀疏数组

基本介绍
当一个数组中大部分数据都为0或者同一个数字时，可以使用稀疏数组来保存该数组。

稀疏数组的处理方法是：
第一行记录数组一共有几行几列，一共有多少个不同的值
把具有不同值得元素记录在一个小规模得数组中，从而缩小数组得规模，这个小规模的数组就是稀疏数组。

二维数组转为稀疏数组的思路
遍历原始的二维数组，得到有效数据的个数sum
根据有效个数sum就可以创建出稀疏数组 int [sum +1] [3]
将二维数组的有效数据存入稀疏数组。

稀疏数组转换为二维数组的思路
先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，
在读取稀疏数组后续的行，将值填入上面创建的二维数组。

package com.xingchen.day001;

public class SparseArray {

   public static void main(String[] args) {
       // 创建一个原始数组11*11
       // 0表示没有棋子,1表示黑子,2表示白子
       int arr [][] = new int[11][11];
       arr[1][2] = 1;
       arr[2][3] = 2;
       System.out.println("原始数组");
       for (int [] row : arr) {
           for (int data : row) {
               System.out.print(data +" ");
           }
           System.out.println();
       }

       // 遍历数组，得到有效数字的个数
       int sum = 0;
       for (int [] row : arr) {
           for (int data : row) {
               if (data != 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 (arr[i][j] != 0) {
                   count ++ ;
                   sparseArr[count][0] = i;
                   sparseArr[count][1] = j;
                   sparseArr[count][2] = arr[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]);
       }

       // 将稀疏数组恢复为原始的二维数组
       // 先根据稀疏数组的第一行创建一个二维数组
       int arr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];

       // 从稀疏数组的第二行开始,进行有效值的赋值
       for (int i=1; i < sparseArr.length; i ++) {
           arr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
       }

       // 恢复后的二维数组
       for (int [] row : arr2) {
           for (int data : row) {
               System.out.print(data +" ");
           }
           System.out.println();
       }
   }

}

结果如下图：

原始数组
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
有效数字个数:2
得到的稀疏数组:
11   11   2
1   2   1
2   3   2
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0

Tags：

很赞哦！ ()

上一篇：线性结构和非线性结构(图文)

下一篇：队列(图文)