00:00
那待会儿这个单向环形链表长的样子呢,大致就是这样子的。啊,就是找一个节点往下指,往下指形成一个链表,数的时候呢,找找到一个就出圈,出圈就把它删掉,删掉过后再形成一个环形链表,接着再数。再做最后留下最后一个人,好,那现在呢,我们就来开始,这个示意图也也已经有了,那下面我们就开始写代码了啊,那写代码我大体把这个思路给大家说一说,待会我要做的这个题呢,大体分这么几个步骤,第一个步骤,首先呢,我要见小孩的节点,这个很简单。小孩,我待会有个编号,有个next就行了,我也我也不要名字了啊,张三李四这无所谓,但你要带信息也可以,那么待会我编号就从这个一到几呢?我们有七个人一到七,好,那七个人呢,我待会会写一个boy game游戏这个游戏,呃,其实待会整个这个游戏里面呢,我先建一个first这个头节点。
01:00
这个这个头节点呢,待会大家知道什么意思呢,就是说呃刚开始我们有默认有一个小孩,但这个小孩呢,呃事先呃是呃是先初始化的,但实际上呢,这个小孩会被呃重新复制,那待会我有两几个方法,一个是添加小孩的方法,一个是显示。现在有有几个小孩的这个几个方法,还有一个countboy countboy就是开始玩了,就是大的,这个N大的number就是代表我们刚才。从第几个小孩开始数count number呢,就代表数数几个,这个numbers呢,就是numbers呢,就代表一共有几个小孩,那这三个信息就是刚才我们,呃,事事先要定好的,好,那现在待会我们进行这个初始化的大致的工作啊,大致的工作呢,我们就是这样子的,这有一个循环,大家看一个思路。
02:01
我我会有一个countbo,这个count boy是一个什么呢?是我们做用来做辅助的,事先为空,然后我用1TWO numbers,这个to就代表包含。就是numbers numbers这个变量本身会初始化,那numbers到时是怎么确定呢?我们确定一个七就可以了啊,Numbers我是从这传进去的,从这地方传进去的,那就循环啊,循环第一个小孩比较特别。第一个小孩是把这个创建好的小孩给first,然后让first指向first,这形成一个环,形成完过后呢,让canboy。你让这个kind boy也指向first,后面这个first就不动了。不动过后呢,我让这个当前这个小孩啊,将看到next指向小孩,然后这个地方就循环的形成一个,形成一个环,就是不管有多少小孩,以以以这个kind boy来进行这个衔接,最后当我们这个爱的boy做完以后,整个小孩的环形就形成了,还有一个short boy案呢,就是显示,显示的时候呢,大家看我这个思路也很简单啊,先判断你当前有没有小孩,一我一个都没有。
03:13
那我就不玩了,如果有的话呢,我有一个辅助指针,然后循环的进行这么一个便利。啊,循环的进行便利,好,这是显示关键是。这个数这个小孩的时候呢,我们我分成几步走呢,我分成这么这么几步,第一步首先我。有这么一个步骤,这个步骤是事先有一个T,这个T是干什么的呢?因为我是单向环形链表,待会在删除的时候,这个胎儿很有用。大家知道我们一个first在前面移动,后面在first后面跟了一个指针。我那个first就指向你,你数到哪个小孩了?那后面跟着屁股,它的尾巴后面跟着一个干什么呢?这个就是将来用来。
04:02
让通过这个胎把你这个first指向的那个小孩干掉。OK,所以说他们这里面有一个关系,就是他始终是在这个first的屁股后面跟着的,然后呢,我不停的这样去进行这个数,数完了之后,最后这儿不停的循环数,数完了过后呢。呃,来一次就数一数,该数几次数几次,最后最后稻场什么时候就退出来,就是first等于,就是T等于first的时候就说明只有一个小孩了,我就退出来,代码思路大家看清楚了啊,分成三步走,第一步先创建,然后有一个显示,最后有一个玩的方法,那现在呢,思路我们都清晰了,那老师来把这个代码给他敲一遍。我把这个思路说一下呢,大家知道我大致我要怎么去写哈,代码不难,那老师开始写代这个代码了,嗯,结合刚才这个这个环形,我应该还需要一个环形,待会儿呢,我要用哦,我把这个再简单的放,诶我这个不动它。
05:02
因为待会呢,我在分析我写法的时候,我还用一下这个东西啊,快速的把这个链表再放这拿一下,刚才把它删掉好。待会儿我要用它。做做一些分析,适当的分析。不然的话,听起来有点吃力。好,这是二号。哦,这是三号。这是四号。这是四号小孩,这是五号小孩。这是六号。好,这是六号。六号小孩好,这是七号小孩。好的,那待会儿这几个小孩怎么形成呢?好的,我现在就开始来写一段代码。好,我们写一个类啊,叫做我们就叫约瑟夫吧,这个就就以他的这个名称来定,叫约瑟夫。好,写一个,然后我们叫做。是个object。
06:01
开始写了。主方法先写上。主方写写完过后呢,先创建或者叫定义这个Y。这个类对吧,这个呢,刚才同学们已经看过了,我就不多说,呃,那这个地方我们呢,让他给我传一个number进来,这个没问题,呃,因为到时候我要初始化嘛,对不对,所以说VR。呃,然后呃,它的编号编号是一个int类型,然后呢B因为这个值其实本身不变,所以说也可以写成Val,然后有一个指向下一个节点的一个next域,这个呢类型是boy。哦,等于next,等于空,默认为空,大家看看清楚了。好的,这个写完了,写完过后呢,我们再来定义第二个类,或者写编写这个最核心的类。编写核心的这个类。核心这个类呢,就是刚才同学们看到的这个boy game啊,比如说这个是丢手帕的小游戏,那刚才规则同学们也都清晰了啊,那走一个boy game。
07:11
好好,然后这边呢,我们根据刚才的分析,首先我有一个头节点对吧,定义先初始化一个,或者是定义一个都可以叫定义一个定义一个初始的。初始的头头节点啊,这个节点呢,后面会被呃重新复制的,OK,那刚才我们是怎么写的呢?头节点v al好,这个VR呢里面呢,它要它本身是不会变化的,头节点本身啊,那现在呢,我们写上这个头节点,先写一个这个吧,First。然后呢,这个地方是一个boy。对不对,然后六一个boy。这个boy呢,我们初始化先给他来个负一,当然后面要改啊,就是这个值,这个boy这个first的这个内容会,呃,这个这个节点会修改内容会修改啊内容。
08:08
内容会修改。会。就是它的这个里面的这个编号啊,会改啊,这个我就不写了啊,先初始化后面会改好,下面呢,我们写几个核心的方法,先写一个添加小孩的方法。就是先形成一个圈,说白了。这个方法就是要形成圈。形成一个环形,形成一个单向,单向环形的。OK,环形的一个链表,能理解大家环形链表会形成一个什么样子呢,各位同学就是呃这样大致大致是这样子啊,就是一,就像这个二。二。二指向这个三,以此类推,那就形成了这么一个。这么一个环状。哦,然后是。到五哦,五指向这个六。好,六到这个七。
09:02
啊七呢,又反过来指向了我们这个一大体是这样一个环形的,我这用的是单向的,同学们可以在这个基础上做成双向的,那就那就更好了,那如果是双向的话呢,我们在删除的时候就不需要那个辅助节点了。那我这里我这里是这样思考的啊,好,有了这样一个东西,我们怎么来做这个事呢的,Deep爱的一个boy OK,那你添加这个小孩的时候,你就告诉我你一共要添加几个小孩,当你大家也可以做成那种,就是让他输信息,输名字那个控制台的形式来输,来做也行,我这就简单一下,就一次性的把七个小孩全部加进去,所以说我要得到一个numbers。这个numbers呢,就是我说一下这个含义啊,这个numbers。表示表示共啊,共有共有几个小孩。
10:01
这就是我们用单向环形链表来解决一个实际的应用场景,大家注意听好,那我怎么来做这个事儿呢?首先我先判断一下,就如果你的number这个值不正确,我们就不玩了,那怎么说呢?如果这个numbers啊,它都小于一了,那我肯定就。不做了,就是你比如传了一个零,传了一个负数,对吧,我们就不玩了,就提示一句话。就说numbers。Numbers的值不正确。不正确,我们就退出。不正确,然后就直接return。OK,那如果说他这个numbers这个值是正确的,那下面呢,我们就开始怎么做呢,好。那就开始循环的来处理,对吧,首先我们先做一个啊辅助,辅助的指针先因为在在这个在形成。注意听这句话啊,在形成环形链表时,需要需要一个辅助之针。
11:05
啊,那么我们就叫current boy,就当前这个小孩,那怎么做呢?很简单,Current。好,我们写到这karenboy,然后呢,初始化,给它来一个初始化为空吧。没问题,诶那。好,现在呢,我们就来循环的做这个事儿了,那就for循环,For循环,那for循环,呃,怎么做这个事儿呢?就是I,比如说这个number的编号我们先拿到。这样子做。呃,我一共要从一到哪里呢,到numbers这么多的小孩要加进去。是不是就是一到。Numbers,这个NUMBERS1共有几个,有几个就有几个。那么在形成的时候呢,我们首先要来对第一个小孩比较特别,因为第一个小孩为什么特别呢?因为第一个小孩要去改变他的这个。
12:00
这个指向啊,改变它的这个指向,所以说那会让它指向一个新的这个节点,其实这个地方我们也可以写成空也行,所以把你写成空也可以。啊,写成空也可以,但是呢,我这写成这个也没有什么大的问题啊,我将先写,先按我的思路写完,如果如果是诶应该是这样子的,先把这个小孩创建起来。根据什么呢?应该是根据。根据这个编号。啊,根据这个编号创建这个小孩对象,那这个就很简单了,我们就叫VR啊,我们v boy啊,Boy等于等于什么呢?等于六一个boy。六一个boy,这个boy的它需要初始化的编号,就是。N啊,Number就是你这遍历出来的,大家看懂哈,然后呢,我们判断如果是第一个小孩,如果是第一个小孩。
13:02
那我怎么做呢?我就判断如果。等于一说明这是第一个小孩,那第一个小孩比较特别,因为我要让这个first指向第一个小孩,并且并且形成一个闭合啊,那我看要做什么,做什么工作啊,首先我让这个first。啊,First,呃,指向这个boy。指向这个boy,然后我让这个first.next。啊,Next指向这个,也指向这个boy啊,实际上也可以这样说,这样子就first.next指向first,这样它就自己形成了一个就是自己的next指向自己,那肯定就形成一个啊闭环了嘛,这就是我们的形成了一个什么,形成一个自。啊,形成了一个环形的环形的链表,只是这个信息里面只有一个,但但是这个first呢,一旦定下来不能动,我们一般不会改变它的位置,比我们一般不要去轻易动它,所以说我现在让这个跑龙辅助指针也指向这个first。
14:13
好大体这样子的啊,大体这样的,也就是说这其实这一个就。已经形成了,但是呢,你后面的就不一样了,后面。后面咱们怎么去处理呢?后面就是如果有了,就是当有一个小孩形成这个过后,后面的代码呢,我们就用current来。帮助我们形成因为first不能动了吗?不能动了,那下面应该怎么做呢?来同学们想一想啊,如果再有一个节点来了。我们应该怎么办呢?有current boy.next。应该这么写。应该这么写,就是你这个boy。你这个boy。老大,想想咱们。
15:01
可不可以这样写啊?点next。先指向这个boy。先指向这个boy,然后让这个boy.next指向这个first,因为first没有动吗?这样大家看是不是是不是一个环。能看懂吗?那我们来看看这个代码,理解一下啊。前面这个我相信同学们没问题,我们以这个为例,我我主要是这一点算法吗?我们把这个算法拿过来,我们对一下来分析一下同学们。慢慢点啊。好,同学们,现现在看,当我们只有一个,我把这个先先这个先把它拿到这边来。先不要看这个啊,先不要看这个,然后呢,我们来来演示一个这个效果,比如说第一次我们创建一个小孩为一号小孩。那一号小孩做完了以后,你让这个first,让这个first。
16:01
这个first指向了这个boy,没有问题。指向这个boy first指向这个boy。First指向这个boy以后,然后你让first next指向first,那也就是说相当于在一个first里面有一个next域,它指向自己了。大家看这个能理解,就说他自己指向自己,其实这个呢就已经是个环了,那么然后你让这个current boy指向first,好,这个也没问题,那就是我们还有一个指针叫current慢点啊,就是有个current boy指向了他。好,这其实你就说当你第一个节点处理完了过后,他在内存里面是变成这个样子的。好,紧接着我们又来了,Number不是一就是二了吗?234,那我又怎么做的呢?好,这时我们又有一个节点,你看它怎么加进去的,同学们。有个二号,二号刚创建的时候,它是一个独立的节点,然后呢,我让current点点next。
17:09
就是current.next这个指向这个boy,那current是它,它的next就是它了。好,那也说这个地方就称了一下,指向谁了呢?指向塌了。对吧,指向他了,以后同学们这个时候Kan boy.next等于first boy,这个是boy吗?它的next是在这个域指向first first没有动。因此呢,它就。自赢了他。形成了一个环,形成一个环,我们这有一个问题大家看到没有,我们这个current boy要怎么样,是不是要指向这个boy才行呢?因为如果你你这个current boy不指向这个boy,那就意味着下一次添加的时候,他会把这个二。重新处理掉,是不是因此我们这还少了一个什么动作呀,还少了一个什么动作,同学们是不是让这个current boy要指向这个新的这个boy?
18:06
这样就对了,也就是说你这个地方处理完毕以后,你这个current boy其实指向了。这个。OK。那这样子处理完了过后,当我们再有第三个小孩来的时候,会变成什么样子呢?同学们看我把第三个讲完,我就不讲了啊,因为后面这个思路都一样的了。第三个小孩来了啊,你看他又这样做了,Current这个地方,我们把这个写进去,就是current boy指向这个boy,那会怎么样呢?Current boy.next指向boy,那就说这条线。会指向了他没有问题吧,然后你这个。这个这个不是boy吗?boy.next指向这个first,那也就是说这条线又会形成。对不对,是不是又是一个环,然后你这个current boy又指向这个新的boy。
19:00
是不是这个道理啊?好,是不是这样子,就一次,每次一个,经过他一番处理,这个环状就形成了。没有问题吧,好,没有问题,那下面老师就接着继续往下面讲了啊,这个没有问题,没有问题,我们先来把这个便利出来,看看OK不OK,先把第一步做完,因为添加和显示相对比较简单。那现在呢,我们来写一个显示。或者叫便利。便利这个。单向的。注意听啊,单向的环形环形链表。OK,呃,那么我们就直接写个list或者show都行,我们我这边取的叫show boy,好,Show boy。没有问题。那so boy的话,是不是我们经过这番处理过后,大家有没有发现我们这个first一直没动啊?这就是first不动的根本原因,你first动的话,麻烦了你到现在也不知道,从而便利了说first为什么不动?
20:00
好,那这个first没有动,那现在我们就比较简单了,各位同学,那因为好我们还是老规矩啊,先做一个判断,如果这个first.next。如果它等于空,说明目前是个空链表,是不是就不玩了?因为你你上来过后,你没有做处理嘛,没有做处理,所以说我们写一个大话就说链表。啊,这个,呃,这个链表为空。就是没有小孩,这样写吧,没有任何小孩,没有任何小孩,那就没法显示了,直接return。OK,那如果否则的话呢,下面我们就来开始跑跑,一样first不能动,因为first不能动,你还得用一个辅助指针来做,是不是大家一定要注意first指针不要轻易的动啊,还是因为first不动不能动?我们还是要借助一个,还是借助。啊,借助。一个辅助指针来完成便利,辅助指针便利辅助借助一个辅助指针完成便利。
21:04
好,这个呢,也很简单,我们也不叫别的名,就叫这个current就完了,好吧,简单一点,我们就写一个。Current boy,老子应该付一个first。大家看到,因为这个first它是我们这个类的一个属性,因此呢。因此你这边处理完了后,这个first自然也就是最新的这个first了,那现在老规矩我循环。OK,那Y循环这个地方,它退出这个循环的条件是什么呢?是不是这个current boy.next等于first就代表遍历完毕了呀?是不是,所以说我们上来过后可以这样来处理啊,我们看看可以这样写,先把这个c boy信息说出来。说来啊,就是小孩小孩的信息。
22:02
我们小孩小孩的编号吧,咱们直接把这个编号打出来就行了D。一个F。好,这些在Java里面都是一样的啊,写法都是一样的,那当前这个编号。是current boy。点no。是吧,是这个吧,然后我们这儿显示的是为了好看呢,我们仍然是来一个换行。那显示完了过后是不是我就应该判断一下。我判断什么呀?同学们,是我判断,如果current boy next,它等于了我们的这个first。是不是我就可以break了呀?大家看是不是就可以break了,否则我是不是让这个currentbo继续往下移动移位,因为我要变利完毕嘛,对吧,后移继续移动啊,就是看boy后移继续后移,只要他没到那个退出条件就后移。
23:00
OK,那这个时候呢,我们要用一个break able把它包起来,同样这边我们需要一个包import u.control.break。好,注意听,那现在呢,我们这边有了,我们整个把它包起来,Break able。好的。把它整个包起来。好,这就这就这就OK了。这就OK,而且编辑完了功能,这个first仍然没有动。没动,好,同学们,我们现在来测试一下,看看这个代码有没有问题。大家看有没有什么问题啊,没有问题我就测了一下啊,我测一下来玩一把啊,首先呢,我们创建一个这个boy game,那这个比较简单,我就来创建一个叫661个boy。All boy game,又一个boy game,然后呢,VR。Boy game,好,然后我们把这个初始化一下,Boy game,点爱的boy我加七个进去。
24:04
我加七个进去,加进去过后我们便利一把。啊,Show一下不完,那这个时候只能看到编号,那理论上就应该是,呃,在没有做任何处理的时候,就应该是1234567。啊,在没有做任何处理的时候,就应该是1234567运行。好,我们看一下这个代码有问题没有,好我们看一看。好,我们可以看到没有任何问题,1234567正确的。没有认为,也就是说此时此刻我们这个形成的,那我们现在回头看这个地方,如果我我发现这个boy这没有用,那现在呢,我们如果这样处理的话,我们直接写个空看行不行。大家觉得这样行不行啊,我们执行一下先。运行。运行其实也可以,对不对,也可以,因为什么这个也可以呢?是因为我们在这第一个小孩,其实是让这个first指向一个实实在在的boy,也可以也可以啊,这两种方法都行,就是我这第一种方法呢。
25:07
就是初先初始化一个boy,就相当于说没有用,但是暂时初始化,如果说同学们直接附一个空也可以,如果附一个空呢,有一个不好的地方,就是我们在判断的时候,这样判断就不好判断了,所以说我还是先保留这个啊,保留这个,因为我判断的时候是看first.next如果你上来过后不小心的话,你如果这去加的时候,你直接判断这个next,这可能就直接给你报报错了,因为first本身是空,在next就直接报错了,明白这意思吧,所以说我这呢还保留这个用法啊,无所谓的这个好,嗯,第一个关于这一个约瑟夫问题的。第一个问题就是形成这个小孩的一个圈和显电力,这个就讲完了,我们先截取一段。
我来说两句