00:00
各位同学,我们来完成一下约瑟夫问题的代码实现。那么根据刚才的分析呢,我们是需要创建一个单向的环形链表,没问题吧?好,那么现在呢,我们这样做,我们把这个约社会问题的实践分成两个部分。第一个部分呢,我们把这一个环形链表创建起来,并且呢,能够显示这个环形链表,好吧,好,那现在呢,我们来先来分析一把,呃,这个功能,呃,假如我们现在呢,要去构建一个环形链表。构建一个环形链表,好的,那第一个节点,第一个节点创建起来过后呢,我们有这样一个提示啊,先创建一个节点,让一个first指针,比如说我这里有一个first指针,先指向它。First,这是我的第一个,第一个。
01:03
节点,第一个节点OK,那当我创建第二个节点的时候,我怎么做呢?波怎么做呢?第一个节点创建的时候,同学们看啊。虽然它是一个节点。虽然它是一个节点,但是呢,我们也让这个节点,我们也让这个节点形成一个环形。大家明白我的意思吧,就说先让这第一个节点形成一个环状。就自己指向自己。同时让first指针指向它。那么为了考虑到后面有一个节点,再把它加进去,我们怎么办呢?假如我又来第二个节点。我们要把它加到这个环形的列表里面去,我怎么做呢?同学们,我会再去设置一个节点,叫做current。Current boy,比如说我,你叫做CU boy。
02:03
这么一个辅助指针。那这个辅助指针有什么用呢?好,当我把第二个节点创建好以后。我先让这个,因为first不能动嘛。对不对,First,所以说我让这个current指针的下一个下一个next先指用它,也就是说先让。同学们看清楚啊,我们先让这个线。指向他。能理解我的意思吧,然后让这个current干什么呢?让当我们把这个current指向boy过后,我们再让这个这个新的节点。这个不是你创建的新的节点吗?比如这个节点我们用一个变量来表示,比如叫boy。没问题吧?Boy,然后我们让这个boy.next再执行first。也就是说,我们让这个节点在此向。
03:02
第一个节点指完了以后呢,我们把这个current。Cover这个节点往后面挪一下。大家看我在说什么吧,First不能动,因为first他是头节点,他是我们第一个小孩。好,当我们在创建一个小孩,你看我怎么做,假如再来一个三号小孩。好,三号小孩创建好以后呢,肯定会有一个变量。对吧。会有一个boy这个变量指向他,假设这是第三个小孩,第三个小孩完了过后呢,我们又让这个cover boy的点next指向他。那也就是说先把这条线连起来。那么一旦这条线连起来,这条线是不是就自然的就没有了,因为你这个next呢,指向只能指向一个地方,不当这个next的改变过后,这条线自然就没有了,然后现在形成这样,形成这样以后呢,我们怎么办,让这个boy。
04:01
点再指向这个first。大家明白我在说什么吧,因为这first没动嘛,所以说它是可以再指向这个first,然后我们再把这个current往后面挪一下,以此类推,你看这样子经过一个操作,是不是就形成了一个单向的环形链表。而且呢,First的指针是指向第一个小孩的。明白我在说什么吧。哦,大大体应该明白什么意思吧。好,那也就是说我们刚才分析的这个思路就已经出来了,干什么呢?就是构建构建一个单向,哎,单向的环形环形链表的思路。是怎样子呢?第一步第一步对,先创建第一个对吧,第一个这个节点。好,但这个是小孩节点,然后让什么呢?让这个first指向指向该节点。
05:03
该节点。对不对,并并干什么呢?并形成环状。并形成一个环形没问题吧,好,后面当我们每加一个,当我们每加一个新的节点,我们怎么构建呢?后边后边当我们每创建一个新的节点,就将就把该节点怎么样加入到。环已有的就是前面已经是一个环状了嘛,但是这个环状只有一个是吧,加入到前已有的,已有的这个环形环形链表中。啊环这样写啊,环形链表中即可。怎怎么样怎么样加进去呢,是不是刚才老师已经分析过了。
06:01
没问题吧?同学们好,这是我的构建环形链表的书,待会代码实现。紧接着呢,我们再说,呃,便利便利这个环形链表。变利环形变利其实特别的简单,其实特别简单,你只需要做一个辅助指针,让他先想first,然后呢,让这个辅助指针不停的来便利就可以了,明白我在说什么吗?这个就比较简单,就是先先让,先让一个辅助指针。辅助指针或者辅助变量。变量。变量指向哪里呢?诶指向这个first。这个节点是不是,呃,指向完了过后,下面是不是一个while循环就可以了,然后然后。然后遍历,呃,通过一个while循环遍历,遍历该单项啊,该环形链表链表,诶链表即可,那么问题来了,你在做这个环形链表。
07:10
呃,这假如这个辅助指针,呃,辅助指针我们叫做假如叫做current啊current boy,我就我就假如叫这个名字,那么他在进行这个便利的时候,什么时候代表把这个环形的链表遍历,遍历完毕了呢?请同学们思考这个问题。请同学们思考这个问题,你们你们想一想,什么情况下就代表整个这个环形链表病理结束了?变结束是不是是这个current boy的next?因为你这个next这个current肯定是肯定是这样子的嘛,就是相当于你待会呢,有一个这个指针叫current,它先指针它它先把它打出来,打出来过后往下挪一下,然后再往下挪一下再打是不是那什么时候。
08:00
这个。表示环形链表遍历结束呢?是不是应该是current的点next,它等于了什么first?就结束。是不是这个道理啊,哎,就结束了,就是便利便利完毕。好,那现在呢,我们把单项的环形链表的这个创建,以及它的便利就讲完了,那把这个讲完以后,同学们下一步是不是我们就可以把这个来进行一个简单的实现。来吧,那么我们来开始玩一把啊,刚才我的思路已经分析清楚了吧。一个是构建。对不对。一个是便利,没毛病吧,那同学们打开我们的这个代码,我们来进行一个快速的演示啊,快速的演示,好的,打开我们这个代码,来给大家跑一把跑一把。好,同学们,那现在呢,因为现在讲的还是链表,因此呢,我在这儿新建一个文件,好,我把这个。
09:04
这些不要的,先都把它关闭啊关闭,那现在呢,我们新建一个类。啊,新建一个class文件,这个名字呢,我们就叫约瑟夫,没问没问题吧,约瑟夫这个别写错了啊约瑟啊夫夫应该是U吧,啊约瑟夫啊约瑟夫,看写没写错,约瑟。还有个P,应该是还有个P对吧,因为我们这个约瑟夫呢,它这个英文单词有个P,把它加进去吧,约瑟夫问题把这个主方法呢,咱们将其勾上。没有毛病吧,跟着老师思路啊。那刚才老师已经把这个思路已经分析完毕了,那么首先呢,你是不是先应该定一个这样的节点呢?这个节点是不是我们小孩节点,这个就是现在同学们看到的这个老师标量的这个玩意,是不是一个节点,这个节点呢,我们就给他创建一个叫boy的一个节点啊,比如说先定创建一个boy。
10:05
Boy类表示一个什么呢?节点没毛病吧,好class class,那就boy了,那就boy,那boy呢,我们这里面新建几个属性,一个是他的编号,这个是他的编号后面有用啊,编号后面有用,然后呢,我们是不是小孩名字我们就不要了,名字我们主要是看编号嘛,就boy next这个呢是指向指向。指向下。下一个小孩,下一个节点。啊,下一个节点,然后呢,默认默认是不是空。没问题吧,好,然后呢,我们写一个构造方法,Public。Boy对不对,然后呢,这边我们构造的时候呢,让他传一个编号过来,Z4.no。对,this.no。等于它传进来的这个no就搞定,然后呢,这里面几个属性,因为都是私有的,所以说我把他的这个晒的方法和盖的方法都给它生成。
11:12
没问题吧,比如说boy我们就创建起来了,创建好以后呢,同学们,现在我们就来创建这个环形的。环形的链表哈,环形列表,那么我们创建。创建一个什么呢,环形的。啊,环形的单向啊,单向链表。对不对,叫环形的吗?环形的链表好,那现在呢,我就写一个名,写一个类了,Class class circle CR c环形的。呃,Single单向的什么呀,领的什么呀,List。List没,没问题吧,同学们看这个能看懂吗?Circle single link list没问题,好,那有了这样一个类,有了这样一类,首先我们要去创建的时候,那第一个就是首先开篇名义你第一个节点是不是应该先把它做起来,只是第一个节点呢?现在呃,不知道是几号,所以说我先做这样一个动作干什么呢?我先创建一个叫做first节点。
12:23
啊,但是目前呢,目前先不要赋值,目前给一个默认值就行了啊啊。就是先创建一个当前,当前还没有,指当前没有编号编号的。OK,那现在老师就开始来写一个,我们起个名字叫private什么玩意boy first,因为第一个小孩必须得有,那第一个小孩他的编号是什么呢?我不知道,我就先随便写一个,比如说负零负一啊,当然后面我要修改他。后面我会修改它,好吧,当然我也可以可以先制成空,后面再给他创建也是可以的,也是可以的,我先这样做一下啊好,这个做完了以后呢,我们就来加入小孩添加。
13:06
添加小孩的节点。构建成,构建成一个环形链表,诶,环形的链表。没毛病吧,那现在从老师开始写这个代码啊,VOI。Boy。啊,加加一个小孩,那你给我加一个小孩,你应该怎么加呢?这样子你直接告诉我你要加多少个小孩就可以了,就说这个numbers代表你整个这个环形链表一共有几个小孩。说白了,就是几个节点。几个节点好,那现在呢,我们先做一个,因为这个numbers呢,它有些。做个验证,你不能给我传一个负一,你也不能传一个小于小于小于这个零的数,对不对?好,所以说我对这个numbers呢,做一个做。做一个数据校验啊,简单的数据校验没问题吧,同学们跟着我的思路啊校验。
14:06
好,那现在呢,我们认为有这么几个情况,如果如果numbers它小于一,我们不允许,对吧,你至少得有一个嘛。啊,至少得好,那现在呢,我们这样子做,如果这个地方它不满足这个,呃,它满它是小于一的情况,那么我们就认为这个数据是不正确的,啊,Numbers的值不正确。对吧,不正确。因为我们至少需要它大于大于一啊,大于一才可以。啊,大于一才可以好,他如果numbers不正确呢,我们就直接return回去就完事了,就不做了这个事情好,现在呢,我们就可以使用一个循环for循环。For循环来创建我们的。环形链表环形链表。
15:01
对吧。环形链表好,呃,那现在呢,我们来看一下这个情况。那我现在呢,用个for循环,For循环。For int I等于1I小于等于numbers。对不对,爱家家。大家讲就说我现在呢,要把这几个就是你给我,比如你传个九个小孩,那么编号我们就从12345开始。好,从一一号开始把这个环形链表构建起来,刚才老师已经分析过了。我刚才做了一个分析,就是先把第一个小孩做好,然后呢,后面每加一个新的节点加进去就可以了,好,那就这个代码呢,老师就不啰嗦,直接写写代码了啊啊,那我就写根据编号,根据编号创建小孩节点。能看到我的思路吧,创建小孩节点好,所以说我先创创建小孩节点,那创建小孩节点的时候,同学们还记不记得,刚才我分析我们需要一个辅助变量叫cover boy来构建这个环形命令表,所以说我先把这个cover boy呢先创建起来,在这啊,我们先创建一个这样的东西叫boy。
16:16
跟上我的思路啊,跟上我的思路boy,然后呢,就叫CU boy,等于一个空,这个是干什么呢?这个是一个辅助指针,或者叫辅助变量,帮助我们帮助构建环形链表。刚才我是不是已经分析出来有这个card boy了?是不是?是不是?所以说首先如果numbers小于零小于一的话,我们就不做了,比如你创建一个零零小于零小于一成立。对吧,那么如果你是一呢,一个,我们也可以玩一把一,他不小于一,那么也可以啊,就是假设你只有一个小孩,我们数完了过后不就。还有一个嘛,就说其实至少你要有一个对吧,其实这个地方我们可以,呃,可以在座的更好一点,就说至少有两个小孩的话呢,你就这样子写。
17:09
比如说呃,如果你这个穿个一,一个小孩一小于二,我们也不玩,那至少要两个。对吧,也可以就看你怎么去确定,假设我们是number小于一的话呢,就认为。至少要一个是不是。好,那现在这个根据我们编号,我们先创建一个小孩吧,那就boy。Boy等于六一个boy,然后把这个I放进去。是不是这样子,这句话就代表我们创建了一个节点?那么这个节点刚才是怎么加进去的,是不是老师分析过了,那现在我们就开始把它加进去,那么加的时候呢,要考虑一个小孩比较特别,是不是刚才我讲过第一个情况要单独的考虑一下。后面就。就用一个循环就搞搞定了,是这意思吧,好,现在呢,我们先把第一个小孩搞定哦,如果如果是。
18:03
最近啊,如果是第一个小孩。那么我们怎么做呢?这样写,因为它比较特别,第一个小孩要形成一个环状,它是第一个环嘛,是不是好,如果I等于一。说明我是构建第一个小孩,如果是第一个小孩的话呢,就让这个first等于谁呢?等于这个boy。叫first,所以说这个地方其实呢,你这如果直接写个空也是可以的。对不对,因为相当于我的这个first指向这个boy了。这也是可以的,第一个小孩就构建成功,然后下一步呢,我们的这个first.set next。构成环状,它的下一个应该是什么,First?是不是这句话就构成一个环状了?构构成一个环。只是这个环里面呢,只有一个小孩。但是不要忘了一件事情,因为后面我们这个current是需要帮我们来构建环形链表的,因此你要有这样一个动作,让他指向first。
19:10
是不是刚才我已经分析过了,这个是干什么呢?让current boy指向指向第一个小孩,那为什么我要让这个康只用第一个小孩呢?因为后面这个这个first我们先不能动。对吧?所以说我以后只能靠这个current来帮助我们构建这个环状,因此呢,我让它指向第一个小孩,即指向first。那么第一个小孩做完了以后,后面的情况应该怎么做呢?后面只跟我们的current boy。有关系了,让他来构建缓冲,因此呢,我们来个as。就说如果是,呃,第二个小孩开始怎么做呢?大家看刚才是不是老师老师说的说的第一个动作,先让这个新建的小孩先指向。
20:01
不是先,先让新的小孩指向这个。呃,我们看看是啊,是让这个current先。像这样写的啊。我们新创建一个节点应该怎么做呢?大家想一想,是不是先让这个,比如说我们新加一个节点,假设又来一个新节点,你看我们怎么加进去的啊,假如这是四号节点,我们再回忆一下现在current呢?呃,是在这个位置,因为它始终是只在最后的。好,我们怎么做的呢?我们是先让这个current next先跟他连起来,还记得这句话吧。是不是先让它指向它。是不是这样子的,当它指向它的话,这条线是不是就断掉了。没问题吧,然后我们这因为你创建这个节点过后,它其实有一个变量是boy指向它的是吧,然后我们再让boy的点next指向这个first。是不是刚才也是这样分析的,然后呢,这个current怎么办?
21:03
往前挪一下。是不是三部曲?好,现在我就把刚才三个动作做一下,第一个动作先让这个current boy。点一下next。谁呀,First?啊,我们先不是啊,这个写错了啊,应该是先指向这个新的boy,是不是这句话。就是老师写的这句话,是不是就先把这条线构建起来了?没,没有问题吧,然后紧接着呢,我再写下一句话,什么呢?就是我们的boy.set next,谁呀,First。同学们,这这一句话,第34行这句话是不是把这条线构建起来了?但是你构建完了之后,你是不是得把current往前面挪一下,因为你要准备下面可能还有节点是不是,所以说呢,下面还有一个动作,不要忘了让这个current boy在指向boy。
22:08
是不是有点绕啊,就3333条动作,这就是第三十五行,这句话的作用是什么呢?是呃,是你,你原先是在这吗?是吧,然后你做完了以后就到这来了。那也就是说,如果下面再来一个节点,是不是又如法炮制了?因此通过这样一个循环操作以后呢,我们这一个环状就构建起来了。没问题吧,好,现在我们紧接着再写一个方法,干什么呢?我们能够便利出当前所有的学,所有的节点便利。便利当前这当前的这个环形链表。没有问题吧?好,那现在我写一个方法,刚才是不是便利当前环形链表我们已然做了一些思路分析,是不是也要用一个辅助指针帮助我们来做,就说上来过后呢,先让这个current boy指向最前面,然后一个个的走,走,诶,走第一个打印,再打第二个,再打第三个,再打第四个,最后我们看这个cardboy的点next是不是等于first就结束了。
23:19
没,没有问题吧,同学们,好的,那现在呢,老师把这个代码快速的写一遍,Public。VO,哦,我们就叫show boy吧,Boy。好,上来呢,首先我们先判断是不是一个空的链表啊,呃,先判断判断是否链表是否为空,链表是否为空,如果为空我们就不打了,明白这意思吧,就不用浪费感情了,那如果是first。点他get它的next。啊,或者这样说,First目前等于空。这样写啊,因为我我们原先这个first如果一个都没构建起来,是不是它是个空的呀。
24:02
所以说我这样写,如果我们的first,它等于no。对于弄。那说明什么呀?说明是个空的,既然是一个空的,那就没有什么可说的了,直接说链表为空。念表为空,就或者叫没有,没有任何小孩退出了。那就直接return。是不是,那如果说有怎么办呢?有好,我们做一个辅助指针,因为first注意听啊,因为first这个不能动,它是不是不能动啊,不能动,因为后面还要用到它呢,因此我们仍然。仍然使用一个什么呢?辅助指针,辅助指针。完成便利。能能理解我的意思吧,好,还是用这个刚才我们那个指针吧,Boy。好,我们写一个啊,Boyn Co boy。
25:00
然后呢,我们让他直接先使用first。有问题吧?有问题没有,没有吧,然后呢,我们就Y循环了,Y循环还是老规矩,根据刚才的分析呢,我们来做一下,做一下先把这个小孩的编号打出来。写一个啊,我们格式化一把,就稍微有一点点麻烦啊,就是小孩的编号先输出吧。百分号D打个空格。写个N把它的编号打出来,那么你当前这个编号是不是就是用current boy来获取就可以了。因为我们。这几个属性都是私有的了。所以说我给的是。几个方法来获取的,拿到,拿到以后同学们。是不是你要判断。到有没有到最后,因为到最后我们就要退出了,因此呢,你判断一下是否已经到最后了,怎么判断呢?就是current.boy得到它的这个next,如果等于first,表示什么意思?
26:01
啊,如果它等于first了,说明已经遍历完毕了。那就说明什么呢?说明遍历完毕,说明你当前这个cover呢已经最后了,而且你在前面已经输出了是吧,说明已经遍历完毕,完毕怎么办?Break。Break,那如果说没有满足这个条件,你怎么办呢?是不是让这个current往后一下,那刚才我的说了吧,Current boy等于current boy.next。Next,哦,叫get next啊get next,这个相当于是让这个car boy后移。A boy后裔。后羿,那这样子他不就便利起来吗?这句话的动作其实就是刚才老师演示的这个效果,就是你原先在这儿。对吧,诶我下一个再打印,再下一个再打印,然后打印完了过后,我再判断你这个current next是不是等于first,如果等于退出。
27:03
如果等于就退出,好,同学们,那关于这这个构建和显示我们就写完了,来朋友们,我们先测试一把。测试一把看看。看看看看这个构建这个圈,就是构建这个环形环形链表。和这个显便利是否正确?和便利和便利啊,便利是否OK,那么同学们那首先呢,我们先六。对不对,我们先溜一个circle。List。没问题吧,同学们,一个环形的单向链表。好,这个有有有有点长啊,这个名称有点长,无所谓,然后呢,我们先把这个小孩创建起来,爱的一个值。那么现在我们构建几个小孩呢?为了跟我们前面讲这个案例匹合,呃,配合我们就创建五个小孩。
28:04
五个节点的小孩啊,就是呃,加入加入五个小孩节点。小孩能跟到我的思路吗?好,然后我们再显示一把。看看对不对呀,点瘦。如果这个地方显示没有问题,那么它的顺序是12345,好同学们,我运行一把字。好,当我运行,我们看到小孩12345,没没毛病吧,假如我们这把这个词改了,比如说我有50个小孩,或者或者25个小孩,你看他仍然是正确的,你看。是不是编号是。123456789,到25就给你结束了。好,我还把它改回去,好,同学们根据前面这个讲解呢,我们就已经把我们这个约瑟夫问题的。它这个圈的构建和便利写完了,那么我们先把这一部分整理一下,待会儿再写这个怎么去产生一个出对的编号序列,明白。
29:04
好,我们先那这样子啊,待会这个代码呢,我们统统一的整理吧,统一的整理,呃,这个思路也在这,好,关于构建和便利,我们先为同学们讲到这里。
我来说两句