Java数据结构之稀疏数组的实现与应用

什么是稀疏数组

稀疏数组是一种刻画二维数组中许多元素值都为0的特殊数据结构。它可以提高存储空间的利用率，实现对数据的压缩和优化，减少不必要的处理，提升程序的运行效率。

在稀疏数组中，只有非零元素被存储，而这些元素的索引信息和具体数值的信息都会被记录下来。

稀疏数组的实现与应用

实现步骤

1. 创建原始的二维数组，存入多个元素；
2. 统计原始数组中非零元素的个数sum；
3. 创建大小为(sum+1)*3的稀疏数组，并在第一行记录原始数组的行数、列数和非零元素的个数；
4. 遍历原始数组，将非零元素的行列信息和具体数值存入稀疏数组；
5. 将稀疏数组存入文件中。

代码实现如下：

//创建原始数组
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();
}

总结

通过本文的介绍，我们可以了解到稀疏数组的实现方法和应用场景。在编写程序时，可以结合实际情况，采用恰当的数据结构和算法，提高程序的运行效率和稳定性。