浅谈Java数据结构之稀疏数组知识总结

浅谈Java数据结构之稀疏数组知识总结

稀疏数组

当一个数组中的元素大多为0或者相同元素的时候，可以用稀疏数组来压缩

稀疏数组只记录 行row 列col 值value

将下列的二维数组转为稀疏数组,如下两图所示

1.实现二维数组转为稀疏数组的步骤：

遍历数组，得到数组中 不为0的个数，并记录为sum，作为稀疏数组第0行的 value

遍历数组，将数组中不为0的数的行和列和值分别写入稀疏数组的 row col val 中

代码实现：

public class SparseArray {

public static void main(String[] args) {

// 创建一个原始二维数组

// 0表示没有棋子，1，2各表示一种棋

int chessArr[][] = new int[8][8];

chessArr[1][1] = 1;

chessArr[2][2] = 2;

// 遍历原始数组，获得不等于 0 的个数,并输出原始数组

int sum = 0;

System.out.println("原始数组：");

for (int[] ints : chessArr) {

for (int anInt : ints) {

System.out.print(anInt+"\t");

if (anInt != 0){

sum++;

}

}

System.out.println();

}

System.out.println(sum);

// 创建稀疏数组并赋值

int sparseArray[][] = new int[sum+1][3];

http:// int row = chessArr.length; // 原数组的行数

int col = chessArr[0].length; // 原数组的列数

sparseArray[0][0] = row;

sparseArray[0][1] = col;

sparseArray[0][2] = sum;

// 遍历原始数组并赋值给稀疏数组

int count = 0; // count 为计数器

for (int i = 0;i < row;i++) {

for (int j = 0;j < col;j++) {

if (chessArr[i][j] != 0) {

count++;

sparseArray[count][0] = i;

sparseArray[count][1] = j;

sparseArray[count][2] = chessArr[i][j];

}

}

}

// 输出得到的稀疏数组

System.out.println("稀疏数组为：");

for (int i = 0 ;i < sparseArray.length;i++) {

System.out.println(sparseArray[i][0]+"\t"+sparseArray[i][1]+"\t"+sparseArray[i][2]);

}

}

}

2.实现二维数组转稀疏数组的步骤

根据稀疏数组的第一行创建新的二维数组

遍历稀疏数组，将row col val 赋给新的二维数组

代码实现：

public class SparseArray {

public static void main(String[] args) {

...... // 接上一段代码

// 输出得到的稀疏数组

System.out.println("稀疏数组为：");

for (int i = 0 ;i < sparseArray.length;i++) {

System.out.println(sparseArray[i][0]+"\t"+sparseArray[i][1]+"\t"+sparseArray[i][2]);

}

// 创建新的二维数组

int newChessArray[][] = new int[sparseArray[0][0]][sparseArray[0][1]];

for (int i = 1 ;i < sparseArray.length;i++) {

newChessArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];

}

// 输出新的二维数组

System.out.println("恢复后的二维数组是：");

for (int[] ints : newChessArray) {

for (int anInt : ints) {

System.out.print(anInt+"\t");

}

System.out.println();

}

}

}

3.将稀疏数组写入磁盘

public static void main(String[] args) {

........

// 将稀疏数组存入磁盘

FileOutputShttp://tream fw = null;

try {

fw = new FileOutputStream("sparseArray.txt");

// 遍历写入磁盘

for (int i = 0; i < sparseArray.length; i++) {

for (int j = 0; j < 3; j++) {

fw.write(sparseArray[i][j]);

}

}

fw.flush();

} catch (FileNotFoundException e) {

e.printStackTrace();

} catch (IOException e) {

e.printStackTrace();

} finally {

if (fw != null){

fw.close();

}

}

}

4.从磁盘读取稀疏数组

public static void main(String[] args) {

.......

// 从磁盘读取稀疏数组

FileInputStream fi = null;

intGakguIbw newSparseArray[][] = new int[sum+1][3]; // sum 指前面二维数组有值的个数

try {

fi = new FileInputStream("sparseArray.txt");

for (int i = 0;i < newSparseArray.length;i++) {

for (int j = 0;j < 3;j++){

newSparseArray[i][j] = fi.read();

}

}

} catch (FileNotFoundException e){

e.printStackTrace();

} finally {

if (fi != null){

fi.close();

}

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。