00:00
好,那么接着的话呢,咱们来看下这个第14章啊,这个第14章呢,是延续我们这个第12章的这个内容的啊,主要呢,我们就来讲一下啊,原来讲这个第12章的时候呢,提到过这个层次三,诶我们在这个位置呢,讲到的啊,这个层次三的话呢,主要是针对于咱们集合当中啊,它相关的这个源码啊,第一个呢做一个剖析,第二个呢,就这源码呢,我们来讲讲常见的数据结构的问题,OK,因为呢,这块内容相对来说难一点,所以呢,我把它呢就分开了啊,12章呢,主要是代码层面,大家呢去。诶掌握一下这个一和二啊,然后呢,第14章呢,主要就是看源码这块呢,现在代码呢就比较少了,但是呢,对大家要求呢比较高一些,因为呢相对来说难一些,好那这时候我们直接打开我们这个课件。啊,来看一下啊,这一章涉及到内容呢,其实也比较直接啊,主要呢,就是两大块儿,第一个呢,我们就来说一说常见的这样的一些数结构啊,然后第二部分呢,我们来看一看,咱们在集合这一块是跟数据结构呢接触比较近的地方了,我们看一看集合当中是如何使用啊一些相关的数据结构来设计它底层的这样的一些容器的啊。
01:02
好,那首先的话呢,我们来讲解一下这个数据结构的一个问题,那用一个比较形象的例子呢,来理解一下这个数据结构,这儿呢,我举了一个这样的一个战场上的一个例子,那以这个打仗为例呢,这个战场就相当于我们这个程序运行所需的软件和硬件的一个环境,这个环境呢,有的好,有的呢就恶劣一些啊,有的配置高,有的呢就配置低一些啊。然后敌人的话呢,就是我们这个项目或者模块呢,一些功能需求,针对这个需求呢,我们该如何呢去设计啊,相关的业务逻辑如何呢,去选择更好的更适合的数据结构啊,指挥官的话呢,就是大家。啊,就相当于你写代码了,你自己啊,这个士兵和装备呢,就是一行一行代码了,那么这里所谓的战术和策略呢,就是数据结构,包括呢,还有相关的算法的问题。那当然了,你说我这块呢,写这个工程逻辑,写这个业务逻辑哈,我要是不太注重这个战术和策略呢,也行,因为基本上历史上我们看到这个战争是吧,战役的话呢。
02:00
基本上我们看到都是以多胜少的。是吧,你人数多的话呢,跟别人打仗,数倍于敌人的这个兵力,一般情况下呢,就别呢犯一些常识性的问题是吧,然后别跟对方这个智力水平差别太大是吧,一般情况下呢,都是胜的。啊,所以说在历史上呢,我们看到的一个以少胜多的战役呢,通常都比较有名,因为除此之外呢,一般都是以多胜少的啊。啊,那也就是说呢,我们要是不太注重这个战术和策略啊,我们就纯靠这个代码给它往上怼呢,相应的逻辑呢,也能够实现。啊,只不过呢,这个性能呢,相对来说呢,就会差一些啊。啊,这个呢,你可以理解成了,就是不太讲究这个战术战略的是吧,诶你要讲究这种战术战略的话呢,我们可以呢,实现叫事半功倍的一个效果是吧。啊,一说到这儿的话呢,通常我们说这个,呃,东西方打仗呢,这个思路呢,就不太一样是吧,这个中国人打仗的话呢,就讲究这个36计啊,孙子兵法呀,是吧,从那个很早呢就延续到现在啊,这个西方人打仗的话呢,其实都是。呃,思维比较直是吧,一般呢,就约定咱们哪一天啊,上午十点啊,你在这边我在这边,咱们就fire是吧,大家就往一块儿中间冲,然后谁赢了就算谁的哈,诶中国人打仗的话呢,可能约了十点前一天晚上都给你抄了家了,都是吧。
03:15
哎,这中国人打仗这个思路啊。诶就是中中西方这个思维方式呢,就不太一样啊,之前呢看过一个例子啊,说呢讲这个军人是吧,说这个美国人啊,如果呢,这有一个小的部队是吧,往前这块去走,这块呢就是悬崖了啊,让他呢跑步前进啊,美国人呢,就走到这个悬崖边上的时候呢,自动的就拐弯了是吧。哎,说日本人呢。啊,掉一下也不至于,那也太太蠢了是吧?哎,日本人跑到这跑这个悬崖边上就停下来了。不走了是吧,他知道了,再往前走就掉下去了是吧?哎,中国人呢。诶,中国人过去之后呢,然后呢,呃,就是日本人,你要在这停了,他会说谁让你停了是吧?中国人呢,不停在这边还原地踏步啊,你让他走吧,他也不走,你说停了吗?他也没停,我也没拐弯是吧,你也没让我拐弯,就是原地踏步是吧?聪明的做法是。
04:04
OK啊行,这个思路呢就不一样啊。啊,那么刚才呢,我们由这样一个例子呢,指出来啊,这个战术和策略呢,就好比是我们的数据结构啊,没有说呢,我们解决相关的问题,一定要使用这样的数据结构,只能说呢,我们选择更适合的数据结构。啊,那数据结构是什么呢?说就是一种程序设计优化的方法论啊,研究数据的,那这块我们关注一下啊,研究数据的叫逻辑结构和物理结构,以及它们之间的相互关系,并对这种结构定义相应的运算。啊,目的是什么呢?加快程序的执行速度,减少内存占用的空间,说白了,前面呢,对应的就叫时间法度。是吧,你越快越好啊,后边呢,减少内存空间的占用,那就是空间复杂度。啊,很多时候呢,我发现呢,时间复杂度和空间复杂度呢,他俩是此消彼长的。啊,从我们相关的一些经验上来看的话呢,时间复杂度和空间复杂度来讲,我们更看重是时间。
05:02
所以在很多的这种算法当中,我们都出现了叫以空间来换时间,哎这样的一些做法,OK啊好,这呢就是关于我们这个数据结构呢,呃,整体上的一个描述,这样的一个概念啊,诶,我们打开现在的这个零一啊,第一个呢,就是相关的一个概念,这个呢,大家也是作为一个了解就可以了。但是呢,在这个概念当中啊,其实我们就看到了几个啊,数据是吧,几个词儿,这几个词儿呢,其实就刻画了我们整个数据库,呃,数据结构的一个研究对象,这里边呢,看就提到了这个三个研究对象啊,第一个研究对象呢,就是数据之间的叫逻辑关系啊,也可以叫逻辑结构。哎,数据之间的。哎,这个我们叫哎逻辑啊关系啊,好,那么数据之间的这个逻辑关系都有什么样的关系呢?哎,下边这块呢,你看就是它的研究对象啊,最弱的一种关系呢。哎,就是叫集合的一个结构,就好比我们下边这个图当中,你说这里边儿呢,这些元素之间是什么关系呢?诶我们只能说呢,要用一个圈呢包起来,他们就是一个集合当中的多个元素,这种关系呢特别弱。
06:07
啊,就比如说你在路上呢,看到一个美女是吧。然后你说你俩有什么关系呢。对,都是人是吧,对,就是之间这种,诶都是人在呢,对,算是一种集合结构了是吧?诶你要非要说有什么关系呢,就是在某年某月某日啊,这个时间出现在这个地方了啊画一个圈呢,你俩都是一个集合里边了是吧。除此之外的话呢,可能就没有别的关系了,如果还有点儿别的关系呢,你得想办法发生点什么关系是吧。啊,有的呢,就是处在你的一个图形结构当中了啊,错综复杂的是吧。OK啊,那这种关系呢,我们叫做集合结构啊,那还有一种结构呢,叫做线性结构,线性结构呢,它对应的就是这种一对一的一种关系,诶前一个元素指向后个元素,后元素呢又指向下一个元素。啊,这样呢,就一对一的。比如说像这个这个革命年代的时候,这个地下党是吧,地下党的话呢,就前一个人啊,跟后个人呢去通信,后个人呢,再跟后个人去通信,甚至一对一的这样的一个场景,而且呢,咱们说这种低压党呢,通常都是。
07:13
哎,这个单链表是吧。对,这个人呢,万一要被抓了,他顶多呢,把他下边这个人给供出来啊,上边这个他是找不到的,那这个呢,有效的保护这个组织是吧,这样啊。好,这个呢叫线性结构啊,那另外呢,还有这种一对多的关系,一对多的话呢,那就像我们这样的一个结构就分叉了,这个一看呢,就相当于是一个倒着的一个竖一样,所以这呢就叫做树形结构啊。然后呢,还有这种图形结构,图形结构呢,你可以看到就是多对多的一个场景了,比如说这一个元素呢,它可以指向多个元素,然后这一个元素呢,也可以被多个元素呢指向过来。啊,这个呢,就是属于叫图形结构。啊,整个的话呢,就有这样的四个关系啊,来回过来,我们可以写一下这个呢,大家做一个了解啊,诶第一个呢,我们称为它叫集合的一个关系,或者叫集合的一个结构啊都行。
08:02
啊,这是一个啊,然后呢,下一个呢,叫做线性。结构是吧,这个呢,就是来刻画呢,叫一对一的这种关系哈。哎,树形结构。哎,这个树形结构的话呢,来刻画的就是一对多的这种关系。哎,图形结构。对他来刻画呢,叫多对多的这种关系。诶行,这个是我们说呢,叫数据之间的一种逻辑关系啊,那么基于这个逻辑关系呢,我们更关心的呢,其实第二个点就是这个数据呢,有这样一种关系了,我们到底底层呢,该如何呢去刻画这样的关系呢?哎,这就涉及到数据之间的一个物理结构,或者也称为呢,叫数据的一个存储结构啊。哎数据的一个存储结构,或者也称为那叫哎物理结构。说的那是一个事儿。好,那么数据的这种存储结构呢,其实就要考虑到他们相互之间的这种关系了,那在我们这数据结构当中呢,诶典型的来讲呢,就有这样的四种结构哈,第一种结构呢,叫做顺序结构。
09:07
诶,顺序结构其实就好比是我们这个数据表,其实呢,在我们Java当中就类似,对应的叫数组。这叫顺序结构,然后第二类结构呢,叫做链式结构,然链式结构呢,跟顺序结构呢有明显区别啊,这个数组呢,咱们讲过,它在内存中都是。换个红色的啊,在这个内存中呢,都是依次紧密排列的啊,这样的一整块儿的这个空间来存,存放我们这个数组结构,而这个链式结构呢,就我们说的这种链表的这种结构了哈,它呢是前面个元素,然后呢,跟它的第二个元素呢,它在物理磁盘上呢,它可能是不连续的。啊,但是在这个逻辑上呢,我们认为它是连续的啊,因为呢,你也可以给他设计呢,它叫角标零,它叫角V1,它叫角标二啊你在处理代码的时候呢,感觉上以为它们是挨着的,实际上呢,它们在磁盘上呢,是不挨着的,这种呢叫链式的结构。啊,这个链式结构话呢,你现在来看这也是一对一的一种关系啊,但问题是你要练的话呢,可以一个练俩,这不就出来这种分叉了是吧?如果这个还往下分叉,其实就有点儿像这个树形结构了吗?
10:07
对,就是这样的啊。好,然后第三类结构呢,称为呢叫索引结构,这个索引结构的话呢,就比上面两种结构呢,要复杂一些啊,这个典型的话呢,就是我们讲到MYSQL数据库的时候呢,它使用的这个索引,它对应的呢,就是这样的一种结构。这种结构简单说一下啊,这个结构里边呢,核心数据库里边呢,存的都是一些数据了,这个数据呢,其实就是这个数据页。但是未来我们这个数据库查询速度更快啊,它要建立这个索引,所以呢,它有专门这个索引页,这个索引页呢,它只是一些啊,针对你相关的这个列建立的这个索引,所以这里边儿呢,不去核心存储我们这个数据本身它只是存储一些相关的字段,诶为了便于我们更好的做一个查询操作,OK啊,这个呢提到叫索引结构。然后再下边这个呢,叫散列结构,散列结构呢,似乎大家也发现了,诶这不还是一个数组,这边也有链表吗。对,但是把这个呢,也单独的归成一种这个存储结构了啊,这个呢,就比如说咱们的哈希map。
11:04
是吧,哈希set它使用的其实都是这个叫散裂的这种结构。那这块我们把它也稍微的写一下啊,存储结构,哎,第一个呢,我们看到叫做诶顺序。结构是吧,第二呢,我们称它叫链式结构。第三呢,我们称为,它叫索引结构。啊,这个呢,我们叫什么呀。散裂结构是吧。哎,散列结构啊好,这个呢,是一般我们讲到这个数据结构的时候呢,通常这样的去提啊,但是在实际开发当中呢,我们更习惯上呢,诶就是用下边这样的一种方式呢,去记忆这个存储的结构啊,最后在这写一下说呢开发中。啊,说我们。哎,更习惯上。啊,如下的方式来理解。哎,咱们这叫A存储结构啊,好怎么去理解呢,首先的话呢,我们提到了一个叫做线性表。
12:00
这个线性表的话呢,它其实主要呢,对应的就是我们上面提到这种线性的这种结构,也就是说呢,用这个线性表来刻画呢,叫一对一的关系。好,那这时我们就要看一看,在实际的开发当中,这个线表主要都有哪些结构呢?哎,典型的话呢,就是哎,比如说一为数组。是一位数组是,然后呢,我们提到这个像单向列表啊,双向列表啊,这个其实也都算是吧。啊,比如这呢,写个叫诶单项链表。啊,这个双向链表,其实呢,就是链表结构了。诶这呢都算是叫链表结构啊,然后呢,还有我们基于这个数组结构,或者是这个链表这个结构呢,我们派生出来的呢,比如说这个站结构。啊,站结构叫先进后出的这样的特征的啊,这叫战,然后呢,还有呢,叫先进先出的,叫做队列是吧。啊,叫做队列啊,英文呢就是Q。啊,这个队列的话呢,叫先进先出,它们呢都叫做线性表。
13:03
诶注意这都叫做这个线性表了啊好,这呢是我们说的第一类这种结构,然后第二类的话呢,我们通常就做数了,数呢主要来刻画这个一对多的这种关系了。对这个树的话呢,我们常见到的是吧,就是这种二叉树。啊,这里边儿其实就是各种数了,比如说呢,叫二叉树。这个二尔叉树的话呢,其实下边又可以分成很多的这种,诶细分的这种数了是吧?有的呢,是比如说满二尔叉树啊,完全二尔叉树啊,结合二叉术啊,排序二叉树啊是吧,还有这个比如说avr术啊,红黑术啊是吧,这都属于这个二尔叉树的这种场景啊,还有呢,比如我们在后边讲到这个数据库,比如说MYSQL啊,它只能使用的叫B加数。是吧,它这个这个叉呢,就很多了,就啊不是二叉了,呃,那你要差越多的话呢,其实我们这个深度的话呢,是不是就会小一些是吧。你比如说我们这样,这是一个二叉哈。
14:01
这呢相当于是一个满二塔,就是每一个元素呢,它这个除了叶子节点之外呢,其他的这个都是满的啊,这呢我是有七个元素是吧。12345677个元素,好,那如果我们要用这种类似于B加这样场景呢,有可能这一个下边呢,就来了六个。一个两个三个四个五个还差一个是吧,六个诶类似于这样特征的啊,我就简单写一下了啊,那么为什么这个MYS用这种B加数呢,你看它这个差多了以后呢,就使得我们这个树的深度。像这个我们就理解成了是不是有三层,所以它的深度就是三是吧,哎,我这个差多的话呢,这个深度是不是就少了。诶,深度要少了,只要每增加一个深度,我们就需要跟磁盘交互一次,那你要是差越多的话呢,深度就短了,深度短了MY磁控呢,跟磁盘交互的次数就少了,进而能大大的提升查询的一个效率。诶,所以这个呢,就把它的差呢,就分的比较多啊,这叫B加数啊其中的一种。好,那除了这个树形结构之外呢,我们说还有这种图的这种模型是吧,这个呢,就是诶多对多的这种关系的刻画。
15:04
啊,这个图的话呢,不在咱们现在讲解这个范围内。啊,如果大家需要呢,像比如说做这种地图相关的一些场景是吧,这个呢,就需要接触到我们这叫图模型了啊好,那此外的话呢,还有我们提到这个叫诶哈希表。诶哈表这块儿呢,我们主要对应的就是咱们,诶重点呢,这一章要提到的,比如说叫哈希map,诶哈希set是吧,这样的结构,哈希底层使用的就是哈希map,然后呢,我们对应的那个数组,它除了数组之外呢,还有这个单链表,甚至说呢,后期还入了红啊这个我们统称哈西。诶,所以呢,咱们在平时开发当中更习惯呢这样的去提,诶这个内容啊啊这呢就要研究对象二,在研究对象三呢,就我们上面还提到了,除了这两个之外呢,还研究他们相互之间的这种运算。啊,就是有这个结构之后呢,关键呢,在实际开发当中怎么用啊,这就涉及到这个运算了,运算呢,就是我们上面提的这个事儿。
16:01
啊,运算啊,在这儿呢啊。诶,就是这里边的这个点啊,这个呢也很好理解啊,诶比如说我们基于这样的一个异位数组是吧,我们如何看待这个数据的插入删除啊,获取遍历啊,修改排序啊是吧,你跟用列表的话呢,肯定它相应的这个性能呢就不太一样。诶,所以这块呢,就表现出来了,他们建立相关的这种算法呢,就有所不同,诶这个呢,就是研究相关的这种算法是吧。哎,这个操作的啊,OK,这个呢,就是咱们说数据结构啊,主要关心的这样的三个问题。啊,当然这里边儿大家应该很明确的知道,数据结构呢,跟咱们Java是一种什么关系呢。是吧,数结构呢,是独立于编程语言的这样的一个课程了,是吧,所以大家呢,你在学习计算机基础课的时候呢,诶讲过数结构,包括像考研的话呢,这个408里边儿也专门考这个数据结构是吧。至于说你说这个数据结构,你是用Java去写的呀,你还是用C写的,还是C加加去写的,那我就不关心了。
17:03
啊,就是这儿呢,相当于是不同的语言去实现这样的一个内容。所以你像我们说的这个数据结构也好,操作系统组成原理,计算机网络是吧,这些呢,都属于计算机的这种通识的课程,哎,我们现在接触这些语言呢,都属于诶去。叫什么?诶基于这样的基础知识呢,我们去做一些应用的这样的一些语言,一些工具了,是吧,所以至于说你是用Java呀,你还是用C呀,包括后期呢,我们换成比如说有学go呀,Python呀是吧,诶这个呢,都可以体现不同版本的,比如说书结构。啊,包括我们前面还提到过,像设计模式是吧,都用不同的语言去实现。OK,行,这个呢你理解啊,这个数据结构它呢是独立于编程语言的。OK行,这个呢,清楚以后呢,我们关于啊数据结构这块呢,就不专门的咱们开一门课,或者咱们讲上三四天了,这要一讲的话呢,这个内容呢,其实也挺多的是吧,所以我们呢,在Java基础里边呢,就诶。这个有效的这个范围内,我们看讲到什么程度啊,这块呢,咱们就通过这样一个方式呢,给大家去过一下啊,这个过怎么过呢?诶把核心的这样的一些数据结构,它底层是怎么设计的,咱们把它呢,诶抛出来,大家能够清楚这个事儿就可以了。
18:14
好,那这块我们按照这个顺序来讲的话呢,最先接触到的那就是数组了。哎,为啥我这可以写一维数组呢,本身其实我们也没有所谓的多维数组,都是一位数组是吧?好,这块我们就先说一下这个数组啊,数组这块呢,其实没有太多可说的了,就是我们在Java层面,你有一个相应类型,我们在内存空间的呢,就会帮你开辟一个连续的空间。然后这块有个首地日值,然后我们的索引呢,就是表示它的这个偏移量了啊,所以这个偏移量是零啊,第二个偏移量是一,当然就是它的这个索引的概念啊,内存空间这块呢,就依次去放就可以了,然后呢,根据你这个类型我们来确定呢,这个元素该给你分配多大的空间,比如你要印的类型。就是四个字节是吧。四个四节呢,在我们内存中呢,其实它就相当于一个slot。啊,一个槽。
19:02
哎,一个槽呢,就是四个字节,这个呢,属于最基本的单位了啊,你像你这个呢,比如是int类型啊,还有呢,比T类型小的BAT类型。是吧,Short类型。这个还有叉类型。是吧,还有这个in的类型本身还有谁啊。的类型是吧,哎,像这些类型的话呢,它都是用一个槽位来装的,那你要是第二个还是in的类型,那就是四个字节之后啊,就是你第二个元素了,在四个字节之后呢,就是你第三个元素。哎,就是这样子的啊,那对于呢,像这个浪类型。是double类型。他们呢,因为都是八个字节嘛,所以这样就是两个槽,就相当于我这块要是存储这个long或者是double的时候呢,那就得是比如说这个两个。啊,存放一个或者一个double啊,这个呢也是两个。哎,这样子的啊好,那除了基本数据类型之外呢,我们说还有引用数据类型,引用数据类型呢,说咱们其实存的就是一个地址是吧。比如我这个a person类型的一个。
20:01
啊,我就比如说哎,这个P是吧,哎右边扭了个对象,那这个P的话呢,存的是个地址,你说这时候它是几个槽。对,一个槽就够啊,所以呢,对于这种引用类型的变量的话呢,它就是使用一个slot就可以了,所以呢,这个数组呢,其实没有太多可说的了,这个咱们也是最熟悉的啊,我这块就写个略了。诶,然后呢,大家如果你想看一看,诶,数组到底有什么样的特征,就我在上面这块呢,也写了一个数组的相应的特点。啊,摆到这儿了啊好,或者的话呢,这个图我实际上呢是放在这个里边的,但是你看这个呢也可以。啊,这个打开啊,真实的这个数据结构啊,展开所有分支,这里边呢,针对于我们常见的这个结构呢,我这都列出来了,包括相关的这个你要感兴趣呢,看对应的这个书啊也都有。啊,这个可以啊,行,这个呢,我就不多去说这个事儿了。哎,那数组啊就过掉了啊,然后下边这块呢,我们看到这个呢叫链表。啊,链表的话呢,这个第一个我们提一下叫单向链表。啊,然后呢,再说一下这个叫双向链表的事儿啊好,那说到这链表的话呢,首先我们说一下啊,这个链表当中啊,它其实有它的最基本的元素。
21:06
啊,那就是我们成为了一个node。啊,你就比如说我们这是一个元素,这练下一个,这又练下一个,这个呢,就是一个基本的单位是吧。啊,在这说一下啊,哎,链表中的基本单位是,哎,我们称为它叫节点,这个节点的话呢,我们习惯上呢,都叫做一个node了。好,那么这时候我们就看一下这个单链表,所以这块呢,我主要想刻画的呢,是这个node的事儿啊,基于这个node呢,你再去设计相关的增删改查的方法就可以了啊。好,那么这个单项列表。啊,链表单向列表就是长这个样子的。啊,这个我比如把核心的这个他呢给拿过来吧。到这儿吧。这个呢叫单向列表,那其中我刚才说的node呢,其实就是里边的这一项。所以呢,我们看到什么样的结构呢,知道它是个单向列表的特点呢,哎,比如说我这块啊,就生明这个class,这个呢,就成为一个node了。
22:03
诶,这个note里边呢,诶需要呢,保这个保存两个数据啊,第一个呢,就是你核心的这个数据。比如说这个呢,就是类型的,我们称为它叫data了。哎,就像我们这里边儿这个data啊,然后另外的话呢,它呢,还有一个指针指向下一个元素啊,那就意味着我这呢,是不是还有一个node类型的。元素,我就称为那叫next了。这个没问题是吧,好,然后这块呢,我们去声明它的这个构造器哈,比如public。哎,这个呢,来一个node。行,这是它这个构造器了,然后这个构造器的话呢,我们就可以呢,去指明,哎,当前你这个元素的具体的核心的数据是谁。是吧,可以这样,当然你要说我们这个net话呢,这块能指明,能指明你就也给它放到这儿,如果没法指明呢,你就。哎,不指名就是你可以提供多个构造器,这是没问题的是吧,比如这块我要不写的话呢,那就先这样空着,先来一个C4点,哎得塔等于这个得塔啊,可以这么着啊,这呢其实就构成我们这个整个呢,这个单向列表的一个核心的这个节点了。
23:04
哎,那怎么算叫单向列表呢,这个呢,我们来比如说创建对象是吧。好,关于这句话对象的话呢,比如我们先来一个这个叫NODE1,诶我们去new一个这个具体的这个node了,这里边呢,假设啊,比如我就写个叫A了,诶我就创建这个对象,好,那这时候由于这个ne没有赋值,所以它就是个no啊我呢在创建一个。啊,这个叫NOTE2了,这个呢,比如说叫BB,哎,然后的话呢,我这个NODE1它不有个属性叫ne吗。哎,让它这个尺寸呢,就指向这个叫NOTE2。那目前的话呢,我们就构成这样的特点啊,它呢指向这个这里边呢,这个叫AA了,哎,这个指针的话呢,就指向它的这个地址,这呢叫BB。然后这个位置没有赋值,它默认的就是个闹。哎,这样的特征的啊,你要再来一个呢,你就比如说这个叫CC,然后让这个next就指向它啊,这个呢,还是这块是个no。哎,就可以了。哎,这呢,就构成了咱们这个单向列表最核心的这个结构了。
24:01
诶中了它以后的话呢,这个单元列表呢,你可以基于我们这个node,诶咱们呢再去写个class,然后呢,你就主要呢,其实就是定义这个增删改查的操作了。你看怎么呢,去添加一个node是吧,其实呢,就是这呢,我就演示的是一个添加的一个行为。哎,详细的我就不多去写了啊,就相当于大家你看到什么样的结构能够证明它是个单向链表核心的话呢,就看这个node。OK啊。好,这是它,然后呢,双向列表。哎,双向链表。哎,这个样子的啊。在这个双向列表的话呢,你会发现呢,我们这个node呢,就比刚才这个要复杂一点了,除了呢,能够记住呢,它的下个元素是谁,然后呢,你还要有能力呢,记住它的上一个元素是谁,所以这里边儿呢,就会有三个这样的属性啊,所以双向列表当中,我们这个node的定义呢。哎,Node是吧,过来以后,哎首先呢,我们这有一个哎node类型的,比如叫。啊,这个就是前一个元素,然后呢,你这个元素的核心的这个数据,还有呢,你这个node类型呢,叫next是吧。
25:05
哎,这样特点好,这块我们可以呢去定义它这个构造器了。哎,定义构造器啊,定义构造器在这块呢,其实你都可以定义重载的啊,哎,比如说呢,你只放这个雷塔的。是吧,哎,这呢是其中的一个。那这一个是吧,跟我们刚才那个单元列表一样,你也呢可以去定义这种三个参数的,比如我呢,在这指明一个node叫做approve。逗号一下,Node类型呢,我们叫next啊,那进来以后的话呢,这个你当然了就这个。哎,在这写啊,这四点啊,VE等于。哎,等于我们这个行三的这个。啊,这个得往前提。嗯,这是。啊,这是这是吧。在这儿啊,然后这个点这个next呢,诶等于这next这呢,我就写了两个这个构造器了,诶核心的这个逻辑呢,就是这个node啊这个完了以后呢,接下来诶我们说怎么样的一个特点呢,它就构成是叫双向列表了呢,诶我们这儿呢,去创建这个对象哈,NODE1啊你一个这个node。
26:11
哎,这里边儿的话呢,我们第一个元素真的是个闹了。那这呢,比如我们写上叫A是吧,然后这呢,是不是也是个no啊。啊,比如第一个来了,啊,这是个闹,这呢也是个no,好,接着我们来创建第二个元素。诶,第二元素创建的时候呢,你一个node,它的前一个呢。是不是就是指向中的一了。对,他是BB的一个没有。OK啊,然后再来一个啊,比如说像NOTE3。哎,我们再去扭一个。哎,那么它的这个前一个呢。叫NOTE2是吧,它那叫CC这个呢,是不是还是no。哎,这里边儿我们再去补一个。诶补一个补得是吧,这时候我们呈现出来效果呢,这是第一个,这第二个,这是第三个啊,诶然后第一个呢,这块呢,它的前一个是no,这是没问题,因为你是第一个元素了啊,这块呢,我们目前它也是no,我们只是把这个第二个呢指向第一个了,第三个呢指向第二个了,这块其实还差一对指针是吧。
27:07
这个和这个啊还没有呢,所以呢,我们还得需要呢,叫note一点,是不是用这个NOTE2去复值啊。哎,然后呢,这个NOTE2的这个NEX呢。哪里弄的三去复制。这样的话呢,就构成了,这不是双向列表了吗。这块我写这个逻辑呢,其实相当于啊,如果呢,大家你要制定一个双向列表的话呢,这个逻辑呢,应该是在你的添加方法当中。啊,添加方法当中啊,呃,添删改查我就不具体去设计了,核心的逻辑你就看这个node。啊,看这啊当然了,如果呢,你要看到一个node里边,它呢定义了两个node类型的这个变量,可能是一个双向列表,我说呀,还有可能是一个。二叉树。是吧,诶你看啊,咱们在一个元素里边。又看到了,他声明了这个元素两个啊类型的变量,那就意味着它可以指向还是一个元素,它还可指向另外一个元素是吧。
28:06
哎,这呢是一种指向关系,你似乎呢,能够看到我似乎要往下延伸的话呢,有点像是个树形结构了。但是我们刚才这个呢,诶你看我们这是一个,我是横着放的话呢,这指向一个,这指向一个,然后又来了一个,这个呢,诶又指向他了,他呢再指向下一个,这个下一个也指向它,这呢明显呢,是不是就构成了一个叫双向列表了。哎,都是有两个元素,但是两个元素的特点就是比如我们这个叫A元素了哈,它指向了这个BB的话呢,就看它指不指A了。要不止AB往下指了,其实这块呢,其实就对像单元列表了,如果还有两个的话,那就是有点像这个树形结构了。如果拿A指BB,也指A。那咱俩其实应该是这个双向链表的特点。啊,所以说呢,哎,你看这么着啊,我要是,哎再来看一下这个阿叉树啊,核心的问题,它长什么样呢?就是因为我们定义过这样的一个node。啊,这个node的话呢,其实你也可以称为呢,叫tree node了是吧,就是树的一个node吧,它里边呢,其实也有两个,哎,当前这个类型的节点。
29:09
啊,这个一般的话呢,我们通过这个呃,变量名也能够大概知道它是一个数还是一个链表。是吧,哎,他其实都能暴露出来啊,这呢我们叫left了,然后核心的你这个object这个这个数据。哎,除以node这个呢,我们叫right。没问题啊好,接下来的话呢,我们去声明,比如它这个构造器哈,啊叫node。啊,这个你要说给一个单独参数的也行是吧,就意味着左右呢,这块都是闹了啊。哎,这是一个啦,然后呢,我们再来一个这个三个参数的。哎,这个我们把这个相应的左右啊,也都给它加进去啊。哎,就得这么着了。嗯,行,在这个前面呢,C4点啊叫left,等于这个left。
30:04
啊在这啊,这right等于right就得这样了啊好,然后呢,看到这样的这个核心的一个节点之后呢,我们有这样的这个代码了,我们去创建这个对象。行这呢,首先啊,我们这个node呢,吹node啊。哎,吹note这块呢,我们来一个就叫做诶NODE1是吧,然后这块我们去new一个呢,叫做吹诶node。好,然后呢,在这里边儿啊,这个左边呢,这个我们先写成这是个闹。啊,又中间这个元素呢,写成叫A啊,右边当然也是个no,这是第一个了啊,然后第二个。哎,第二个元素哈,第二元素的话呢,嗯,这块呢,相当于啥呢,它往下值,其实这块都指不了是吧,就先来一个BB了。啊,咱们再来一个这个啊三啊。或者这块呢,为了形象点,咱就称为呢,它叫做一个left吧。
31:02
Know that?这个呢,就要right not。哎,这么着啊好,这个呢,叫做这个CC了。哎,这样啊,然后呢,这个指针呢,我们给它补上啊,相当于我们这个no left。是不是指向我们这个left not是吧?呃,然后呢,NO1诶right指向这个叫right no,然后至于说他俩这个的话呢,你再往别再往下边去延伸指别人是吧。目前这块我们刻画出来的就是这是呢叫AA的,诶它的左边这块呢,指向这个叫BB的。哎,右边这块呢,指向这个叫CC的,它俩这块呢,还都是两兆的,你再去延伸往下指别人。哎,可以这样子啊。这就相当于构成我们一个叫二叉数,二叉的话呢,就是你看到这里边儿呢,有两个这样的哈。当然了,有的时候呢,还会这样去设计。哎,这个我再写一下,这个写成一个叫货吧,就是我们可能呢,还会设计成这个三个这样的特征的哈。
32:03
只不过呢,这时候我们这个叫吹no的时候呢。哎,我们叫做parent。就是它的这个负节点是谁是吧,对,在这个基础上呢,你可以再补一个这样的一个参数了。啊,我这儿呢,再补一个叫parent。哎,就这样啊。哎,应该也能理解这个事儿。This their parent。哎,就这样。哎,把这几个往前提一下啊。行,就这样特征,哎,那我们要是在接着往下创建的话呢,其实跟它呢,其实类似的啊,诶比如我把这个呢,CTRLC咱们再拿过来放到这儿是吧。这个时候我们在创建的时候,对于你第一个啊,这叫顶级的这个节点了啊,这个节点的话呢,它的这个负呢,就是个no是吧,就是这样的,然后呢,如果这个是左的话呢。这个其实就NOTE1了是吧?哎,然后这块呢,这个叫也是NOTE1,哎这么着,然后呢,相应的这块呢,你这个,诶顶级的这个NOTE1呢,左还指向它,右呢还指向它。
33:06
没问题是吧。哎,就这样的特征啊,就是你看到仨的时候呢,你看它这个名,当然了,我们说呢,变量名其实不起作用啊,只不过通过这个名呢,我们知道它建名之意的一个意思啊,想表达就是他的这个上一个节点是谁。OK啊行,那这儿呢,咱们就把这个呃,树形结构它的这样一个特征呢,就说清楚了。就是大家呢,你见到这样的结构的话呢,它的本质的一个核心问题就是你主要看它这个node,包括呢,咱们下边呢,讲这个绿色也好,讲这个map也好啊,那其实这里边呢,也相应的蕴含的就是对应的这个node,哎看它是什么样特征,我们来决定说,诶你是一个单向列表,你还是一个双向列表,哎其实核心问题是看它。给予它的话呢,我们再去设计这种增删改是吧,查询这样的方法,哎,都是来操作它。OK啊。行,那咱把这个呢。把这个说完吧,行吧。那这个呢叫站结构啊,这个站的话呢,咱们呃,英文对应的叫stack是吧,站啊站的特点呢。
34:08
先进后出。是吧,这个我们要用英文来说的话,叫first in。对,Last out,所以呢,有的时候我们把它呢,也简写成了叫first in last out这样来写,所以你看它这个词的话呢,它其实刻画的就是这个站的这个特点。当然了,你有for in last out呢,对应的那个词呢,就是。要last in first out。就是反过来呗,先进后出,或者叫后进先出,不都说的是他吗。OK啊,那那典型的这个站的这个场景,在生活当中有吧。啊穿衣服对,穿衣服这个也算一个,就是你先穿的衣服你得后脱是吧。OK啊对弹夹啊,这个我这儿好像还有一个这个图的哈。哎,弹夹的话呢,你把这个子弹呢,压到这个这个膛里边是吧,然后先打出来的就是上面这个子弹。
35:03
嗯,这个咱们有一个那个同学,他是原来在部队待过啊,我讲过说这个子弹呢,他们这个实际的话呢,就是下边呢会压入一些甄子弹,上面的话呢,应该是催泪弹,再往上面的话呢,就是这个空包弹是吧,所以一般这块应该有六个这块也有六个这块就剩下的了。啊,就是这样的情况啊。当然这块呢,大家你就别去尝试了是吧。你是被尝试的对象,你还是主动拿的呢?这都不太安全啊。好,这个呢,就是这个站的特征OK啊。好,然后呢,这个队列呢。这个其实我们生活当中很常见啊,大家干什么排队不都是这个特点吗?这个呢叫做Q。那就他哈。他那叫先进先出。哎,先进去的就先出来啊,叫first in。对。In是不是out是吧,这个我们简写的话就in out,这个一般呢就不说in out了,一般就直接说先进先出了,就这呢就是一个队列了。
36:10
啊队列,我们生活当中排队呢,都是属于这个特征啊,现在做核酸是吧。啊,都是做这个队列的啊,然后呢,在我们这个,呃,Java这个层面呢,我们后边会讲好多的这种消息队列。Active是时候,那就是谁先来的,谁就先服务啊,先处理谁啊,就是这个队列这个特征,包括呢,像我们这个手机端也是一样啊,这个我们接收到的消息呢,也有个队列,也是谁先来谁就先服务。啊,先来后到啊,就我们生活中这个概念了啊。然后这个战和队列呢,其实我们还有一个例子呢,可以跟大家说啊,就是大家。这个吃了饭之后啊,有的男生呢,世界杯期间呢,就会喝点酒是吧,就是喝酒没喝多跟喝多的时候的这个区别了。
37:01
对吧。诶喝多的话呢,就是从上面进。上面出这叫战是吧?哎,没喝多呢,上面进第二天呢,下边出是吧,就是队列嘛。哎,这样的特征是吧。好,那么这个站和这个队列,诶注意哈,包括呢,你像咱们刚才说的这个竖形的一个结构,你发现呢,我们说这是个叉,这个叉呢,其实我们也用到了这个相当于一个指针这样的特征。那没问题是吧。那个二叉树不就是这个元素,诶指向下一个,其实这块呢,不就有点儿像基于这个链表我们衍生出来的这个二叉树是吧。诶,对的啊,所以呢,我们通常呢,把注意啊,像这种链表结构啊,包括上面我们提到这个数组结构呢,他们可以理解成呢,叫真实的数据结构。啊,就在我们这个内存当中就有这样数数组,数组什么样的,就是一个挨一个的。诶就这样放的是吧,列表呢,列表就是我们说的这个最基本的,最基本的就是单向列表,单向列表就这个元素,这个元素它俩呢,在内存中不挨着,哎,你通过这样一个指针的指向,双向列表呢,你可以看到基于它我们就多了一个指针,这叫双向列表了。
38:12
包呢,还有这种叫循环链表。就是你这指向下一个,最后这个还指向一开始这个是吧,诶对,这就是一个循环的一个特点啊,循环列表啊也有好,那我们这个二叉树呢,你可以理解呢,就是基于我们这个链表结构,我们衍生出来的这样的一个。啊,就像我们刚才说的,你这个元素,哎,往下指这个,往下指这个呢,接着再往下指。哎,就衍生出来这样叫还树形的这种结构啊。好,那我们这个站结构呢。注意啊,不是说呢,我们在内存当中,你一看说就有一个跟数组链表对应的另外的一个东西叫做占,这个占呢,包括这个队列也是属于像树一样,咱们称为呢叫抽象树结构。哎,这个我写一个啊,叫属于叫抽象数据结构,这个用英文来说的话呢,抽象叫abstract。
39:05
数据呢叫data,结构呢叫structure。哎,不是这个抽象数据结构,这个结构这块呢,用的这个词叫tap抽象数据类型。换成这个词吧。抽象数据类型是吧,Abstract data type,所以呢,就称为叫a dt了。啊,它呢是一个at,然后它呢也是一个DT,什么意思呢,就是我们并不是说真正在底层独立于,呃,这个链表和数组说有一个叫站,实际上呢,是我们使用真实的数组或者是链表给它模拟出来了一个站的特征。啊,让他呢,感受到呢,像是一个先进后出这样一个特点。啊,注意是这样子的啊,那么这个站的话呢,哎,我刚才说了啊,它呢,我们说呢可以使用。哎,真实的数据结构呢,我们提到叫数组是吧,或者呢,使用我们这个链表呢来构建。啊来构建,那比如说啊,咱们现在用数组,咱们去构建一个站。
40:04
啊怎么构建呢,其实这块呢,就是比如说我们现在有一个类啊,就叫做这个stack了。是吧,诶就要它了啊,那具体里边怎么去写呢?首先呢,这个站里边呢,我们呃先进后出,很显然呢,它是能放多个数据的,我说了用数组来构建,那我们首先呢,你得有一个数组。啊,这个呢,我们叫做object,比如它呢,来存放我们这个核心的这个数据。啊,没问题,好,那你到底存了几个呀,我再通过一个size这样一个变量来去记录啊,存储的这个元素的个数。好没问题啊,那接下来的话呢,我们再来一个什么呀,哎,构造器啊。各造器里边呢,我们需要呢,针对这个数组呢,做一个初始化的一个操作了是吧,比如说这块我们来一个啊,Int类型的一个length。看这么着啊,然后这这这个就这样了哈,Value等于new。哎,Object,然后这个位置呢,咱们就写上这个length。
41:03
好,这个能看能看懂吧。哎,那个相当于呢,我们去new一个这个stack一个对象,现在我就相当于内存中啊,咱们有一个占了。但是现在我画的时候呢,是这样一个开口的,所以呢,只能从这一个口进。啊,叫先进的后出的是吧?啊,那对于我们这个数组来讲里边,你放在数组按正常来说呢,我们这个数组的话呢。是不是还可以插入操作了。或者我这块呢,存了仨,我现在呢,我就不想从上面这拿,我就从下边这拿。哎,就是删像删除啊,或者拿拿拿到呀都行是吧,那我们现在要做的事呢,其实就是控制stack里边对这个数组的操作了。诶,我呢只给你提供这样的两个方法,一个呢叫做入战。啊,一个呢叫初战。啊,那么这个入站的话呢,我们就是public y入站嘛,是吧,我叫push就把你放进去,放进去一个具体的元素。
42:00
是吧,然后出站的话呢,诶public,哎,你一调离方法呢,我就给你返回一个元素,自然而然的就是object类型是吧,这个叫pop。注意你看啊,我这个往里边入的时候呢,我不给你机会去一个int型的index。你要真让我们数组的话呢,诶我可以呢,就是填一个index,把它放到那儿,其实就是一个插入的效果嘛。我现在呢,让你入的时候不给你机会去填这个index,那就意味着你只能是在现有的这个,比如有个数组了。就假设呢,存了俩了,哎,你往这里边调这个push的时候呢,我只让你往这放。你要再掉铺,我就让你往这儿放。这不就只能是在现有的元素的后面依次往后放,就这样,那你出站呢,我也不给你机会让你填一个index 2g呢,你一定要push泡泡哈,我就只让你从最后一个元素拿走。然后再把这个拿走,你要再掉呢,再把这个拿走。就不给你机会去拿前面的,你要拿前面也行,那你把后边这个呢,全都拿走之后,剩下的他你再拿。
43:00
那这不就体现出来是一个叫呃先进后出,或者后进先出的一个效果吗。啊,你看这个我们怎么写。哎,要严谨点呢,我们可以判断一下是吧,比如说你这个size呢,哎,我先往里放,如果你发现已经大于等于咱们这个Y6.lengths了。是吧,这种我们可以through new一个runtime。Exception是吧?说这个我们叫哎占空间已满是吧。诶添加失败或者叫入战失败。哎,这么着。失败了好,然后在这块呢,就意味着我现在没有满,没有满呢,我就可以呢,Value在这个size的位置呢,把你放进来。同时呢,我这个size呢,再加加一下是不是就可以了。没问题吧,诶然后你再调理方法的话呢,只要没满的情况下,我就再放到这个尾部啊意思呢就添加就可以了,好这呢就是这个入站的行为啊,那出战。出站的话呢,注意我不给你机会呢,去填任何的索引啊,也就是因为你出呢,只出的末尾的这个,那我们也判断一下啊,如果这个size呢。
44:07
哎,不靠谱的话呢,就是它已经小于等于零了是吧。哎,对,已经没有了啊。哎,这个我们CTRL一下。这个呢,就是占空间以空是吧。啊已空,这个呢,我们叫,哎出战失败。哎,出战失败了,好,那如果说这块呢,你不是零大于零的场景,这说明你还有。啊,还有这个我们就把你现在有的这个里边呢,最后这个给你返回,最后一个呢,应该是size。减一的这个元素是吧。把这个呢给他返回,但是你要这块我们就这样泛泛的这样一写吧,还不行,因为size也得操作呢,是吧。啊,这个怎么整。啊,今天赛。嗯,而且啊,这个还好,这个呢,不涉及到说我们这个,呃,像队列一样,我们从头部取的啊,这个呢,就是从尾部取得了。
45:02
嗯,所以呢。啊直接呢,大家就减减这样是吧。是这么这么着是吧。把这个呢,直接return一下是吧。诶,这个看有没有问题啊,这个呢,我们是先让这个塞呢,先减个一啊少了一个,然后呢,把这个末尾的这个元素呢给它返回了,其实还得有个操作。我方返回之后呢,你这个位置其实元素是不是还在啊。我还得把它得制成no才行是吧,因为不能有它了啊。你这不是让他已经出去了吗?出去之后呢,他就不能在这儿了,所以呢,我们这儿还得有个操作,干脆这样得了。我们先这个S,让他先减个一是吧。然后这块的话呢,先把这个元素呢,先给它取出来。比如叫OB了是吧,取出来之后呢,然后你这个size呢,你该减减的你先减减。哎,先别先啊,先减减也行,或者说你这块呢,先制成闹也行是吧。减一这个位置呢,先是这个闹。然后呢,这个size呢,减减一下是吧,然后我们return一下这个obj。
46:04
没问题吧?这块呢,你看我把这个地址给了他了,然后我把我自己这个地址给擦除了。这个地址不受影响是吧。诶,然后呢,你把你返回就行啊,我这个size减这个OK吧。嗯,行,这下呢,就我们说这个出战操作,那么怎么叫一个站呢,就是我只给你这个方法和这个方法,我不给你去填index的这个机会,所以呢,你表现出来呢,不就是只能从端的去往里添吗。OK啊,在这儿呢,我是用数组来实现的。哎,你也可以用链表来实现。啊,比如说你看我这里边儿的这个,诶站这块呢,我就放了一个链表这样的特征。我们再定一个元素,这个元素呢,它里边还有一个当前这个元素类型的,相当于这呢,有点像个单向列表了吧。对的啊,好,那就相当于这里边我定一个node,这个node里边呢,在多个属性,除了data之外呢,就定义你指针的这个意思啊,第一个元素,哎,它的这个所谓的呢,它就是指向个no了。
47:01
哎,你在整第二个元素造的时候呢,然后这个元素呢,就指向你第一个,然后呢,以此类推嘛。哎,你就往里添就行啊,添加然后呢,还是我们就只给大家去定义这个叫push和这个pop,只不过现在你操作的时候呢,是变成这个单项列表了,让他这块呢,取的时候呢,是不是也取尾部的这个是吧,取完之后的话呢,呃,这个拿出去了,这个元素你想指针该支撑这个no的就指成no啊现在这块呢就指向它了。然后添加的这是诶添加哈,添加呢,就是往尾部添加泡泡的话呢,你就是从尾部这个去取,就是类似的道理。你可以呢,用这个呃,单项列表去刻画一个站,其实主要呢,就是在去写这两个方法。好,这呢属于我们这个站的这样的一个特征了啊好,那下边对应的这个呢,叫做队列哈,这个队列的话呢,其实也同样的啊,我们可以考虑呢,使用这两个结构呢,去来做一个构建。哎,使用这两个结构呢,我们做一个构建啊,那比如说这块呢,我们写一个这个叫队列啊。
48:03
队列的话呢,其实核心的数据呢,如果我们要用数组来去实现。哎,我在这写上啊,叫数组实现。哎,队列上面呢,咱们也是数组实现的,这个叫占啊。OK啊好,那核心的话呢,其实也有一个它,然后这个S的话呢,也可以有一个CTRLC一下这个我们就诶给它粘过来。嗯,这没问题啊,然后下边我们同步的呢,再来一个哎。那Q。这这来一个构造器哈,然后呢,这儿呢,我们同样的去指定一个int型一个length。啊,在这里边啊,这个类型的。哎,把这个S呢,我们添加过来。这呢就是核心的这个逻辑了啊,这个有了这个数字以后呢,我们就可以呢,往里边去添加元素了啊这个呢,比如说哎avoid我们叫爱这个操作吧,哎,我把一个object类型的啊这个元素哎添加进来。
49:03
这呢就是添加的一个方法。哎,这是它啊,然后呢,对应的呢,我们还可以呢,就是诶get的一个操作,那你获取到的也是一个object。哎,Get这块呢,也同样道理,你就不要呢去填所谓的索引了。啊,这个呢,我们去诶就诶获取或者我们即将要处理的这样的一个消息,比如说啊好,那这个添加的话呢,诶跟我们上面这个添加呢,其实有点类似了啊。也是我们先判断一下啊,如果这个S呢是大于等于。咱们这个Y64.ls了。那说明我们这个队列呢已满。哎,这个我们这样写啊,说队列已满。哎,叫添加失败。这么着啊好,然后在这个位置呢,说明我们就可以去添加咱们就诶values这个呢,T还是添到这个末尾啊size这个位置,然后我们把它呢,添加上这个元素。
50:06
哎,贴完之后呢,我们当前这个size呢,也可以加加一下是吧。哎,这样啊,所以你把这个size加加呢,写到这儿也行。好这个呢,就是我们添加这个行为啊,完成了,好现在这个钙的话呢,你得小心点了啊,我们取的话呢,因为它是一个这个这个队列嘛。这样特征的啊。所以我们现在要取的话呢,是不是得从头部这块开始取。头部这个取走以后呢,你后边元素是不是都得跟着过来呀。对这个细节也得去注意啊,嗯,那基于我们上面的点,咱们也可以呢,这么着一下是吧,来做一个这样的判断啊。说呢,哎,这个肉这个呢是小于等于零了。那说用这个队列呢,一空啊。啊,这个呢,我们叫,哎获取失败。那就里边呢,已经没有相应的这个数据呢,需要你去处理了啊好,那这块呢,如果要是有的话呢,咱们先把这个头部的这个得取出来,相当于我们取的呢,永远是角标零的这个位置。
51:06
嗯,对的啊,然后呢,我先把它呢,诶付给一个OB接了,最终呢,我们是要把这个OB基呢给它返回,这没问题啊,把这个地址给他了,把它返回,然后呢,针对我们,呃,接下来是不是还要做一系列的这个事儿啊。啊,想想都做什么事啊?先把后边往前移是吧。所以这块呢,我们先就写一个for循环吧,Int一个I等于。零是吧,I呢小于。诶,这个不用不着这个LA了,主要我们只关心的存了几个处理就行是吧,诶暂时我先写成size了啊,然后I加加。啊,其实这个呢,写size呢不太行是吧。好,进来以后,哎,我们需要呢,是拿着当前这个数组角标,拿它后边的元素。I加一是吧,去替换它嘛。替换的话呢,这个位置,所以我们在。
52:01
两个一是吧。呃,I的最大值呢是S减二加一,最大值呢S减一,这就是所谓的最后一个索引的有数据的元素了啊好,依次替换完以后。贴完完以后的话呢,最后一个位置还得制空是吧。哎,最后一个元素啊,指空,那就是Y6SIZE减一这个位置呢,是不是得改成个no是吧。啊,这个改成闹了,还得size呢。减减一下是吧。这是不是就可以了。啊,这个呢,就是数据呗。看数据迁移啊。嗯,这块你注意哈,你说我们把后一个呢,覆盖了前一个了,会不会影响到我们这个位置读的时候也出问题啊。不会是吧,对这个注意哈,咱们这里边呢,存的比如以数度来讲啊,假如是第一个位置,第二位置,第三个位置,它呢指向的是一个B线啊,现在的话呢,我们是又声明了一个OB,你把你的地址给我,我指向他,然后呢,你这块呢,一开始指向的其实还是他,但是马上这个地址就替换了嘛。
53:07
它影响的只是你这个变量的地址,我这个对象的话呢,还在这指着呢,哎,这个也是我们实际上要取出来的这个对象,所以没有影响是吧。行这块是不是就可以了。啊,然后这块呢,你再把这个一开始这个OB呢给它取出来就行好,那这块呢,就是当我们去创建一个当前这个类的对象的时候呢,它里边就有个数组来存放我们,比如这个消息队列存放我们这个消息呢,然后呢,每次的时候你要有新的消息过来了,我就调这艾特方法,他呢就加到我们这个数组的末尾了。然后呢,你现在有空闲时间能处理了,每次我们就调盖的方法,每盖一次,你把头部的给我,再盖一次,再把头部的给我。体现出来就是先进的就要先出来,哎,就是一个队列的一个特点,好这儿呢,我们通过这样的一个,呃,几个具体的代码的实现啊,就是把核心的这个逻辑呢,给大家抛了一下,就是大家呢,以后看到底层一些数据结构,你知道呢,它是什么样的一个结构,包括呢,诶如果让你去做定义的话呢,对于前面这个呢,核心的其实就是这些node了。
54:06
啊,基于这个node你再去设计啊,定一个类叫做双向列表里边呢,去写增删改查的操作啊,主要呢,就是来操作这个node就可以。好,那么这个队列呢,我们就说完了啊,然后关于树这块的话呢,咱们上面呢,稍微的写了一个这个二叉树,就是大家呢,相当于呢,你要看到这样的特征的话呢,它就是一个二叉树的一个结构了,然后呢,我们在这个课件里边呢,稍微的又诶多讲了一点关于数的一个内容,哎,这儿呢,咱们也看到是一个常识吧,哎,咱们稍微给大家说一下啊。这个生活当中我们看到的树呢,是长这样的。啊,然后呢,我们在计算机当中,这个数呢,是长这样的。诶,那计算机当中的数呢,是它了,包括我们生活当中其实也有这样的。比如说这个家里边儿这个族谱是吧。主谱的话呢,就往下呢,越延伸啊人越多。嗯,还有比如说呢,咱们这个操作系统呢,它这个文件目录的结构。
55:00
啊,你这是一个文件夹啊,越往下越多,包括后边我们讲Linux的话呢,它这个根呢,就是一个斜杠了是吧?呃,下边的话呢,你可以分成好多的这个文件目录。啊,这个呢,也都是长这样子的。包括呢,这个公司的这种人员的架构上面就是个老大是吧,然后下面呢,延伸出来的啊,其实生活当中这样的结构呢,还是挺多的啊,那么我们要用一个树形结构呢,来刻画一个具体的场景的时候,这里边儿呢,就会有一些呃名词。哎,每一个元素呢,我们称为的是一个节点啊,叫这个节也行,叫这个节也行啊,节点或者节点都可以好,然后这个根节点呢,就我们说最头上这个。那就好比咱们Java当中这个继承的这个关系里边这个根,那我们就要根基点就是object。好,然后父节点呢,这个也很好理解啊,就是子父类是吧,你这个父类的话呢,就相当于是这个父节点,子类在这块就相于子节点了啊兄弟节点这个呢,叫兄弟节点啊,没有叫这个姐妹节点啊,也就兄弟啊啊ABC他们之间呢,就是兄弟了。
56:03
啊,这个注意。好,然后呢,这个节点的这个度,度呢,就是你这个节点啊,它所在的这个指数的个数称为节点的度,比如这个B啊,它的度呢,就是三啊,因为它有三个子节点。啊,就分了几个叉啊。好,这个这个树叶,树叶呢,就我们说的这个终端的这个叫叶子节点了,就从树的角度来讲,这就是属于最后的这个树叶了啊,树叶呢,就不能再往下来提供节点了,你要再提供的话呢,那你就不是树叶了,也就不是我们所谓的叶子节点了啊,所以我们凡是没有子节点的这个呢,都是叫叶子了。树的深度或者叫高度啊,就是你往下呢,依次去变粒的时候呢,这个到叶子这块呢,最多需要几次是吧,这个我们其实呢,就K和L呢都一样的,这个就相当于是一层两层三层,这就四层,所以这个高度呢就是四。啊,或者叫深度呢,是四节点的层数。啊,就每往下一层呢,就属于多加一层是吧,OK啊好,同代在同一过程中具有相同层数的这个节点。
57:05
啊,相等层数这个节点就通说明了它这个层数呢,就是相同的啊,叫同代的OK啊。行,这呢有一些相关的一些名词,这个大家呢,做一个了解就可以了啊,然后二叉树呢,自然而然的就是一个节点呢,我们可以分成两个子节点,这就叫二叉树啊。好,然后这块呢,在数结构当中的一个基本问题,就是关于二叉树的一个前序、中序和后续的便利。啊,所谓的这个前序便利呢,其实你就记着啊,咱们如果说以一个基本的结构。那假设呢,就以这个结构来说啊,我把它呢,稍微的这么着一下。对于它这三个元素来讲的话呢,这个呢,你就理解成这个叫根。当然了,这个根呢,就是它叫根,如果呢,你相较于这个结构来讲,B的就是根哈。OK,那么前序便利呢,就是这个根呢,是在最开头的。根左右就是如果我们要用前序变离变离这仨的话呢,那就是。ABC。
58:01
啊,这样好,然后中序变理呢,就是你把这个根呢,再往后移一个那个左跟右。所以说呢,这块呢,如果这三个元素用中序来历,那就是BAC是吧,OK,然后呢,这个再往后移一下这个根,那就是左右根了,这个呢叫后续变利了,那就是BCA吧。BCA啊,就这样个特征。好,那么对于我们下边的这样一个图。所以这样的图的话呢,相应的这个前续中续后续变历啊,这个呢,我就列到这儿了。啊,这个。能清楚吧。举一个例子吧,不都说了啊,前序便利呢,我们说就是先跟后左再右是吧,所以这块呢,我们一上来就先跟这个呢,是不是就先A了。好A完了以后,然后该左了,左边这块呢,是不是就B啊啊这个呢,相当于这个呢是左了,但是这个左呢,就相当于它来讲,它还是根。哎,所以这个我们BB的话呢,按说诶这不是该C了,别这块还没完事呢是吧,这个呢,它呢又相当于是个根了,它是根呢,我写完之后呢,又该这个D了是吧。
59:08
D呢,它就相当于是我们的左,但是D呢,就相当于是他的这个根了。啊,D完了以后,然后该他的左了,是不是该H了。H完了以后呢,概率I是吧。这样的话,你整个这个组这不就算完事了吗?做完事儿以后呢,我们这个B呢,是这你的前序,所以B已经都处理过了哈,是不该E了。啊,移完以后呢,整个这个锁就完事了。这个完事之后呢,我们该这个U了,U呢就是这个C呗。啊,这个C的话呢,你得注意这块,我们先写这个C有问题吗。没问题是吧,先出现这个U,这个U的话呢,它又得是对于这三个来讲的话呢,它也得是一个叫前续的啊,就是先着根儿,本来也是先C没问题,然后呢,完了以后再F。再这一下是吧。这呢,就叫前序便利。啊,你按照这样一个逻辑呢,你去看一下我们后续这个事儿就可以了。OK啊行,那我们后边呢,会有什么呀,就是这种叫呃叫这种数了,这是详细的话呢,我们这个数呢,你看有好多啊,其中有一有一种数呢,叫二叉排序数。
60:07
啊,也称为呢叫二叉查找树,这个呢,英文都叫BSTB呢叫bary。排序呢叫sal,查找呢叫search,反正都是S啊,T呢就是,所以呢,你说英文叫bit呢,可能大家呢更没有歧义了哈,它叫二叉排序数或叫查找数,它是有序的啊,就比如说以它为例的话呢,我就随便呢写一个数啊,比如说这个是20。这个呢是十,这个是30。这个是25,这是40。啊,这个呢。哎,这个先写个15,再写个五,写个二写个八。诶,大家应该明白这个意思啊,就是我们每一个三个元素构成的基本结构的话呢,我们发现呢,左边呢,都比它的小,右边都比它的大是吧。哎,那你这个A呢,右边呢,这仨都算它右边了,那就意味着仨都得比它大哈,每一个呢,都得满足这样的特征。
61:00
啊,你去看一看,每个都满足OK啊行,然后呢,如果我们现在呢,哎,现在想把它们从小到大的去便利。从小到大去便利哈,你看相当于我们这里边儿的什么序啊。其实就是中序,你看是h Di。啊,这不是258是吧,然后呢,这个就是be啊十十五,然后A是吧,然后下边以此类推,这个这个这个。哎,相当于呢,这个如果我们用一个中序便历的话呢,就可以呢,让它从小到大呢去排列了。啊,像咱们提到那个红黑树是吧,就咱们说那个tree map。啊,Tree set,哎,我们说底层用的是叫红黑树吧。红黑素呢,它就属于这个呢,叫呃BST啊。但是呢,它呃跟这个呢有点区别啊,就是它呢属于就是呃这个排序二叉树呢,或者叫二叉排序呢,它呢,其实可能会出现这样的问题啊。
62:00
对,就是这样的。啊,你比如说哎,就是像咱们刚才看到这两个,这都是叫BT了啊,那这样的话呢,是不是也叫BT。比如说我这个元素呢,我就是一个五,这个是七十十二十七,20是不是都满足,我们刚才说的这个左边呢比你小,右边比你大。那只不是左边没有而已,是吧,那这个时候呢,这个数呢,是不是就退化成是一个链链式结构了。这个单向列表了是吧,就是这儿呢,它还是一个BT。但是这个bit的话呢,显然的话呢,我们用它的意义呢,就不太大了,它就化成个列表了,我们查找的话呢,现在效率呢并没有提升,咱们希望呢,尽可能是比如左边一半,右边一半是吧,然后我们比如说要找某个元素,比如这元素呢,比这个八要大,直接呢我们就砍掉左边吧,相当一下子你就省了一半是吧。然后再去找的话呢,诶跟他去判断,诶,假如呢,又比他大,诶左边我们又砍掉一半。这个呢才使得我们查找的效率会更高,你要是整成这样的话,那完全没有提升这个效率。所以说呢,这个bit的话呢,它就更宽泛啊,那在这个基础之上呢,其实呢,就会出现两种。
63:06
啊,一种出的话呢,这个叫你看平衡二塔出。啊,这个呢,其实涉及到我们后边呢,提到了一个叫我这写的哈,叫AV l的个数。这个A这个数的话呢,这个叫自平衡的一个啊BT。所以它呢,属于我们这bit的其中的一种,它呢就不是这样的结构了,它就要求这个A,它的左右两个子数的高度差呢不能超过。啊,那你这样的话呢,就使得左右两边呢,尽可能是不是就平衡了呀,这样的话呢,你每次呢,如果查找的话,就砍掉一半了是吧。哎,这个avr数呢,显然是比较好的。啊,那么呃,AR数,注意还不是咱们要讲的红黑数啊,这个红黑数呢,呃,其实呢,比它的要求呢,又低一些了。啊,因为你看它的特点呢,是左右两边呢,差值不能超过一,就是基本上大家能看到就是差不多就像这样的场景了,这都属于呃,左右两边的这个都是高度一样的了哈,你要把这个六呢抹掉呢,就是左边呢比右边的高度呢少个一。
64:07
然后这个红黑树呢,它有可能会出现这个我就泛泛这样一说就行啊,红黑树呢,就是每个节点呢,不是红的就是黑的,它里边呢,有一些具体的这样一些呃要求啊,然后的话呢,它在实际呢,呃去存放的时候,满足这个要求的情况下,我举个例子啊。比如我这儿呢,用一个。点来表示吧,这呢是一个红的哈,这里边儿有要求,就是你凡是红色的这个节点,它的子节点都得是黑的啊。那你比如说我我这没有黑笔了,我就用一个蓝色的这个就当那个黑色了啊,比如我这个下边呢,我有。嗯,再来一下啊,我先呢整一个,比如说红的。这是一个红的一个节点了,然后下边呢,我换成这个,这算黑的了啊,这儿呢,我左支呢放了比如说三个吧。哎,这样连的就是黑的,这个节点的子节点可以是黑的。诶,就是我这个左支上啊,比如说有三个啊,然后这个右支的话呢。
65:02
哎,我这样啊。你看我这还是撒是吧。然后再换红的啊,这个红的呢,它的死极点不能是红的。它的只能是黑的啊,那就意味这个黑的呢,死机点可以是红的,我这儿可以穿插一个红的。这还可以穿长红的。哎,我就这么着来举例哈,哎,你比如说我现在呢,来一个啊,来一个指针了哈,换成一个。可以的吧,这样啊好,左边的话你看有有仨,右边这块我们去连的时候。诶,我就这么着了啊,这个呢,也满足整个我们这个要求的这个点,那此时的话,你发现左左支上呢有三个,诶虽然这个深度高度算是三吧是吧,而我们这块呢,你看123456是不是有六个呀。诶就相当于我们这个红黑数呢,它的要求比我们这个avr数呢,它要一些avr数要求呢,就左右两呢,高度差不能超过一,而我们这个高度差呢,其实啊,极限的话呢,你看这块还可以再放一个黑的是吧。
66:01
啊,就是它那高度差呢,可以是这种二倍的关系,因为你红黑可以交替嘛。那它的这个高度差呢,就会更大一些,进而的话呢,就是我们不用说像这个呃,AR数一样,我们经常在处理的时候呢,添加元素了,然后呢,加到指定位置之后,发现高度差呢,不满足差一了,我们就得左旋啊右旋啊去改变这样的一个数的结构,这样它来满足AR数,它的要求更高,所以呢,我们这个旋转的这个频率呢,就会更高一些。那我们这个的话呢,要求没有这么高了,所以呢,它在处理啊,首先前提呢,它也是一个排序二法术了是吧,它也是左边的小右边的大,它呢就是左旋右旋的频率就没有那么高了。啊,所以呢,它这个既然频率没有那么高了,这个相应的性能呢,比AV呢,就要稍微的好一点。啊,具体的话呢,怎么左旋右旋咱们就不讲了啊,这个呢,就属于稍微高级的点内容啊。啊,这个我想着咱们讲完这个Java技术之后呢,后边想录一个几天的一个,比如说基础的一个加强版是吧。啊,里边呢,咱们可以把这个红霉树啊,还有一些咱们基础阶段呢,偏南的一些东西呢,往里边攒一攒,讲一讲,啊这个呢,咱们就不在这展开来说了,这个要说起来的话呢,怎么变颜色,怎么呢,左旋右旋这块呢,就比较复杂一些了,咱们得说一会儿呢,而且说完之后呢,大家还得挺懵的哈。
67:16
啊,这个我们就过掉了,好,那么关于这个树这一块呢,咱们就说到这儿了,诶下边的话呢,我们主要来看一看在集合这一块怎么去使用现有的这个树结构如何呢?去提升啊性能。
我来说两句