稀疏数组小记

稀疏数组

问题引入

基本介绍

• 当一个数组中大部分元素为&＃xff10;&＃xff0c;或者为同一个值的数组时&＃xff0c;可以使用稀疏数组来保存该数组。
• 稀疏数组的处理方法是:
  • 1.记录数组一共有几行几列&＃xff0c;有多少个不同的值
  • 2.把具有不同值的元素的行列及值记录在一个小规模的数组中&＃xff0c;从而缩小程序的规模

实例应用

• 使用稀疏数组&＃xff0c;来保留类似前面的二维数组(棋盘、地图等等)
• 把稀疏数组存盘&＃xff0c;并且可以从新恢复原来的二维数组
• 数整体思路分析
  

实现代码

package com.atguigu.sparsearray;import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;public class SparseArray {public static void main(String[] args) {SparseArray sparse &＃61; new SparseArray();// 创建一个原始的二维数组 11*11// 0&＃xff1a;表示没有棋子&＃xff0c;1表示黑子&＃xff0c;2表示蓝色的子int chessArr1[][] &＃61; new int[11][11];chessArr1[1][2] &＃61; 1;chessArr1[2][3] &＃61; 2;// 输出原始的二维数组System.out.println("原始的二维数组~");// for (int[] row : chessArr1) {// for (int data : row) {// System.out.printf("%d\t", data);// }// System.out.println();// }for (int[] row : chessArr1) {for (int data : row) {System.out.print(data &＃43; "\t");}System.out.println();}// 将二维数组转化为稀疏数组// 1.先遍历二维数组&＃xff0c;得到非零数据的个数int sum &＃61; 0;for (int i &＃61; 0; i < 11; i&＃43;&＃43;) {// 遍历行for (int j &＃61; 0; j < 11; j&＃43;&＃43;) {if (chessArr1[i][j] !&＃61; 0) {sum&＃43;&＃43;;}}}// System.out.println("sum &＃61; " &＃43; sum);// 2.创建对应的系数数组int sparseArr[][] &＃61; new int[sum &＃43; 1][3];// 给稀疏数组赋值sparseArr[0][0] &＃61; 11; // 存着二维数组有多少rowsparseArr[0][1] &＃61; 11;// 存着二维数组有多少rcolsparseArr[0][2] &＃61; sum;// 遍历二维数组&＃xff0c;将非零的值存放到稀疏数组中int count &＃61; 0; // 作用:count用于记录是第几个非零数据for (int i &＃61; 0; i < 11; i&＃43;&＃43;) {for (int j &＃61; 0; j < 11; j&＃43;&＃43;) {if (chessArr1[i][j] !&＃61; 0) { // i &＃61; 1,j &＃61; 2count&＃43;&＃43;;sparseArr[count][0] &＃61; i;// 相当于将二维数组中数组的row值存起来sparseArr[count][1] &＃61; j;// 相当于将二维数组中数组的col值存起来sparseArr[count][2] &＃61; chessArr1[i][j];}}}// 输出稀疏数组的形式System.out.println();System.out.println("得到的稀疏数组为&＃xff1a;");for (int i &＃61; 0; i < sparseArr.length; i&＃43;&＃43;) {// System.out.printf("%d\t%d\t%d\t\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);for (int j &＃61; 0; j < sparseArr[i].length; j&＃43;&＃43;) {System.out.print(sparseArr[i][j] &＃43; "\t");// System.out.printf("%d\t", data);}System.out.println();}System.out.println("稀疏数组打印完毕...");System.out.println("****************将稀疏数组存放到磁盘中****************************");//调用写出稀疏数组的方法String fileWritePath&＃61;"E:\\B站Java学习资料存放\\算法与数据结构\\笔记代码课件资料\\课件\\emp.data";sparse.writeSparseArray(fileWritePath, sparseArr);System.out.println("******************稀疏数组存到磁盘中完毕*************************");//将磁盘中的稀疏数组读取出来int[][] readSparseArray &＃61; sparse.readSparseArray(fileWritePath);/// 将稀疏数组转化为二维数组// 1.读取稀疏数组的第一行&＃xff0c;根据第一行的数据创建二维数组int chessArr2[][] &＃61; new int[readSparseArray[0][0]][sparseArr[0][1]];// 2.读取稀疏数组的后几行数据&＃xff08;从第二行开始&＃xff09;&＃xff0c;并赋值给原始的二维数组for (int i &＃61; 1; i < sparseArr.length; i&＃43;&＃43;) {int j &＃61; 0;chessArr2[sparseArr[i][j]][sparseArr[i][j &＃43; 1]] &＃61; sparseArr[i][j &＃43; 2];}// 恢复后的二维数组System.out.println();System.out.println("恢复后的二维数组");for (int[] data1 : chessArr2) {for (int data : data1) {System.out.printf("%d\t", data);}System.out.println();}}/*** * &＃64;param filePath 输入文件路径* &＃64;param sparseArr 要输出的稀疏数组* &＃64;return 是否输出成功*/public boolean writeSparseArray(String fileWritePath,int[][] sparseArr ){// 2.创建对应的流FileWriter fw &＃61; null;try {// 将稀疏数组存到磁盘中去// 1.指定打印的文件File file &＃61; new File(fileWritePath);if (!(file.exists())) {System.out.println("文件不存在创建中...");file.createNewFile();System.out.println("文件创建成功");}fw &＃61; new FileWriter(file);// 3.对应的具体写出操作// 遍历稀疏数组for (int i &＃61; 0; i < sparseArr.length; i&＃43;&＃43;) {
// fw.write(sparseArr[i][0] &＃43; "\t" &＃43; sparseArr[i][1] &＃43; "\t" &＃43; sparseArr[i][2] &＃43; "\r\n" );for(int j &＃61; 0 ; j < sparseArr[i].length; j&＃43;&＃43;){fw.write(sparseArr[i][j] &＃43; "\t"); }fw.write("\r\n");}} catch (Exception e) {e.printStackTrace();return false;} finally {// 4.关闭流try {fw.close();} catch (IOException e) {// TODO Auto-generated catch blocke.printStackTrace();return false;}}return true;}/*** 读入稀疏数组* &＃64;param readFilePath 读入文件的路径* &＃64;return 返回一个稀疏数组*/public int[][] readSparseArray(String readFilePath){BufferedReader br &＃61; null;// 创建稀疏数组int[][] sparseArray &＃61; null;try {// 1.创建处理流br &＃61; new BufferedReader(new FileReader(new File(readFilePath)));// 2.读入文件boolean isNotRead &＃61; false;// 控制sparseArray数组只创建一次String str;// 装从文件中遍历出来的数据int curCount &＃61; 0;int len;while ((str &＃61; br.readLine()) !&＃61; null) {// 使用readLine的原因是因为它不包含换行符String[] split &＃61; str.split("\t");if (!isNotRead) {// 根据磁盘中文件将稀疏数组创建起来&＃xff1a;isNotRead--》控制只创建一次sparseArray &＃61; new int[Integer.parseInt(split[2]) &＃43; 1][3];sparseArray[curCount][0] &＃61; Integer.parseInt(split[0]);sparseArray[curCount][1] &＃61; Integer.parseInt(split[1]);sparseArray[curCount][2] &＃61; Integer.parseInt(split[2]);curCount&＃43;&＃43;;isNotRead &＃61; true;} else {sparseArray[curCount][0] &＃61; Integer.parseInt(split[0]);sparseArray[curCount][1] &＃61; Integer.parseInt(split[1]);sparseArray[curCount][2] &＃61; Integer.parseInt(split[2]);curCount&＃43;&＃43;;}}System.out.println("**********成功写出*************");} catch (IOException e) {e.printStackTrace();} finally {if (br !&＃61; null) {try {br.close();} catch (IOException e) {// TODO Auto-generated catch blocke.printStackTrace();}}}return sparseArray;}}