00:00
我们来看一下数据结构的这个第一个部分就是系数、数组和队列。稀疏数组和队列,好,首先呢,我们还是老规矩啊,我们先讲一个,呃,数据结构的时候呢,我们先提一个实际的需求,这样呢,大家思考起来会比较容易一点,首先我们看在编写五子棋程序的时候,我们有一个存盘退出和续上盘的功能,对吧。那么也就是现在你们看到的,假如我这里有一个棋盘看清楚,那么这个棋盘上面呢,大家可以看到这个棋盘是应该是11乘以11的这么一个棋盘,这个棋盘呢,现在有两个子,一个黑子,一个男子。好,现在呢,我要求同学们把这一个棋盘给保存起来,你们会怎么做?显然我们第一个最简单的思路就是把这个棋盘用二维数组的方式记录下来,是这意思吧?那也就是说我们会把这个棋盘通过一个二维数组保存起来,就形成这样一个二维数组,这个二位数组呢,可以看到一共有11行,11列,我就不去数了,其中有一个一,有一个二,那么假设这个一表示黑子。
01:29
对吧,表示是一个黑字,那么呃二呢,二这个这个咱们可以看到啊,这个二,二表示蓝蓝色的字,所以说这里有一个一,有一个二,而且同学们可以看到是哪里呢?是第二行的,第二行的第三列是一个一表示黑纸,第三行的,大家看第三行的,第三行的第几列呢?第四列。是一个二表示男子,好,这个就是呃,二维数组记录下来,那么现在有一个问题,同学们想哈,我现在提一个问题,请大家思考。
02:07
要把这个棋盘转成二维数组,对我来说没有难度,挺简单的。但是我有一个问题请大家思考,因为该二维数组有很多值都是零,大家可以看到。几乎大部分是零,很多值是默认值零,因此记录了很多没有意义的数据,这个时候呢,就可以用我们稀疏数组来对这个二维数组进行一个什么,进行一个压缩。进行一个压缩好,那么到底二位吸收柱是什么样子呢?我们来看一下。系数数组的基本介绍当一个数组,当一个数组大部分是零,它的元素为零或者为同一个值的数组时,可以使用系数数组来保存该数组。那么系数数组的处理方案,处理方法是什么呢?
03:02
它记录数组一共有几行几列,有多少个不同的值,就是说它的第一行。它的第一行记录你原先这个数组有几行几列。而且一共有多少个不同的值,能理解吧?后面我们有一个图,大家不要着急,那么把具有不同值的元素的行和列极值记录在一个小规模的数组中,从而缩小程序的规模,而这个所谓的小规模的数组就是我们所说的稀疏数组。哎,这就是我们所谓的稀疏数组。那么吸收柱子到底长什么样子呢?我们看一个图。这个就是一个稀疏数组的。一个案例,同学们可以看到,在这儿。这是一个原始的二维数组。这是一个原始的二维数组,那么这个二维数组呢?如果我们保存,如果我们不,我们就使用原始的二维数组来保存,一共有几行?一共有六行七列。
04:10
一共要记录42个数据。是这个意思吧。那如果我们用系数入组,它会变成什么样子呢?大家看这个对应系数入组它的第一行。记录。记录什么?原始数组有几行?有几列?他的第第二第二行,呃,第一行是记录的第一行,第一行的第一列。记录行第一行的第二列记录列。第一行的第三列呢?记录一共有几个值,你看我这一共有几个值呢?有八个值。大家看到没有,一共有八个值,这八个值呢是呃,非零的,所以说记录八,那么在下面呢,在下面每一行分别记录。每一个非零值的行列和它具体的数据大小,那这样子同学们可以看到。
05:07
我们原先这个四乘以七的一个二位数组,就变成了这样一个什么呢?几行几列的呀,九行三列的一个一个数组。27个数据,原先是42,现在变27,所以说。起到了一定的。把这个原始数组规模变小的效果。看清楚没有。好,这个就是我们所谓的稀疏数组的一个。就是它的一个应用场景,就应用场景好,那这个应用场景有了过后呢,我们把它呃讲讲到这儿,就是这是系数数组的应用场景,我们把它用笔记记录下来。好,那刚才我们讲的是系数、数组和队列的第一部分。就是系数数组的应用场景。
06:02
好,这个地方我要稍微的往下拿一下啊。稍等,我先拿一下。好的,首先呢,我给同学们看了稀疏数组的一个应用场景。应用场景就是一个需求嘛。对吧,一个需求好,我记录下来。这是他的一个需求,当我们编写一个五子棋的时候,大家可以看到。假如我这里有一个五子棋,我把这干脆这样子记啊,同学们,咱们整个把它。保存下来。对吧,保存下来好,那有这样一个问题,我们如果使用原始的二维数组是这样记录的。那么原始的二数组存在的问题就是什么样呢?有很多没有意义的数据,因此我们就提出系数数组可以达到一个。
07:02
压缩的效果。好,那么紧接着呢,我们就给大家讲了一下稀疏数组的基本概念是什么。好,我们把它拿过来。稀疏数组的一个基本介绍。对吧,它的概念是这样子的,处理方法呢,是第一行系数数组的第一行。它记录的是。共几行几列和共有多少个不同的值?好,从而达到缩小程序规模的效果。这是它的基本介绍,紧接着呢,我们举了一个案例来说明稀疏数组的。他的,呃,长什么样子?好,这是稀疏数组的一个案例,我们也把它放到这一栏。叙述数组的案例呢?就是这样一个案例。
08:01
这个是同学们看到啊,这个是原始数组。这个就是原始的数组。原始。的二维二维数组。那这个原始的二数组经过了,经过什么呢?经过了我们一个处理过后。它就变成了这样一个数组,这个数组同学们可以看到,就是你们现在看到这个数组呢,就是我们所谓的系数数组。对,稀疏数组就这么来的。好,然后呢,我把这个图给同学们放到我们这个笔记里面去。呃,一目了然对吧?好,这个就是稀疏数组的一个基本介绍,它的一个应用场景,就这样来的,截取一段视频。
我来说两句