00:00
下面呢,我们来讲我们的第一个第一个数据结构啊叫什么呢?叫做稀疏数组SP。那这个这个数组的它的存在的一个价值是什么呢?我们先来看一个需求。说我们在编写一个五子棋程序的时候。那么在这个程序里面呢,一般来讲我们都有一个存盘退出和续上局的一个功能,对吧,一般这个游戏嘛,都有这样一个功能,那现在呢,我们假如有这样一个情况。怎么一个情况呢,就是大家看这是个棋盘。这是一个棋盘。这个棋盘啊,挺简单的,大概是11行11列是不是11行啊,一二三四五六七八九十对。11行11列,那这个11行11列里面呢,假设我们就下了两个字。下了两个子,下了两个纸过后呢,假设我们用黑纸代表。
01:00
一用一代表黑痣,用二代表蓝色的痣。那现在有一个问题,假设我们将来这个棋盘非常的大。我们其实有效的数据其实只有一和二。但是。你却怎么做的呢?你却把整个地图要保存起来,在我们做开发的这种需求上面很多,这种需求很多,那我们能不能。把这个稍微的改进一下呢,就说我们既可以保留有效的数据,同时我们让这个保存的数组变小一点,诶那么在我们这个数据结构里面呢,有一种东西叫稀疏数组,可以解决这个问题。啊,很多这个。呃,编程语言里面都有,它这个主要是一种思想,就什么呢?当我们将来有一些数据,有很多冗余数据,是可以进行一个压缩,其实压缩的本质是什么呢?压缩的本质就是去掉一些重复的没有意义的数据,或者说你这个有意义,但是呢,我们能不能用一条语句把它全部记下来。
02:10
啊,这就是压缩的一个本质,到时间肯定还会涉及到一个,会涉及到一个恢复,好,那么我们就来看一下这个题,我们这是需求,大家知道了啊,需求知道了,那么我们来看一下,当一个数组中大部分的元素均为零或者为同一个值的数组时,可以用系数数组来保存该数组,系数数组的处理方法是这样子的。先记录数组一共有几行几列。有多少个不同的值,就是呃,这个数组里面先记录下来,它原原先有几行几列,然后有多少个不同的值。先把它记下来。然后呢,把具有不同值的元素的行和行列极值记录在一个小规模的数字中,从而缩小程序的规模。我举个例子,比如说同学们看到这边这个数组。
03:12
这个是一个原始数组。那这个原始数组我们可以看到大概是1234566 1234567,就是六行七列。六行七列,那六行七列里面我们看到有效数据其实就这么几个。大家可以看到有这么几个数据对吧?好,同学们,假如这样一个情况,我们就可以把它怎么保存呢。假如我们真的要存盘呢?我们就可以这样存。比如说。我们存一个行列字,这行列零三,这一个有有个22,就把这个记下来,零六。这个15记录下来,其他以此类推,那实际上你看原先的这个规模就得到了一个简化。
04:01
就是原先一个大的数组换成了一个小的数组。OK,当然你的数组越大,我这个效果就越明显。对吧?越明显好,这个思想大家就很清晰了。那现在呢,我们来走一个具体的案例,我们以这个应用案例来写一段代码,比如说我们用系数数组保留类似前面的二维数组棋盘或者地图等,把系数数组存盘,并且可以重新恢复原来的二维数组。整体思路是这样子的,我这画了一个图。所以是这样子的,这边是一个二维数组。系数数组呢,我们到时可以记成,把这个行列记下来,幺幺和21行12列,这个二呢,我们可以记录下一共有几个数据。就说呃,我这个有效数据一共有两个。啊,这个一二,那这个一呢,就代表第一行。第不是代表第一行啊,代表下标,下标为一,下标为一,其实就是代表第二行了,是吧,因为它是从零开始变的嘛,那这个这个一其实就是一二对应的一,这个二呢,是相当于索引,呃,第二第三行第四列对应的一个二。
05:18
好,然后这一张保存起来过后呢,得到这个再进行保存数据,保存完数据过后,如果需要,如果需要我们这个恢复啊,需要恢复我们再把它重新读取。读取到这个系数数组,再恢复成我们的元素组。大致思路,降子。那这里呢,我给大家就直接演示这一部分,因为这个存盘这个地方呢,同学们这个这个对于文件的操作啊,就比较简单,我主要是把这个核心的语法给他写一下。
我来说两句