数据结构与算法——稀疏数组
引言
本篇介绍稀疏数组，二维数组与稀疏数组之间的相互转化，如果你需要了解其他数据结构，请点击下面链接查看！！！
了解更多：数据结构与算法目录整理
稀疏数组
一、稀疏数组的定义
当一个数组（包括多维数组）中的大部分元素为0或者为同一个数值的数组时，为了节约空间起到压缩的效果，将数据用另一种结构来表示，即稀疏数组。
二、根据二维数组转稀疏数组
遍历二维数组，得出有效数据的个数 sum
根据有效数据的个数，确定稀疏数组 sparseArr[sum+1][3]
遍历二维数组，给稀疏数组赋值
/**
* *二维数组转稀疏数组
* @author 蜡笔小新
*
*/public class Test3 {public static void main(String []args) {int arr[][]=new int [10][10];
arr[0][5]=7;
arr[2][7]=6;
arr[3][2]=1;
arr[5][5]=3;
arr[7][1]=4;
arr[8][7]=9;//遍历二位数组,得到有效数据的个数int sum=0;for(int i=0;i<arr.length;i++) {for(int j=0;j<arr[i].length;j++) {if(arr[i][j]!=0) sum++;}}//根据有效数据的个数,确定稀疏数组 sparseArr[sum+1][3]int [][]sparseArr=new int[sum+1][3];//给稀疏数组的第一行赋值//sparseArr[0][0]=二位数组的行,//sparseArr[0][1]=二位数组的列,//sparseArr[0][2]=二位数组中的有效值
sparseArr[0][0]=arr.length;
sparseArr[0][1]=arr[0].length;
sparseArr[0][2]=sum;//遍历二位数组,给稀疏数组赋值int t=1;for(int i=0;i<arr.length;i++) {for(int j=0;j<arr[i].length;j++) {if(arr[i][j]!=0) {
sparseArr[t][0]=i;
sparseArr[t][1]=j;
sparseArr[t][2]=arr[i][j];
t++;}}}
System.out.println("--------------二位数组-------------");for(int i=0;i<arr.length;i++) {for(int j=0;j<arr[i].length;j++) {
System.out.print(arr[i][j]+" ");}
System.out.println();}
System.out.println("--------------稀疏数组-------------");for(int i=0;i<sparseArr.length;i++) {for(int j=0;j<sparseArr[i].length;j++) {
System.out.print(sparseArr[i][j]+" ");}
System.out.println();}}}运行结果：
三、根据稀疏数组转二维数组
根据稀疏数组的第一行确定二位数组的大小
遍历稀疏数组给二维数组赋值
/**
* *稀疏数组转二维数组
* @author 蜡笔小新
*
*/public class Test3 {public static void main(String []args) {int sparseArr[][]={{10,10,6},{0,5,7},{2,7,6},{3,2,1},{5,5,3},{7,1,4},{8,7,9}};//根据稀疏数组的第一行确定二位数组的大小int [][]arr=new int[sparseArr[0][0]][sparseArr[0][1]];//遍历稀疏数组给二维数组赋值int sum=0;for(int i=1;i<sparseArr.length;i++) {
arr[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];}
System.out.println("--------------稀疏数组-------------");for(int i=0;i<sparseArr.length;i++) {for(int j=0;j<sparseArr[i].length;j++) {
System.out.print(sparseArr[i][j]+" ");}
System.out.println();}
System.out.println("--------------二位数组-------------");for(int i=0;i<arr.length;i++) {for(int j=0;j<arr[i].length;j++) {
System.out.print(arr[i][j]+" ");}
System.out.println();}}}运行结果：