361_尚硅谷_Go核心编程_数据结构和算法-约瑟夫问题解决(1).avi原创

好，同学们，我们用代码将其实现。我们走下代码。走下代码。呃，那么有了这个代码，咱们应该怎么走呢？打开我们Vs code，我们就在这个地方来解决，好新建一个文件夹啊，我们这个文件夹名字我们就叫这个啊，约瑟夫。就用这个命名吧，就用这个命名。好，我们新建一个文件夹。好，约瑟夫，没问题，大新现在呢，我们直接在里面写一个主文件。对，Mean mean.go走起来，然后我们开始走，包包，Package，主包，然后import OK。好，肯定有个输出对不对，好，现在我们写出它的主函数。啊。主函数。好，开始。呃，那么怎么完成这个东西呢？首先我个人是这样想的啊，我们先写一个函数来把这个环形的这个单向链表形成，所以说我的第一个思路，各位同学听听我说第一个思路，我们先编写一个函数。

编写一个函数干什么呢？形成形成啊，或者叫构成吧，构成这个单向单向的环形链表。环环形链表，嗯，那这个地方咱们怎么来做呢？啊，怎么来做呢，就写这个函数，比如说叫function ADD ADD的boy。加小孩进去。那现在想一想，因为我们这个示意图呢，每一个小圆圈代表的是一个小孩，那既然代表一个小孩呢，我们应该用一个结构体来描述这个小孩，所以说我们要搞一个什么东西呢？我们先来创建一个小孩的这么一个结构体，好，我来写个啊小孩的小孩的结构体没问题，那就是type boy，然后呢，Structure。

那它有什么属性呢？呃，我觉得有至少应该有它的一个编号，同时呢，应该有他的名字，名字我就不写了啊，名字我就不写了，我就直接写个编号啊，比如说no吧，T这个呢，我们表示编号。因为我们主要是看编号啊，它是怎么出出队列的一个出去出圈的一个顺序啊，第二个呢，它应该有一个指向下一个小孩的一个指针，对不对，好有个指针，那这样就就好办了，那么就写next share boy，那么我写一下就是指向指向下。下一个小孩的指针，OK？好，那现在呢，我们来构建这个小孩，那构建多少个小孩呢？做最好做一个变量。最好做为变量，比如说我想构建20个小孩，构建十个小孩没问题，这个呢，你给他一个变量给他传进去，OK，那我就写个number，明白in，那最后整个这个爱的boy过后呢，给我返回一个这个环形链表的投资人。

对，就是第一个小孩的指针，所以说呢，我这里写一个这样的东西，大家看能不能理解boy。好，我先把这个意思说清楚啊，就是这个n number表示什么意思，这个表示表示小孩的个数，小孩的个数。第二个呢，这个地方就不返回的是个什么呢？让它返回返回啊。让它返回该该什么呢？环形的环形的链表的这个第一个小孩的，第一个小孩的这个指针。因为你最后你没如果没有这个第一个小孩指示，你后面的代码都不好走，因为你你想一想这个道理，因为待会儿呢，你要从第几个人开始走，数几下，这都需要从第一个小孩开始来定位。

如果你没有投，没有这个第一个小孩的指针，那你后面代码都没法写，因此呢，我们先把这个做出来啊，那怎么写呢？同学们，首先我们这样做。我们先来第一个小孩，如果哦，先做一个判断，判断如果这个number，他什么呢？他如果连一都不是，如果它小于一。小于一，说明你这个值我没有办法给你构建对吧，就说你如果如果你连你连一都不到，那么我我我这个就没法给你构建这个环形链表，因为你一个人都没有嘛，那可以这样写啊，可以这样写，就是直接返回一个空子的也行。啊，就这样子做就行了，我们先把先创建第一个小孩。来构建第一个小孩啊，我写这样子，First。走，艾特，艾特什么呢？Boy？空的。啥都没有，这是一个空子，空的节点，目前是个空节点啊，空节点。

好，如果你的number小于一。如果你这个number小于一，那么我们就认为你这个给这个没法构建小孩，就是你给的这个值太少了啊，比如说这样写的啊，这个number number应该。应该。呃，Number的值，Number的值不对啊，Number的值不对啊，不对。不对是吧，不对。好，如果不对的话呢，我就这就不走了，相当于把这个first直接返回就完事了啊，First直接返回就完事了，好，如果它啊不小于一，那就至少等于一嘛，啊一不小于一对不对，那这样子的话呢，我们就可以开始构建，那就开始循环的构建，循环的啊，循环的构建这个这个这个链表啊环形链表。环形列表链表啊，各位同学。

那么怎么来构建这个东西呢？用一个for循环，用一个for循环来开始走I。等于，比如说我先给它等于一构建多少个呢？I小于等于number个I小于等于number个I加加。好，我要开始这么构建，那这里面有一个问题哈，就说呃，因为第一个第一个小孩呢，比较比较特殊，所以说呢，我这里分成两个逻辑来处理啊，当然每个同学可能处理方案不一样，我是这样处理的。我先判断。嗯，因为我说因为第一个小孩，第一个小孩比较特殊，比较特殊，我专门的特殊一下啊这样写，如果I等于一，这说明是第一个小孩。啊，第一个构建第一个小孩，这是第一个小孩，那第一个小孩我怎么处理呢？我这样处理。我先把这个小孩创建起来。我先创建这个小孩，创建小孩我怎么写啊，同学们看boy。

Boy轴等于I的福，I的福，然后呢，Boy。它的这个number，它这个number我们就暂时以这个I作为它的循环构成吗。如果你一个一个的让我从控制台输太累了，所以我就直接用这个循环的方式给他付一个I就可以了。写完，那么如果我给他了一个I，它的这个like的值默认就是near，这个可以保留near这个值，就是说你不给它赋值，它默认值是一个near，这点大家必须清楚啊，它的默认值是near，这点我们以前讲过，默认值是默认值是near，好，我们就用这个特点，那么有了这个小孩过后，又他又是第一个，怎么办呢？就先让first指针。First指针指向它。就指向这个boy。第一句话。就指向他，可是你把第一个小孩指完了过后，这个投资人就不能动了，因为你一旦动了，后面就找不到这个第一个小孩的位置，因此这个时候大家应该分析出来，应该有一个辅助指针。

应该有一个辅助针来帮助它形成这个循环链表，我们以前讲过这个东西啊，同学们跟着老师动起来啊，这地方有有些地方要分析出来，就是我们这里分析出有个东西，分析什么呢？分析构成。构成循环链表。循环链表。列表需要需要一个辅助指针。辅助指针，这个指针呢，你可以理解成是一个帮忙的啊，你也可以认为它是个跑龙套的，无所谓，他是帮忙的啊，帮忙的，那么他为什么要帮忙呢？因为。First指针一旦给了它就不能动，如果first不能动，那你这个环形列表肯定是动不起来的，没没法构建成功，所以说我们要需要一个辅助指针，这个辅助指针呢，我们怎么做呢？好，这个辅助指针我们先这样子来给它创建一个辅助指针。

这样做啊，来第一个，当first等于一的时候，First等于boy，那么头指针就指向这个boy了，我们现在需要一个辅助指针，辅助指针在哪里去创建一个呢？辅助指针在哪里创建一个呢？呃，First针在这儿，那么辅助指针我在上面也创建一个啊，创建一个，那我写个current。Current这个小孩，当前这个小孩啊，那么我也让他指向一个一个这样的类型。啊，它是它目前也是个空的啊，它目前也是个空节点。好，那我怎么做呢？大家看来了，过后我让他注意听啊，我让他也指向这个boy。我让他也指向这个boy，这个没毛病，就相当于说第一个的时候，First指向这个小孩，Current也指向这个小孩，怎么形成这个循环列表呢，Current。

boy.next指向first。这句话的作用，这句话的作用请大家理解一下啊，这句话的作用是什么意思呢？就是让它形成一个循环的，因为有可能人家就是构成一个小孩。对不对，所以这样子呢，它就构成了一个循环，你看大家想一想怎么回事啊，First指称指向go boy，然后呢，Current也指向这个boy，然后呢，current.next进行first，它就相当于是这样一个意思，我简单的画一个图，假设只有一个小孩。假设我们只有一个小孩啊。好，第一个小孩，你重新起过来了。他的编号呢，是一。一过后呢，你做了一些什么动作呢？诶，你先让first指向boy，这个没有毛病，那也就是说你的第一个first指针指向了他。这是可以的。对，这个是可以的，然后呢，你又让谁呢？你又让这个current boy也指向这个，呃，Current boy也向这个小孩，相对说，两个指针都同时指向了第一个小孩。

紧接着你又做了一件什么事情呢？诶，你让这个，你让这个car next只用first，那相当于说它这里面有个next。它下面有个next指针，这个next指针怎么办呢？它指向自己杆。啊纸箱它相对于说这样形成一个环形的。好这样子相当于这个这这个意思啊。像这个意思，相当于说自己指向自己，形成一个环形的好，这是第一个小孩就这样去处理了，那么后面的小孩怎么办呢？后面的小孩就是else。如果是，呃，第一个小孩，以后的小孩我们就应该这样做了，First别动它了，这个是不能动了啊，这个不要动了，不要动，不能动，因为你动了过后，投资人就找不到了，那下面全靠谁来帮忙，全靠他帮忙了，那现在如果是第二个小孩，我就这么走了，Current。

先指向这个。呃，就说current.next。Current点，呃，这个boy next等于。Boy，大家想这句话什么意思？这句话就相当于说，有了一个小孩过来了，有个新的小孩，第二个小孩来了啊，假设我们有第二个小孩来了。好，这个指针你先理解成是一个current啊，这个理解理解成是current好来了一个二号指二号小孩，看你怎么玩的呢。你先让这个current。The next指向这个小号，那向左，原先这个线就没有了，它指向了它。它指向了它，显然这个时候就不是循环列表，然后你紧接着应该怎么做呢，让这个往后面也挪一下。啊，让这个挪下，那也就是说我们现在紧接着做这样一个动作，就current这个boy。

干什么呢？等于不啊，等于不坏，这句话就相当于是老师刚才的这个动作，他说然后呢，你让这个再给它形成一个环形电表，说让它下面不是有个next吗？好，然后呢，你让它重重新指向它。这就形成一个环形链表。啊，形成一个环形列表，那下面我们还少一句话，还少一句话，少句什么话呢？就是current boy.next等于first，你看这个first就非常重要，不要去动它，因为你first跑的话，那这个环形电表就呃形成不了了，啊first好这样子，同样这样的作用是构成环形链表。关系列表。OK。好，通过这样一个处理过后呢，同学们，我们可以想象啊，就是我们就可以构建一个环形的单向列表啊，最后把这个返回去，经过你的一番处理过后，你不要忘了一件事情，Return啊，Return什么呢？这个first。

好，这个投资人就有了。好，那么这样子呢，就把这一个构成了，我们紧接着做第二步，把这个环形链表小孩显示出来。好，我们来显示显示这个单向的啊，单向的环形环形链表。OK，那么显示它其实就是便利，说白了就是便利，这个便利就简单了，这个便利特简单啊，这个就是便利。便利，那便利的时候呢，你看老师怎么写啊，我就写范啊范。那么我们比如说取个名字就叫受boy，好吧，我就简单的取个名字受boy，就显示小孩，那么同学们可以想象到啊，你如果要去显示这一堆小孩，你首先得知道这个first指针，所以说你必须把这个first指针给我，我才能够才能去把这个呃，环形列表显示出来，这个是first啊，那相当于说这个这个是first，大家都清楚，好，现在呢，我需要你给我一个first指针。

First boy，好，然后呢，没有返回值，因为你是便利嘛。好，那现在我们开始来遍历，那遍历的时候同学们大家也注意啊，遍历的时候呢，我们也不要去动这个first指针啊，不要去动它，一般不去动这个first指针，好，我们来做一个动作啊，就是啊先还是一样啊，先定义或者创建，创建一个指针，指针帮助便利帮助便利。便利啊便利，OK，帮助便利。那么帮助便利的话呢，我们就来这样子来处理就行了，来一个跑龙套的，我们也叫current吧，BY等于first先给他。

先给他好，先给他，过后呢，我们用他人的帮助，我们便利帮助便利，其实大家应该可以想象假设说说韩老师，假设我们就用这个first指针去编利，行不行呢？其实也可以。其实也可以，因为你这这边的改变也不会影响到这个指主主主子针的这个改变对不对，好我们这样就做了啊开始这样做，那这地方我们就用来帮助便利的一个指针写完了first，然后开始做for循环。For循环好，首先还是老规矩啊，我们这样子对这个空的，对这种空的，这这种环形列表呢，咱们单独处理一下。处理一下，处理一下，如果环形链表，环形链表为空的情况。这个它比较特别啊，那我就这样写了啊，同学们想一想，什么时候为空呢？显然是first，如果first.next它等于一个near，说明这个是个空链表，就啥都没有啊，一个小孩都没有，那这个时候呢，就不要变利了，直接给他打一句话说。

这个是空的链表，无法遍历，就返回了，就写一个链表为空，对吧，这链表链表为空，没有小孩，没有小孩就退出了。就直接退出。对就直接退出，那就不给他啰嗦了啊，直接就完事了。那如果说嗯不为空，那下面呢，就接着走，开始写啊，那怎么走呢？说明它这至少有一个，只要这个地方没有进去，那说明至少有一个小孩，对不对，至少有一个小孩，那么我们就用那个do well的形式来处理它，因为你这段过了，说明至少有一个小孩啊，这说明至少有一个小孩。啊，说明至少有一个小孩，是，既然有一个小孩，那么我们就直接先输出小孩的信息。

注意听看我的这个逻辑啊，Printtf，好，我就说小孩编号编号来走一个。小孩编号。然后呢，这个地方我们就这样写一个啊，那它的编号怎么取呢？非常的简单，直接用current。点它的no就可以了。啊，我们也不去换行，就让他打成一排，打成一排，但是什么时候退出呢。对，退出的条件是什么呢？要思考，你如果没有退出条件，他就他死在里面了，他一定要退出，他退出的条件是什么呢？各位朋友，它退出的条件是什么呢？好，它退出条件就是它把整个便利完了，那也就是说current.next等于first的时候，它就遍历完了。他就便利完了，所以说他这边有个条件，如果你想吧。

你想你这方式，你你现在现在说C指向这，你先把这个一输出来了，输出来过后你再判断，注意啊，我是先输出再判断的，所以说他把一输出来过后，我再下去，再把二输出再去判断，注意看这个逻辑啊，所以说我这方是很有讲究的啊，那这方应该怎么写呢？如果current boy。点next等于near。OK，这说明我们显示到最后这个小孩了，就这个环形列表里面那个最后小孩好，这个时候呢，这个地方就是推出条件，它的推出条件是他。对它推迟条件是吧，所以说我们这就可以break出去完事了。完事了，好，那现在呢，我们先把这个东西来测试一下，看看我们写的一个形成环形链表和显示环形列表到底对不对，我们来做一个小测试啊，看行不行啊，如果行的话继续走，不行我们再调试，好，那么现在呢，老师先来接收一个投指针。

好的，那现在呢，我先调用这个I boy。Bad boy。好，待会儿有代码错误们再调啊呃，我们就构建五个小孩吧，不构建多了，多了待会儿不好调，然后呢，显示一下。显示的时候这个投资人就拿到了啊，那现在呢，我们就show show boy，然后把first值填进去。好，填进去过后，我们保存了一下，我们发现代码呢，好像没有报错，呃，没有报错，但是好事，我们来执行小板，我们来执行小板打开我们的D盘。找到我们的这个src，进到我们的这个目录20里面有个约瑟夫，OK，好，我们CD，然后呢，Go一下，注意啊，这个是一个考点啊，大家不要小看这个东西，现场就让你写。这是韩老师以前这个痛苦的回忆，对不对？但是我成功的过去了，最后我没选择他，是因为工资太低了啊，工资太低我没去。

那那些公司还可以，但是没去好，当时我们写的环境比这个恶劣多了，直接用那个U，我记得是在那个so上面写的，而且就用那个VI写的，你知道吗？啊，VI写的用C写的啊，现在想起来还是挺有意思的，好找一个看看代码行不行，我们发现呢，我们发现这个代码对不对，死的哪里面，死在哪呢？大家看一下，死的问题是在这里，我们走完这个东西以后，大家看到啊，你不停的构建，你在显示的时候看到没有。你这只你这方显示完了之后，你是不是没有next一下呀，你没有next是不是它永远都是死的打一对不对，所以说这还有一个非常重要的条件，我们写应该是下一步下移一下，让我们这个current boy移动。移动到下一个，移动到下一个啊，下一个OK，那现在呢，就boy等于current boy.next对这个条件非常的重要，你看没有写的话就是一个死循环对不对？好，Clean一下走诶。

走起来，走起来，我们看效果。好，同学们看还有毛病啊，还有毛病，我们看哪里还有问题。好，它是current点哦，这个是first啊，我们看看先把first给了他。它使用它，然后呢打印。啊，等于first，对，等于first啊，退出条件我们刚才写的是first，对，把它写成first才对，刚才我们已经分析出来了，是指向投资人，但是写的时候没有写对啊，好。再来走一下，同学们走，口令一下。走，好，这次应该没毛病了，好，这次应该没毛病了，好，同学们看到现在呢，是12345全部打印出来，那么刚才的两个重要点，一个呢，就是退出的条件是current boy next指向投资者。第二个。

一定要注意，在我们进行这个处理的时候，这个current boy要下移一下，如果你不移动，就是会出现他一直在打第一个小孩，然后呢，永远不退出。好，这是我们的第一部分，就是环形链表的构建以及显示，或者叫便利这一部分先给大家讲到这里。