数据结构与算法--稀疏数组

转换方法

记录数组有几行几列，有多少个不同的值
把不同的值的元素的行列，记录在一个小规模的数组中，以此来缩小数组的规模

如图：

二维数组转稀疏数组

对原始的二维数组进行遍历，并得到有效的数据个数（这里用sum表示）
根据sum的个数，创建稀疏数组 sparseArr int[sum+1][3]
将二维数组的有效数据存入到稀疏数组中

PS：sum+1是因为稀疏数组的第一行存放的是数组的行列数以及有效数值个数

稀疏数组转二维数组

先读取稀疏数组中的第一行，并且根据稀疏数组中第一行的数据，创建原始的二维数组

 int num1,num2;

 num1 = sparseArr[0][0];

 num2  = sparseArr[0][1];

 chessArr int[num1][num2] = new int[num1][num2];

读取稀疏数组后面几行的数据，并且一一赋值给原始的二维数组

代码实现

输出原始数组

public static void main(String[] args) {

        //创建原始数组

        //1代表黑子，2代表白子

        int[][] chessArr = new int[11][11];

        chessArr[1][2] = 1;

        chessArr[2][3] = 2;

        for (int[] items: chessArr) {

            for (int data: items) {

                System.out.print(data+"\t");

            }

            System.out.println();

        }

    }

结果如下：

转换稀疏数组并输出

public static void main(String[] args) {

        //创建原始数组

        //1代表黑子，2代表白子

        int[][] chessArr = new int[11][11];

        chessArr[1][2] = 1;

        chessArr[2][3] = 2;

        //sum用来记录不为0的数值个数

        int sum=0;

        for (int[] items: chessArr) {

            for (int data: items) {

                if(data != 0){

                    sum++;

                }

                System.out.print(data+"\t");

            }

            System.out.println();

        }

        //原始数组转逻辑数组

        //1、找出数值不为0的元素个数

        int[][] sparseArr =new int[sum+1][3];

            //chessArr.length代表行的长度

            //chessArr[0].length代表列的长度

            sparseArr[0][0]=chessArr.length;

            sparseArr[0][1]=chessArr[0].length;

            sparseArr[0][2]=sum;

            //第一行以后的稀疏数组的数据

            int count = 0; //count用来统计是第几个不为0的数

            for(int i=0;i<11;i++){

                for(int j=0;j<11;j++){

                    if(chessArr[i][j] != 0){

                        count++;

                        sparseArr[count][0]=i;

                        sparseArr[count][1]=j;

                        sparseArr[count][2]=chessArr[i][j];

                    }

                }

            }

            //输出稀疏数组

        for (int[] items: sparseArr) {

            for (int data: items) {

                System.out.print(data+"\t");

            }

            System.out.println();

        }

    }

其结果如下

稀疏数组转换会原数组

		//将稀疏数组还原

        //1、通过第一行的稀疏数组数值，建立原始二维数组

            int[][] chessArr1 = new int[sparseArr[0][0]][sparseArr[0][1]];

        //2、将稀疏数组的值赋值给原始数组

        for(int i=1;i<sparseArr.length;i++){

            //将稀疏数组中的第i行的第1/2分别取出作为原始数组的行和列，第三个值作为原始数组的值

            chessArr1[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];

        }

        //转换后的原始数组输出

        for (int[] items: chessArr1) {

            for (int data: items) {

                System.out.print(data+"\t");

            }

            System.out.println();

        }

其结果如下：

好啦~

今天的更新到此结束

下次再更新其他文章哦~

巴特西

Java成神之路：第二帖---- 数据结构与算法之稀疏数组

数据结构与算法--稀疏数组

转换方法

二维数组转稀疏数组

稀疏数组转二维数组

代码实现

输出原始数组

转换稀疏数组并输出

稀疏数组转换会原数组

最新文章

热门文章