一、概要

　　一个稀疏矩阵A可以压缩为一个n+1行、3列的矩阵B。其中n表示稀疏矩阵A中非零数字的个数。

　　采用的压缩方式为：

• 矩阵B的第一行记录矩阵A的行列数以及非零数字的个数；
• 从第二行开始，记录每个非零数字所在的行和列，以及值。

　　于是稀疏矩阵A与压缩后的矩阵B的对应关系如下图所示

 

 

 

二、代码实现

　　[附]将一个二维数组以矩阵的形式显示出来

 1 /**
 2  * 以矩阵形式返回一个二维数组的内容
 3  * @param arr: 二维数组
 4  * @return 以String类型按矩阵形式返回该二维数组的内容
 5  */
 6 public static String getStringOfArray(int [][] arr) {
 7     StringBuilder builder = new StringBuilder();
 8     for (int[] ints : arr) {
 9         for (int item : ints) {
10             builder.append(item).append('\t');
11         }
12         builder.append('\n');
13     }
14     return builder.toString();
15 }

getStringOfArray

 

 

　　将一个稀疏矩阵进行压缩，得到一个压缩后的矩阵：

 1 /**
 2  * 将一个稀疏数组压缩为一个矩阵
 3  * @param arr: 要压缩的稀疏数组
 4  * @return 压缩后的矩阵
 5  */
 6 public static int [][] getSparseArray(int [][] arr) {
 7     if (arr == null)
 8         return null;
 9     if (arr.length == 0)
10         return new int[0][0];
11 
12     int rowCount = arr.length;
13     int columnCount = arr[0].length;
14     int totalNumberCount = 0;
15     for (int i = 0; i < rowCount; i++) {
16         for (int j = 0; j < columnCount; j++) {
17             if (arr[i][j] != 0) {
18                 totalNumberCount++;
19             }
20         }
21     }
22     int [][] sparseArray = new int[totalNumberCount + 1][3];
23     sparseArray[0][0] = rowCount;
24     sparseArray[0][1] = columnCount;
25     sparseArray[0][2] = totalNumberCount;
26     int sparseArrayRow = 0;
27     for (int i = 0; i < rowCount; i++) {
28         for (int j = 0; j < columnCount; j++) {
29             if (arr[i][j] != 0) {
30                 sparseArrayRow++;
31                 sparseArray[sparseArrayRow][0] = i;
32                 sparseArray[sparseArrayRow][1] = j;
33                 sparseArray[sparseArrayRow][2] = arr[i][j];
34             }
35         }
36     }
37     return sparseArray;
38 }

getSparseArray

 

 

　　将一个压缩后的矩阵还原为压缩前的稀疏矩阵：

 1 /**
 2  * 将压缩后的矩阵还原为稀疏数组
 3  * @param sparseArray: 要还原的压缩后的矩阵
 4  * @return 原来的稀疏数组
 5  */
 6 public static int [][] getNormalArray(int [][] sparseArray) {
 7     if (sparseArray == null)
 8         return null;
 9     if (sparseArray.length == 0)
10         return new int[0][0];
11 
12     int rowCount = sparseArray[0][0];
13     int columnCount = sparseArray[0][1];
14     int totalNumberCount = sparseArray[0][2];
15     int [][] arr = new int[rowCount][columnCount];
16     for (int i = 1; i <= totalNumberCount; i++) {
17         int currRow = sparseArray[i][0];
18         int currColumn = sparseArray[i][1];
19         int currValue = sparseArray[i][2];
20         arr[currRow][currColumn] = currValue;
21     }
22     return arr;
23 }

getNormalArray

 

 

　　将一个稀疏矩阵压缩后保存到指定文件中：

 1 /**
 2  * 将一个稀疏数组压缩后写入到指定文件
 3  * @param arr: 要保存的稀疏数组
 4  * @param file: 要保存到的文件
 5  */
 6 public static void saveArray(int [][] arr, File file) {
 7     if (!file.exists()) {
 8         try {
 9             file.createNewFile();
10         } catch (IOException e) {
11             e.printStackTrace();
12         }
13     }
14 
15     BufferedWriter bw = null;
16     try {
17         bw = new BufferedWriter(new FileWriter(file));
18         int[][] sparseArray = getSparseArray(arr);
19         String stringOfArray = getStringOfArray(sparseArray);
20         bw.write(stringOfArray);
21         bw.flush();
22     } catch (FileNotFoundException e) {
23         e.printStackTrace();
24     } catch (IOException e) {
25         e.printStackTrace();
26     } finally {
27         if (bw != null) {
28             try {
29                 bw.close();
30             } catch (IOException e) {
31                 e.printStackTrace();
32             }
33         }
34     }
35 }

saveArray

 

 

　　从指定文件中读取出稀疏矩阵：

 1 /**
 2  * 从一个指定文件中读取稀疏数组
 3  * @param file: 保存稀疏数组的文件
 4  * @return 原稀疏数组
 5  */
 6 public static int [][] openArray(File file) {
 7     if (file == null || !file.exists())
 8         return null;
 9 
10     int [][] sparseArray = null;
11     BufferedReader br = null;
12     try {
13         br = new BufferedReader(new FileReader(file));
14         List<int []> list = new ArrayList<>();
15         String str = null;
16         while ((str = br.readLine()) != null) {
17             //System.out.println(str);
18             String[] strings = str.split("\t");
19             int [] ints = new int[3];
20             for (int i = 0; i < 3; i++) {
21                 ints[i] = Integer.parseInt(strings[i]);
22             }
23             list.add(ints);
24         }
25         int size = list.size();
26         sparseArray = new int[size][3];
27         for (int i = 0; i < size; i++) {
28             sparseArray[i][0] = list.get(i)[0];
29             sparseArray[i][1] = list.get(i)[1];
30             sparseArray[i][2] = list.get(i)[2];
31         }
32     } catch (FileNotFoundException e) {
33         e.printStackTrace();
34     } catch (IOException e) {
35         e.printStackTrace();
36     } finally {
37         if (br != null) {
38             try {
39                 br.close();
40             } catch (IOException e) {
41                 e.printStackTrace();
42             }
43         }
44     }
45 
46     return getNormalArray(sparseArray);
47 }

openArray

 

　　

　　测试

 1 @Test
 2 public void testOpen() {
 3     File file = new File("file/test.data");
 4 
 5     int[][] array = openArray(file);
 6     System.out.println(getStringOfArray(array));
 7 }
 8 
 9 @Test
10 public void testSave() {
11     File file = new File("file/test.data");
12 
13     int [][] a = new int[11][11];
14     a[1][2] = 1;
15     a[2][3] = 2;
16     saveArray(a, file);
17 }

Test