数据结构002之稀疏数组
2020-08-28 本文已影响0人
吴维
什么是稀疏数组?
稀疏数组可以看做是对普通数组的压缩，普通数组是指无效数据量远大于有效数据量的数组,为什么要进行压缩,不用说也知道,肯定是为了节省空间
稀疏数组的数据结构
image.png
通过上图可以发现:
- 稀疏数组也是一个二维数组.
- 稀疏数组的第一行,存储了原始二维数组的大小和有效数据个数
- 第二行往后,存储的都是真实的数据和这个数据对应的位置
稀疏数组案例图解
image.png
原始二维数组中存储的真实数据只有2个,其它的都是无效数据
通过将原始二维数组转换为稀疏数组后发现只用记录真实数据的行即可,节省大量空间
再次理解稀疏数组:
-
第一行:固定为 [行 列 有效数据个数]
-
第一行对应的二维数组:[行(9) 列(9) 有效数据2个(1,2) ,最终得出:9,9,2
-
第二行向后对应的是真实数据
-
例如第二行中rows的位置为1,cols的位置是2,值是1
实战案例一:二维数组转稀疏数组并保存到磁盘
实现思路:
- 创建二维数组大小为(9*9)
- 存储数据:(在第2行第3列存储数据1),(在第3行,第4列存储数据2)
- 转换为稀疏数组:遍历二维数组,记录非0数据的个数
- 定义稀疏数组:稀疏数组定义时,列固定为3列,行等于(有效数据的个数+1)
为什么要加1?为什么是有效数据个数?
- 因为稀疏数组第一行是固定的格式,而有效数据个数有多少个就需要向稀疏数组插入多少行,所以最终的稀疏数组行的大小为:(有效数据个数+1)
- 设置稀疏数组第一行(二维数据的行数,列数,有效个数)
- 将二维数组中的值存储到稀疏数组中
- 将稀疏数组中的数据写入磁盘
/**
* @author 凡人静水
* 注释: 二维数组转稀疏数组并存储磁盘
*/
public class ArrayToSparseArraySaveFile {
public static void main(String[] args) throws IOException {
//1.创建二维数组大小为(9*9)
int array[][] = new int[9][9];
//2.存储数据:(在第2行第3列存储数据1),(在第3行,第4列存储数据2)
array[1][2] = 1;
array[2][3] = 2;
//3.转换为稀疏数组:遍历二维数组,记录非0数据的个数
int sum = 0;
for (int[] rows : array) {
for (int cell : rows) {
if (cell != 0) {
sum++;
}
}
}
System.out.println("有效个数为:" + sum);
//4.定义稀疏数组:稀疏数组定义时,列固定为3列,行等于(有效数据的个数+1)
int sparseArray[][] = new int[sum + 1][3];
//5.设置稀疏数组第一行(二维数据的行数,列数,有效个数)
sparseArray[0][0] = array.length;
sparseArray[0][1] = array[0].length;
sparseArray[0][2] = sum;
//6.将二维数组中的值存储到稀疏数组中
int count = 0;
for (int i = 0; i < array.length; i++) { //行数
for (int j = 0; j < array[0].length; j++) { //列数
if (array[i][j] != 0) {
/**
* 如果不是0需求赋值给稀疏数组
* 如果第一次发现非0数据时,count++,此时count为1,表示将数据插入到第二行位置
* 之后每一次发现非0数据时,count都会加1,表示将数据插入到下一行位置,不理解可以打断点调试
* 注意:一定要先count++,因为稀疏数组默认第一行是固定的格式,只能从第二行开始设置值
*/
count++;
sparseArray[count][0] = i; //行的位置
sparseArray[count][1] = j; //列的位置
sparseArray[count][2] = array[i][j]; //真实数据
}
}
}
//7.将稀疏数组中的数据写入磁盘
BufferedWriter writer =
new BufferedWriter(new FileWriter("sparse_array.txt"));
for (int i = 0; i < sparseArray.length; i++) {
StringBuilder sb = new StringBuilder();
sb.append(sparseArray[i][0]).append("\t")
.append(sparseArray[i][1]).append("\t")
.append(sparseArray[i][2]).append("\t");
writer.write(sb.toString());
writer.newLine();
writer.flush();
}
writer.close();
}
}
输出结果:
9 9 2
1 2 1
2 3 2
实战案例二:将文件中的稀疏数组转为二维数组
实现思路:
- 读取文件第一行数据,并获取行与列信息
- 创建二维数组
- 读取文件后面每一行数据,并获取行与列和数据信息
- 直接赋值给二维数组
- 完成打印
/**
* @author 凡人静水
* 注释:稀疏数组转为二维数组
*/
public class ReadFileAndSparseArrayToArray {
public static void main(String[] args) throws IOException {
//1.读取文件第一行数据,并获取行与列信息
BufferedReader reader =
new BufferedReader(new FileReader("sparse_array.txt"));
String firstContent = reader.readLine(); //获取第一行信息
String[] positions = firstContent.split("\t");
int row = Integer.valueOf(positions[0]);//行信息
int col = Integer.valueOf(positions[1]);//列信息
//2.创建二维数组,读取第一行内容,并获取二维数据的行与列信息
int array[][] = new int[row][col];
//3.读取文件后面每一行数据,并获取行,列,数据信息
StringBuilder sb = new StringBuilder();
String content;
while ((content = reader.readLine()) != null) {
sb.append(content).append("\n");
}
reader.close();
//4.解析广西,并赋值给二维数组
String[] dataLines = sb.toString().split("\n");
for (String dataLine : dataLines) {
String[] dataPositions = dataLine.split("\t");
int dataRow = Integer.valueOf(dataPositions[0]);
int dataCol = Integer.valueOf(dataPositions[1]);
int data = Integer.valueOf(dataPositions[2]);
array[dataRow][dataCol] = data;
}
//5.完成打印
for (int[] rows : array) {
for (int cell : rows) {
System.out.print(cell + "\t");
}
System.out.println();
}
}
}
输出结果:
0 0 0 0 0 0 0 0 0
0 0 1 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
关注微信公众号:** javastu**
