开发者学堂课程【Go 语言核心编程 - 数据结构和算法：数据结构和算法-稀疏数组介绍】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/627/detail/9828
数据结构和算法-稀疏数组介绍
内容简介：
一、实际的需求
二、稀疏数组
三、小结
一、实际的需求
(1）前言
上一次对数据结构的一个基本概念做了一个介绍，当然也讲了数据结构和算法之间的一种关系，那么说数据结构它是算法的一个基石，也就是一个算法往往是建立在数据结构基础之上的，所以，就来具体的看在实际开发中，会用到哪些常见的一些数据结构。
一个数据结构，往往是一个具体的需求关联的，所以往往都是通过一个需求来导致一个新的一个数据结构的一个学习的，这是第一点；
第二点就是今天讲的内容，听起来可能会有点绕，就是它听起来比前面学一个文件编程，学这个结成的一个序列化、反序列化，也就相对来说抽象一点，它需要去动脑筋想一下这个是为什么，所以会突然感觉到好像思路有点不是那么畅通了，甚至有时候会怀疑，是不是会编程了，会有这样的一种错觉在里边，但这很正常。
(2）五子棋问题
那么来看第一个数据结构-疏数组，首先既然是稀疏数组，那么它还是一种数组一个基本的结构，只是它体现的形式是稀疏数组，那稀疏数组它是怎么来的？
稀疏数组一般是这样写的，稀疏 sparsearray 数组，稀疏数组它是为什么来的？举一个例子，看看会不会让你去想一个算法来进行优化，比如现在要去编一个五子棋程序，
如下图:
那么这个五子棋程序有一个功能，叫做存盘退出和续上盘的功能，那么什么是存盘退出？
比如下棋下着下着，想去上厕所了，但是你不想退出，然后对方说”那我们先把这个存盘退出“，一点存盘退出，就需要把如下图中当前的二维数组的棋盘给记录下来；没有下棋子的地方是用零表示，那么下了黑子的地方，表示有蓝旗的地方用。
这个二表示好了，那么现在问题来了，在第一种方式，不做任何的优化，就把二位数组原封不动地进行一个保存，比如扫描这个棋盘，这个棋盘是11乘11，也就是11行11列，就把它存起来了，但是这个没有问题，黑色的标一，蓝色的标二，这个很正常，然后其他地方标零代表没有任何的子，那现在想一想这样做好不好，显然从功能上来说没有任何问题，但是从效率上来说，假设这个存盘假设只有两个棋子，可是这是无用的，保存了很多没有用的数据全是零，其实这些零，它是没有用的。
那为了保存一和二，保存11乘11个数，这个肯定不划算，一个棋盘就这么一点东西，也无所谓对的，如果针对一个人而言，可能还算可以，但是将来做的 CS 结构中这种类似的问题很多，现在只是抛砖引玉说有这么一个问题，将来做的是一个游戏，游戏那就大了，网游也好，还是普通的这种 CS 结构的游戏，这种保存地图类似的问题很多，如果不加处理，第一个占用磁盘，第二个我们效率也不高，因为回复的时候，得一个个回复，很不划算，所以说要基于这种思想，那么想想有没有一种方法能帮它解决？
它的解决方法是这样的:可以把这些没有意义的数据不记录了,直接把有意义的数据记录下来，那么这个就叫稀疏数组.
二、稀疏数组
（1)稀疏数组基本介绍
当一个数组中大部分为零，当然也可能是其他的，就是说大部分有些元素是固定的，或者为同一个值的数组时，可以使用稀疏住来保存该数据。
(2）稀疏数组的处理方法
记录数组中一共有几行几列，有多少个不同的值，先把它记录下来，因为有些编程语言，它可以在定义数组的时候，它的行和列可以是一个变量，就是可以临时输进去，但是数据结构它不是针对这一个，换言之 go 语言的所有语言都可以，所以先记录一个几行几列，然后有多少个不同的值，这是第一点；第二点把具有不同值的元素的行列极值记录在一个小规模的速度中，从而缩小程序的规模。
（3)稀疏数组举例说明
①举个例子，先看下图:
这个就是一个很经典的稀疏数组的案例，左边是一个原始的二维数组.它真正不为零的只有八个，那如果想把这个数组保存起来，那应该怎么保存？
第一种方式是:看他是几行几列，这是六乘七的，可以先保存它一共有几行几列，有多少个数可以这样子对几行几列，比如是六行七列，然后其他的可用来保存它具体的数，只是这个稀疏数组，没有去保存行和列，但一般来说，稀疏数组会保存行和列。
②举个例子，画一了个图，如下:
如何将左边的数组怎么保存？
会这样去保存，即现在有一个数组，要将其转成稀疏数组，换言之这是原始的一个数组，里面有很多相同的数据，现在准备要存盘退出了，应该怎么做?首先先做一个 N 行，三列的，即 N 行乘以三列的一个数组，这个有多少行不能确定，因为将来到底有多少个有效数据并不知道，所以写的是 N ，那么怎么记录？
针对这个情况就这样记，先把它的行和列记录下来，假设是它代表这么一个意思，那么第一个记录它是有六行，它有七列，它一共有切好的，那么它的值是多少？
零的默认值全为零，但是，六乘七一共有12个数据，其中有七八个数据是有效数据，下面记录22，是第零行三列，然后再看15，十五是零行六列，以此类推，就不一个一个的写了，到了最后一个，那么最后这个就是第七行三列有一个数据是28了，可以看到，这样子记录下来，其实只记录了几个数据，即记录了七个数据，当然这中间有些没写出来的，那大家看到的原先的数组是六乘以七的一个规模，其实就是一共有八个数据，那就是八乘以三的一个规模了，那原先有六乘七十二个数据，现在二十四个数据显然规模缩小了，那么这个东西只是一个很小的一个地图，在实际开发中，这个地图可能会很大，很庞大的一个数据、很庞大的一个二维数组，而且这种数组很多，显然这个相当于把数组怎么样进行了压缩，压缩的原理其实就是这个原理，可能看到有各种压缩算法，这个其实是稀疏数组，稀疏数组它其实就是一种压缩数组，本质就是压缩，压缩的本质也就是把一些有用的数据给记录下来，把一些没用的数据或者默认的数据继承一条，打个比方，有篇文章，我有这么一段字符串:tom tom tom tom tom abc，其实这里面 tom 一共出现了五次，所以它的基本算法，就是把这些都扫描，不记录那些相同的记录，然后再把不同的记录下来，最后形成一个串，打回去，对方再给你解压，只是它的压缩算法中有些算法比较更复杂一点，这个就是一种，压缩完，这个原理就讲清楚了。
三、小结
稀疏数组，是一个比较简单的数据结构，来存放这个二维数组的一个弊端，或者是一个问题，那这个问题是什么，刚才也做了一个简单的分析，就是因为有很多数据，它是没有意义的，这样就导致用新的方法来解决，就提出了一个稀疏数组的一个基本介绍。
怎么做记录，数组一共有几行几列，有多少个不同的值，把具有不同元素的行和列记录在一个小规模中，从而缩小程序的规模，这是它的一个核心的思想，这种思想可以推而广之，那如果将来有面试官问到我们说，假设有一个文件，在进行传输的时候，打个比方前面讲了一个聊天，假设聊天的时候，有人发了一篇很长的一篇文章，他说请设计一种方式，能不能把这个字符串进行一个简单的一个压缩，再再传递，非常简单，先把这个要发的内容，先去进行一个检索，检索发现这里面有哪些这个很多重复的字符串，然后先给对方发一个说明，后面那个串有哪些，是怎么的，然后就相当于把这个原始的内容就不发了，它的基本原理是这样子的。
