数据结构之稀疏数组

骑猪看日落 2021-05-10 11:33 476阅读 0赞

## 1.稀疏数组(sparsearray) ##

### 1.1 应用场景 : ###

当一个数组中大部分为0或者为同一个数值时可转化为稀疏数组进行存储

例子 : **五子棋棋盘**

![在这里插入图片描述][2019070921434283.png]

假设黑棋为1, 白棋为2, 其它未放置棋子的位置为0, 则可得到如下一个二维数组

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 2 2 2 2 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \\begin\{matrix\}0&0&0&0&0&0&0&0&0\\\\0&0&0&0&0&0&0&0&0\\\\0&0&0&1&0&0&0&0&0&\\\\0&1&2&2&2&2&0&0&0\\\\0&0&0&0&0&1&0&0&0\\\\0&0&0&0&0&0&0&0&0&\\\\0&0&0&0&0&0&0&0&0&\\\\0&0&0&0&0&0&0&0&0&\\\\0&0&0&0&0&0&0&0&0\\end\{matrix\} 000000000000100000000200000001200000000200000000210000000000000000000000000000000

**如果需要保存当前棋盘的状态时 , 保存没有放置棋子的地方是毫无意义而且浪费内存空间的 , 所以此时稀疏数组可以起到非常大的作用.想一想QQ游戏里成千上万名玩家在对战五子棋, 内存早就被挤爆了吧**

### 1.2什么是稀疏数组 ###

稀疏数组共有3列 , 第1列表示行, 第2列表示列, 第三列表示值.

稀疏数组的第1行保存原数组中共有多少行, 多少列与多少个有效值

第2行开始保存每一个有效值所处的行数, 列数与对应的值

### 1.3 二维数组对应的稀疏数组 ###

行  列  值

9 9 5 3 1 1 3 2 2 3 3 2 3 4 2 3 5 2 4 5 1 \\begin\{matrix\}9&9&5\\\\3&1&1\\\\3&2&2\\\\3&3&2\\\\3&4&2\\\\3&5&2\\\\4&5&1\\end\{matrix\} 933333491234555122221

这样做的好处是将9\*9=81个值压缩成3\*7=21个值保存, 大大减小了占用的内存空间

### 1.4 压缩数组思路 ###

① 遍历原始二维数组 , 得到有效数据的个数count

② 根据count创建稀疏数组 , 行数为(count+1), 因为第一行保存原数组的行列及有效值个数, sparseArray\[count+1\]\[3\]

③ 将原二维数组的有效数据存放到sparseArray当中

### 1.5 解压数组思路 ###

① 读取稀疏数组的第一行, 构建原始数组 array\[sparseArray\[0\]\[0\]\]\[sparseArray\[0\]\[1\]\]

②从稀疏数组的第二行开始读取数据存放到原始数组中

### 1.6 代码实现 ###

package com.smallpineapple.sparseArray;
    
    public class SparseArray { 
    
    	
    	public static void main(String[] args){ 
    		//构建原二维数组
    		int chessArr[][] = new int[9][9];
    		chessArr[3][1] = 1;
    		chessArr[3][2] = 2;
    		chessArr[3][3] = 2;
    		chessArr[3][4] = 2;
    		chessArr[3][5] = 2;
    		chessArr[4][5] = 1;
    		//输出原始二维数组
    		System.out.println("原始的二维数组:");
    		for (int[] row : chessArr) { 
    			for (int item : row) { 
    				System.out.print(item+" ");
    			}
    			System.out.println();
    		}
    		//遍历原始二维数组的有效数据
    		int count = 0;
    		for (int[] row : chessArr) { 
    			for (int item : row) { 
    				if(item!=0){ 
    					count++;
    				}
    			}
    		}
    		System.out.println("有效数据个数为:"+count);
    		//创建稀疏数组
    		int sparsearray[][] = new int[count+1][3];
    		sparsearray[0][0] = 11;
    		sparsearray[0][1] = 11;
    		sparsearray[0][2] = count;
    		//遍历二维数组, 将非0数据存放到数组当中去 
    		int row = 1;
    		for(int i=0;i<9;i++){ 
    			for(int j=0;j<9;j++){ 
    				if(chessArr[i][j]!=0){ 
    					sparsearray[row][0] = i;
    					sparsearray[row][1] = j;
    					sparsearray[row][2] = chessArr[i][j];
    					//下一个数据存放到下一行
    					row++;
    				}
    			}
    		}
    		//输出稀疏数组
    		System.out.println("稀疏数组:");
    		for (int i = 0; i < sparsearray.length; i++) { 
    			System.out.printf("%d\t%d\t%d\t", sparsearray[i][0],sparsearray[i][1],sparsearray[i][2]);
    			System.out.println();
    		}
    		
    		//稀疏数组转换成原始数组
    		int[][] transferArray = new int[sparsearray[0][0]][sparsearray[0][1]];
    		for (int i = 1; i < sparsearray.length; i++) { 
    			transferArray[sparsearray[i][0]][sparsearray[i][1]] = sparsearray[i][2];
    		}
    		//输出原始数组
    		System.out.println("原始数组形式:");
    		for (int[] a : transferArray) { 
    			for (int i : a) { 
    				System.out.print(i+" ");
    			}
    			System.out.println();
    		}
    	}
    }
    
    输出结果 : 
    
    原始的二维数组:
    0 0 0 0 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0 
    0 1 2 2 2 2 0 0 0 
    0 0 0 0 0 1 0 0 0 
    0 0 0 0 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0 
    有效数据个数为:6
    稀疏数组:
    11	11	6	
    3	1	1	
    3	2	2	
    3	3	2	
    3	4	2	
    3	5	2	
    4	5	1	
    原始数组形式:
    0 0 0 0 0 0 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0 0 0 
    0 1 2 2 2 2 0 0 0 0 0 
    0 0 0 0 0 1 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0 0 0

[2019070921434283.png]: /images/20210509/bda6863ff7094e02bd5cbe0e2b273879.png