00:00
同学们,我们来首先呢,花那么十分钟左右,把上一次课我们讲的内容呢,给大家简单的回顾一下,那如果是昨天没有来,就是因为啊什么原因没有来听课的同学呢,就把我们昨天讲的那个视频自己去看一看啊好,我们来回忆一下上次课我们讲的啊,主要是讲了哪些内容。上次课呢,我们是讲的这个从这里开始讲的,讲到哪里呢?讲的队列就是数据结构里面的这个队列。队列呢,我们是怎么讲的,我们简单的回顾一下队列,我们在年前讲的呢,是用数组来模拟了一个队列,但当时那个队列有一个问题,就是他的数据存储空间不能够复用,对吧,所以说他他这个比如说那个用完一次就不能用了,那在实际开发中呢,这种队列其实用的非常少,所以说我们就对他进行了一个改进,我们怎么改进的呢?我们来看一看。
01:02
我们就。就针对这个问题,我们用数组呢,模拟一个环形队列,这个环形队列其实它并本身并不难,但是它重点就是给大家提出了一个什么呀,提出一个解决方法,就是同学们以后需要把一个数组做成做成一个环形来对待的,你比如说我们昨天布置的那一个题,什么题呢?就是丢手帕问题,一一群小孩围在一起丢手帕,其实他也可以用数组来完成。因为宿主呢,你可以通过取模的方式把它当做一个环形对待,那当然宿主其实也是可以完成的,因此同学们如果有兴趣,如果你有兴趣的话呢,你也可以尝试着用数组来解决我们昨天布置的那个约瑟夫问题,我这也提示大家啊,因为。因为这个数组,数组也可以可以通过这个取模的方式方式当作一个环形来环形结构来使用,对不对,那么那么那么也可以解决约瑟夫问题。
02:16
约瑟夫问题。啊,同学们呢,要是有兴趣的话,可以尝试着用数组来解决,但是用数组来解决呢,他可能需要你更动脑筋一点,因为它没有像用环形这个单向环形列表那么形象。因为有些同学呢,他习惯形象的思维,有些同学呢,他可能习呃这个呃,习惯这个抽象的这种思维,那如果用数组来解决这个约束符问题呢,大家也可以去尝试着做一做这个,我给大家提示一个信息,提示一个就说如果用数组来来来解决约束符问题呢,你就不能,你就不能说当我把一个小孩数到过后,我把它从数字里面踢掉。因为数组大家要知道它是不能一般来讲数组我们不动态改变,那这个时候呢,你可以通过一个标志来表明这个数据的人已经出圈了。
03:09
可以这样来设计,所说这个地方呢,大家提示大家一下,如果这样解决的话呢,提示啊,提示可以通过通过这个。这个修改修改元素元素。元素的这个值来表明,或者在标识该该元素是否是,呃,对该元素对应的这个小孩是否出出队列了,出这个出圈了。啊,同学们可以尝试着去完成一下,动动脑筋,那我们这个数组模拟环形队列里面呢,最重要的就是这几个比较重要的一个小算法,哪哪个算法呢,第一个,第一个就是怎么去判断这个队列已经满了。
04:01
是用的这个来做的。对,我们是用的这个real加一模马,Size等于front,这个就代表满。但是因为因为我们上来过后,先把这个front,就是队列的头部和这个RA呢,是用零来标识的,所以说这样呢,其实在我们这个数据结构里面,它有一个。空出了一个容量作为一个约定,所以说有一个数据空间呢,会被浪费。但这个问题不是很大,因为你队列可能很大嘛,比如说你这个你这个数组假设有,呃,30个元素有一个作为空出来约定,这个也不是特别影响。当然如果说同学们有兴趣的话,也可以尝试着说解决,连一个连这个一个空间都不浪费的,就一个元素的空间也不浪费,也可以实现,但是那个呢,可能理解起来稍微麻烦一点,好,这是这个地方就是判断队列已满,那么怎么去判断对队列已空呢?就是这个real,如果等于front,这个就是队列以空,最后呢,还有一个地方特别重要,就哪个地方呢?就这里。
05:09
就是你在整个这个入这个入队列和这个出队列,比如说我们这个地方有一个入队列的操作,那么在整个这个操作过程中,你的这个尾指针就是对立的尾指针,始终是按照这个取模的方式来进行操作的,你就不能说按以前的操作,诶没有这个取模了,没有取模那肯定它就不是一个环形的了,所以这方要注意。另外取的时候也是同样的道理,你取的时候呢,取完了过后,过后这个队列的投掷人他在往后面移动的时候,也要按取模的方式来操作。还有一点在哪里呢?就是我们在显示队列所有数据的时候,这个呢,就要用找到这个队列的投子帧,然后按后面应该取多少个来进行这个便利,便利的时候呢,同样也是按照取出来的这一个。
06:04
值来通过取模方式来找到对应它在这个数组,数组里面真正的那个下标,因为你你始终是当成一个环形来对待的吗?说你在任何一种操作的时候都千万不要忘了取模,否则肯定要越界。对,还有一点呢,就是怎么去求这个size子,求出这个数据,就是当前这个队列里面真正有多少个数据呢?这个算法是在这里的,大家看这里啊。为什么是这样子,大家要动脑筋去想,就是real加max size减方模MAS,这个是求出了什么呢?这个就是求出求出啊,或者要返回求出该队列或者当前队列,当前队列有实际啊,实际有多少个数据实际。有多少个数据对数据,那么我始终给大家,呃,阐述一个观点,就是同学们呢,在后边你们在做这个大数据开发,有些同学还要学这个机器,你们应该是Java加大数据还是机器学习加大数据啊。
07:14
你们是机器学习,那机器学习里面像这种小小算法就特别的多。你比如说我们有有一个,我举个很形象的一个例子,对吧,就好像咱们有一个杀猪宰牛的,他在杀猪的时候,他用一把大刀,一刀把这个猪先砍死,但是他提骨头的时候,他用用用很多小工具,这小工具就是像这种小技巧你得有。不然的话呢,你感觉上去过后就总是不能驾驭这种这种这种结构,说这些小算盘呢,我建议大家有时间的话,呃,可以多看看,这种就是比较就是看起来不是那么的高大上,但是呢,他在解决一些实际的问题的时候呢,也感觉。很很有意思,就是你首先有些小工具,哎,这个大家要去多注意积累。
08:04
好,下面我就不再去讲了啊,最后把这个队列用环形来模拟过后呢,就提高了我们数据空间的使用使用对吧,你可以出队列过后我还可以继续放。啊,这样子就很好了,然后呢,我们就讲了一个链表,那么首先这个链表大家要非常清晰的知道,就说链表它在存储的时候呢,有一个特点,什么特点,这个一定要跟面试官或者你自己要理解,就说他在这个存储的时候,这个头指针呢。你看这个头指针,它指向的是这个位置。他不就说指完了过后这个后面这个next域呢,它又指向的是这,那就意味着在我们内存空间里边呢,我们这个就是说从从这个逻辑上来看,我们经常这样画,比如这是个头,它指向了下面一个节点,然后这个下面又指向一个节点,从这个,从这个逻辑示意图来看,我们感觉好像它的空间是这样排序的,比如说就是0X12B10吧。
09:13
这个呢,它不一定就是0X的,比如说你这个数据的这个大小站,呃,八个字节假设样子,它不一定,因为它在这个,在这个分配这个节点的空间时,它有可能并不是连续的,但那他怎么做的呢?它主要是靠这个next的域来关联下一个节点。这样呢,就说我们这个链表就可以有效的利用我们内存的这个碎片,内存碎片就是说可能你这这个空间它不是一大一整块,它同样可以把我们列表放进去,所以说有时候你会翻到一些特别有意思的情况,就是你放一个同样大小的数组,你它会报内存不足,但是你放一个同样大小的链表,它却放进去了。为什么呢?因为操作系统它会自动去分配,就是怎这个分配,这个地址到底是多少,是由操作系统来来做来做的,它会仍然给你放进去,就好像小的空间有效的利用起来了。
10:12
有效利用起来,那么因为这样一个原因,这正是因为这个原因,所以说我们链表呢,也存在一个巨大的问题,它有什么巨大的问题呢?就说你在进行这个检索的时候,进行这个检索的时候,如果你没有做优化,那么他整个在检索的时候只能读这个投资帧,一个一个的这个比较。对吧,说他这个就比较麻烦,但有同学说了,说老师那这样子这样做,我们能不能解决这个问题呢?可以解决,可以解决,后边呢,我们会讲一个比较有用的一个东西叫二叉树,这个二叉树呢,它底层也是基于这个链表的,它就能够解决这个检索和。删除还有修改这个效率,那个你们听完了过后,这个叫这个BST,这个二叉搜索数,你们就突然感觉,诶把链表和这个数就完美的结合在一起了,后面呢,我们会讲这个BST,这个我觉得非常有用,因为二叉数很多,这个二叉搜索数就是BST这个数,我感觉在我们做开发的时候非常有用,到时间我们重点讲这个啊,OK,那么链表呢,就是它的一个基本结构,大家要非常清晰。
11:25
然后我们讲的是怎么讲的呢?先给大家讲了一个单链表。单链表呢,一般来说为了呃操作比较方便,我们写的是带头节点的,那有些同学老师那个单链表能不能不带头节点呢也可以。今天我们讲这个哈希就散裂。就是我们讲这个散裂。散列,散列呢它也叫哈希啊,讲这个这个哈希表的时候呢,我们就会用到一个不带头节点的这个单链表,而且它不是一条,它是多条,就会体体会这个不带头节点又是怎么去使用的啊,今天我们要讲这个哈西。
12:08
好,呃,那么单链表长什么样子,我就我不再多说了啊,比如hide指向这个,那么它的特点是什么呢?就是别人问你单链表带头节点的单链表,它的特点是它事先会创建一个头节点,但这个头节点呢,本身并不存放真正的这个有效的数据,但当然它本身仍然是个节点啊。只是这个头节点,它的存在的价值是什么?诶,它主要是为了让我们更加方便的对这个链表进行增删改查。对。是这样子的,你如果没有这个头节点,你再进行这个增删改查的时候,要考虑你在添加或者删除的刚好是头节点的情况,就会这个代码写起来就相对比较麻烦,同学们如果有兴趣可以去尝试着写不带头节点,你会发现代码比我们原先给的带头节点的呢要麻烦一些。
13:06
带头稍稍稍微麻烦一些,但是也是可以解决的啊,所以说一般来讲单链表呢,大家如果为了这个方便就带一个投节点,我觉得是比较好的,好,那么这个带头节节点的具体的这个理解,包括它的代码增删改查我都写的有,比如说诶他怎么去,你看下面不都有吗?对吧,怎么去,呃删除。对不对,怎么去这个修改怎么去。啊,下一面是怎么去添加,对怎么去便利啊,这是第二,两种添加方式我都讲了,怎么去便利啊,下面是怎去遍历,都讲了,那同学们至少要单链表要非常熟悉,那有的有些同学老师单链表看起来为什么要非常熟悉呢?因为你后面学所有的基于这种链表结构的啊,比如像二叉术。
14:00
啊,或者多路数,你全部都是基于这个链表结构的,如果你对链表不理解,那你学那些东西呢,你感觉就是有点空,好所以说这个呢,我要求大家能够,呃,理解的到位,就增删改查,又很熟悉,噼里啪啦就能写出来。好的,那我们单列表呢,我们讲完了过后,我们发现单列表一个有一个问题。啊,是不是老师已经分析了,单调有个最大的问题,就是说它只能是从一个方向去检索。那假如我们将来有一种可能性是逆向的,或者是我们要实现这个链表的自我删除单链表就不行了,所以说我们就提出了一个新的叫双向链表的这么一个数据结构,那为什么呢?因为我们刚才讲了单向链表它是有缺点的,对吧?它有缺点,缺点是它只能沿一个方向走。但是实际上在有时候做开发呢,我们有可能要反向或者说找到一个节点,我要。我比如说我找到一个节点,打个比方。
15:00
打个比方,我有这么一个,我有这么一个东西,我找到一个节点,我想找它的前节点和后节,或者说我要实现自我删除,那单链表就不好使了。于是乎呢,在我们数据结构里面有有个叫双向链表的,那双向链表呢,这个示意图就这样子的,就说这个图集点指向它啊,指向它,它还这边的有个节点,有个前驱节点,它可以指向前面。好,这就是双向链表,那双向链表呢,我们没有没有全新写,我们在单链表的基础上改成双向链表,这个呢,大家也要熟悉啊,OK,这次双向链表正三改造,我就不再一个个念了,好吧。那么这个讲完了之后呢,我们又提出一个新的数据结构,叫单向环形链表,前面讲的单链单向的或者双向的,它是它不是环形的。但在很多情况下,我们需要这个链表是环状。
16:00
因为有很多应用场景,它需要你是环形的,你比如说约瑟夫问题就是一个经典的用单向环形链表来解决问题的一个应用场景,那我们就用单向环形链表解决了这个问题,对吧?那具体怎么走的?呃,我也画了示意图,也具体写了代码。呃,具体写的代码这个我就不再一个个念了啊,就是把这个,呃,把昨天讲的那个回顾一下。哦,这这就不一个念了啊,包括怎么怎么操作的,就咱们一行一行代码写出来的,不念了。好,这个讲完了过后呢,我们呃,我们我们就又接着讲了一个数据结构,叫占占,这个数据结构其实同学们并不陌生,一般来讲,只要是学计算机的,不不管你们是呃科班的还是非科班的老师,都应该提供这个站站,这个结构确实也挺简单,因为他最重要的操作无所谓,就是这么几个操作,一个是这个出战。
17:02
一个是出战。一个是入战。这是他最经典的两个操作。而且呢,赞它是先进后出。对,先进。先进后出。啊,那那这个数据结构它本身很简单,但是它应用起来可就不太简单了,就当你学完一个站过后,很多人其实很难理解这个站有什么用。对吧,就说这个站你喜欢出战,出战都很都很好写,但是它到底有什么用呢?它一旦应用起来,你会发现也很麻烦,就说你能想到它的应用场景。你比如说我们用站就做了一个什么事情呢,大家看我们就用这个站完成了一个最经典的叫一个计算器,你比如说我给你一个字符串。就是计算这个表达式的一个值。那这个时候你你突然发现你就没有思路了,而这个呢,恰好就是我们这个站的经典应用场景,那为什么这个用站比较合适呢?大家看,因为它有个特点,就是当你遇到这类问题的时候,注意听这句话啊,就说数据结构它往往是解决一类问题而产生的。
18:14
就说就说这个数据结构是怎么产导致的呢。就是因为在我们编程的过程中,就是在我们这个编程的过程中,有很多程序员。他遇到了一个问题,这个问题呢,是一个共性的问题,然后才推出这个结构。而我们这个站,它最经典的一个应用场景,就说你看你看,当我们去做这样一种操作时,你就可以考虑用膳,什么问题呢?你打个比方,就说我们这个数据,注意听,我们在进行一个操作时,这个数据它不是马上处理。比如说这个一啊,这个七乘以二,再乘以个二,这个七。乘以二的这个动作是不是马上处理不知道。
19:02
那这个时候呢,我们可以把这个数据先放到一个空间里边,然后呢,再把这个符号放到另外一个空间里边,然后再进行下一次扫描的时候,因为你这个七乘以二或者七加二到底要不要不要进行运算,取决于后面的这个操作服务,就说就说你你有这样一个问题,就是说你的一个操作它不是马上要进行,它要取决于后面的一个符号或者一个。一个标识来决定你前面的操作是否要进行的时候,就可以考虑站,而为什么呢?因为站它刚好是一个先进后出的。这么一种结构再说一遍啊,就是说你的一类问题是这样子的,说你这个问题当你要去做之前,你要考虑后面的,才知道前面要不要做的情况下,就可以考虑站。为什么?因为站刚好是先进后出。你先进去,我我先不处理你。
20:01
我要决定处理的时候,是由后面来决定的,到底要处不处理,像这种问题你你们就可以考虑用这个站来解决。哎,这就是他一个一个一个一个一类问题的一个小结,就大家要注意去总结好,那这个你看这个就是这样一种情况啊,老师呢,就一步一步写出来了啊,我就不再一个念了,因为代码也很多,你看我这还提示大家就说,就说我们讲这个数据结构一个最核心的一个观点,就是开阔大家的一个编程思路。就是说你你学完数据结构的人,或者说数据结构写的好的人,和没有数据结构这个基础的人,他最本质的区别是在于有数据结构的人,他在解决问题的时候,他的思路很开阔。就很开阔,就是当他遇到一个具体问题时,他会想,诶,我可以用队列还是战,还是用链表,还是用速,还是用我们的递归回溯,还是用哈希来解决,但是如果你没有这个数据结构的人呢?
21:04
他就很懵啊,他说这个东西怎么解决,突然就感觉短路了。就好像有你们两个人打架对吧,人家来了一个。猴子在逃是吧,你你你这个你这个要是学过套路的人,你就知道我用一个这个猴子上树先跑了再说嘛,对吧,就是你你就有个套路来知道我怎么对付他。但是如果你没有学过这个数据,数据结构,或者没有学过套路,人家打过来,你就直接在这干癌着。就就这么一点区别,就你学完之后,你感觉我下一个我我能用用一个什么方法来解决,至少能开阔你的思路,因此同学们呢,就是说如果有这种可能的话,包括我们学完这个数据结构,你们在老师这个基础上可以再多看一点,因为我们时间有限,理论上说像这个数据结构啊,如果像科班出身的,像一般科班出身的啊,就是说甚至。有些我看到包括我的同学,他们基本上是够那个工作以后,都还要把那个大学的数据结构好好看一遍,为什么?因为大学里面学这个数据结构,它有个最致命的问题,一般老师呢,就把那个PPT念一下,就大部分同学有没有敲代码。
22:15
就好像知道这个概念,但实际上啥都不知道。啊,但是到了工作时候才发现它的重要性,就回去才回回下炉,所以你们到时间还可以,有时间再可以好好的去看一看,理论上这个数据结构算法如果能讲,如果说咱们踏踏实实的能讲五天,或者十讲的讲个八天,那你们整整个人的水平不一样了。但是很遗憾,我们只有两天时间对吧,但但但这个你们呢,就是说知道这个事就行了,因为这个东西他也不是每个人都要去,就说嗯,为有可能你感觉到没有用嘛。数据结构其实很有用,它为什么大家感觉没有用呢?因为你没有应用场景,就你看我,我每次我每讲一个数据结构,我往往都来用一下,大家感觉还诶感觉好像还有点儿用。
23:02
那一般那老师就不讲了,他直接把这个站讲完,入战入战出战讲完确实没有用啊,他一讲一个应用场景,诶有用啊,就这样子的好,那么这个站的这个应用场景思路,我先把它整理了一下,然后呢,我们就用代码一步一步将其实现哦,一步一步将其实现,这个呢,我就不再一步一步看了啊同学们。好的,这是那段,就是写计算器的一段代码,然后呢,这个。赞说完了过后呢,昨天我们就主要是讲到这儿了,对吧,好,回顾我们就到这里。
我来说两句