稀疏数组（java实现）

1.稀疏数组

当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。 稀疏数组的处理方法是：

1.1记录数组一共有几行几列，有多少个不同的值

1.2把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模 I

2.二维数组转稀疏数组的思路

2.1.遍历原始的二维数组，得到有效数据的个数sum

2.2.根据sum 就可以创建稀疏数组sparseArr intsum+1

2.3.将二维数组的有效数据数据存入到稀疏数组

3.稀疏数组转原始的二维数组的思路

3.1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如 上面的chessAr2=int11

3.2.在读取稀疏数组后几行的数据，并赋给原始的二维数组即可.

4.应用实例

使用稀疏数组，来保留类似前面的二维数组（棋盘、地图等等）把稀疏数组存盘，并且可以从新恢复原来的二维数组数整体思路分析

public class SparseArray {
    public static void main(String[] args) {
//创建二维数组  1表示黑色的  2表示蓝色的  0表示空
        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();
        }
        //遍历原始二维数组，从而得到非0的个数
        int sum = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessarr1[i][j] != 0) {
                    sum++;
                }
            }
        }
        //创建对应的稀疏数组
        int sparsearr[][] = new int[sum + 1][3];
        //给稀疏数组复制
        sparsearr[0][0] = 11;
        sparsearr[0][1] = 11;
        sparsearr[0][2] = sum;
        //遍历二维数组 将非0的值放在 sparsearr中
        int count=0;//用于记录第几个非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();
        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();


        //将稀疏数组转换为二维数组
        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];
        }
         //恢复后的稀疏数组为
      for (int[] row : chessarr2) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
        }
    }

 

原文链接:https://www.cnblogs.com/GEMyd/p/11647267.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有