数组 – 稀疏数组
大家好，又见面了，我是你们的朋友全栈君。
文章目录
一，稀疏数组
1.定义
稀疏数组可以看做是普通数组的压缩，但是这里说的普通数组是值无效数据量远大于有效数据量的数组
形如：
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 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其稀疏数组形式：
11 11 2
1 2 1
2 4 22.存储
刚说到稀疏数组是一种压缩后的数组，为什么要进行压缩存储呢？
- 原数组中存在大量的无效数据，占据了大量的存储空间，真正有用的数据却少之又少
- 压缩存储可以节省存储空间以避免资源的不必要的浪费，在数据序列化到磁盘时，压缩存储可以提高IO效率
3.存储方式
1.普通存储
第一行存储原始数据总行数，总列数，总的非0数据个数
接下来每一行都存储非0数所在行，所在列，和具体值
形如：
rows cols n
r1 c1 val1
r2 c2 val2
. . .
. . .
rn cn valneg :
11 11 2
1 2 1
2 4 22.链式存储
以这个为例：
0 0 0 0
0 1 0 0
0 0 2 0
0 0 3 0a.普通链式存储
# 一，稀疏数组
b.行式链式存储
在这里插入图片描述
c.十字链式存储
在这里插入图片描述
4.代码实现
/** * @Description: 稀疏数组 ---> 数组中有很多无效数据，压缩数组 * @Author: Kevin * @CreateDate: 2019/7/2 22:39 * @UpdateUser: Kevin * @UpdateDate: 2019/7/2 22:39 * @UpdateRemark: 修改内容 * @Version: 1.0 */
public class SparseArray {
/** * <p> * 稀疏数组可以简单的看作为是压缩，在开发中也会使用到。比如将数据序列化到磁盘上，减少数据量，在IO过程中提高效率等等。 * * <p> * 为什么要进行压缩？ * - 由于稀疏矩阵中存在大量的“空”值，占据了大量的存储空间，而真正有用的数据却少之又少， * - 且在计算时浪费资源，所以要进行压缩存储以节省存储空间和计算方便。 * </p> * * </p> * @param args */
public static void main(String[] args) {
/** * 初始化二维数组 * <p> * 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 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 * </p> */
//初始化原数组
int[][] array = new int[11][11];
array[1][2] = 1;
array[2][4] = 2;
for(int[] row : array){
for(int item : row){
System.out.printf("%d\t",item);
}
}
System.out.println("---------> 二维数组转稀疏数组");
/** * 稀疏数组 * <p> * 11 11 2 * 1 2 1 * 2 4 2 * </p> */
//得到非0数据数
int sum = 0;
for (int i = 0;i<11;i++){
for(int j = 0;j<11;j++){
if(array[i][j] != 0){
sum++;
}
}
}
//创建稀疏数组
int[][] sparseArray = new int[sum+1][3];
//给稀疏数组赋值
sparseArray[0][0] = 11;
sparseArray[0][1] = 11;
sparseArray[0][2] = sum;
//将非0的数放入稀疏数组
//count：标识第几个非0数
int count = 0;
for (int i = 0;i<11;i++){
for(int j = 0;j<11;j++){
if(array[i][j] != 0){
count++;
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = array[i][j];
}
}
}
//遍历稀疏数组
for(int i = 0;i<sparseArray.length;i++){
System.out.printf("%d%d%d\t",sparseArray[i][0],sparseArray[i][1],sparseArray[i][2]);
}
System.out.println("----------->稀疏数组转回原始数组");
/** * 恢复的二维数组 * <p> * 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 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 * </p> */
int[][] oldArray = new int[sparseArray[0][0]][sparseArray[0][1]];
//将原来非0的数填充回去
for(int i = 1;i<=count;i++){
oldArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
//遍历刚转回的原始数组
for(int[] row : oldArray){
for(int item : row){
System.out.printf("%d\t",item);
}
}
}
}3.将稀疏数组存到此磁盘中
我们可以使用java的IO流将稀疏数组存放到磁盘中，原数组和稀疏数组比较，肯定是稀疏数组体积更小，占用空间更小
/** * 将稀疏数组存入磁盘（文件） * */
public static void sparseArrayToIo(int[][] sparseArray) throws Exception {
File file = new File("sparseArray.txt");
if(!file.exists()){
file.createNewFile();
}
FileWriter writer = new FileWriter(file);
for(int i =0; i < sparseArray.length; i++) {
for(int j = 0; j < 3; j++) {
writer.write(sparseArray[i][j]);
}
}
writer.flush();
writer.close();
}4.从磁盘中读取稀疏数组
在这里有个缺陷就是我不能动态的知道稀疏数组一共有几行，所以我选择传参的方式，这样其实是不太友好的
/** * 读文件获取稀疏数组(获取指定行数的稀疏数组)【不足】 * @return */
public static int[][] sparseArrayFromIo(int lineNums) throws Exception {
FileReader reader = new FileReader("sparseArray.txt");
int getNum = 0;
int[][] sparseArray = new int[lineNums][3];
for(int i = 0;i < lineNums;i++) {
for (int j = 0; j < 3; j++) {
getNum = reader.read();
sparseArray[i][j] = getNum;
}
}
return sparseArray;
}恢复原数组
System.out.println("----------->稀疏数组转回原始数组");
//读取磁盘中的稀疏数组
try {
int[][] sparseArrayFromIo = sparseArrayFromIo(3);
int[][] newOldArray = new int[sparseArrayFromIo[0][0]][sparseArrayFromIo[0][1]];
//将原来非0的数填充回去
for(int i = 1;i<=count;i++){
newOldArray[sparseArrayFromIo[i][0]][sparseArrayFromIo[i][1]] = sparseArrayFromIo[i][2];
}
//遍历刚转回的原始数组
for(int[] row : newOldArray){
for(int item : row){
System.out.printf("%d\t",item);
}
}
} catch (Exception e) {
e.printStackTrace();
}5.完整代码
public class SparseArray {
/** * <p> * 稀疏数组可以简单的看作为是压缩，在开发中也会使用到。比如将数据序列化到磁盘上，减少数据量，在IO过程中提高效率等等。 * * <h> * 为什么要进行压缩？ * - 由于稀疏矩阵中存在大量的“空”值，占据了大量的存储空间，而真正有用的数据却少之又少， * - 且在计算时浪费资源，所以要进行压缩存储以节省存储空间和计算方便。 * </h> * * </p> * @param args */
public static void main(String[] args) {
/** * 初始化二维数组 * <p> * 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 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 * </p> */
//初始化原数组
int[][] array = new int[11][11];
array[1][2] = 1;
array[2][4] = 2;
for(int[] row : array){
for(int item : row){
System.out.printf("%d\t",item);
}
}
System.out.println("---------> 二维数组转稀疏数组");
/** * 稀疏数组 * <p> * 11 11 2 * 1 2 1 * 2 4 2 * </p> */
//得到非0数据数
int sum = 0;
for (int i = 0;i<11;i++){
for(int j = 0;j<11;j++){
if(array[i][j] != 0){
sum++;
}
}
}
//创建稀疏数组
int[][] sparseArray = new int[sum+1][3];
//给稀疏数组赋值
sparseArray[0][0] = 11;
sparseArray[0][1] = 11;
sparseArray[0][2] = sum;
//将非0的数放入稀疏数组
//count：标识第几个非0数
int count = 0;
for (int i = 0;i<11;i++){
for(int j = 0;j<11;j++){
if(array[i][j] != 0){
count++;
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = array[i][j];
}
}
}
//遍历稀疏数组
for(int i = 0;i<sparseArray.length;i++){
System.out.printf("%d%d%d\t",sparseArray[i][0],sparseArray[i][1],sparseArray[i][2]);
}
try {
//将稀疏数组写入文件
sparseArrayToIo(sparseArray);
} catch (Exception e) {
e.printStackTrace();
}
System.out.println("----------->稀疏数组转回原始数组");
/** * 恢复的二维数组 * <p> * 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 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 * </p> */
int[][] oldArray = new int[sparseArray[0][0]][sparseArray[0][1]];
//将原来非0的数填充回去
for(int i = 1;i<=count;i++){
oldArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
//遍历刚转回的原始数组
for(int[] row : oldArray){
for(int item : row){
System.out.printf("%d\t",item);
}
}
System.out.println("----------->稀疏数组转回原始数组");
//读取磁盘中的稀疏数组
try {
int[][] sparseArrayFromIo = sparseArrayFromIo(3);
int[][] newOldArray = new int[sparseArrayFromIo[0][0]][sparseArrayFromIo[0][1]];
//将原来非0的数填充回去
for(int i = 1;i<=count;i++){
newOldArray[sparseArrayFromIo[i][0]][sparseArrayFromIo[i][1]] = sparseArrayFromIo[i][2];
}
//遍历刚转回的原始数组
for(int[] row : newOldArray){
for(int item : row){
System.out.printf("%d\t",item);
}
}
} catch (Exception e) {
e.printStackTrace();
}
}
/** * 将稀疏数组存入磁盘（文件） * */
public static void sparseArrayToIo(int[][] sparseArray) throws Exception {
File file = new File("sparseArray.txt");
if(!file.exists()){
file.createNewFile();
}
FileWriter writer = new FileWriter(file);
for(int i =0; i < sparseArray.length; i++) {
for(int j = 0; j < 3; j++) {
writer.write(sparseArray[i][j]);
}
}
writer.flush();
}
/** * 读文件获取稀疏数组(获取指定行数的稀疏数组)【不足】 * @return */
public static int[][] sparseArrayFromIo(int lineNums) throws Exception {
FileReader reader = new FileReader("sparseArray.txt");
int getNum = 0;
int[][] sparseArray = new int[lineNums][3];
for(int i = 0;i < lineNums;i++) {
for (int j = 0; j < 3; j++) {
getNum = reader.read();
sparseArray[i][j] = getNum;
}
}
return sparseArray;
}
}发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/125468.html原文链接：https://javaforall.cn
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022年4月5，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
腾讯云开发者
