343_尚硅谷_Go核心编程_数据结构和算法-稀疏数组介绍.avi原创

好，同学们，我们接着上课的内容呢，继续为大家讲解啊，那上一次呢，我们对这个数据结构的它的一个基本概念给大家做了一个介绍，对吧？然后呢，我们也跟大家讲了一下数据结构和算法之间的一种关系，对不对？那么我们说数据结构呢，它是算法的一个基石，也就是说我们一个算法呢，往往是建立在数据结构基础之上的。所以今天呢，我们就来具体的看，在我们这个，呃，实际开发中我们会用到哪些常见的一些数据结构啊数据结构，嗯，那么我们一个数据结构呢，往往是一跟一个具体的需求关联的，所以说呢，我们往往都是通过一个需求来导致一个新的一个数据结构的一个学习，这第一这是第一点，第二点呢，呃，跟大家说一下，就是今天我们讲的内容呢，听起来可能会有点绕，就是它听起来比前面咱们学，比如说学一个文件编程呢，学这个，呃呃，接生的一个序列化，反序列化呢，也就相对来说抽象一点，它需要我们去。

动脑筋去想一下这个东西是为什么。对，是为什么？所以说你会突然感觉到好像思路有点不是那么畅通了，甚至有时候你会怀疑，哎，我是不是会编程呢，对不对，它会有这样一种一种错觉在里边，那这很正常哈，这很正常好，那么我们来看第一个数据结构，第一个数据结构呢，叫稀疏数组。稀疏数组，那首先既然是稀疏数组呢，那它仍然呢，还是一种数组的一种这么一个基本的结构，只是它体现的形式呢，是稀疏数组，那稀数数组它是，呃，它是怎么来的呢？它稀数组一般我们这样写的space space啊。而这就是稀疏数组。系数组，那系数数组它是为什么来的呢？我就举一个例子吧，我就举个例子，大家看看会不会让你去想一个算法来进行优化，你比如说现在我们要去编一个五子棋，对不对？我们要去编一个五子棋程序。

那么这个五子棋程序呢？嗯，有这么一个功能，叫做存盘退出。叫存盘退出和续上盘的功能，什么叫什么叫存盘退出呢？就说比如说我们下棋下着下着，诶你想去上厕所去了。那但是你不想你不想退出，那对方呢，说那我们先把这个存盘退出吧，一点存盘退出好，那存盘退出呢，就需要把你当前的这个二维数组的这个棋盘给记录下来。对，记录下来，那么我们约定好了，就是没有下棋子的地方，没有下棋子的地方是用零表示，那么下了这个黑子的地方呢，咱们用一表示，有蓝旗的地方呢，用。

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

那你你为了保存一和二，但是你保存了11乘11个数。大家想想这个肯定不划算，说老师那这个棋一个棋盘不就这么一点东西吗？也无所谓，对对的啊，如果说针对一个人而言，可能还还算OK，但是你想想将来你做的是个CS结构，这种类似类似的问题很多，我只是抛砖引玉，说有这么一个问题，那将来你做的是一个游戏，这个游戏游戏，那就大佬你看网游也好，还是我们这个普通的这种这种这个CS结构的游游戏哈，它这种保存地图类似的这种这种这种问题很多。如果我们不加处理，第一个我们占用我们的磁盘，占用我们的磁盘，第二个我们效率也不高。因为你回复的时候，你得一个个的回复很不划算，所以说同学们，那么基于这种思想呢，我们就得想有没有一种方法能把它解决呢？好，它的解决方法是这样子的，我们可以把这些没有意义的数据，或者叫默认的数据不记录了。

不记录了，我们直接把有意义的数据记录下来，那么这个呢，我们就叫系数数组，看一个案例，它是这样子的啊，怎么看。基本介绍什么叫系数数组呢？当一个数组中大部分为零，当然也有可能是其他的啊，当然也可能是其他的，就是大部分有些元素是固定的，而或者或者为同一个值的数组时，可以使用系数组来保存该数据。系数数组的处理方法是这样子的，记录数组中一共有几行几列，就一共原先有几行几列，先把它记录下来。把它记录下来，因为有些有些编程语言呢，它可以在定义这个数组的时候，它的行和列可以是一个变量，就是临时可以去输进去，只是构语言呢，咱们必须要写死对不对，那么但是数据结构它不是针对，不是针对这一个，呃，就是说构语言的所有语言都可以，所以你先记录一个几行几列，然后呢，有多少个不同的值。

好，这是第一点。第二点，把具有不同值的元素的行列极值记录在一个小规模的数组中，从而缩小程序的。规模。从而缩小程序的规模。那么我举个例子，同学们看这里。举个案例啊，这个呢就是一个很经典的系数数组的案例，大家看到这边呢，是一个原始的二维数组，这个原始的二维数组里边呢，大家可以看到它真正不为零的只有八个，123456788个，那我如果说将来想去把这个数组保存起来，那我怎么保存呢？我可以这样保存。

我可以把这个，呃，第一种方式是这样子的啊，你看它是几行几列，1234567啊，这是一行两行，三行四行，五行六行，就是六乘以七的，你可以这样子，你先你先保存它一共有几行几列。有多少个数可以这样子对吧，几行几列，比如说是呃，六行七列，六行七列，然后呢，其他的呢，可以用来保存它具体的数，只是我这个系数数组呢，我没有去保存这个行和列，但一般来说系数数组会保存行和列啊，就是行和列默认值就这样子的，我举一个例子吧，一个标准的系数组组应该是这样子，我给大家画一个图。比如一个标准的系数数组，它是这样子的。嗯，打个比方，我待会再板书啊，同学们，比如我这有这么一个数组。我这儿有这么一个数组，大家看清楚了。

这个数组，那么这个数组我会怎么保存呢？我会怎么保存呢？我会这样保存。我会这样去保存，说我现在有这么一个系数数组。我要把它转成稀疏数组啊，转成一个稀疏数组，就说它原先这是原始的一个数组，这个原始数组呢，里面有很多相同的数据。我现在准备要存盘退出了，我怎么做呢？我这样做。我首先看一下，我先做一个NN行三列的，就是NN行乘以三列的一，三的三的一个数组。这个这个有多少多少行不能确定，因为你将来到底有多少个有效数据不知道，所以说我写的是N，那么怎么记录呢？针对这个情况，我就这样记，我先把它的行和列记录下来，哎，一行两行，三行四行五行六行七列，那就这样记了六。

谢谢。肉。假设是它代表代表这么一个意思啊，这是肉，这个是行，这个是直看清楚了啊呃，那么我第一个季度是它是有六行。它有几列呢？它有七列，它一共有七列，好的，它的值是多少呢？零就默认值全为零。就默认是权威零。但是。六乘以七一共有12个数据，其中有七八个数据是有效数据，下面接着接着记录哦，22是零行。零行三列。第零行三列。第零行三列好，这个数呢是22。OK，然后呢，我们再看15 15是零行，注意听啊零行这个第12340第六列，0123456第六列，然后呢，他呢，4545好以此类推，以此类推啊，以此类推，我就不一个个的说了，不一个说的好，到了最后这一个啊同学们到最后这一个，那么最后这一个呢，就是我们的第啊123456第六行。

第六行第其实是第七行了，然后第第二列有一个数据是28O了。同学们可以看到，那这样子我一记录下来，其实我只记录了几个数据呢，诶，那就记录了七个数据啊，当然这中间我有些没写出来的啊，那么就是行列，那么将来大家看到原先的数组是。六乘以七的一个规模，现在到我这来说说呢，其实就是我一共有七个数，一共有七个数据，123456788个数据，那就是八乘以三这么一个规模了。那你想一想，原先有六乘以七十四二个数据，现在24个数据，我显然规模缩小了。对不对，显然规模缩小了，那么这个东西只是一个很小的一个地图，那实际上在我们开发中，这个地图将来可能会很大很大很庞大的一个数据，很庞大的一个二维数组，而且这种数组很多，那你这样子的话，显然这个相当于把数组怎么样进行了压缩，压缩的原理其实就是这个原理，同学们。

你们可能看到有各种压缩算法，这个其实稀疏数组啊，同学们，稀疏数组它其实就是一种压缩数组本质就是一种压缩，压缩的本质也就是把一些有用的数据给记录下来，把一些没用的数据或者默认的数据呢，记成一条，就说假设你有很多这个，比如说，呃，比如说，比如说打个比方，我这有篇文章，我有一篇我有。有这么111段字符串，汤姆汤姆汤姆汤姆汤姆ABC，其实这里面汤姆一共出出出现了五次，所以说它的基本算法就是我把这些都扫描，把那些相同的字算我记录有多少数，然后再把不同的记录下来，最后形成一个串打回去，对方再给你解压。

只是它的压缩算法呢，有些算法更比较更复杂一点，这个就是一种压缩，好那这个原理我们就讲清楚了，好那么我们就来实现一把，来同学们先把这个进行一个小小的板书，那前面呢，我们把新书数组做了一个介绍，来各位朋友，新数做了完介绍，我相信同学们应该能够听懂，对不对，应该能够听懂，好先把稀疏数组拿过来。这个系数数组呢，是一个比较简单的数据结构，可以这么说比较简单数据结构，所以大家听起来没有压力啊，没有压力，因为现在我们要缓一缓对不对，不能说一上来就整一个特别难的，让大家感觉到，呃，压力山大，压力山大好，这个我看了一个需求，就是说类似于咱们去存盘对不对。那我举了这么一个案例，诶，编写五子棋的时候，咱们有这种存盘退出的这么一种功能。

那这种这种事情呢，在我们开发中会很经常的遇到，很经常的遇到，好那关于这个呢，我就截个图，哎，这个。地图，这是我们的一个棋盘。啊，这是我们的一个棋盘。好，这个棋盘呢，原始的是这样一个二维数组，对吧，现在呢，我们要提出一个问题，我们分析了一个问题，分析按照。按照原始的方式，哎，按照。按照原始的方式。原始的方式。来存放，来存放这个二维数组的，二维数组的一个弊端啊，或者是一个问题，那这个问题是什么呢？刚才老师也做了一个简单的分析啊，就是因为有很多数据呢，它是没有意义的，没有意义的好，这样子就导致这个我们要有新的方法来解决，怎么解决的呢？OK，我们就提出了一个基本介绍，就稀疏数组的一个基本介绍，对。

那么系数数组的基本介绍就从这儿来了。好，这个标题三，这个呢，也给它来一个标题三，对那系数数组它是一个大概什么概念呢？就这么一个概念对吧？啊这么一个概念，我把它板述一下，就第一点他怎么做。第二点，怎么做记录数组一共有几行几列，有多少个不同的值，把具有不同的元素的行和列记录在一个小规模数组中，从而缩小程序的规模，从而生小程序的规模就是它的一个核心的思想，它的思想就这样子的这种思想啊，同学们，这种思想呢，大家可以推而广之啊，推而广之，那如果说将来有面试官问到我们说，诶，同学，假设我们有一个文件。在进行这个传输的时候，打个比方，我们现在呃，我们前面呢讲了一个呃，就是聊天，假设聊天的时候有人发了一篇很长的一篇文章，他说哎，请你设计一种方式，能不能把这个字符算进行一个简单的一个压缩，再再传递好，你就告诉他可以的。

那非常简单嘛，我先把我的这一个，呃，你要发的内容，我先去进行一个检索啊，我检索发现你这里面有哪些哪些这个很多重复的这个字符串，然后呢，我先给对方发一个说大致是一个说明我后面这个串有哪些是怎么怎么样的，对吧，然后我就我相当于说我把那个就不发原始数，原始的那个内容我就不发了。不发了，我就直接说这里面有哪些，比如说汤姆有几次，Jack有几次发给你，发给了对方过后呢，对方进行一个解，进行一个解压，解压过后呢，就恢复到原始做手算，它的基本原理是这样子的啊同学们基本原理是这样子的，好了，那这个原理知道了过后呢，我们这边也画了一个这样的一个示意图，哎，基本介绍的一个示意图，好系数数组的一个举例说明，我们现在呢，把它也放在这里。

对啊，放在这里，过后呢，我们就来具体的实现一把啊，同学们实现一把。来吧，这个是稀疏数组的一个案例。OK。好，同学们，这个是关于系数数组的基本介绍，系数数组的基本介绍来走一个。