00:00
同学们,我们来继续学习数据结构和算法的数结构这个部分的基础部分,那么数结构呢,我们把它分成两个部分来讲,一个部分呢,就是给大家讲数结构的基础,另外一个呢,就跟大家讲数结构的应用,实际应用这一部分把它分成两个部分,那么我们来先从基础部分给大家讲解。好的,各位同学首先看,既然我们要学数,首先我们应当适当的了解一下为什么需要数这种数据结构,我们讲过,当我们学一个知识点的时候,我们理解为什么有这个东西的时候呢,学习起来会比较轻松,而且呢,会直接掌握到它的本质,并且跟原先学过的数据结构呢,有一定的区分度,是不是这样子的?那位同学,我们来考虑一个问题,从目前来看,我们存储数据,就是我们要把数据。我们要把这个数据存储起来,在内存里边,我们要把这个数据存储,存储起来,我们有几种方式。
01:05
是不是第一种方式就是用数组来存储?这个没有问题吧,那么数组存储方式它有优点也有缺点,我们来分析一把,首先我们看数组呢,它的优点是我们可以通过下标来访问这个元素,因此呢速度比较快。而且对于有序数组呢,我们还可以用二分查找,或者是前面讲的飞波拉器查找,或者是插值查找算法,提高检索的速度。这个的确是。我们用数组来存储的优势,但是数组呢,咱们毋庸置疑也有它的一些缺点,它的缺点是什么?各位同学,就是当我们要建设一个具体的某个值。比如说我们是一个。数组存的是对象,那么要检索它的名字,我们仍然要一个个去测,一个一个去比对,是不是第二个呢?我们发现我们要插入值。
02:01
这个时候呢,就会需要整体移动效率较低,这里我们先来画一个图,你再加深一下对这个的对数组的它的存储方式的一个理解来看一下。好,这里呢,我们画个图来说明一下数组存储方式。数组。存储。对存储方式的一个分析,同学们首先看,假如呢,现在我这里有一个数组。好,这是。呃,我我这样画啊同学们。我换。画的时候呢,带一个颜色。好,同学们,这是我们的数组。这是我们的数组,假如我们这个数组里边呢,有这么几个元素,我就随意。好吧,我就随意好,这是一个元素,第二个,第三个,第四个,第五个。好,咱们一共有这么五个元素,好,我先把它放在我们的这个数组里边去。
03:02
好的,假如我们这个数组呢,有五个元素。好,同学们先理解一下啊,现在假如我们第一个数组是二,第二个三,第第三,这第三个是五,这个是八,这个是十。好同学们,那我们要去,因为它它这个下标呢,这边对应对应的是零,这边是一,这边是二,这边三,这边是四,所以说我们刚才讲过,如果我们用下标访问呢,的确速度很快。对不对?但是有一个问题就是如果我们要去插入一个数据,或者说增加一个数据会怎么办呢?比如现在我有一个数据要放进去是多少呢?是六。各位,如果我要把这个六放到这个数组里面去,假如我们这个数组是。Alright。二那么我们要放到数组,能放进去吗?各位,各位同学。
04:01
实际上你是放不进去的,为什么呢?我们知道数组它是事先分配这个空间的。对吧,也就是说你原先有五个空间,你就不可能动态的增长。因此在我们在对数组进行这个添加数据的时候,其实底层是有一个动作的,叫什么呢?叫做扩容。就是数组扩容,这个我相信大部分同学都应该有这个印象,就是他要数主要扩容。它是怎么扩容的呢,各位同学。它扩容是这样扩的,各位朋友好,它首先呢,先把各位他先把。这个数组。复制一份,按照哎这个这个这个空间是刚开始这个数组里面是没有数据的啊,就是刚开始这里面是没有东西的,我这些大家应该是理解的,就是他第一次他先做一个分配一个什么呢,大小为六的。一个数组。
05:02
好大小为六数组,然后然后怎么办呢?它就后移,比如说。那比打个比方,他先他先分配一个六这样一个数组,然后把这里面的数组怎么办呢?拷贝过来,比如说十。对,他先把十拷贝到这个地方来,把几把八拷贝到这个位置来,好,这时呢,把六这个值插入到这个位置,五呢,这个地方就不用移动了,五。三一不用移动,大家可以看到这种数组扩容,它有问题是什么呢?就是它每次每次在底层呢,每次在底层他有点问啊,在底层都需要干什么呢。创建创建,创建新的。新的数组。这是第一个问题,第二个问题呢,他需要后移,就是要干什么呢,要将。原来的原来的数据,数据拷贝过来,拷贝到新的数组。
06:06
数组并并干什么呢?并加入或者叫插入新的数据。好,这个我们可以看到这个性能是比较低的,当然有同学说了,说老师我们也可以事先把这个数组整大一点吗?比如说我们不需要扩容,我们事先虽然存了五个数据,但是我们可以事先干什么呢?我们。我们事先把它开六个开七个,这个也是可以的,是你这个方案呢是可以,但是呢,你想一想,你想想,毕竟。他还是有一个问题,就说你开多大。是不是你开大了呢,浪费,开小了不够用,是不是这样的问题,所以说不管你用什么,你你去。通过事先预留一些空间,还是动态扩容来处理这个添加,其实都是比较麻烦的。那有些同学老师,我们学过一个叫做叫做什么呢?叫做这个叫做集合的,不是他就可以动态的增长吗?各位同学。
07:09
我在这里顺带给他说一下集合,你比如说你们很多同学应该我们都知道有list,其实这个a list呢,它的底层也是它的底层是维护了,维护了一个数组的。这个数组呢,是个object数组。这个速度也是在动态的扩容,就说他事先呢,先分配一个空间,当不够的时候,他按照一定的这个比例来扩容,也是它底层仍然是按照刚才老师讲的这个方式来扩的,只是呢。他的那个策略不一样而已,不是说来一个来加一个,扩一次,而是按照一定比例来扩,我们可以适当的看一下这段代码,来,同学们看,我们打开这里,我给他写一段简单的测试程序,好,刚好我们讲到数了,对不对,所以说我建一个包。那么这个呢,就是我们讲的这个数据结构。
08:03
好,同学们,我们好呢,写段测试代码来看一下集合,它是怎么来进行这个处理的呢?来,同学们,我就以release的为例。好吧,我们以。就是以什么呢?以这个r r list的为例为例。看看什么呢?看看底层它是是怎样怎样进行这个数组扩容的。对不对,数组扩容的,其实呢,非常的简单,你看啊扩容。扩展也行啊,扩容扩容比较精准一点,那比如说我六一个r list。简单一点哈,简单一点,那么我分配一个2LIST,好,现在呢,这里面我们要需要引包包对吧,把包引进去,引进去过后呢,这边有一些警告,是因为我们没有用泛型呢,或者这样写东西哈,把它加进去就可以了,还有一个没有使用的,我也不去管它了。
09:04
把这个也粘进去,On。Onus正确,好,同学们可以看到,现在我们看一下源码,我们看一下这个R的源码,各位同学请看。我们看一下这个源码它是长什么样子的。各位同学,请看O的底层,你看它的构造器,就是刚才构造器,你们有没有发现它上来过后呢?先把一个空数组给到了element。Data这个element是什么呢?大家看,其实它就是个数组,看到没有,是个对象数组。也就是说,也就是说我们这一个list,它这里面是干什么呢?它。就是r r list,它维护了,它底层维护了一个数组,就是这个数组。这个数组呢,它会根据你的需求来适当的扩容,它初始化是个什么东西,大家看是不是初始化,我们回到刚才,那你看是不是初始化,诶我再进去一下啊,你看它初始化的时候。
10:05
看这里是不是一个这样的DEA capital emptypity element data,你到这去看一下,其实它是个空数组。是不是?这是一个空数组,是这样子的吧,那么它怎么增长的呢?大家看在这个在这个list的不够的时候呢,它有一个方法叫做grow。来看这里这个grow,这个你们有没有发现,就是当。按照他这个几率,当他。当这个容量不够的时候,它会按照一种策略来进行这个这个增长,它的容器,也就是实际上它底层呢,是靠这个格的方法来进行这个扩容的,我写到这来。也就是说数什么呢?就是说a list的a list的底层,底层仍然仍然是进行了进行了数组扩容。
11:02
数组扩容,也就是说,也就是说刚才我们分析的这个逻辑,其实也是运用在我们A,那具体来说是什么样子呢?刚好我这里以前讲过这边的是讲过一套Java基础,在第21天二十二天的时候,我专门讲这个东西了,大家看。在21天的时候,我讲了阿list,它的底层结构和源码分析,在二十二天呢,第二十二天的时候呢,我又接着讲了哈西赛特的。源码和底层分析,在下面这一天呢,我们又讲了另外一套,就是关于哈希map的底层结构分析,刚好呢,我们可以看一下a list它是怎么做的,打开我以前这写的笔记。好简单,看一眼咱们就走了啊,就是让大家知道,其实我们的集合底层它的确是用数组扩容的方式来处理的,那么我们来看看他是怎么处理的呢?好,我往这儿拿下。
12:01
那都进来。看这里呢,我这儿有一有一个章节专门讲的,诶往这边挪一下啊。点一下这稍微有点慢,因为这个文件太大了。好,同学们看a list的它的它的底层操作机制和源码分析,其实它是这样几个特点,首先or list的维护了是一个。Object类型的数组,就是刚才给同学们看的那段代码,那么如果你是无参构造呢?这个element data它容量为07点,呃,JDK7是默认为十个,那么它的容量是什么?如果你在创建的时候指定的这个容量,就按你指定的容量来分配这个大小,但是注意啊,呃,当添加元素的时候,其实它底层是先判断是否需要扩容,如果需要扩容呢,它掉的就是那个grow方法,就是刚才给同学们看的那个grow。否则就直接加进去,就是还有的话就加到四个位置,那么呃,如果是无参构造器,它第一次添加呢,需要扩容,它是按照直直接扩容到十。
13:06
以后再次扩容就按1.5倍扩,如果你是按照指定容量来创建R的时候呢,它要扩容的时候直接按1.5倍扩容。就是刚才给大家看的grow这个方法,也也就是说,从而证明了我们刚才讲的这一个数组存储方式其实是R历史的底层,大家想它的底层他为了解决这个数组频繁的扩容,是不是它实际上是按照一种策略来进行扩容的呀?是不是,所以说它仍然是数组存储的,那么这个数组扩容,不管你事先预留还是不预留,它整体移动还是存在这个问题的,是吧,效率仍然是较低的,因此呢,我们现在呢,可以看看能否用链式存储来解决这个问题,我们先看链式存储的优点,链式存储呢,它在一定程存度上对数组存储是有一定优化的,比如说它插入一个数字节点,只需要将只只需要插入节点。
14:08
把这个插入节点链链接到链表就可以了,删除效率也比较好,你还是看一个案例,比方说现在我们这里有一个链表,我就快速的演示一下啊。我就写,呃,我就写三个节点就可以了。好,是的。大家看我这里有四个节点,比如说这个这个节点仍然是一,这是三,这是五,这是八吧,现在呢,我们要加入一个节点,大家体会一下,比如现在我有个节点是六。这个六这个节点呢,我需要加到五到八之间,大家看如果是按照我们这个链表来说,其实大家有没有发现它至少不需要。不再需要进行整个拷贝,是不是他只要怎么做呢?各位同学是不是按照我们以前讲链表的时候,只需要让新的节点先指向。
15:04
这个八,然后让五这个节点的next指向六,这个事就完成了,是不是它的添加效率还是very good的,而且呢,因为它是链表嘛,内存里面它可以动态的扩展。删除当然也是一样,对吧?我们删除的话,删除一个节点只需要让前一个节点指向下一个节点就可以了。同样数组的删除也存在这个问题,比如说我要删除我,你把这个五删除了,是不是理论上来说这个八和九应该往下移,又得整体移动?因此通过刚才我们这个讲解呢,同学们可以看出这么几个问题,就是就是我们开始总结的就是劣势存储呢,他在加入或删除的时候效率很好,但是在进行检索。是仍然很低,你看啊,刚才我们分析到链表它进行这个添加和删除的时候,性能还是不错的。
16:01
但是链表仍然存在一个问题,就是检索。比如说我要检索。五这个节点是不是我们还是得从这一个头节点,比如说一号是我们的头节点,是不是它得便利,他说诶,一是先按到一不是,我于是往下移动一下,看下一个节点是不是我不是再往下面走一下,是不是他仍然是要进行这个整体遍历的,假如我们这个链表很长,各位假如跟我们这个链表有100万个数据。而你刚好查的是在最后,是不是你这个要比较100万次啊。是不是同学们,所以说我们得出这个结论是什么呢?就是我们得出这个结论是呃数组链,数组存储方式呢,它呃下标很快,但是它插入和。删除比较效率比较低,那链式存储呢,它的插入和删除效率还不错,但是它在检索的时候仍然速度比较慢。
17:02
是不是这样的?同学们好,那我们分析了数组存储和链式存储的问题,必然就会提出一种新的存储方式,就是数。这个数存储方式呢,它能够提高数据的存储和读取效率,如果我们利用二叉排序数呢,还可以保证数据的检索速度。同时呢,也可以保证数据的插入,删除修改速度,诶,这个数结构就是一个非常不错的存储数据的结构,而实际上在我们开发中呢,很多集合的底层就是用的数,比如说我们的红黑素。对不对?那数到底是个什么样子的东西,它为什么可以既能够提高存储读取的效率,还能够保证插入、删除、修改的速度呢?好,各位同学,我现在先简单的给大家画一个图,帮助大家理解,然后我们后面再详讲,所以说我这写的先画一个示意图理解,后面详讲来同学们,我们仍然以一个数组来为例,还是完成一个添加和删除的一个分析,来我们分析一下。
18:12
我们分析啊,如果以二叉排序数来存储数据。数据数据,那么那么我们对对对数据的这个数据的增删改查,增删改查的改查的效率,效率都可以得到保证,效率都。啊,都可以提高,那为什么可以提高呢?可以提高。好,同学们,诶,提高。好,那同学们来,我们仍然以一个实际的案例给大家聊聊吧,啊,大家看,假如这里面有一个数组啊,有有有些数据。我们就以这个为例。
19:01
这有几个数呢?咱们这一共有啊七个数,如果七个数我们以数的方式来存储,以这个二叉排序数啊,现在我直接以二叉排序数来讲,如果以二叉排序数来存的话呢,它是在,它在这个存储的形式是这样子的,首先有一个节点,他先存的是一,存的是七。然后呢,他按照一定的规则来走,怎么走呢?好,当他发现有三的时候,就放在七的左子节点。那三三用七呢,用七指向这个三,显然我这里画了一条线,就意味着他们之间是有一个连线的,这个连线呢,实际上就是一个指针,或者说一个引用。就有点像我们的,呃,前面讲的单链表的那个left,但是呢,这个呢,呃就叫left。好,如果十怎么办呢?十就放在七的什么呢,右边,就是它的右直接点,那这个就是十。
20:03
看清楚了啊,这就是十。啊,这个人仍然指向他,那下面我们要放放放一怎么办呢?一放在三的左子节点。啊,放在三,因为它比山要小,所以说放在山的左子节点,同样让山指向这个节点。OK,好,紧接着我们发现有一个五,五怎么办呢?五放在五是这样子的啊,大家看五的特点是它比七小,比三大,所以说我们就放在三的右子节点。同样它也有一个。指针指向它,或者叫引用指向我们这个五,那么还有一个九,九怎么办呢?各位同学,九它是比七大的,所以说呢,放在七整整体放在七这边,那么它又比十小,所以放在十的左子,左子节点。同样让它指向它,注意听啊,同学们。
21:02
这一会大家就看到它的优势了,下面呢,12 12怎么办呢?12放在十的。右子节点,因为它比十大。同学们看,当我们这样存储过后,诶,我们来玩一玩,假如现在我要查找,我要删除,我要修改,是不是效率得到了一定保证呢?我们来分析一下。好分析一把,分析分析一把什么呢?分析一把这个以以二叉排序数来。来存储,存储数据的这个效率。那大家可以看到,假如我现在要去干什么呢?要去检索检索一个啊三或者检索检索九吧,检索12。检索12,你看我怎么检索呢,大家看,首先我先到。这个最上面顶级的这个七来比较比较。
22:03
那么我发现七,我我要我假设我要查查12啊,假如我们要查找12。大家看效率是不是提升了很多,第一个第一个需求要查找。查找。12。那么查到12的话呢,我们先跟七比较,发现12比7大,于是我马上往它的右边去找,大家可以看到有没有发现。是不是一下就折半了?是不是一下就走半了?是不是有点像我们二分呢?当然12,呃,十再跟十十二比较,我们发现呢,12比10大,继续往它的右子眼找,12找到,也就是说经过两轮比较,就是经过。而经过。经过两次。哎,两次比较就找到了,找到了我们这个12这个节点。是不是非常的快呀,那有些同学老师,那我们添加快不快呢,添加也很快。
23:05
添加也很快,你比如说我们现在要添加这一个,假如啊,我们要添加13。假若没添加。添加13,比如说我举一个例子,那首先我要找位置,是不是因为你添加你首先得找到位置,找位置应该很快,我们首先我们应该先定位到12,这是肯定的,因为你要找一个呃找找到一个比比13,最比13那个呃是呃比13小一点的嘛,但是呢,又比其他数大的是不是,我们找到相当于找到整个这个链表里面最大的是不是12,找到以后我们怎么办呢?我们把。我们只需要这样做,就是假设这是13这个节点,我们直接把13这个节点挂到12的右子节点,这个事就完成了。是不是也是一个动作就搞定?添加是不是样子,那删除也是一样的啦,删除说老师那删除如果我们删除中间的这个行不行呢,也很快,只是现在呢,我先不讲删除的时候呢,我们需要处理,如果删除的是呃十这个节点稍微要处理一下,但是速度也很快。
24:13
那假如说我们现现在删除的是看啊这地方很快对吧,很快。那如果说我们现在要删除,我举一个最呃大家容易思考的,比如说我们要删除什么呢?删除一这个节点。是不是很快说老师,我们怎么看呢?我们首先找这个一。1:7是不是要小啊,先到它的左支节点,发现3:1还大,于是再往左边一找,诶找到了,找到了过后我们其实干什么呢?其实我们在找的时候呢,会有一个它的负节点。留在这,我们就让这个负节点的na nap制空,就把这个线拿掉,这事就完成了。这事就完成了,所以说我们可以看到呢,删除的速度也很快,当然了,当然有同学老师,假如说我们删除的是中间怎么办,待会再说,中间也很容易处理,我稍微的给它进行一个,进行一个。
25:11
进行一个处理,这个事就完事了。是不是很好很好解决,其实我就是干什么呢?我只需要把它右边的这个桌子尽量往上移动就可以了,这事就搞定,是不是仍然保证它是一个二叉排序数,因此我们分析出来他的查找、添加、删除、修改都很快,修改为什么很快呢?修改是不是先查找到,把值改一下就可以了。啊,对不对,所以说我们通过这个分析呢,发现二叉,二叉以二叉树的形式,呃,以数的形式啊,但不一定是,不一定只是二叉树,将来也可能是B速必加速。Avl树,霍夫曼树等等,那反正是以树的这种结构呢,显然它比我们这个链表的结构要。要灵活,关键是解决了一个查找速度问题。同时呢,我们比数组呢也灵活,因为它添加和删除速度也是非常快的,好同学们经过这个分析,我相信大家对数这个结构的好处有一定的了解了,有一定的了解了,好的,那现在呢,我把数刚才讲的这部分内容给同学们进行一个简单的板书,来打开它。
26:21
诶,我们是在这边啊郭同学。那现在这块给大家讲的是什么呢?现在这一块给大家讲的是数结构的基础部分结构。数结构的基础。部分。那么基础部分我怎么讲的呢?首先先给同学们说了一下二叉树的呃,为什么需要这个数对不对?先给同学们聊了一下为什么需要这个数,好,我说了三点。是不是说了三点,同学们给他整理一把。好,这是首先我们说先给大家聊了一下这个数组存储方式的一个分析,紧接着呢,我们给大家分析了把链式存储方式的分析,最后我们说明了数存储方式的分析是这样子的吧,同学们好把这个稍微的整理一下。
27:15
我们分析了宿主这个。它的优点,优点就是可以通过下标来访问。是这样子的吧,啊,而且呢,还可以通过二分查找来提高我们的检索速度,但前提是一个有序的,但是它的缺点呢,非常的明显,缺点就是说在插入的时候呢,会整体移动。那么就会造成效率的低下,对不对,接着呢,我们画了一个示意图,对不对,我们画了画出。诶,这个地方稍微重点啊,画出了画出这个操作示意图。示意图。加深同学们对数组的一个存储方式的理解,这个图呢,是不是就在这啊?对,我们就是通过这个方式呢,给同学们聊了一下。
28:01
把这个图呢,我们拿到咱们的笔记中去,便于同学们的复习。是不是以这种方式,我们发现的确是有问题的,紧接着呢,我们说诶,那既然数组不好,我们用链链式存储,比如说链表行不行呢,也分析了一下,首先我们发现链式存储呢,它在一定程度上对这个插入还有删除。删除效率它的确有所提升,这个大家刚才看到了,但是呢,它的检索效率仍然比较低下,为什么比较低下,因为他在找的时候,他会。一个一个一个的找。是是仍然存在问题,所以说我们画了一个图呢,说明了他的一个操作示意图。啊叫做操操作示意图。是这样子的吧,我们把操作示意图仍然给同学们拿到我们这块来。操作示意图呢,就是刚才老师在这个Excel里面画的这个图。加深同学们对它的理解。这是这个问题,那紧接着说老师,哎,那这个都不行怎么办呢?我们就引出了真正要讲的内容,就是数存储,也就是我们的数数结构,那么数结构它的好处是干什么呢?它有这么几点好处,第一个呢,它能够提高我们数据的存储和读取的速度。
29:19
那比如说我们刚才讲的以二叉排序数就可以解决,对不对,那它既可以保证检索,而且呢,对插入删除修改的速度也是very good的。所以说你们可以看到,在很多的这个优化里边,包括集合底层呢,很多它其实是以数的方式来玩的。对吧,那这里呢,我们也有一个示意图。一个案例,一个示意图,给大家来聊了一把,那图在哪里呢?就是刚才老师在这里画的这个图。是不是同学们,诶,你看这儿我就给同学们聊了一下,如果我们怎么怎么做,对不对,我说如果查找12其实。要添加13也很快,找到12这个节点,直接把12这个节点的右右子节点把它挂,呃,把13挂在12这个节点的右子节点完事,删除一很简单,找到一的负节点,把它的负节点就是三,它左边左侧节点直接支空就拿出去了。
30:20
同学们可以看到,的确啊,的确这个结构呢,还是非常OK的OK的好,同学们,那关于我们对数结构的一个引出这一部分内容呢,就给同学们先聊到这里。
我来说两句