数据结构-4.稀疏数组

1. 当一个数组中大部分元素为 0，或者为同一个值时，可以使用稀疏数组来保存该数组

处理方法：

记录数组一共有多少行多少列，有多少种不同的值

把有不同值的元素的行列数及元素的值记录在一个小的数组里，从而缩小程序的规模，这个小数组就是稀疏数组

这个数组可以用稀疏数组来表示

这个原始的二维数组，一共有 6 * 7 = 42 个元素

用稀疏数组来记录它

记录用的稀疏数组

[0] 元素，记录了一共有 6 行，7 列，8 个不同值（不是 0）的元素，之后的每一个元素，分别记录每个不同值元素的行数，列数和值

稀疏数组只需要存储 3 * 9 = 27 个值

再来看一个例子：假如我们需要编写一个五子棋，有这样的棋盘

五子棋的棋盘

使用二维数组来记录它，

用二维数组来记录棋盘，1 表示黑棋，2 表示蓝棋

用稀疏数组 a 来表示它 a[0] = {11, 11, 2} a[1] = {2, 1, 1} a[2] = {3, 2, 2}

2. 二维数组转稀疏数组的思路：

（1）遍历原始二维数组，得到有效数据的个数 sum

（2）用 sum 来创建稀疏数组 sparseArray int[sum + 1][3]

（3）将二维数组的有效数据存入到稀疏数组中

3. 稀疏数组转二维数组的思路：

（1）读取稀疏数组的第一行，读取行数和列数，创建原始数组

（2）读取稀疏数组后面的数据，赋值给原始数组

注意：二维数组的长度：

（1）二维数组是规则的长方形或正方形

int[][] a = new int[11][11]; 它表示声明了一个数组，里面有 11 个元素，每个元素是一个长度为 11 的整数数组，长度是 11， a.length = 11

int[][] b = new int[2][12]; 它表示声明了一个数组，里面有 2 个元素，每一个元素是一个长度为 12 的整数数组，长度是 12，a.length = 12

（2）二维数组是不规则的，每一行的元素个数不等

int [][] c = new int[3][];

c[0] = new int[] {1,2,3,4};

c[1] = new int[] {2,3,4,5,6,7,8};

c[2] = new int[] {0,0};

此时，c.length = 3，遍历时应该分着使用 a[0].length，a[1].length，a[2].length

这说明，如果行数和列数都已经定义，二维数组的长度为列数，如果只有行数没有列数，二维数组的长度为行数

具体代码实现：（举例）

1. 假设有这样一个数组可以用稀疏数组来简化表示它

原始的二维数组

大部分元素都是 0，有几个非 0 元素的数组

2. 将其转化为稀疏数组，首先遍历二维数组，计算出有多少个元素是非 0 的

计算非 0 元素的个数

3. 创建稀疏数组并为其赋值

定义稀疏数组的大小，并将其第一行的三个元素赋值，即原数组的行数，列数，和特值数

4. 将原数组转化为稀疏数组

转化并显示

转化后的稀疏数组

5. 可以用 IO流将其输出到指定位置

使用 StringBuffer 来将数组以字符串形式输出

6. 假如要将某个文件中存储的稀疏数组转化为原始数组

使用 BufferedReader 的 readLine() 方法来读取，更适合一次性读取稀疏数组的一整行

流的关闭

7. 将稀疏数组转化为二维数组

通过稀疏数组中记录的行数和列数来创建数组，再依次为特值赋值

注意：在实际工作中，通过 IO流读取稀疏数组文件，同时将其之间转化为原数组更为方便，而这种先读取为字符串再转化为稀疏数组再转化为原数组的方法是非常麻烦的

具体操作如下：

还是使用 BufferedReader 中的 readLine() 方法来一次性读取一行，注意在每一行的结尾处也加入 \t，以方便分割字符串，将所有的数字（String）放入 String 数组中，先用前三个元素来恢复创建原数组，再每三个一组，恢复数组中的特值