[数据结构与算法]稀疏数组(Java代码的实现)

稀疏数组

• 当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组 可以帮助我们节省空间

  其中稀疏数组的处理方法是:

• 记录数组一共有几行几列，有多少个不同的值

• 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

稀疏数组的实战（五子棋的编写 并保存到文件当中）

package com.song.sparse;

import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

/**
 * @author sc
 * 完成一个棋盘操作(11 X 11) 二维数组 变成 稀疏数组
 */
public class SparseArray {
    public static void main(String[] args) {
        //0默认为空 1默认为白子 2默认为黑子
        int[][] chessArr = new int[11][11];

        //默认 第二行 第三列 有一颗白子  第三行 第四列有颗黑子
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        //chessArr[4][6] = 1;
        //计算 棋子个数
        int num = 0;
        //遍历原始棋盘
        for (int[] row : chessArr) {
            for (int data : row) {
                if (data != 0) {
                    num++;
                }
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
        //将数组 转换为稀疏数组 记住稀疏数组只有三列
        int[][] sparseArr = new int[num + 1][3];
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = num;

        //System.out.println("num=" + num);
        int count = 0; //用于计算是第几个非零数
        //将二维数组转换为稀疏数组
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;//放行数
                    sparseArr[count][1] = j;//放列数
                    sparseArr[count][2] = chessArr[i][j];//存放值
                }
            }
        }

        //遍历稀疏数组(将稀疏数组存放到文件当中) 打印到控制台
        for (int i = 0; i < sparseArr.length; i++) {
            System.out.printf("%d\t%d\t%d\n", sparseArr[i][0], sparseArr[i][1],sparseArr[i][2]);
        }
        String s = "";//定义一个字符串 将二维数组变为字符串
        for (int[] ints : sparseArr) {
            for (int anInt : ints) {
                s += anInt+"\t";
            }
            s+="\n";
        }
        //创建文件 Mydata
        File file = new File("Mydata");
        //创建输出流
        FileWriter fileWriter = null;
        try {
            fileWriter = new FileWriter(file, false);
            //将数组存到文件当中 数组变为字符串 字符串直接通过输出流写入到文件当中
            //System.out.println(s);
            fileWriter.write(s);
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            //关闭流
            if (fileWriter != null) {
                try {
                    fileWriter.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
        //通过稀疏数组 转换为二维数组(读取文件当中的稀疏数组)
        System.out.println("===================文件读取 转换为 字符串 然后将字符串转换为稀疏数组 再转为二维数组===================");
        //接收文件当中内容
        String s1 = "";

        //从文件当中读取稀疏数组
        FileReader fr = null;
        try {
            //流的创建
            fr = new FileReader(file);
            //读取文件的内容存放在cbuf数组中 ，一般为char[1024]
            char[] cbuf = new char[1024];
            int len;//记录每次读取的个数
            while ((len = fr.read(cbuf)) != -1) {
                //将字符读入数组。如果已到达流的末尾，则返回 -1。否则返回本次读取的字符数。
                s1 =new String(cbuf, 0, len);
            }
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (fr != null) {
                //关闭流资源
                try {
                    fr.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
        //读取一下
        //System.out.println(s1);
        //将字符串变为稀疏数组
        String[] split = s1.split("\n");//按照换行分割 记录行数
        //稀疏数组
        System.out.println("从Mydata文件当中读取到数据---》稀疏数组");
        int sparseArr2[][] = new int[split.length][3];
        for(int i= 0 ;i<split.length;i++){
            String[] split1 = split[i].split("\t");//按照空格分割
            for(int j=0 ;j<3;j++){
                sparseArr2[i][j] = Integer.parseInt(split1[j]);//得到稀疏数组
            }
        }
        //遍历稀疏数组(将稀疏数组存放到文件当中) 打印到控制台
        for (int i = 0; i < sparseArr2.length; i++) {
            System.out.printf("%d\t%d\t%d\n", sparseArr2[i][0], sparseArr2[i][1], sparseArr2[i][2]);
        }

        //变为二维数组
        int chessArr2 [][] = new int[sparseArr2[0][0]][sparseArr2[0][1]];
        //往二维数组里面赋值 从第二行开始
        for (int i=1;i<sparseArr2.length;i++){
            chessArr2[sparseArr2[i][0]][sparseArr2[i][1]] = sparseArr2[i][2];
        }

        //遍历二维数组
        System.out.println("稀疏数组恢复成二维数组");
        for (int[] ints : chessArr2) {
            for (int anInt : ints) {
                System.out.printf("%d\t",anInt);
            }
            System.out.println();
        }
    }
}

#控制台打印的结果
0	0	0	0	0	0	0	0	0	0	0	
0	0	1	0	0	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	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	
11	11	2
1	2	1
2	3	2
===================文件读取 转换为 字符串 然后将字符串转换为稀疏数组 再转为二维数组===================
从Mydata文件当中读取到数据---》稀疏数组
11	11	2
1	2	1
2	3	2
稀疏数组恢复成二维数组
0	0	0	0	0	0	0	0	0	0	0	
0	0	1	0	0	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	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	

Process finished with exit code 0

可以换成BufferedWriter/BufferedRead流来进行文件的存储 都其余差不多

package com.rg.java;

import java.io.*;

/**
 * @author sc

 * 稀疏数组的应用
 */
public class SparseTest {
    public static void main(String[] args) {
        //创建普通二维数组
        int Array1[][] = new int[11][11];
        //给定位置赋值
        Array1[1][2] = 1;
        Array1[2][3] = 2;
        Array1[5][6] = 9;
        //将二维数组遍历出来
        int index = 0;//用来计数有效值的个数
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (Array1[i][j] != 0) {
                    index++;
                }
                System.out.print(Array1[i][j] + "\t");
            }
            System.out.println();
        }
//        System.out.println(index);
        //根据普通二维数组创建稀疏数组
        int sparseArray[][] = new int[index + 1][3];
        int sum = 0;//用来表示稀疏数组
        sparseArray[0][0] = Array1.length;
        sparseArray[0][1] = Array1.length;
        sparseArray[0][2] = index;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (Array1[i][j] != 0) {
                    sum++;
                    sparseArray[sum][0] = i;//在普通二维数组中所在行的位置
                    sparseArray[sum][1] = j;//在普通二维数组中所在列的位置
                    sparseArray[sum][2] = Array1[i][j];//在普通二维数组中此元素的值
                }
            }
        }
        System.out.println();
        //遍历稀疏数组
        for (int i = 0; i < sparseArray.length; i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print(sparseArray[i][j] + "\t");
            }
            System.out.println();
        }
        //创建一个输出流将控制台数据保存在map.data中
        BufferedWriter butw = null;
        try {
            butw = new BufferedWriter(new FileWriter("map.data"));
            for (int i = 0; i < sparseArray.length; i++) {
                for (int j = 0; j < 3; j++) {
                    butw.write((sparseArray[i][j] + "\t"));
                }
                butw.write("\n");
            }
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            try {
                butw.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        System.out.println();

        //通过输入流将稀疏数组变为普通二维数组
        BufferedReader bufferedReader = null;
        int arr2[][] = new int[index + 1][3];
        int getNum = 0;
        String line;
        try {
            bufferedReader = new BufferedReader(new FileReader("map.data"));
            while ((line=bufferedReader.readLine())!=null){
                String[] temp = line.split("\t");
                for (int j = 0; j < temp.length; j++) {
                    arr2[getNum][j]=Integer.parseInt(temp[j]);
                }
                getNum++;
            }
        } catch (IOException ex) {
            ex.printStackTrace();
        } finally {
            try {
                bufferedReader.close();
            } catch (IOException ex) {
                ex.printStackTrace();
            }
        }

        int[][] Array4 = new int[arr2[0][0]][arr2[0][1]];
        for(int i=1;i<arr2.length;i++){
            for(int j=0;j<3;j++){
                Array4[arr2[i][0]][arr2[i][1]] = arr2[i][2];
            }
        }
        //遍历普通二维数组
        System.out.println();
        for(int i=0;i<11;i++){
            for(int j=0;j<11;j++){
                System.out.print(Array4[i][j]+"\t");
            }
            System.out.println();
        }
    }
}