数据结构和算法-稀疏数组介绍|学习笔记

简介: 快速学习数据结构和算法-稀疏数组介绍

开发者学堂课程【Go 语言核心编程 - 数据结构和算法:数据结构和算法-稀疏数组介绍】学习笔记,与课程紧密联系,让用户快速学习知识。

课程地址:https://developer.aliyun.com/learning/course/627/detail/9828


数据结构和算法-稀疏数组介绍


内容简介:

一、实际的需求

二、稀疏数组

三、小结

 

一、实际的需求

(1)前言

上一次对数据结构的一个基本概念做了一个介绍,当然也讲了数据结构和算法之间的一种关系,那么说数据结构它是算法的一个基石,也就是一个算法往往是建立在数据结构基础之上的,所以,就来具体的看在实际开发中,会用到哪些常见的一些数据结构。

一个数据结构,往往是一个具体的需求关联的,所以往往都是通过一个需求来导致一个新的一个数据结构的一个学习的,这是第一点;

第二点就是今天讲的内容,听起来可能会有点绕,就是它听起来比前面学一个文件编程,学这个结成的一个序列化、反序列化,也就相对来说抽象一点,它需要去动脑筋想一下这个是为什么,所以会突然感觉到好像思路有点不是那么畅通了,甚至有时候会怀疑,是不是会编程了,会有这样的一种错觉在里边,但这很正常。

(2)五子棋问题

那么来看第一个数据结构-疏数组,首先既然是稀疏数组,那么它还是一种数组一个基本的结构,只是它体现的形式是稀疏数组,那稀疏数组它是怎么来的?

稀疏数组一般是这样写的,稀疏 sparsearray 数组,稀疏数组它是为什么来的?举一个例子,看看会不会让你去想一个算法来进行优化,比如现在要去编一个五子棋程序,

如下图:

 image.png

那么这个五子棋程序有一个功能,叫做存盘退出和续上盘的功能,那么什么是存盘退出?

比如下棋下着下着,想去上厕所了,但是你不想退出,然后对方说那我们先把这个存盘退出“,一点存盘退出,就需要把如下图中当前的二维数组的棋盘给记录下来;没有下棋子的地方是用零表示,那么下了黑子的地方,表示有蓝旗的地方用。

这个二表示好了,那么现在问题来了,在第一种方式,不做任何的优化,就把二位数组原封不动地进行一个保存,比如扫描这个棋盘,这个棋盘是11乘11,也就是11行11列,就把它存起来了,但是这个没有问题,黑色的标一,蓝色的标二,这个很正常,然后其他地方标零代表没有任何的子,那现在想一想这样做好不好,显然从功能上来说没有任何问题,但是从效率上来说,假设这个存盘假设只有两个棋子,可是这是无用的,保存了很多没有用的数据全是零,其实这些零,它是没有用的。

那为了保存一和二,保存11乘11个数,这个肯定不划算,一个棋盘就这么一点东西,也无所谓对的,如果针对一个人而言,可能还算可以,但是将来做的 CS 结构中这种类似的问题很多,现在只是抛砖引玉说有这么一个问题,将来做的是一个游戏,游戏那就大了,网游也好,还是普通的这种 CS 结构的游戏,这种保存地图类似的问题很多,如果不加处理,第一个占用磁盘,第二个我们效率也不高,因为回复的时候,得一个个回复,很不划算,所以说要基于这种思想,那么想想有没有一种方法能帮它解决?

它的解决方法是这样的:可以把这些没有意义的数据不记录了,直接把有意义的数据记录下来,那么这个就叫稀疏数组.

 

二、稀疏数组

(1)稀疏数组基本介绍

当一个数组中大部分为零,当然也可能是其他的,就是说大部分有些元素是固定的,或者为同一个值的数组时,可以使用稀疏住来保存该数据。

(2)稀疏数组的处理方法

记录数组中一共有几行几列,有多少个不同的值,先把它记录下来,因为有些编程语言,它可以在定义数组的时候,它的行和列可以是一个变量,就是可以临时输进去,但是数据结构它不是针对这一个,换言之 go 语言的所有语言都可以,所以先记录一个几行几列,然后有多少个不同的值,这是第一点;第二点把具有不同值的元素的行列极值记录在一个小规模的速度中,从而缩小程序的规模。

(3)稀疏数组举例说明

①举个例子,先看下图:

image.png

这个就是一个很经典的稀疏数组的案例,左边是一个原始的二维数组.它真正不为零的只有八个,那如果想把这个数组保存起来,那应该怎么保存?

第一种方式是:看他是几行几列,这是六乘七的,可以先保存它一共有几行几列,有多少个数可以这样子对几行几列,比如是六行七列,然后其他的可用来保存它具体的数,只是这个稀疏数组,没有去保存行和列,但一般来说,稀疏数组会保存行和列。

②举个例子,画一了个图,如下:

image.png

如何将左边的数组怎么保存?

会这样去保存,即现在有一个数组,要将其转成稀疏数组,换言之这是原始的一个数组,里面有很多相同的数据,现在准备要存盘退出了,应该怎么做?首先先做一个 N 行,三列的,即 N 行乘以三列的一个数组,这个有多少行不能确定,因为将来到底有多少个有效数据并不知道,所以写的是 N ,那么怎么记录?

针对这个情况就这样记,先把它的行和列记录下来,假设是它代表这么一个意思,那么第一个记录它是有六行,它有七列,它一共有切好的,那么它的值是多少?

零的默认值全为零,但是,六乘七一共有12个数据,其中有七八个数据是有效数据,下面记录22,是第零行三列,然后再看15,十五是零行六列,以此类推,就不一个一个的写了,到了最后一个,那么最后这个就是第七行三列有一个数据是28了,可以看到,这样子记录下来,其实只记录了几个数据,即记录了七个数据,当然这中间有些没写出来的,那大家看到的原先的数组是六乘以七的一个规模,其实就是一共有八个数据,那就是八乘以三的一个规模了,那原先有六乘七十二个数据,现在二十四个数据显然规模缩小了,那么这个东西只是一个很小的一个地图,在实际开发中,这个地图可能会很大,很庞大的一个数据、很庞大的一个二维数组,而且这种数组很多,显然这个相当于把数组怎么样进行了压缩,压缩的原理其实就是这个原理,可能看到有各种压缩算法,这个其实是稀疏数组,稀疏数组它其实就是一种压缩数组,本质就是压缩,压缩的本质也就是把一些有用的数据给记录下来,把一些没用的数据或者默认的数据继承一条,打个比方,有篇文章,我有这么一段字符串:tom tom tom tom tom abc,其实这里面 tom 一共出现了五次,所以它的基本算法,就是把这些都扫描,不记录那些相同的记录,然后再把不同的记录下来,最后形成一个串,打回去,对方再给你解压,只是它的压缩算法中有些算法比较更复杂一点,这个就是一种,压缩完,这个原理就讲清楚了。

 

三、小结

稀疏数组,是一个比较简单的数据结构,来存放这个二维数组的一个弊端,或者是一个问题,那这个问题是什么,刚才也做了一个简单的分析,就是因为有很多数据,它是没有意义的,这样就导致用新的方法来解决,就提出了一个稀疏数组的一个基本介绍。

怎么做记录,数组一共有几行几列,有多少个不同的值,把具有不同元素的行和列记录在一个小规模中,从而缩小程序的规模,这是它的一个核心的思想,这种思想可以推而广之,那如果将来有面试官问到我们说,假设有一个文件,在进行传输的时候,打个比方前面讲了一个聊天,假设聊天的时候,有人发了一篇很长的一篇文章,他说请设计一种方式,能不能把这个字符串进行一个简单的一个压缩,再再传递,非常简单,先把这个要发的内容,先去进行一个检索,检索发现这里面有哪些这个很多重复的字符串,然后先给对方发一个说明,后面那个串有哪些,是怎么的,然后就相当于把这个原始的内容就不发了,它的基本原理是这样子的。

 

相关文章
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
73 1
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
83 0
|
7月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
189 10
 算法系列之数据结构-二叉树
|
7月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
158 3
 算法系列之数据结构-Huffman树
|
7月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
196 22
|
8月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
200 30
|
7月前
|
存储 监控 算法
关于员工上网监控系统中 PHP 关联数组算法的学术解析
在当代企业管理中,员工上网监控系统是维护信息安全和提升工作效率的关键工具。PHP 中的关联数组凭借其灵活的键值对存储方式,在记录员工网络活动、管理访问规则及分析上网行为等方面发挥重要作用。通过关联数组,系统能高效记录每位员工的上网历史,设定网站访问权限,并统计不同类型的网站访问频率,帮助企业洞察员工上网模式,发现潜在问题并采取相应管理措施,从而保障信息安全和提高工作效率。
92 7
|
8月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
313 25
|
8月前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
286 23
|
6天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)