6.8 稀疏數(shù)組

稀疏數(shù)組是一種數(shù)據(jù)結(jié)構(gòu)，在程序中數(shù)據(jù)結(jié)構(gòu)的思想，是非常重要的。例如

• 需求：編寫五子棋游戲中，有存盤退出和續(xù)上盤的功能。
• 分析問(wèn)題：因?yàn)樵摱S數(shù)組的很多值是默認(rèn)值0，因此記錄了很多沒有意義的數(shù)據(jù)，當(dāng)存盤退出的時(shí)候，棋盤上有大量的默認(rèn)值，存儲(chǔ)沒有必要。也是是我們可以編寫一個(gè)壓縮算法讓我們的存儲(chǔ)更為高效，也就是我們要學(xué)習(xí)的稀疏數(shù)組

一、稀疏數(shù)組介紹

當(dāng)一個(gè)數(shù)組中大部分元素為0，或者為同一值的數(shù)組時(shí)，可以利用稀疏數(shù)組來(lái)保存該數(shù)組。

• 稀疏數(shù)組的處理方式是：

  1. 記錄數(shù)據(jù)一共有幾行幾列，有多少個(gè)不同的值
  2. 把具有不同值的元素和行列及值記錄在一個(gè)小規(guī)模的數(shù)組中，從而縮小程序的規(guī)模

• 如圖，左邊是原始數(shù)組，右邊是稀疏數(shù)組

  

示例

package com.baidu.www.array;public class ArrayDemo08 {public static void main(String[] args) {//1、創(chuàng)建一個(gè)二維數(shù)組11*11 0代表沒有棋子，1：黑棋，2：白棋int[][] array1 = new int[11][11];array1[1][2] = 1;array1[2][3] = 2;//輸出原始的數(shù)組System.out.println("輸出原始的數(shù)組");for(int[] ints : array1 ){for (int anInt: ints) {System.out.print(anInt+"\t");}System.out.println();}System.out.println("====================================");//轉(zhuǎn)換為稀疏數(shù)組保存//1、獲取有效值的個(gè)數(shù)int sum = 0;for (int i = 0; i < 11; i++) {for (int j = 0; j < 11; j++) {if(array1[i][j]!=0){sum++;}}}System.out.println("有效值的個(gè)數(shù)為"+sum);//2、創(chuàng)建一個(gè)稀疏數(shù)組的數(shù)組int[][] array2 = new int[sum+1][3];//根據(jù)有效值的個(gè)數(shù)加一就能確定稀疏數(shù)組的行數(shù)array2[0][0]=11;array2[0][1]=11;array2[0][2]=sum;//3、遍歷二維數(shù)組，將非零的值，存放稀疏數(shù)組中int count = 0;for (int i = 0; i < array1.length; i++) {for (int j = 0; j < array1[i].length; j++) {if(array1[i][j]!=0){count++;//有了這個(gè)我們就知道里面存了多少個(gè)數(shù)字array2[count][0]=i;array2[count][1]=j;array2[count][2]=array1[i][j];}}}//輸出稀疏數(shù)組System.out.println("輸出稀疏數(shù)組");for (int i = 0; i < array2.length; i++) {System.out.println(array2[i][0] + "\t" + array2[i][1] + "\t" + array2[i][2] + "\t");}System.out.println("====================================");System.out.println("還原稀疏數(shù)組");//相當(dāng)于根據(jù)稀疏數(shù)組重新構(gòu)建一個(gè)新的數(shù)組//1、先讀取稀疏數(shù)組的值，定義一個(gè)新的數(shù)組int[][] array3 = new int[array2[0][0]][array2[0][1]];//2、給其中的元祖還原它的值for (int i = 1; i < array2.length; i++) {array3[array2[i][0]][array2[i][1]]=array2[i][2];}//3、輸出還原后的數(shù)組System.out.println("輸出還原的數(shù)組");for(int[] ints : array3 ){for (int anInt: ints) {System.out.print(anInt+"\t");}System.out.println();}}
}
/*
* 輸出原始的數(shù)組
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	
====================================
有效值的個(gè)數(shù)為2
輸出稀疏數(shù)組
11	11	2	
1	2	1	
2	3	2	
====================================
還原稀疏數(shù)組
輸出還原的數(shù)組
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	Process finished with exit code 0*/