线性结构-稀疏数组
数据结构包括:线性结构和非线性结构。
线性结构
- 线性结构作为最常用的数据结构,其特点是数据元素之间存在一对一的线性关系
- 线性结构有两种不同的存储结构,即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的
- 链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息
- 线性结构见的有:组队列、链表和栈
非线性结构
非线性结构包括:二维数组,多维数组,广义表,树结构,图结构
今天我们的主角是线性结构中的稀疏数组
,今天讲解一下什么是稀疏数组,稀疏数组什么时候该用,以及怎么用。
什么是稀疏数组
当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。用于减少存放这些数据使用的空间。
稀疏数组的处理方法是:
1)记录数组一共有几行几列,有多少个不同的值
2)把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模
用图说话:
原数组:(有很多0,这个时候可以选择稀疏数组进行压缩空间)
稀疏数组:(第一行分别代表有6行,7列,以及有8个值,最终构成一个3列(8+1)行的二维数组)
稀疏数组怎么用
代码实现:原数组是一个11*11的二维数组
生成稀疏数组
1 | /** |
解析稀疏数组
1 | /** |
总的代码为:
1 | package top.ryan.sparsearray; |
输出结果为:
1 | 0 0 0 0 0 0 0 0 0 0 0 |