稀疏数组是一种压缩后的数组，把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
- 原数组中存在大量的无效数据，占据了大量的存储空间，真正有用的数据却少之又少
- 压缩存储可以节省存储空间以避免资源的不必要的浪费，在数据序列化到磁盘时，压缩存储可以提高IO效率
Scala
class Node(val row: Int, val col: Int, val value: Int)
//稀疏数组实现
def main(args: Array[String]): Unit = {
//先使用二维数组，映射棋盘
val RowSize = 11
val ColSize = 11
val chessMap: Array[Array[Int]] = Array.ofDim[Int](RowSize, ColSize)
//初始化
chessMap(1)(2) = 1 //表示黑子
chessMap(2)(3) = 2 //表示蓝子
chessMap(3)(5) = 1 //表示黑子
chessMap(6)(8) = 2 //表示蓝子
println("原始棋盘")
for (row <- chessMap) {
for (item <- row) {
printf("%d ", item)
}
println()
}
//将chessMap转成稀疏数组
//对原始的二维数组进行压缩
// class Node (row ,col ,value)
//创建一个ArrayBuffer , 可以动态的添加数据
//使用Node 对象，表示一行数据
val sparseArray = ArrayBuffer[Node]()
//放入第一行数据
val node = new Node(RowSize, ColSize, 0)
sparseArray.append(node)
//遍历chessMap ,如果发现有非0的值，就创建一个Node对象，并加入到sparseArray
// for (i <- 0 until chessMap.length) {
// for (j <- 0 until chessMap(i).length) {
// if (chessMap(i)(j) != 0) { //有效数据，需要保存
// sparseArray.append(new Node(i, j, chessMap(i)(j)))
// }
// }
// }
for (i <- 0 until (chessMap.length)) {
for (j <- 0 until (chessMap(i).length)) {
//判断该值是否为0，如果不为0就保存
if (chessMap(i)(j) != 0) {
//构建一个Node
val node = new Node(i, j, chessMap(i)(j))
//加入到稀疏数组
sparseArray.append(node)
}
}
}
//遍历chessMap ,如果发现有非0的值，就创建一个Node对象，并加入到sparseArray
println("稀疏数组情况是")
for (i <- 0 until sparseArray.length) { val node = sparseArray(i) printf("%d\t%d\t%d\n", node.row, node.col, node.value) } // 将稀疏数组恢复成原始的棋盘 //思路 //1. 读取稀疏数组的第一行，创建一个二维棋盘chessMap2 //2. 遍历（从稀疏数组的第二行）， 每读取到一个Node ,就将对应的值，恢复到chessMapR //存盘 //读盘 ->
//稀疏数组 -> 原始数组
//读取稀疏数组的第一个节点
val newNode = sparseArray(0)
val rowSize2 = newNode.row
val colSize2 = newNode.col
val chessMapR = Array.ofDim[Int](rowSize2, colSize2)
for (i <- 1 until sparseArray.length) {
val node = sparseArray(i)
chessMapR(node.row)(node.col) = node.value
}
println("从稀疏数组恢复后的数组")
for (row <- chessMapR) {
for (item <- row) {
printf("%d ", item)
}
//换行
println()
}
}Java
public static void main(String[] args) {
//创建一个二维数组 11*11
//0表示没有棋子，1表示黑棋，2表示蓝棋
int[][] chessArr = new int[11][11];
chessArr[1][2] = 1;
chessArr[1][3] = 1;
chessArr[2][3] = 2;
chessArr[2][4] = 2;
//输出原始的二维数组
System.out.println("原始的二维数组：");
for (int i = 0; i < chessArr.length; i++) {
for (int j = 0; j < chessArr[i].length; j++) {
System.out.print(chessArr[i][j] + "\t");
}
System.out.println();
}
//将二维数组转换为稀疏数组
//1.先遍历二维数组得到非零数据的个数
int sum = 0;
for (int[] row : chessArr) {
for (int item : row) {
if (item != 0) sum++;
}
}
//2.创建对应的系数数组
int[][] sparseArr = new int[sum + 1][3];
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;
//遍历二维数组将非零的值存放到稀疏数组
int count = 0;
for (int i = 0; i < chessArr.length; i++) {
for (int j = 0; j < chessArr[i].length; j++) {
if (chessArr[i][j] != 0) {
count++;
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = chessArr[i][j];
}
}
}
//输出稀疏数组
System.out.println();
System.out.println("稀疏数组：");
for (int i = 0; i < sparseArr.length; i++) {
System.out.println(sparseArr[i][0] + "\t" + sparseArr[i][1] + "\t" + sparseArr[i][2]);
}
//将稀疏数组恢复成二维数组
//1.先读取稀疏数组的第一行，根据第一行创建二维数组
int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
//2.读取稀疏数组后几行赋值给二维数组
//注意这里是从第二行开始
for (int i = 1; i < sparseArr.length; i++) {
chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
System.out.println();
System.out.println("恢复后的二维数组：");
for (int[] row : chessArr2) {
for (int data : row) {
System.out.print(data + "\t");
}
System.out.println();
}
}python
# 稀疏数组
m = n = 6 # 6X6二维数组
arrys = [[0 for i in range(m)] for i in range(n)]
arrys[1][2] = 1 # 数组赋值
arrys[3][5] = 2
"""[[0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 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]]"""
# 自动生成稀疏数组
line = len(arrys) # 获取原数组行列数
column = len(arrys[0])
value_count = 0 # 值计数器
for i, v in enumerate(arrys): # 循环数组每一个元素找到有多少个元素有值
for ii, vv in enumerate(v):
if vv:
value_count += 1
"""稀疏数组 ： 有原数组的value个数+1 行，
有三列 其中第一行 也就是sparse_array[0]比较特别，sparse_array[0][0]表示原数组的行数 sparse_array[0][1]表示原数组的列数
sparse_array[0][2]表示原数组的value个数。
其余稀疏数组的 每一行表示 一个原数组的value [x][0]代表这个元素位于原数组的行 [x][1]代表列 [x][2]代表value具体的值
"""
sparse_array = [[0 for i in range(value_count + 1)] for i in range(3)] # 创建稀疏数组
sparse_array[0][0] = line
sparse_array[0][1] = column
sparse_array[0][2] = value_count
s_count = 1 # 计数器
for i, v in enumerate(arrys): # 给稀疏数组赋值
for ii, vv in enumerate(v):
if vv:
sparse_array[s_count][0] = i
sparse_array[s_count][1] = ii
sparse_array[s_count][2] = vv
s_count += 1
"""sparse_array : [[6, 6, 2], [1, 2, 1], [3, 5, 2]]"""
# 从稀疏数组还原到原数组
old_arry = [[0 for i in range(sparse_array[0][0])] \
for i in range(sparse_array[0][1])] # 生成原二维数组
for k, val in enumerate(sparse_array):
if k == 0:
continue
old_arry[val[0]][val[1]] = val[2]C#
using System;
namespace 数据结构
{
public class SparseArray
{
static void Main(string[] args)
{
#region 创建原始二维数组
//0表示没有棋子，1表示白棋，2表示黑棋
int row = 11;
int col = 11;
int[,] chessAarry1 = new int[row, col];
chessAarry1[1, 2] = 1;
chessAarry1[2, 3] = 2;
chessAarry1[5, 6] = 1;
chessAarry1[3, 5] = 2;
//打印二维数组
Console.WriteLine("打印原始二维数组：");
for (int r = 0; r < chessAarry1.GetLength(0); r++)
{
for (int i = 0; i < chessAarry1.GetLength(1); i++) { Console.Write($"{chessAarry1[r, i]}\t"); } Console.WriteLine(""); } #endregion #region 创建稀疏数组 //（1）统计原始二维数组有效数据 int sum = 0; foreach (var item in chessAarry1) { if (item > 0) sum++;
}
int[,] sparseArray = new int[sum + 1, 3];
sparseArray[0, 0] = row;
sparseArray[0, 1] = col;
sparseArray[0, 2] = sum;
//（2）从原始二维数组读取有效数据到稀疏数组
int insert = 0;
for (int r = 0; r < chessAarry1.GetLength(0); r++)
{
for (int i = 0; i < chessAarry1.GetLength(1); i++) { var val = chessAarry1[r, i]; if (val > 0)
{
insert++;
sparseArray[insert, 0] = r;
sparseArray[insert, 1] = i;
sparseArray[insert, 2] = val;
}
if (sum == insert) break;
}
if (sum == insert) break;
}
//打印稀疏数组
Console.WriteLine("打印稀疏数组:");
for (int r = 0; r < sparseArray.GetLength(0); r++)
{
Console.WriteLine($"{sparseArray[r, 0]}\t{sparseArray[r, 1]}\t{sparseArray[r, 2]}");
}
#endregion
#region 恢复原始二维数组
//（1）创建所有元素都为0的二维数组
int row2 = sparseArray[0, 0];
int col2 = sparseArray[0, 1];
int val2 = sparseArray[0, 2];
int[,] chessAarry2 = new int[row2, col2];
//（2）从稀疏数组读取有效数据到原始二维数组
for (int r = 1; r < sparseArray.GetLength(0); r++)
{
row2 = sparseArray[r, 0];
col2 = sparseArray[r, 1];
val2 = sparseArray[r, 2];
chessAarry2[row2, col2] = val2;
}
//打印二维数组
Console.WriteLine("打印原始二维数组：");
for (int r = 0; r < chessAarry2.GetLength(0); r++)
{
for (int i = 0; i < chessAarry2.GetLength(1); i++)
{
Console.Write($"{chessAarry2[r, i]}\t");
}
Console.WriteLine();
}
#endregion
}
}
}
文章评论