00:00
下面呢,我们用代码将刚才我们分析的二位数组转系数数组和系数数组转二位数组的这个功能予以实现。好打开我们的。打开我们这段代码啊,打开我们这段,呃,这个eclips我就在这写,首先我们创建一个Java项目。这个项目呢,我们取个名字叫做。叫做data。Data structure。Structures就是数据结构structures structures数据结构这个项目,然后呢,在这里面呢,我们把数据结构写到这算法呢,我们到时间单开一个项目,好吧,下一步。Punish。好,首先我们建第一个包。这个包呢,我们讲的是系数入组,我这样见I com点艾特硅谷,硅谷点什么呢?SPA。
01:01
这个英文单词啊,SPASPA就是稀疏的意思,RA当然是宿组,这个很好理解,对不对?好,我们先写第一个案例。捡个包。那现在我先写第一个啊。勾上这个主方法。勾上这个主方法好的。那首先我们是不是按照刚才的思路,先把这一个原始的二维数组先创建起来,这个是不是很简单,来跟着老师思路,第一步先创建一个原始的。原始的二维二维数组,这个二维数组是11乘11大小的,是不是很简单了,那么写一个吧,还有一点啊,我们表示这个这个钱零表示没有子。没有棋子。啊,棋子。对不对,一表示什么呀,表示黑字。
02:01
我们刚才讲的一表示黑子,二表示男子,还记得吧,一表示黑子。黑子,那么二呢,表示蓝色的紫蓝紫。这个蓝色啊,蓝色。男子,好,呃,那现在我们就开始创建了第一个chase数组吧,就是棋盘chase。二位一,然后呢,它是一个二位数组,我们这样写六。Inch 11乘以11啊,好,这就是11,然后呢,我们给它赋值,我们刚才已经讲过了,他的黑子和男子分别只有一个,是不是分别只有一个?好分别位置是在哪里?第一这个位置。给他附一个一。这个大家不用多说,也理解什么意思吧。第三行的第四列。
03:00
是不是有一个蓝色的纸,是二复制完毕,现在呢,我们输出一把,输出一下输出。原始的二维数组。就原始二维数字已经创建好了,那这个时候呢,我们用for循环增强来输出一下。这个大家能看懂哈,Chase。我用的是for循环增强,从切位呢遍历出来,先是一个一位数组,这个我就不讲了,好吧,因为它原先是二位数组,你。循环便利的时候,显然是取到了每一行,然后呢,我们对它再进行一个取,那这个时候没取出来是个item,就是一个具体的数据了,对吧,也可以写个data。就是一个具体的数据RA。然后这里面我们就把这个纸打出来给大家看一下,我们格式化输出比较好看。格式化输出MD写成T,然后呢,我们这写个得塔。那么每打一行呢,我换一行。
04:01
代码就写完了,来各位朋友运行一下,同学们可以看到原始的二维数组呢。就长这个样子,诶地方好像有个小问题,呃,这个地方我们写写的有问题啊,这个是第,因为是第二行,第三行的第四列应该就是三。应该是在这个位置对吧,刚才我写成四了,这就不对了,在运行。好,同学们看这这个就对了,这是原始的二维数组,我们在这输出之前呢,可以给它。写句话叫做原始的二维。二维数组没问题吧?好,原始二维数组有了过后,下面我们要准备做一件事情,将什么呢?将。刚才根据我们这个思路,我们现在要把二维数组转成系数数组。是这个是动动作吧,第一步我们应该先便利。
05:00
便利,因为你拿到这个20组,你并不知道这个二维数组它一共有几个有效数据,所以你有些同学说我这儿不是写了两个呢,那是因为你写的。实际上你在。你在你在做的时候,你并不知道有几个有效数据,因此呢,你要先遍历二维数组。是不是先变六二组得到。得得到什么呢?非零,非零数据的个数。这个能理解非零个非零数据的个数。这个对我来说很简单,我就for循环一把就行了,先用一个int来记录,我想一共有几个。几个这个非零的值上默认为零或循环。我不喜欢谁呢?我不喜欢。这个切实以这个数组。对吧,就是他原先有多少,我们就便利多少。便利多少?一共我们进行一个便利。
06:01
便利。好,那现在呢,这个地方一共是11乘以11,我们就要去,这样便利了,假设我这写的稍微的笨一点啊,就写个11,因为它有一共有11个嘛,11行,再来遍历列列数。结。等于零。等于零,解小于多少呢?11解加加。好的,那么现在我做一个判断,如果切数组一,它的I和解,现在呢?它不等于零。它不等于零,如果它不等于零,我就让这个sum加加。这就完成了,好,现在呢,我可以验证一下上等于多少。它应该等于二。是不是等于二,它应该有两个两个非零的值。好,我们看到的确等于二好,有了这个结果过后呢,我们下一步干什么呢?
07:01
来创建啊,我们现在创建。对应的对应的一个稀疏数组。为什么?根据刚才我们的分析,是不是因为你有这个上这个系数,数组的行就固定下来了,而列呢,始终是三?因此这个系数组就可以创建了,那我们在创建一下int。Spas。SPASPRSPRSP。As系数组。那么同样它是一个二维数组,对不对?等于六一个int,那么它的行呢?刚才我们已经统计了,是上加一列是三。没有问题吧,同学们。啊,这个是没有问题的。然后下一步有了这个东西过后呢,我们就把这个非零的值给到他啊,然后是干什么呢?给稀疏数组赋值。
08:09
是这个意思吧,因为你要复制,大家都知道第一行稀疏数组的第一行,根据刚才分析,第一行应该是存的什么。原始数组的有多少行,有多少列,以及一共有多少个非零数据,是这意思吧?好,这个对我来说很简单,来走一下。好的,那SPA。Spas。第零行第零列应该是11。没问题吧,那么第零行。第一列啊,应该是第一行的第一列,第一行的第二列,但是它下边从零开始嘛,对吧?好,然后值一共有几个有效数据呢?一共有三个,这个sum后面有用。这个上后面有用啊,同学们好,那第一行我们就初始化完毕了,初始化完毕了,现在呢,我们来做下一个动作就是。
09:04
因为你现在有什么呢,你现在一共是拿到了。呃,第一行做完了,那下面是不是一。你现在要。你你现在要把这一个二维数组的,就是把这个二维数组里面的非零数据存放到系数数组里面去,所以说你又要进行遍历,对不对,好现在呢,电力二维数组。变力二位数组将非零的值,非零的值干什么呢?存放到。哎,存放到哪里去呢?系数数组中就可以了。因为你刚才编辑的时候呢,只是拿到了这个sum。对不对,你拿到说这个时候稀数数数还不知道有多大呢。因为你不先把这个sum遍历出来,你无法创建这个系数数组。
10:03
除非你用集合,但是呢,我这要求大家不能用集合,我用的就是数组,因此你先拿到上的时候。你有了上门才能创建这个系数数组。好,现在有了系数入组,我们对这个原先这个20组再变遍历一次呢,就可以把这个具体的非零数组数据放进去了,那前面这段代码我们拿过来用一下就可以了。怎么做呢?好,同学们看,这是一段for循环代码,我拿来用一用。那你在便利的时候,这个地方是一个非零的数据,好非零数据,那你就往里面放呗。对不对,就往里面放那。这个地方。这个位置很好放,就是它的第零列,它的第一列应该就是什么呢?就是I,这个没问题吧,它的第二列应该是节瑞士基的行和列嘛,它的第三列。它的第三列应该是什么呢?应该就是这个值本身。
11:05
大家看看能不能绕过来,问题是这里这个问号是什么,因为这个问号呢,它需要递增,就是你的第一个非零数据是放在。系数数组的第二行,而你的第二个非零数据放在系数数组的第三行,那你这个地方应该递增,所以说我这里用一个计数器来搞定它,Count默认来一个零,这个count干什么呢?Count用于记录。用于记录是。是第几个非零,非零数据能理解我意思吧,那就很简单了,那同学们,我们把这个count进行一个加加。那加加完了过后呢,我们把它直接放在它这个所在的行。完事。好,当我们这样完毕过后,同学们,我们系数数组就创建起来了。能理解意思吧,好,现在呢,到了这一步,刚才就是给系数数组赋值啊,这个也是赋值,那么现在我们可以看一看输出输出。
12:09
稀疏数组的这个形式是什么样子的?系数数组的输出呢,也非常的简单,我们把这个系数数组来进行一个输出。来,先换一行。当然了,我们再说一句话啊,就是说一个就是。呃,得到的,得到的这个稀疏数组为。为为如下形式。好,那么现在呢,我们把这个系数入组来遍历输出一下就可以了,来说一下啊,For循环。For循环对谁进行for循环呢?对这个系数数组进行循环。是不是它一共有几行。那就是认识,我现在把它打出来看一下。好,我把它格式化一把,把它格式化一把。首先呢,我们先输出它的第一列。
13:03
第一列好第一列,然后呢,再来第二列。再来第三列,大家能跟上我的思路啊,再来第三行,第第三列,这是格式化,每一个呢,来一个制表符隔开。斜杠T100分号斜杠T100分号斜杠T好,那这样这样就它就每打一个呢,就有个制标符,然后呢,这边我们就输出第一个啊SPA。它所在的这个行的第一个数据。其他以此类推,是不是?它所在行的第二列,它所在行的第三列。代码就写完了。好,现在呢,我们运行一下,看看这一个系数数组跟我们想的是不是一样,它的系数数组应该长的这个样子。是不是这样子的呢?我们便利一半。代码非常简单对不对,你看好这个,因为为什么没有看到这个效果,是因为我在这输出了过后呢,没有换行。
14:02
没有换行,那如果现在我要换行的话呢,我在这加一个斜杠N就能解决问题,大家现在再看一下。是不是第一行是。记录的原始数组的有多少行,有多少列,以及原始数组有几个非零数据。下面的行呢,分别记录这个非零数据的行列以及值,那比如说同学们,我给你再稍微改一改,你们看看有没有相应的变化。比如。我说比如啊,比如我在这个地方又加了一个蓝色的字,男子是第几行呢?第四第五行第六列有一个蓝,有一个蓝子。假设是这样子的,你同学们看我运行。同学,看是不是这个稀疏入组马上就得到变化。他说,在原始数组的第五行第六列有一个男子,他的职位二。
15:00
是不是这个道理,同学们好了,那有了这个数据以后,有了一个数据以后,这个我们所说的这个动作就已经完成了,就是二位数组转系数数组就做完了。比较简单吧,那现在呢,我们紧接着完成下一个动作干什么呢?我们完成将稀疏数组。恢复成。我们叫做恢复,好吧,恢复。恢复成什么呢?原始的二维数组。也非常的简单思路其实刚才老师已然讲过。是不是这个思路,是不是在这儿我已前给同学们分析过了,而且也很easy,就现在给大家讲的系数数组其实是最简单的一个。最简单,那现在呢,我们来按照这个思路先走一走。因为你现在要把系数数组返回去得到二维数组。你首先。要知道原先这个二维数组应该有多大,有多少行,多少列,你必须要把这个数据和这个数据读取出来,这个能理解吗?
16:09
因为你没有这个,你没办法得到一个新的二维数组。因为你原先那个数组已经丢失了嘛。你可能是在另外一个程序里面做的,是这个道理吧,所以你先要把它的行和列读取出来,这个很简单,来第一步,第一步先。读取。啊,我这其实已经有了,先读取系输入第一行,根据这行来得到一个二维数组,那我现在就直接写代码了啊,那同学们跟上我的思路,现在呢,我们来开始完成这一段代码的。功能第一个动作啊,首先我们新建切实。A2。它是一个二维数组。IN61个int。第一个行是多少,第二个列是多少,我先问大家应该怎么怎么做是不是?
17:04
拿到这个稀疏数组以后。拿到这个系数数组以后,这个稀疏数组的第零行的啊,第一行的第一列。就是它的行。能理解意思吧?系数数组的第一行的第二列就是。二维数组有多少列?能理解我意思吧,好,这个就搞定。搞定,那么这个。这个二维数组搞定以后呢,它其实现在大家都知道,此时此刻这个二维数组如果你输出来的话呢,它是全零的。能理解为什么你看你们可以看一下啊,比如说我现在输出这个恢复。就是我们说恢复后的。这个二维数组,如果这个恢复后的二维数组,我没有做任何处理,我们看看是长什么样子啊,恢复恢。
18:01
恢复后的二维数组。它长什么样子呢?好,我们来换一行输出。这样呢,大家看起来比较清晰,诶,这写错了啊。我们system out。啊说你诶print。好,这样子就可以了,那么我们把二位数组呢,再给大家打一遍。这个是不是二位数组啊。这是二位数组吧,当然我输出我输出,现在呢,要把这个切时位一改成切时二位二就可以了,来我们看看此时此刻你恢复完了过后,其实。它是全零的。原因也很简单,因为你没有把他的数据。给重新付回去吗?因为你还少了一个什么动作呢?这个动作是不是你现在应该做这件事情,把读取到的系数数组的后几行记录分分别付给分别并读取这个数据,并付给原始的二级数组,那这个工作呢,我们要做一下。
19:08
这个动作应该怎么做?显然应该用循环来做,你不做循环的话肯定很麻烦了,对不对?现在呢,我们来便利。我们便利这一个稀疏数组来做这样一个工作。For循环我走一下啊。我们遍历这个系数数组,遍历系数组,那么int I从第几行开始遍历呢?从系数数组的第二行七书数的第二行开始。从第二行。开始。因为第一行我们存的是。原始数组的行列以及它的有效数据的个数是吧?所以要跳过,因此从第二行,那么I就应该等于一,能理解吧,那就I应该小于什么呢?小于我们这个稀疏数组的。
20:01
这个认识。I加加能理解。哎,就这好,现在我们要做的就是把这个系数数组里面的值放进去,而且这地方不需要再判断是不是零了,因为系数数组放的全部都是非零数据,或者说有效数据。好,那现在呢,我们就要做这样一个工作,走72。是不是因为这个72是我们恢复后的嘛,那现在呢,这个72的行和列就直接从这个系数组里面来读,是I里面的第零列是它的行。稀疏数组的这个I行的第二列就是它的列。好,然后这边是不是多打了一个啊,然后这个是值是多少呢?值就是稀疏数组的。这个第行第。Did行D节裂的这个数据这就恢复回去了。
21:03
好,当然这个结没有啊,这个节是写错了,应该是二。因为是呃,第行的第一列是它的行,第行的第二列是它的列,第行的第三列是它的值,这就恢复完毕了,好,同学们,我们来看看恢复有没有成功打开。当我们运行过后,我们发现数据已然恢复一。二。一。好,我们再来看原始数据呢,121搞定。好,你看我们中间经过一个二系数数组的一个处理呢,其实数据量变得很小了。数据量变得很小,这就达到了一个压缩的效果,如果我们在开发中呢,使用这个小的技巧,在无形中可以节省我们的这个空间,或者提高我们的效率,提高我们效率,这就是七书数组的一个经典应用,经典应用好,最后呢,我给大家出一个课后题,希望大家去完成。
22:05
大家也看到,刚才我有一个问题,就是我的代码呢,没有去把这个系数组保存在文件中。那同学们啊,我给同学们一个课后练习,在老师这个代码的基础上,将稀疏数组保存在磁盘中,比如说map点带塔。在恢复数据时,先读取这个map点塔恢复成系数数组,再恢复成。二位数组。也就是说同学们把这一条线。给我完成了,难不难,不难,为什么?因为你学Java的时候一定学过。IO,那你。把这一个当成一行存进去,把这个当成第二行存进去,把这个当成第三行存进去,不就完了吗?啊,这个你要完成不了,说不过去啊,因为我把这个系数数组的一个核心代码已经给同学们介绍了,而这一块才是我们的数据结构的核心,这块属于IO,我就没去讲了啊,同学们可以课后自己把它完成,也并不难。
23:10
也并不难,好同学们,我把刚才的代码和给大家整理一下。那刚才呢,我们。呃,我们讲完这个思路过后,我们把代码呢给同学们实现了一把。实现了一把,就是第四步对代码进行了一个实现。我把代码呢,给同学们板书过来,代码我这样板书啊,简单一点,直接拷贝,然后放在我们的笔记中即可。好吧,同学们这个课后呢,哪个地方不明白,就把这个代码拿出来看一看,理解一下并不难,最后这有一个课后练习,要求同学们去做的课后练习,课后课后练习。这个课后练习呢,是要要求同学们把我们在老师基础上把系数数组保存在磁盘中,这个也并不难。
24:04
啊,稍微带一点点文件IO的东西在里边。啊,只要学过Java的同学对这个应该是没有难度的。好,同学们,那关于稀疏数组的一个代码实现就给同学们讲到这里,讲到这里。
我来说两句