美文网首页Java数据结构和算法
数据结构之 稀疏数组

数据结构之 稀疏数组

作者: 测试员 | 来源:发表于2019-08-22 09:30 被阅读0次

作用

当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。


实现思路

1)记录数组一共有几行几列,有多少个不同的值
2)把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模


实现代码

import java.io.*;
import java.util.Scanner;

/**
 * @author Yuan_9826
 * 这是一个稀疏数组工具类
 *
 * 稀疏数组介绍
 */
public class SparseArrayUtils {

    /**
     * 将二维数组转为稀疏数组 数组 [行][列]
     *
     * @param arrs   传入的二维数组
     * @param row    行
     * @param column 列
     * @return 转换之后的稀疏数组
     */
    public static int[][] ArraytoSparse(int[][] arrs, int row, int column) {
//        1.拿到这个数组的非0数据的个数 count
        int count = effectiveCount(arrs);
//        2.创建稀疏数组:二维数组[count+1][3],
        int[][] sparseArray = new int[count + 1][3];
//        3.赋值
        sparseArray[0][0] = row;
        sparseArray[0][1] = column;
        sparseArray[0][2] = count;
        int effective = 1;
        for (int i = 0; i < arrs.length; i++) {
            for (int j = 0; j < arrs.length; j++) {
                if (arrs[i][j] != 0) {
                    sparseArray[effective][0] = i;
                    sparseArray[effective][1] = j;
                    sparseArray[effective][2] = arrs[i][j];
                    effective++;
                }
            }
        }

        return sparseArray;
    }


    /**
     * @return 二维数组的有效值个数
     */
    public static int effectiveCount(int[][] arrs) {
        int count = 0;
        for (int[] arr : arrs) {
            for (int i : arr) {
                if (i != 0) {
                    count++;
                }
            }
        }
        return count;
    }


    /**
     * @param sparse 稀疏数组
     * @param name   文件名
     * @param url    保存路径
     *               将稀疏数组写到本地临时保存
     */
    public static void writeArray(int[][] sparse, String url, String name) {
        try {
            FileWriter out = new FileWriter(url + name);
            for (int i = 0; i < sparse.length; i++) {
                for (int j = 0; j < 3; j++) {
                    out.write(sparse[i][j] + " ");
                }
                out.write("\r\n");
            }
            out.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * 读取本地文件并创建稀疏数组返回,如果返回null表示读取失败
     *
     * @param url  读取路径
     * @param name 文件名
     * @return 返回一个稀疏数组
     */
    public static int[][] returnArray(String url, String name) {
        int initRow = readLine(url, name);
        if (initRow == 0 ) {
            return null;
        }
        int[][] sparse = new int[initRow][3];
        try {
            BufferedReader in = new BufferedReader(new FileReader(url + name));
            String line;
            int rowNumber = 0;
            while ((line = in.readLine()) != null) {
                String[] strLIne = line.split(" ");
                sparse[rowNumber][0] = Integer.parseInt(strLIne[0]);
                sparse[rowNumber][1] = Integer.parseInt(strLIne[1]);
                sparse[rowNumber][2] = Integer.parseInt(strLIne[2]);
                rowNumber++;
            }

        } catch (IOException e) {
            e.printStackTrace();
            return null;
        }
        return sparse;
    }


    /**
     * 读取文件行数
     *
     * @param name 文件位置
     * @return 文件行数
     */
    public static int readLine(String url, String name) {
        int count = 0;
        if ((url + name).length() <= 0) {
            return 0;
        }
        try {
            FileInputStream fis = new FileInputStream(new File(url + name));
            Scanner scanner = new Scanner(fis);
            while (scanner.hasNextLine()) {
                String s = scanner.nextLine();
                count++;
            }
        } catch (IOException e) {
            e.printStackTrace();
            return 0;
        }
        return count;
    }

    /**
     * 利用稀疏数组转为原来的数组
     *
     * @param sparse 稀疏数组
     * @return 原来的数组11X11
     */
    public static int[][] sparseToArray(int[][] sparse) {
        int[][] arr = new int[sparse[0][0]][sparse[0][1]];
        for (int i = 1; i < sparse.length; i++) {
            arr[sparse[i][0]][sparse[i][1]] = sparse[i][2];
        }
        return arr;
    }
}

相关文章

  • 数据结构之 稀疏数组

    作用 当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。 实现思路 1)记录数组一...

  • 数据结构002之稀疏数组

    什么是稀疏数组? 稀疏数组可以看做是对普通数组的压缩,普通数组是指无效数据量远大于有效数据量的数组,为什么要进行压...

  • java数据结构之稀疏数组

    今天学习了数组中的一种-叫做稀疏数组。什么叫稀疏数组呢?如果一个数组(包括多维数组)中的大部分元素为0,或者为同一...

  • 数组之稀疏数组

    稀疏数组,程序员听了,难道冥冥之中是天意?和头发一样的稀疏。 其实不然,例如:下棋的棋盘(11*11),用二维数组...

  • 数据结构--稀疏数组

    概述 稀疏数组也是一种数组(总是二维的),是一种多维数组的数组压缩技术。比如存在一个的数组,但是数组中只有3个元素...

  • 算法之稀疏数组

    当一个数组的元素包含大量的0时,或者为同一个值的数组时,可以使用稀疏数组来保存数组. 稀疏数组的处理方法: 1,记...

  • Java数据结构之稀疏数组和队列

    稀疏数组: 应用场景,实际的需求: 编写五子棋程序中,有存档退出和保存上一句的功能。 实现: 用0代表还没有下的位...

  • 重温:数据结构与算法 - 03数组

    数据结构与算法之美 - 数组 数据结构与算法之美-学习大纲 什么数组? 数组是一种 线性表 数据结构。它用一组 连...

  • 数据结构入门教程-队列

    上节我们简单的了解了什么是稀疏数组以及通过一个案例来简单分析它,关于它的更多详情请移驾数据结构入门教程-稀疏数组,...

  • 重学数据结构 --- 分类+稀疏数组

    一、数据结构的分类 1. 数据结构两大类 线性结构和非线性结构 1) 线性结构 线性结构是最常见的数据结构,特点是...

网友评论

    本文标题:数据结构之 稀疏数组

    本文链接:https://www.haomeiwen.com/subject/keygsctx.html