00:00
我们现在来看稀疏数组的一个应用实例,那么再讲一个稀疏数组的,呃,应用实例的时候呢,我们这样子做啊。我们先做一个思路分析。同学们看。使用系数入组来保存类似前面的二维数组,比如说棋盘或者地图对不对?因为我刚才举的是棋盘,但在实际的应用中呢,也可能是一个其他的地图,比如说二维,二维数组就可以,那么我们用系数数组来存盘,并且希望可以重新恢复为原来的二位数组。那么这个思路我们来分析一下,比如比如我们就以前面的这个二维数组为例,以哪个二位数组呢?以这个二维数组为例,这是原始的地图啊,这是原始的,呃,这个棋盘,这是数组,我们看看它会怎么做,打开我们的图解。打开我们的图解,我们要画一个图来描述一下这个过程。好,往下面走一走啊,同学们看。
01:02
现在的情况是这样子的。这个棋盘对应就是同学们可以看到这个棋盘。它对应一个二维数组,这个没有问题。好,因为这个二位数组里面有大量的大量的零这个默认值没有意义的数据,因此呢,我们要把它转成一个什么呢?把它转成一个稀疏数组,那么转成一个系数数组,这个数组会长什么样子呢?我给同学们简单的画一下,大家一下就明白了。这个稀疏数组,稀疏数组它长的样子大概是这样子,我把这个图放大一点。首先呢,它的第,它的它是这样子的,第一行若。列。然后呢值,所以它总是呢,Value va al啊,它总是一个三,就是行不确定,但是列势三列的这么一个动态数组,好它的第一行记录的是什么呢?好重新看要把这个转了啊,它的一行记录它原始的二维数组一共有几行几列,显然是11行。
02:14
11列它有几个数据呢?两个有效数据,它的第二行。第二行,第二行记录的是第一个有效数据,第一个元数一,它是第几行,这个一是在原始数字的第几行,第几列呢?第二行,第第二行第三列,因此这边应该记住的是一。二值是什么呢?一大家能看懂吧?大家能看懂这是什么意思吗?第一个一代表是。第一个有第一个有效数据所在的行行为一,但是实际上因为它下边从零开始嘛,一其实代表第二行。二代表第三列,能理解这意思吧,好值是一,紧接着呢,它还有一个有效数据是二。
03:00
它是这个二呢,它是在第几行呢?是在第三行,第三行应该是用二表示了,因为下标是从零开始的,对吧,这个我就不讲了,第几列呢,第四列,因此这边应该记几啊三值是多少呢?二。好,同学们看,这个圆心的二维数组就变成这么一个数组。那你同学们想一想,你原先它的规模是11乘以11这么大,现在经过一个稀疏数组的处理,它变成多少了呢?它就变成了一个几行几列的呀,三行。吉列三粒变久了。很小了吧?那这个呢,就是我们刚才所说的一个,呃,用系数数组来压缩二维数组,那反过来。反过来我们还需要干什么呢?到时间我们还需要把这个系数数组再恢复成二维数组。也就是说,当我们进行这个。
04:02
这个读盘操作的时候,就是续上局的时候呢,我们还有一个功能,就是能够把这个吸数数组再恢复成二位数组。那么我们来把这个思路捋一捋。来,我说一下待会儿我们要做的这个思路。那么二维数组转转这个稀疏数组的思路如下,第一步。第一步,第一步干什么?首先呢,我们要去,我们要去统计,你看啊,要完成这个做完成这条线。完成这条线,好,我换一个不同的颜色啊,这边换另外一个颜色,就是我们要完成这一条。这个这个蓝色的线,它的思路应该怎么样,首先我们要便利。遍历二维数组,原始的,原始的二维数组得到有效。
05:02
有效就是得到要保存的有效。有效数据的个数。是这意思吧,个数这是第一步我们要做的,为什么要得到有效数据的个数呢?因为我知到有有效数据的个数有多少,我就知道将来这个系数数组它的大小是多大了,好,然后根假设这个有效数据个数为sum,好,然后呢,根据根据这个sum sum就可以创建稀疏数组。系数数组呢?我们一般用pass这个单词来表示这个系数数组大小,同学们可以看到它的大小就应该是这样子了,就int行一共有多少行?Sum加一行列有几列,三列。因为列它是固定的,能理解吧,行不确定,因为行呢,取决于你有多少个有效数据好了,然后第三一步,第三一步将什么呢?将二维数组的有效数据存入到系数数组即可。
06:12
将二维数组的有效数据。的的A的有效数据。的有效的有效有效数据。数据存入到系数数组中。系数组中就完成了,这个是二位数组转系数数组的一个思路。大体的一个思路,现在我们再说稀疏数组,转转原始的,原始的二维数组。二位数组的一个思路,同学们看好。你这个sum加一它第一行啊,我刚才还有一句话,呃,还有一句话没有说出来,大家应该知道这个稀疏数组的第一行。
07:05
就是存的原始数组的行和列,这个没问题吧,好,那么你在恢复的时候应该第一步干什么呢?先先读取到,先读取稀疏数组的第一行。没问题吧,第一行。它的第一行里面不是有二位原始二位数组的行和列吗?好,根据啊,根据根据第一行的这个数据创建原始数组。原始。原始的二维数组。比如上面的啊数组,比如上面这个原始的数组,比如说我们叫CHS棋盘hes ch2它的大小呢,就应该是一个int多少,这边读到11,这边再读一个11对不对。
08:00
好把这个就可以恢复出来,第二步在干什么呢?再读取。读取稀疏数组后后面的后几行的数据后后几行的。几行的数据并并干什么呢?并付给。付给。付给这个原始的二维数组。即可,代码就写完了,是不是道理很简单呀,代码很简单,那我这里有一个过程没有写,就是系数数组保存到磁盘,这个过程没有写。那么同学们呢?因为把这个数组保存到磁盘,这个是属于IO的。IO的这个部分同学们呢,自己去完成就可以了,就说你这个系数入组最终还要保存到哪里呢?还要保存到磁盘上去。我这块呢,就没有去给大家,呃,写了啊,就是实际上呢,你这个系数数组,因为要存盘的话呢,你仍然还有这样一个过程,整个过程呢,还要把我们的稀疏入组。
09:10
存盘到一个文件中,这个我就没写了。文件,当然你要把这个系数组恢复到原始数组,其实还有一个过程,你要干什么呢?你要把这个文件。文件先恢复成系数数组,然后再从系数数组恢复成原始的二维数组,大家明白这意思吧,但是这个过程就是关于这个过程我就没有写了,同学们有兴趣自己去写,好思路我们就分析完毕了。就是二位数组转系数数组和系数数组转原始二维数组的思路就分析完毕,下面呢,我们就准备写代码。准备写代码,好,我在写代码之前,把这个思路捋捋到我们的笔记中去。好,刚才我们讲的这个系数数组实际案例的前面三个部分我们已然完成。
10:02
已然完成那三个部分,哪三个部分。好,第一个部分。啊,第一个部分,第一个部分就是我们所说的,呃,保存,第二个呢,存盘是将二数组转成系数组,整体思路分析。整体的思路分析呢,我也给同学们这做了一个分析,把这个图拿过来,大家看一下就行了。好,我把这个图整取整体给同学们放到我们的笔记中。其实思路挺简单对不对,思路挺简单,下面呢,我们就准备代码实现。其实同学们要知道,我们写一段代码本身并不难,而前面这个思路其实是挺重要的,就你怎么想到能够这样去处理。这个就是算法的力量,就是别人在设计这个数据结构的时候呢,嗯,也是动了脑筋的,而我们要做的就是根据别人的这种设计来应用到实际的开发中。
11:05
当然提高我们程序的一个效率,好,那么呃,思路分析就到这儿。
我来说两句