数据结构之稀疏数组

简介: 数据结构之稀疏数组

数据结构之稀疏数组


概念

  • 当一个数组中大部分元素为0,或者为同一值的数组时,可以使用稀疏数组来保存该数组。
  • 稀疏数组的处理方式是:记录数组一共有几行几列,有多少个不同值;把具有不同值的元素和行列及值记录在一个小规模的数组中,从而缩小程序的规模
  • 如下图:左边是原始数组,右边是稀疏数组

解析

代码

package cn.tedu.sparsearray;
/**
 * @ClassName SparseArray
 * @Description
 * @Author keke
 * @Time 2022/1/3 2:58
 * @Version 1.0
 */
public class SparseArray {
    public static void main(String[] args) {
        // 创建一个原始的二维数组 11 * 11
        // 0:表示没有棋子,1表示黑子,2表示蓝子
        int[][] chessArr1 = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        // 输出原始的二维数组
        System.out.println("原始的二维数组");
        for (int[] row : chessArr1){
            for (int data : row){
                System.out.print(data + "\t");
            }
            System.out.println();
        }
        // 将二维数组 转换为 稀疏数组
        // 1.先遍历二维数组,得到非0数据的个数
        int sum = 0;
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[i].length; j++) {
                if (chessArr1[i][j] != 0){
                    sum++;
                }
            }
        }
        // 2.创建对应的稀疏数组
        int[][] sparseArr = new int[sum + 1][3];
        // 给稀疏数组赋值
        sparseArr[0][0] = chessArr1.length;
        sparseArr[0][1] = chessArr1[0].length;
        sparseArr[0][2] = sum;
        // 遍历二维数组,将非0的值存入 sparseArr 中
        // 用于记录是第几个非0数据
        int count = 0;
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[i].length; j++) {
                if (chessArr1[i][j] != 0){
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr1[i][j];
                }
            }
        }
        // 输出稀疏数组
        System.out.println("\n得到稀疏数组");
        for (int i = 0; i < sparseArr.length; i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print(sparseArr[i][j] + "\t");
            }
            System.out.println();
        }
        // 将稀疏数组恢复成原始的二维数组
        /**
         * 1.先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,
         *   比如上面的  chessArr2 = int[11][11]
         * 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("\n恢复后的二维数组");
        for (int[] row : chessArr2){
            for (int data : row){
                System.out.print(data + "\t");
            }
            System.out.println();
        }
    }
}

截图

目录
相关文章
|
4月前
|
存储 Java 程序员
数据结构之 - 深入了解数组数据结构
数据结构之 - 深入了解数组数据结构
58 6
|
4月前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
140 64
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
92 5
|
3月前
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念,并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素,以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用,还涉及到了算法逻辑的设计与优化。实验结果显示,学生能够有效掌握并运用这些知识完成指定任务。
77 4
|
4月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
62 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
4月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
42 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
5月前
|
存储 Java
java数据结构,线性表顺序存储(数组)的实现
文章介绍了Java中线性表顺序存储(数组)的实现。线性表是数据结构的一种,它使用数组来实现。文章详细描述了线性表的基本操作,如增加、查找、删除、修改元素,以及其他操作如遍历、清空、求长度等。同时,提供了完整的Java代码实现,包括MyList接口和MyLinearList实现类。通过main函数的测试代码,展示了如何使用这些方法操作线性表。
|
7月前
|
存储
【数据结构OJ题】轮转数组
力扣题目——轮转数组
51 2
【数据结构OJ题】轮转数组
|
6月前
|
存储 Java 程序员
"揭秘HashMap底层实现:从数组到链表,再到红黑树,掌握高效数据结构的秘密武器!"
【8月更文挑战第21天】HashMap是Java中重要的数据结构,采用数组+链表/红黑树实现,确保高效查询与更新。构造方法初始化数组,默认容量16,负载因子0.75触发扩容。`put`操作通过计算`hashCode`定位元素,利用链表或红黑树处理冲突。`get`和`remove`操作类似地定位并返回或移除元素。JDK 1.8优化了链表转红黑树机制,提升性能。理解这些原理能帮助我们更高效地应用HashMap。
55 0

热门文章

最新文章