Java数据结构之稀疏数组的实现与应用
什么是稀疏数组
稀疏数组是一种刻画二维数组中许多元素值都为0的特殊数据结构。它可以提高存储空间的利用率,实现对数据的压缩和优化,减少不必要的处理,提升程序的运行效率。
在稀疏数组中,只有非零元素被存储,而这些元素的索引信息和具体数值的信息都会被记录下来。
稀疏数组的实现与应用
实现步骤
- 创建原始的二维数组,存入多个元素;
- 统计原始数组中非零元素的个数sum;
- 创建大小为(sum+1)*3的稀疏数组,并在第一行记录原始数组的行数、列数和非零元素的个数;
- 遍历原始数组,将非零元素的行列信息和具体数值存入稀疏数组;
- 将稀疏数组存入文件中。
代码实现如下:
//创建原始数组
int[][] originalArray = new int[5][5];
originalArray[1][2] = 2;
originalArray[2][3] = 3;
originalArray[4][4] = 4;
//统计非零元素的个数
int sum = 0;
for (int i = 0; i < originalArray.length; i++) {
for (int j = 0; j < originalArray[i].length; j++) {
if (originalArray[i][j] != 0) {
sum++;
}
}
}
//创建稀疏数组
int[][] sparseArray = new int[sum + 1][3];
sparseArray[0][0] = originalArray.length;
sparseArray[0][1] = originalArray[0].length;
sparseArray[0][2] = sum;
int count = 0;
for (int i = 0; i < originalArray.length; i++) {
for (int j = 0; j < originalArray[i].length; j++) {
if (originalArray[i][j] != 0) {
count++;
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = originalArray[i][j];
}
}
}
//将稀疏数组存入文件中
try {
FileWriter fw = new FileWriter("sparseArray.txt");
for (int i = 0; i < sparseArray.length; i++) {
for (int j = 0; j < 3; j++) {
fw.write(sparseArray[i][j] + "\t");
}
fw.write("\n");
}
fw.close();
} catch (IOException e) {
e.printStackTrace();
}
应用场景
在棋类游戏中,对于棋盘上空白位置较多的情况,采用稀疏数组可以有效地压缩存储空间、简化程序实现。
示例一:五子棋
在五子棋游戏中,棋盘上空白的交叉点较多,采用二维数组存储所有交叉点信息会造成大量浪费,不够实用。通过使用稀疏数组存储五子棋中的棋盘信息,则可以达到压缩存储空间、提高程序响应速度,减少不必要的运算等效果。
代码示例如下:
//创建原始的棋盘数组
int[][] originalArray = new int[15][15];
//在3,3位置下黑子
originalArray[3][3] = 1;
//在4,4位置下白子
originalArray[4][4] = 2;
//在5,5位置下黑子
originalArray[5][5] = 1;
//将原始数组转换为稀疏数组
int sum = 0;
for (int i = 0; i < originalArray.length; i++) {
for (int j = 0; j < originalArray[i].length; j++) {
if (originalArray[i][j] != 0) {
sum++;
}
}
}
int[][] sparseArray = new int[sum + 1][3];
sparseArray[0][0] = originalArray.length;
sparseArray[0][1] = originalArray[0].length;
sparseArray[0][2] = sum;
int count = 0;
for (int i = 0; i < originalArray.length; i++) {
for (int j = 0; j < originalArray[i].length; j++) {
if (originalArray[i][j] != 0) {
count++;
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = originalArray[i][j];
}
}
}
//将稀疏数组存入文件中
try {
FileWriter fw = new FileWriter("chessSparseArray.txt");
for (int i = 0; i < sparseArray.length; i++) {
for (int j = 0; j < 3; j++) {
fw.write(sparseArray[i][j] + "\t");
}
fw.write("\n");
}
fw.close();
} catch (IOException e) {
e.printStackTrace();
}
示例二:地图数据
在类似地图信息存储的场合中,采用稀疏数组能够有效地优化存储空间。如果使用一个二维数组存储每个格子的信息,那么在空白格子数量占比较高的情况下,存储空间的浪费比较严重。而使用稀疏数组存储地图信息,则可以达到压缩存储空间、提高程序可读性和目录性的优点。
代码示例如下:
//创建原始的地图数组
int[][] originalArray = {
{0,0,0,0,0},
{0,1,0,0,0},
{0,0,1,0,0},
{0,0,0,1,0},
{0,0,0,0,0}
};
//将原始数组转换为稀疏数组
int sum = 0;
for (int i = 0; i < originalArray.length; i++) {
for (int j = 0; j < originalArray[i].length; j++) {
if (originalArray[i][j] != 0) {
sum++;
}
}
}
int[][] sparseArray = new int[sum + 1][3];
sparseArray[0][0] = originalArray.length;
sparseArray[0][1] = originalArray[0].length;
sparseArray[0][2] = sum;
int count = 0;
for (int i = 0; i < originalArray.length; i++) {
for (int j = 0; j < originalArray[i].length; j++) {
if (originalArray[i][j] != 0) {
count++;
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = originalArray[i][j];
}
}
}
//将稀疏数组存入文件中
try {
FileWriter fw = new FileWriter("mapSparseArray.txt");
for (int i = 0; i < sparseArray.length; i++) {
for (int j = 0; j < 3; j++) {
fw.write(sparseArray[i][j] + "\t");
}
fw.write("\n");
}
fw.close();
} catch (IOException e) {
e.printStackTrace();
}
总结
通过本文的介绍,我们可以了解到稀疏数组的实现方法和应用场景。在编写程序时,可以结合实际情况,采用恰当的数据结构和算法,提高程序的运行效率和稳定性。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java数据结构之稀疏数组的实现与应用 - Python技术站