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

那现在呢，我们来看一个具体的案例，我们来看一个具体案例，我们就以这么一个数组来为例进行一个讲解啊，比如说应用一个案例，使用系数数组来保存类似前面的二维数组，比如棋盘或者是地图。那么第二步把C输数组存盘，就把它存在这个文件里边去。啊，然后呢，并且可以重新恢复原来的二维数组，OK，那么整体这个思路我这大致有了，大家想一想啊，嗯，我要做这么一件事情，我要做这么一件事情，这是一个二维数组。11乘11的，那么我要把它做成一个系数数组的话呢，我的思路这样子的啊，比如说嗯，这是一个系数数组，我就记录了一和二。比如说一是一行二列是一个一，然后呢，二是第二行第第二，第二行的第第二，第三列是一个二，我就记录下来了，当然了，作为一个标准的系数数组呢，做一个标准的系数数组，它应该还要记录这个这个值。

就是呃，它一共有11行11列，那其他值应该是零啊，这应该写错了，应该是零。标志性输出组，它首先记录了一共有11行，有11列，默认值为零，把它记录下来，但是呢，对于我们这个构语言而言啊，对于我们构言而言，这个11和这个11，如果如果把它重新恢复成二位数组的话，嗯，这个11和11意义不是特别的大。因为构员有个有个问题，就是他在进行定义一个数组的时候呢，他必须把那个写死。对吧，它必写死，所以说你要恢复的话呢，可能你你得想办法把它做成一个切片性质的，那就意义不大了，所以说呃，如果是勾圆这两个值就是行和列有多少个，呃，意义不是特别大，但是你也可以把记录下来，按照一个标准的系数组，应该把它记录下来啊，应应该把它记录下来，那这样子我们现在呢，就来把它完成了，哎，我们就来把它完成了，来应用案例走一个。

好，我们来一起玩一下应用实例。我们来把这个应用实例给他走一走。好，标题三，我的具体的要求呢，有这么三个啊，整体思路，代码实现，我们都马上写出来，第一个。第二个系数数组存盘整体思路的分析，最后呢，我们来一个代码实现。代码实现OK，那整体思路分析的话，刚才呢，老师也画了一个简易的示意图。来，我们一起玩一下。好，那么打开我们的Vs code，打开我们的Vs code，然后我们新建一个章节，对，我们新建一个章节，注意听啊，同学们，这个还是一个小小入门，所以大家没有感觉到特别难度。

Chapter chapter20。二零。二零。好，然后呢，在这个包包里面，我们建一个文件夹，我们就叫系数数组pass对不对。好的，那这边呢，我们新建一个文件，这个文件呢，我们就直接叫面点个完事。好，来package。Package呢，我们写一个包包叫主包，然后import好，里面有什么内容呢？先一下。啊，那现在呢，我们来走一个啊，Form function啊，主函数。来，直接在这里做测试就行了，来测试我们先第一步先干什么呢？我们先创建一个原始数组。对，现创建一个原始的数组。对原始的数数组。对，那么第二个原始数组有了过后呢，我们现在这样子做一个数组啊，比如说这是我的一个棋盘，我就这样写了VRCHS棋盘嘛，这是我的棋盘的一个地图，棋盘的一个地图，然后呢，我把它定好，这个假设是11乘11。

OK，然后呢，它的值呢，就用int来表示，那么int我们怎么表示呢？就是它的一表示黑棋，那个二呢表示蓝起，对就这意思，然后现在呢，我们来把它做一下啊，比如说它初始的时候呢，有一个下map，它的第一第一行第二行一二有一个值是一，我们看一下。对，看一下啊，我们看一下啊，就是一二是一个一，还有一个二三十二，对232CHES map。二三它是几呢？它是二好假设一呢表示黑棋啊，黑棋就代代表是黑子。

黑子，那么二呢，表示是男子。蓝蓝色的。男子，OK，好，现在呢，我们来先看一看，第二步，我们先看看原始的数组对不对啊，输出一下，输出看一看原始的原始的数组对不对，大家看一下啊，负循环。啊，我们进行对待一个便利就完事了，对待一个便利，那便利的时候呢，我们就用for来搞定就行啊，啊现在呢，也比较简单I。V，对，然后呢，IV，呃，这个I对我来说可能也也要啊，也要把它把它输出来吧，啊然后呢，等于range。认对谁进行一个便利呢？对Che map进行一个便利。那么遍历完了过后呢，大家都很清楚的知道，这个V其实是一个一位数组，对我们先讲过一位数组，那对它再次进行一个遍历，就勾，勾好，我们把这个地方连在一起勾，然后这边再取出它的V2，这个V2就是具体的值了。

V2就是具体的值好的走range v，然后呢进行边力，我们把它输出来，怎么输出来呢。Print轴，好，我们这样输啊，同学们，我们这样数A，它的数组CHCH，这可能太多了，呃，我们就直接把那个值输出来。D啊，它是第几个值D，然后呢，输一个咱们来一个斜杠T，它的值就是V2。就是V2就可以了，然后打完打完一个过后呢，我们换一行。来来这样这样一看呢，这个I和V我们就没有用到，没有用到的话呢，我们先将其怎么样把它忽略。好，同学们，原始数组我们就有了，我们来执行一下，看看它是一个什么情况，这少了一个F。这少了一个F啊，OK。好，同学们看看原始数组长什么样子，打开我们的D盘，对，找到我们刚才写的这一段代码所在的目录chapter，然后呢，系数数组好来运行小啊，同学们走。

来勾一下go run main.go跑起来。好，我们可以看到当前这个二位数组呢，长得就这样子的，跟我们想的很像。对，有一个一，有一个二，那么这个时候呢，我们发现这样子不合理不合理，因为你如果我们原先按照这个这个方式去存盘的话呢，它一共有11乘以11个数据比较大，规模比较大，那现在呢，我们要把它转成系数数组来。怎么把它转成一个稀疏数组呢？这个就叫思想了。这个时候要把它转成转成啊。转成一个稀疏数组。那问题来了，说老师我要把它转成一个稀疏数组，我怎么转呢？显然。

你事先并不知道它有多少个有效数据。那在我们go语言这里面呢，你只能使用切片，对的，因为你并不知道它有一个121和二啊苏老师我不是看到了你，你看到程序不知道啊，那没办法，你只能用切片，那用切片的话呢，怎么保存比较好呢？我觉得最好的一种设计方式就是直接咱们用一个结构体就可以了。对，结构体注意啊，结构体仍然是可以做成一个数组的咯，对，因为我在一个切片里面放有多个结构体实例，它就是一个结构体的一种一种切片嘛，那切片的本质它还是一个数组嘛，对吧，所以这个是没有问题的，这个就就要大家去想怎么做，这个就叫算法，这个就叫算法啊。说老师这个算法好像很神秘的样子，算法可以说是无处不在，打个比方冒泡，我们说算法，算术肯定是算法，再比如说你将来有一个东西，比如说你将来在实现这个go web编程的时候，别人让你去把近十天不把把近最近前十个浏览的商品给我排到上面去，好你写了一个代码，这个也叫算法。

只是有些算法呢，它是一些常规算法，就大家都认同的一种算法，比如说语音识别算法，比如说像人工智能的图像识别，语音图像识别，还还有是文字识别，那些是比较有名的算法。就很有名了，大家都认同的，还有一些算法是你在工作中，实际开发中，你去解决一个小问题，设计的一个解决方案，也叫算法，那我们这个也叫算法，诶这个就叫算法，那么怎么怎么做呢？那我的思想就这样子的，我的思路如下，我的思路如下，就说我们呢，把这个东西放在一个将扫描啊思路这样子的第一步。第一步，我们便利。我们便利。哎，注意听我们便利。便利，我们便利什么呢？我们便利这个chess map。

变离麦加速，如果我们发现，如果我们发现，发现有一个有一个元素的值，有一个元素的值，注意听啊元素的值。元素不等于零，不等于零，那么就怎么办呢？哎，它不等于零了，不为零。不为不为零，那么我们就把它装在一个，我们就创建一个note，我们创建一个节点，我们创建一个note节点，我们就干什么呢？就创建一个root节点。哎，创建。创建一个note节点。啊，露底那个结构体吧，咱们先不要节点的结构体，然后把它放入到哪里去呢？第二步将其放入到切片中。哦，将其。将其放入到对应的切片中即可。

OK，那这个思路就有了，那这个时候的问题是在于这个结构体你怎么设计？这老师这个究体怎么设计呢？那你想一想啊，你想你将来长的什么样子吗？你将来长的样子不就是这个样子的吗？你将来说有行列，还有这个值啊，那显然这个结构体呢，至少应该有三个字段，一个是行，一个是列，一个是值嘛，对不对，所以你这个地方你就分析出来东西了。好的，同学们，这个就叫解决问题啊，同学们不要把那个解决问题搞得很神秘，这个就在就在让你解决这个一个压缩的问题，那我就来了，那就是type，我整一个节点，Note节点。对不对，一个漏的节点，但是有些可能叫Y6，就是一个直接点也可以。也可以，这无所谓对吧，也可以就叫直节点吧，因为后面我们还有好多节点，各种节点都有。那这个时候呢，我们就用structure，那这个就很简单了，哎，我说它有个行。它是第几行的行，哎行是这个RA in列column in，还有呢，就是它的值value，诶那就放进去了，当然如果你将来这个值呢，不是inter类型的，是其他，比如说有个字符是可能是一个，呃，小数点呢，或者字符串呢，那你这就其成interface接口就可以，没问题啊，这根根据你的需要来走，根据你的需要来走，但前面这两个肯定是都是inter性，因为我们这个行格列不可能是下标为小数点嘛，不能说我这个是二点五行，没有那个说法啊，好定好了，那定好过后呢，我们这个切片就可以把它定下来啊，切片好，我们现在先做一个切片。

来整一个切片再说吧，VR，我将来这个就叫。期数的啊，Pass per，我就认为这是个系数数组了，他么，那这个系数数组呢，我是以这种切片的形式来实现的，就是以这种节点的切片的形式来实现的，这个就叫算法啊，同学们那一共有多少个，不知道不知道好，现在呢，我开始便利了，因为你现在要开始便利它啊，来走four。

我要遍历这个数组，那遍历这个过程跟刚才很像，我这个代码呢，咱们可以拿来为我所用，为我所用，但有些地方是不一样的啊，同学们看一下，走这个时候我来便利它，我便利它，便利它的时候呢，这种逻辑要发生变化。发生变化，这里面也不用打印了，就说我要开始判断，假设这个值不等于零，你必须全部扫描一遍啊，那就是如果这个V2。V2它不等于零，不等于零表示什么意思呢？就是说呃，这个值就是要记录下来的。记录下来的，它现在这个纸要记录下来，它记录下来的话呢，咱们咱们就可以把它扔进去了，咱们就可以把它扔进去了，那就这样写了pass。来，走一个。

首先你先创建一个节点，先创建一个这样的节点，还不着急啊，你首先要创建几个节点，创建一个怎样的节点呢？诶，咱们创建一个这样的节点。创建一个value直接点，这个叫直接点啊呃，也有专业的术语叫直接点。直接点啊，那么就搞一个这个出来就行了，Vlo等于啊，那么就搞一个这个东西V。L。那这个直接点里面有什么值呢？大家非常清楚的知道啊，非常清楚的知道它应该有一个行，它这个行呢，其实就这两个字就有用了，大家看到这个I和I和勾就有用了啊，原先没有用，现在有用了。你现在是第几行啊I没问题，给他第几列啊，诶第几列显示勾好，这个值是什么呢？值就是V2。

好，这就写完了，这就说你先创建了一个，这样直接点这个直接创建完了过后呢，你得想办法把它扔到你的系数组数组里边去，按照顺序来啊，那我就把它扔进去了，怎么扔。非常的简单啊，判一下就可以了。轴等于aend aend a aend，那aend的时候呢，咱们这个就这样做了啊，碰的就把它包起来啊包起来，然后呢，我们是在这个基础上。End的一个va al no的节点，好，经过一番便利，经过一番便利，同学们都可以清楚的知道，我们就把这个数存进去，但是有一个问题，我们这样做呢，有一个巨大的问题，就说我们没有做一个标准的系数数组，标准的系数数组呢，前面应该还有整个有你的这个数据，原始的数据规模有多大，比如说你原先是几行几列的。

原先是将几裂的，那这个时候呢，呃，前面大家都知道，它是往屁股后边追。而且呢，我们在之前这个11本身就是确定的，所以说呢，如果我们这个更语元要做一个标准的系数数组的话呢，你在前面先可以先加一个表示它的这个，呃，规模的这么一个节点可以这样做，因为个元它有个特点，不是它这个呃数组啊，他必须得写，写死了，说这个呢，其实意义不是很大，但是我们做一个标准的吧，啊做一个标准的来。标准的我就直接写到这里啊，写标准的。标准的一个稀疏数组呢，稀疏数组啊是什么呢？标准的稀疏数组应该应该还含有还含有。还有什么呢？还还有一个，还有一个。

还有一个就是表示记录，记录原始的，原始的二维数组的规模。规模和默认值规模。规模行和列嘛，所以规模就是它的原始的行，行和列有多少对不对，然后呢，呃，然后呢，这地方还有一个默认值要记下来默认值。默认值。好，那这个地方我们也把它搞进去啊，做一个标准的。那你要把它这个搞搞进去的话，也很简单，因为它这个行和列，我们先前就可以知道啊，先前就可以知道，那就这样做一下noe初始化一个节点。好，这个地方我们少了一个这个啊，少了一个这个。好，我们先前先创建一个这样的节点。哎，向前先创建这么一个节，这个节点啊走。啊，因为呃，这个节点呢，是原始的一个节点，比如说它的它的一个no value6，这个VALUE6呢，它行和列是写死的，第一个是11，第二个是11，默认值是零。

好，默认是零，那这样子的话呢，也先把它加进去。啊，这是它的一个初始的一个节点。好，这就写完了。写完了大家看一下啊，11110加进去。呃，那么我们先来保存一下，我们来保存一下。好保存过后呢，我们来把它这个系数数输出来看一下。我们现在去输出。输出稀疏数组。我们把这个系数数给大家说出来，看一下现在长什么样子啊，I负循环，嗯，然后呢，我们，呃，它这个系数数组的第几行第几列，咱们也可以把它打印出来，可以把它打印出来啊，那就是I。啊，然后呢，这边里面是它的一个结构体对吧？啊结构体啊，就是相当于是个节点呢，相当于是个节点load，直接点value load取出来就是value load嘛，然后呢。

Range。我稍微慢一点啊，这个还是刚刚开始啊，呃，还一点都不知道啊，待会我们那个双向列表上去过后，大家都肯定很模很模糊的，我慢点。这个是锻炼你们大脑的时候到了啊，就哎，突然一下感觉到这个大脑有点不够用了时的样子，好，然后呢，把它遍历一下。遍历一下，现在你要想象到我在干什么，我在遍历这个奇数数组，那我遍历的时候呢，这个load没遍利出来，这个load其实相当于我在遍利这个东西。一个一个的这个东西，我现相当说我现在又把它取出来了。我把它取出来，把它打印一下，对，我把它打印出来，那打印的时候呢，非常简单，这个I是代表它是第几个节，直接点好，那这样子就输嘛，Form点不FF好，我们把它输出来啊呃，首先我们看它是第几个。D然后这边我们打一个冒号，打一个冒号，把它的值给输出来，把它的阻值输出来，呃，那这边值呢，一共有三个，大家都很清楚的知道第一个。

第二个。第三个好，然后呢，呃，第一个值就是代表它是第几个第几个节点，那么我们写个I。那么它这里面的呃，行刚好就是value这个节点里面的哪一个呢？OK，大家应该反应过来，只用。啊OK，那第二个呢，就是它的这个这个行啊，行行一个行一个列，然后呢，第三个就是它本身的这个值。Y，好，完事打完一个呢，咱们换一个行。好，这个就编辑成功了，我们来看一下，我把这个系数数组打出来给看看。好，我稍微这个地方我没有画图啊，因为我觉得还不算太难print。好，我写一句话，叫做当前的稀疏数组，稀疏数组是什么样子的呢？来运行一半。

好，我们看一下各位各位各位。同学们可以看到。原始的数组是长这个样子的。这样子的，等到我们新输数组一处理，你看变得非常小了，变得非常小了，他说你第一个节点是11110正确，他说你第二个呢，有一个第二个节点是在第一行和第二列有个值是一，第二个节点它记录了第二个有效值是第二行第三列有个二，完事，你看原先这么大一个速度变得这么小了。啊，变得这么小了，其实在我们实际的开发中，大量存在着这种情况的，这种数组也好，字符串也好，很多很多。如果说我们作为一个程序员，从来不去在脑海里面从来没一种思想，就从来没想过这个事儿，那是一种很失败的啊，你看为什么说有些程序员他的他这个代码一跑起来又节省内存，速度还快，而且感觉到很有很有灵魂，就说人家是有想法的，那你你当然也能实现，说老师诶从代码上来说，这个也也可以啊，是的，如果从这样子来看，你就是无所谓，就是多占点空间。

多占点内存，速度稍微慢一点嘛，无所谓嘛，对不对，但是你做一个好的程序员，你做一个优秀的程序员，你肯定要去想，诶怎么样让它变得更小一点。对不对，你想这个原先11乘11，现在我一下就变成了这么几个数据都有，都有用啊，而且这个好处是，呃，对于像有些编程语言来说，它这个行和列可以直接从这读取出来，直接初始化一个新的二维数组，只是各语言不行。啊，你看Java里边啊，还有pap里面，他直接把这个读出来，就知道你原始规模是什么。那多多舒服对吧，而且还可以变化，你将来你原先是11的，假设你原是原始规模是11，以前是十乘以十的，我也可以做，只是构元里面这个量必写死，所以他这有点稍微基础组用的不是特别的好啊，但有别的办法用切片啊，好了，同学们，那现在有了这个东西，你要反过来用适引它。

你要反过来的把它，你得把这个家伙存到磁盘里面去。因为你的目标是干什么，你的目标不就是希望将来存盘。退出吗？那你还得把它搞到这个磁盘里面去，然后等到别人保存恢复的时候，你要把它重新读出来，再恢复成原来的这个数组。OK。哦，这里面呢，又得动脑筋了，对吧，我们讲过怎么把一个数，把一个东西存到存到这个。把它存到一个，就是我们说存到一个呃，文件里面去，我们是讲过的，大家回忆一下当时是在哪讲的。对，当时是这样讲的，如果说同学们想不起来，那么你不用犹豫啊，找到我们曾经讲过的一个章节，是在在我的印象中应该是在16，不是16就是17。

博士时期。就是16。好，不是16就是。上哪去了这个啊，十十四啊，我们终于找到了啊，在这个地方我们寻寻觅觅，哎，老师曾经讲过，诶，怎么去把一个字符串一步一步的读进去，大家看。有reader，哎存这是读，我们还讲了一个存，哎，你先看存是怎么存的呀，是在第零个里边啊，这个里面讲的，看看是不是要写的哦，这个不是这是读，这个是读对不对，我们还写做了个写在这写大家看。这是一次性写入，这个肯定不合理，咱们不能用这个加货文学，我们肯定是一一行一行有效的数据存存啊，就是一个一个有效数据，咱们存存一行对不对，第二个又存一行，你看这样子的话呢，诶，我们应该是在第四个里面讲的。

果然是在这讲的，看到没有，你可以先建一个新文件，新文件比如说这个文件呢，你取个名字，哎，你取个名字在D盘下面有一个叫做chess棋盘。棋盘的一个data。注意啊，这个后缀无所谓，一般来讲呢，咱们存东西一般是自己定义一个文件格式啊，文件的一个后缀data，然后呢，你打开它，打开它过后呢，诶以写的方式打开，同学好，然后呢，怎么怎么样，最后关闭这里面这个十寸。同学们可以想象到，这个十寸就应该是你去遍历那一个。就是这这句这句话其实就相当于是我们在哪个地方写的呢，在便利。就是在我这个地方，同学们可以看到在我这，我不是在不停的遍历这个奇数数组吗？对不对，我可以把这里面的这个东西做成一个串串。

做成一个串，用空格隔开，把它保存进去。说所以说这个地方一保存进去过后呢，这个大家就应该有思路了，哎，你就应该有思路了，找到这个位置。那你每你你每没有一个字符串，你就把它写一行进去，写一行后面有个换行，所以说最后在数据库里边，在这个文件里边，应该是保存了这么一个东西。这个零一这个可以不要，你真正遍利的时候，这个零一这个我是为了让你们看到方便写的，其实你真正保存的数据应该是这样子的。各位，你真正在吸收数组压缩过后，你保存在文件里面的应该是这样子的，比如说chess。这是我们棋盘的脉图，对，然后呢是个data。啊，这个一一一般就不要取那个取他的名字了，就data叫数据把它保存起来。

对，把它保存起来，保存起来过后呢，你在这个里面应该是这样子的。哦，其实就这么三行。这个是零。那这个时候在你的在你的这个压缩过后的文件里面，其实就这么就这么一点数据，好这么一点数据过后呢，下一步你该做什么事情呢？诶你就把这个文件，你刚才不是把这个文件写进去了吗？诶你经过一番这个折腾对吧，你把它保存在一个文件里面了。你把它保存一个文件，这个文件呢，就是同学们刚才看到的现实。注意听啊，Map确实点data，这是你的文件，这个文件长的样子呢，大概就是这样子的。当然有些同学说老师我有别的方法，你最好用这个啊，这是最最简单的一种方式了，放进去，放进去完了过后，这个就叫存盘退出。存盘对数，当我们需要把这个东西再经过一系列的操作恢复到这个地方的时候呢，咱们就叫续上盘，那续上盘就是你要把这个东西重新恢复回来，这个简不简单呢？显然很简单。

这个很简单了，你恢复的时候是恢复到这个数组啊，这个系数数组在中间就意义不大了，你没有必要说老师我有没有必要把这个东西先恢复这稀疏叔组，再把它恢复到这，你吃饱了就没事干了，对不对？因为你这个地方完全没有必要这么走，走了嘛，你很简单嘛，你到时间可以这样干。你是这样做的，你说这个我在遍历这个，遍历整个这个地图的时候，我直接把它恢复成我们的这个原始的数组，这是可以的，因为你每遍历一行，我就可以建一个每我每。我每次遍历一次，我就知道你现在这个第一个数哪一个是零，我就把它初始化就行了。好了，同学们。现在呢，我给大家。初始化一下啊好，这个保存这块我就说完了，我们先截取一个视频，那么我。