【数据结构(二)】稀疏 sparsearray 数组（1）

文章目录

  • 1. 稀疏数组的应用场景
    • 1.1. 一个实际的需求
    • 1.2. 基本介绍
  • 2. 稀疏数组转换的思路分析
  • 3. 稀疏数组的代码实现
    • 3.1. 二维数组转稀疏数组
    • 3.2. 稀疏数组转二维数组
  • 4. 课后练习

1. 稀疏数组的应用场景

1.1. 一个实际的需求

问题：
    编写的五子棋程序中，有存盘退出和续上盘的功能。

在这里插入图片描述

分析问题：
    因为该二维数组的很多值是默认值 0, 因此记录了很多没有意义的数据 -> 稀疏数组

1.2. 基本介绍

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

稀疏数组的处理方法:
    ①记录数组一共有几行几列，有多少个不同的值
    ②把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

在这里插入图片描述

上图右表中：
    第[0]行表示：数组大小是6×7，共有8个不为0的值；下面每一行都代表不为0的数值所在的行列数，[1]~[8]共有8个。

2. 稀疏数组转换的思路分析

1. 步骤
    ①使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
    ②把稀疏数组存盘，并且可以从新恢复原来的二维数组数
    

2. 整体思路分析

在这里插入图片描述

二维数组 转 稀疏数组的思路

  1. 遍历 原始的二维数组，得到有效数据的个数 sum（上图为：2）
  2. 根据sum 就可以创建 稀疏数组 sparseArr int[sum + 1] [3]（上图为：[3][3]）
  3. 将二维数组的有效数据数据存入到 稀疏数组
        

稀疏数组 转 原始的二维数组的思路

  1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2 = int [11][11]
  2. 在读取稀疏数组后几行的数据，并赋给 原始的二维数组 即可。

3. 稀疏数组的代码实现

3.1. 二维数组转稀疏数组

package sparsearray;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;//可以在后面继续加棋子//输出原始的二维数组for(int[] row : chessArr1){for(int data : row){System.out.printf("%d\t", data);}System.out.println();}//将二维数组 转 稀疏数组//1.先遍历二维数组，得到非0数据的个数System.out.println("数组的长度为：" + chessArr1.length);int sum = 0;for(int i = 0; i < chessArr1.length; i++){for(int j = 0; j < chessArr1.length; j++){if(chessArr1[i][j] != 0){sum ++;}}}System.out.println("sum=" + sum);//2. 创建对应的稀疏数组int sparseArr[][] = new int[sum + 1][3];//给稀疏数组赋值sparseArr[0][0] = 11;sparseArr[0][1] = 11;sparseArr[0][2] = sum;//遍历二维数组，将非0的值存放到sparseArr中int count = 0; //count 用于记录是第几个非0数据for(int i = 0; i < chessArr1.length; i++){for(int j = 0; j < chessArr1.length; j++){if(chessArr1[i][j] != 0){count++;sparseArr[count][0] = i;sparseArr[count][1] = j;sparseArr[count][2] = chessArr1[i][j];}}}//输出稀疏数组的形式System.err.println();System.out.println("得到的稀疏数组为~~~");for(int i = 0; i < sparseArr.length; i++){System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);}System.out.println();}
}

运行结果：

在这里插入图片描述

如果在棋盘上继续加子，如在第5行第6列加一个黑子chessArr1[4][5] = 1;

代码：

package sparsearray;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;chessArr1[4][5] = 1;//输出原始的二维数组for(int[] row : chessArr1){for(int data : row){System.out.printf("%d\t", data);}System.out.println();}//将二维数组 转 稀疏数组//1.先遍历二维数组，得到非0数据的个数System.out.println("数组的长度为：" + chessArr1.length);int sum = 0;for(int i = 0; i < chessArr1.length; i++){for(int j = 0; j < chessArr1.length; j++){if(chessArr1[i][j] != 0){sum ++;}}}System.out.println("sum=" + sum);//2. 创建对应的稀疏数组int sparseArr[][] = new int[sum + 1][3];//给稀疏数组赋值sparseArr[0][0] = 11;sparseArr[0][1] = 11;sparseArr[0][2] = sum;//遍历二维数组，将非0的值存放到sparseArr中int count = 0; //count 用于记录是第几个非0数据for(int i = 0; i < chessArr1.length; i++){for(int j = 0; j < chessArr1.length; j++){if(chessArr1[i][j] != 0){count++;sparseArr[count][0] = i;sparseArr[count][1] = j;sparseArr[count][2] = chessArr1[i][j];}}}//输出稀疏数组的形式System.err.println();System.out.println("得到的稀疏数组为~~~");for(int i = 0; i < sparseArr.length; i++){System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);}System.out.println();}
}

运行结果：

在这里插入图片描述

3.2. 稀疏数组转二维数组

package sparsearray;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;chessArr1[4][5] = 1;//输出原始的二维数组for(int[] row : chessArr1){for(int data : row){System.out.printf("%d\t", data);}System.out.println();}//将二维数组 转 稀疏数组//1.先遍历二维数组，得到非0数据的个数System.out.println("数组的长度为：" + chessArr1.length);int sum = 0;for(int i = 0; i < chessArr1.length; i++){for(int j = 0; j < chessArr1.length; j++){if(chessArr1[i][j] != 0){sum ++;}}}System.out.println("sum=" + sum);//2. 创建对应的稀疏数组int sparseArr[][] = new int[sum + 1][3];//给稀疏数组赋值sparseArr[0][0] = 11;sparseArr[0][1] = 11;sparseArr[0][2] = sum;//遍历二维数组，将非0的值存放到sparseArr中int count = 0; //count 用于记录是第几个非0数据for(int i = 0; i < chessArr1.length; i++){for(int j = 0; j < chessArr1.length; j++){if(chessArr1[i][j] != 0){count++;sparseArr[count][0] = i;sparseArr[count][1] = j;sparseArr[count][2] = chessArr1[i][j];}}}//输出稀疏数组的形式System.err.println();System.out.println("得到的稀疏数组为~~~");for(int i = 0; i < sparseArr.length; i++){System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);}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.err.println();System.out.println("恢复后的二维数组");for(int[] row : chessArr2){for(int data : row){System.out.printf("%d\t", data);}System.out.println();}}
}

运行结果：

在这里插入图片描述

4. 课后练习

    
要求：
（1）在前面的基础上，将稀疏数组保存到磁盘上，比如 map.data
（2）恢复原来的数组时，读取 map.data 进行恢复

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/195839.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【VSCode】配置C/C++开发环境教程（Windows系统）

【VSCode】配置C/C++开发环境教程（Windows系统）

下载和配置MinGW编译器 首先&#xff0c;我们需要下载并配置MinGW编译器。 下载MinGW编译器&#xff0c;并将其放置在一个不含空格和中文字符的目录下。 配置环境变量PATH 打开控制面板。可以通过在Windows搜索栏中输入"控制面板"来找到它。 在控制面板中&#xf…
阅读更多...
JavaScript 浮点数运算的精度问题及解决

JavaScript 浮点数运算的精度问题及解决

JavaScript 浮点数运算的精度问题及解决 在 JavaScript 中整数和浮点数都属于 Number 数据类型&#xff0c;当浮点数做数学运算的时候&#xff0c;你经常会发现一些问题&#xff0c;举几个例子&#xff1a; 0.1 0.2 0.30000000000000004 console.log(0.1 0.2) 0.3000000…
阅读更多...
vite+vue3+electron开发环境搭建

vite+vue3+electron开发环境搭建

环境 node 18.14.2 yarn 1.22 项目创建 yarn create vite test01安装vue环境 cd test01 yarn yarn dev说明vue环境搭建成功 安装electron # 因为有的版本会报错所以指定了版本 yarn add electron26.1.0 -D安装vite-plugin-electron yarn add -D vite-plugin-electron根目…
阅读更多...
关系代数、SQL语句和Go语言示例

关系代数、SQL语句和Go语言示例

近些年&#xff0c;数据库领域发展日新月异&#xff0c;除传统的关系型数据库外&#xff0c;还出现了许多新型的数据库&#xff0c;比如&#xff1a;以HBase、Cassandra、MongoDB为代表的NoSQL数据库&#xff0c;以InfluxDB、TDEngine为代表的时序数据[1]库&#xff0c;以Neo4J…
阅读更多...
二分查找和二分答案

二分查找和二分答案

【深基13.例1】查找 题目描述 输入 n n n 个不超过 1 0 9 10^9 109 的单调不减的&#xff08;就是后面的数字不小于前面的数字&#xff09;非负整数 a 1 , a 2 , … , a n a_1,a_2,\dots,a_{n} a1​,a2​,…,an​&#xff0c;然后进行 m m m 次询问。对于每次询问&#x…
阅读更多...
Django 配置 Email Admin 详细指南

Django 配置 Email Admin 详细指南

概要 Django 是一个高级的 Python Web 框架&#xff0c;它鼓励快速开发和清洁、实用的设计。当你正在开发一个 Django 项目时&#xff0c;监控网站的运行情况是非常必要的。Django 提供了一个功能强大的 admin 界面&#xff0c;但同时也可以通过配置 email admin 来获取网站的…
阅读更多...
vue-pdf在vue框架中的使用

vue-pdf在vue框架中的使用

在components目录下新建PdfViewer/index.vue vue-pdf版本为4.3.0 <template><div :id"containerId" v-if"hasProps" class"container"><div class"right-btn"><div class"pageNum"><input v-m…
阅读更多...
2023年（第六届）电力机器人应用与创新发展论坛-核心PPT资料下载

2023年（第六届）电力机器人应用与创新发展论坛-核心PPT资料下载

一、峰会简介 大会以“聚焦电力机器人创新、助力行业数字化转型、促进产业链协同发展”为主题&#xff0c;展示电力机器人产业全景创新技术&#xff0c;探讨数字化战略下电力机器人应用前景和发展趋势。为加快推进电力机器人应用拓新&#xff0c;助力电网数字化转型升级&#…
阅读更多...
Xrdp+Cpolar实现远程访问Linux Kali桌面

Xrdp+Cpolar实现远程访问Linux Kali桌面

XrdpCpolar实现远程访问Linux Kali桌面 文章目录 XrdpCpolar实现远程访问Linux Kali桌面前言1. Kali 安装Xrdp2. 本地远程Kali桌面3. Kali 安装Cpolar 内网穿透4. 配置公网远程地址5. 公网远程Kali桌面连接6. 固定连接公网地址7. 固定地址连接测试 前言 Kali远程桌面的好处在于…
阅读更多...
B站批量取消关注

B站批量取消关注

找到关注页面&#xff1a; 右键检查或者按F12进入开发者界面 然后选console&#xff0c;在页面下面输入下面jQuery代码&#xff0c;然后按回车。复制粘贴两次这一页的博主就能全部取消大概20个 然后刷新页面&#xff0c;接着粘贴两边代码&#xff0c;循环如此即可。 $(".…
阅读更多...
【XTDrone Ubuntu20.04】XTDrone+ Ubuntu20.04 + PX4安装

【XTDrone Ubuntu20.04】XTDrone+ Ubuntu20.04 + PX4安装

XTDrone仿真平台配置 文章目录 XTDrone仿真平台配置依赖安装 ROS一键安装Marvos安装PX4 安装安装QTGroundControlXTDrone下载安装 环境&#xff1a; VMWare 16.0 Ubuntu 22.04 &#xff08;因为没人配过&#xff09;Ubuntu 20.04 参考文章&#xff1a; 仿真平台基础配置 (yuq…
阅读更多...
docker数据卷详细讲解及数据卷常用命令

docker数据卷详细讲解及数据卷常用命令

docker数据卷详细讲解及数据卷常用命令 Docker 数据卷是一种将宿主机的目录或文件直接映射到容器中的特殊目录&#xff0c;用于实现数据的持久化和共享。Docker 数据卷有以下特点&#xff1a; 数据卷可以在一个或多个容器之间共享和重用&#xff0c;不受容器的生命周期影响。…
阅读更多...
计算机毕业设计 基于SpringBoot的医院档案管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解

计算机毕业设计 基于SpringBoot的医院档案管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…
阅读更多...
C++单调向量算法：132 模式解法三枚举1

C++单调向量算法：132 模式解法三枚举1

本题不同解法 包括题目及代码C二分查找算法&#xff1a;132 模式解法一枚举3C二分查找算法&#xff1a;132 模式解法二枚举2代码最简洁C二分查找算法&#xff1a;132 模式解法三枚举1性能最佳C单调向量算法&#xff1a;132 模式解法三枚举1 分析 时间复杂度 2轮循环时间复杂…
阅读更多...
IIC总线概述和通信时序代码详细图文解析

IIC总线概述和通信时序代码详细图文解析

IIC总线 1 IIC总线概述 I2C总线两线制包括&#xff1a;串行数据SDA&#xff08;Serial Data&#xff09;、串行时钟SCL&#xff08;Serial Clock&#xff09;。总线必须由主机&#xff08;通常为微控制器&#xff09;控制&#xff0c;主机产生串行时钟&#xff08;SCL&#x…
阅读更多...
eclipse启动无法找到类（自定义监听器）

eclipse启动无法找到类（自定义监听器）

一.报错 二.排查 1.首先检查代码是否有问题 本人报错是找不到监听器&#xff0c;故检查监听器的代码和web.xml文件是否有问题 public class DoorListener implements ServletContextListener 监听器是否继承并实现ServletContextListener中的方法。 web.xml中&#xff1a; &…
阅读更多...
rabbitMQ的direct模式的生产者与消费者使用案例

rabbitMQ的direct模式的生产者与消费者使用案例

消费者C1的RoutingKey 规则按照info warn 两种RoutingKey匹配 绑定队列console package com.esint.rabbitmq.work03;import com.esint.rabbitmq.RabbitMQUtils; import com.rabbitmq.client.Channel; import com.rabbitmq.client.DeliverCallback;/*** 消费者01的消息接受*/ p…
阅读更多...
天津市专业大数据培训班，大数据就业岗位的多样性

天津市专业大数据培训班，大数据就业岗位的多样性

大数据技术应用广泛&#xff0c;几乎涉及到了各个行业和领域。毕业后&#xff0c;我们可以选择从事大数据工程师、数据分析师、数据科学家等职业&#xff0c;也可以选择进入金融、医疗、电商等行业进行数据分析和决策支持。 大数据就业岗位多样 大数据培训所涉及的就业岗位有…
阅读更多...
微信小程序H5 uniapp

微信小程序H5 uniapp

最近微信小程序对有视频播放的审核严&#xff0c;需要提供“文娱类资质”。而申请这个资质比较繁琐。所以我们在小程序上用web-view做跳转到H5&#xff0c;H5使用uniapp编写。这是小程序关于web-view文档说明。https://developers.weixin.qq.com/miniprogram/dev/component/web…
阅读更多...
ClickHouse的分片和副本

ClickHouse的分片和副本

1.副本 副本的目的主要是保障数据的高可用性&#xff0c;即使一台ClickHouse节点宕机&#xff0c;那么也可以从其他服务器获得相同的数据。 Data Replication | ClickHouse Docs 1.1 副本写入流程 1.2 配置步骤 &#xff08;1&#xff09;启动zookeeper集群 &#xff08;2&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023