Java数据结构和算法（2）之稀疏数组
2021-02-18 21:18
标签：个数 out 避免 读取 程序 art 数据 arrays ring 稀疏数组可以看做是普通二位数组的压缩，但是这里说的普通数组是值无效数据量远大于有效数据量的数组，关于稀疏数组的运用有五子棋盘,地图等.. *当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组如图 * 原数组中存在大量的无效数据，占据了大量的存储空间，真正有用的数据却少之又少 *把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模 * 压缩存储可以节省存储空间以避免资源的不必要的浪费，在数据序列化到磁盘时，压缩存储可以提高IO效率 *记录数组一共有几行几列，有多少个不同的值 * 第一行存储原始数据总行数，总列数，总的非0数据个数 * 接下来每一行都存储非0数所在行，所在列，和具体值(如下图) 行列都是11的二位数组 把上面的二维数组转化为稀疏数组 备注：因为数组的下标是从0开始的，所以他们的标号也是从0开始的(重要) *遍历原始的二维数组，得到有效数据的个数 sum *根据sum 就可以创建 稀疏数组 sparseArr int[sum + 1] [3] *将二维数组的有效数据数据存入到 稀疏数组 *先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组， 比如上面的 chessArr2 = int [11][11] *在读取稀疏数组后几行的数据，并赋给 原始的二维数组 即可. Java数据结构和算法（2）之稀疏数组 标签：个数 out 避免 读取 程序 art 数据 arrays ring 原文地址：https://www.cnblogs.com/gzxg/p/12687975.html1.定义
2.好处
3.稀疏数组的结构
4.二维数组 转 稀疏数组的思路
5.稀疏数组转原始的二维数组的思路
6.代码实现
1 public class Sparsearray {
2
3 public static void main( String[] args) {
4 System.out.println("===========二维数组转换稀疏数组============");
5 int[][] array=new int[11][11];
6 array[1][2]=1;
7 array[2][3]=2;
8 System.out.println("============转换前的二维数组============");
9 forToarray(array);
10 System.out.println("============转换后的二维数组============");
11 int[][] sparsearry = arrayToSparsearry(array);
12 forToarray(sparsearry);
13 System.out.println("===========将稀疏数组转化为原始数组============");
14 array = sparsearryToArray(sparsearry);
15 forToarray(array);
16
17 }
18 /**
19 *二维数组转换稀疏数组
20 * @param array
21 */
22 private static int [][] arrayToSparsearry(int[][] array) {
23 int sum=1;
24 for (int i = 0; i ) {
25 int[] datas=array[i];
26 for (int j = 0; j ) {
27 if (array[i][j]!=0) {
28 sum++;
29 }
30 }
31 }
32
33 int [][] sparse=new int[sum][3];
34 int s=0;
35 sparse[s][0]=array.length;
36 sparse[s][1]=array[0].length;
37 sparse[s][2]=sum-1;
38 for (int i = 0; i ) {
39 int[] datas=array[i];
40 for (int j = 0; j ) {
41 int a=array[i][j];
42 if (a!=0) {
43 s++;
44 sparse[s][0]=i;
45 sparse[s][1]=j;
46 sparse[s][2]=a;
47 }
48 }
49 }
50
51 return sparse;
52 }
53 /**
54 *遍历数组
55 * @param array
56 */
57 private static void forToarray(int[][] array) {
58 for (int i = 0; i ) {
59 int [] ints=array[i];
60 for (int j = 0; j ) {
61 System.out.print(" "+array[i][j]);
62 }
63 System.out.println("");
64 }
65 }
66 /*
67 * 稀疏数组转化为原始数组
68 * @param array
69 */
70 private static int [][] sparsearryToArray(int[][] array) {
71 int [] [] arrays=new int [array[0][0]][array[0][1]];
72 for (int i = 1; i ) {
73 int[] js = array[i];
74 for (int j = 0; j ) {
75 arrays[array[i][0]][array[i][1]]=array[i][2];
76 }
77
78 }
79 return arrays;
80 }
81 }
*执行后的结果如下
===========二维数组转换稀疏数组============
============转换前的二维数组============
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
============转换后的二维数组============
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
下一篇：Python：Linux常用命令
文章标题：Java数据结构和算法（2）之稀疏数组
文章链接：http://soscw.com/index.php/essay/57219.html