357_尚硅谷_Go核心编程_数据结构和算法-环形链表创建和显示.avi原创

好，同学们，那下面呢，我们就来实现一个环形链表，就是单向环形链表的一个应用，刚才我们讲了单向环形链表最经典的一一个用法呢，就是约瑟夫问题，它的一个。结构大概就这样子的，那么我们的案例呢，就围绕对它的添加。删除和显示展开。把这个讲完了以后，就说我们先走一个对单向环形链表的案例，然后我们回头再去解决约师付问题，就是丢手帕问题啊好，我们开始来完成这个这个表的案例，走，打开v code。打开Vs code，我们新建一个啊，这个这个这个这个文件夹，我们叫circle吧。Circle。环形的环形的这个single single链表。Link。好，我们先写一个文件。

叫没点go。面结构，那么我们放什么东西进去呢？假设我们放了一堆小猫啊，我还要画一个示意图，因为待会呢，我要用这个图来帮助大家理解，对我们现在呢，新建一个结构体，这个结构体呢，我们叫做猫猫结构体。比如说我们放了。第一个环形的猫啊，一堆猫，那么这个节点呢，我们就叫这样子一个节点叫tap啊，Tap type。开一个节点，这个节点里面有什么信息呢？啊是四个结构体啊四个结构体这个节点里面有什么信息呢？比如说有它的编号，呃，它的编号我们可以看到，然后这个猫猫有个编号，这个猫猫呢有个名字。同时呢，它是单向的那个呃链表，所以说它应该有一个next节点，指向下一个猫猫的节点。Cat，这点大家应该可以很清楚的知道。

好，这个就没问题，那现在呢，我们来看怎么做打开它啊，我们现在开始写了package p。主包，然后然后呢，Import肯定地方也有大量的这个，呃，引用好，然后呢，我们定义这个猫结构体，定义猫的这个结构体，结构体节点。好，那刚才我们写了啊，叫type Type Cat no。对，然后呢，它的一个no是int，这个是猫的编号。猫猫的编号。编号。好，然后呢，猫猫有个名字叫name。好，还有猫猫指向下一个节点，叫新cat。好，写完。那现在呢，我们写一个主函数，写一个主函数。好，写个主函数呢，我们先来做一个添加的操作啊，Fun叫insert一个什么呢？猫猫的节点。

好，那问题来了，你再往里面添加的时候，你需要什么东西呢？仍然你是需要一个投节点的，周老师这个环形不是没有投节点吗？对，环形确实没有头节点，但是你自己要初始化一个头节点，也就是说你刚开始的时候呢，你要想象这里面什么都没有。这里面确实什么都没有对，所以说你要开始做一个做一个这个头节点才能玩，你没有头节点，你肯定是到时间什么都干不了，只是这个头节点的维护呢，比较麻烦一点啊，所以说我们仍然要有一个头节点，这个是我们的猫。它仍然是有no的啊，当然它也有next。好，太nice，我们待会再说。然后呢，这你可以想象到仍然会有一个变量。头节点指向这个这个塔。这个头节点呢，我们要真的放猫了啊，以前前面我们学的那个头节点呢，是呃，只是一个空的头节点，但是环形链表的头节点一定要放数据。

所以说倒线这个要要做起来好，那现在呢，我们先传进去一个头节点head。或者first都行行，然后呢，Cat no。那你要你你这个头节点有了过后，你还得给我传一只新猫进来，对不对，你要传一个新的猫猫的节点cat no，好，然后呢，心仍还仍然是开着no。没问题。好，抱歉。那这个头节点的初始化在哪里做呢？显然在这个主函数里面是比较合理的。这里。在这里，我们初始化。初始化一个什么呀？头节点就是猫的头节点，环形链表的环形链表，链表的这个头节点。

好的。那么我们就先把写起来，Had。走。艾特艾特五，然后呢，Cat猫。Cat猫load。好里面不知道是什么，所以说先放这儿，因为你第一只猫呢，我也想通过这边添加进去，好现在呢，我们来创建一只新猫。创建一只一只猫。好，这个猫呢，对这个猫。自贸。自贸。好，这个猫呢，我们给它取个名叫第一只猫嘛，开的一。好，等于I的符号。Cat，然后但这些呢，你可以通过键盘输进去，说猫的名字啊什么啊，对，我这里就直接写了第一只猫。我来做测试，第一只猫，这个猫猫的名字呢，我们也把它写出来，比如说叫做啊汤姆，看汤姆猫，汤姆猫，然后呢，它的这个next默认肯定是near，所以你不用给它指第一只猫有了，那第一只猫有了过后呢，我们调用insert cat。

把这个头接连给他传进去。然后呢，把这个猫也穿进去，好，你就要完成这个添加，添加完了过后这个hide呢，就能够得到这个。这这个环形链表的那个投机点，因为你说是通过引用传进去的，你里面的改变会直接影响到这个he的指向，对吧，所以说这个大家应该很清楚，现在呢，我们做一个判断，判断是不是第一只猫来了。先判断。判断是不是是不是添加第一只猫。第一只第一只猫，第。一只猫，因为为什么你要判断是不是第一只猫呢？因为你你现在这个head啊，本身要放数据了。所以说你先判断是不是第一支，如果不是第一支，你就必须把这个6K把值给他，如果不是第一支，有时真的添加。

说这面是有两种逻辑在里边的啊好，那怎么判断是不是第一次呢？非常简单，如果had。它的next等于near。如果这个条件说明。他是第一只猫，就说头猫还没有呢。那你第一次来的猫就是头猫？就是你第一次来的猫就是头猫，因为我现在没有没有头猫，所以说我就害一下点它的no，就等于妞这只猫。你新来的这只猫。他的no。好，我给它复一下字，同样害的这只猫，这个头猫呢，它的名字也就相当于你这个新猫给我带过来的名字，就第一只啊，内蒙。好，紧接着呢，它的。它有一个问题啊，这个头毛的下一个节点怎么办呢？头毛下一个节点让它形成一个环状，就说一只猫也可以形成环状，就说你那只只猫，第一猫叫什么名字，比如说一叫汤姆，叫汤姆好来了过后呢，头孢本身指向它的，你出化了，然后它下面不是有个next吗？我让这个next。

我的negle指向自己。这个大家可能有点不好理解，就自己执行自己。其实这也是个环状。这也是因为你是环形的嘛，说哎，老师，一只猫怎么形成环状的，就它自己，那他之行自己不就是一个环形嘛，只是这个这个环状里面只有一只猫而已，这很正常。就好像一个圈，圈里面就一个人，一个人也是一个圈。他可能不太好理解，你两个人可以是是一个圈，那一个人为什么不能是一个圈呢？对吧？因为他的下一个next就是用自己，他就自己形，自己形成一个闭合的一个环形就是可以的，那怎么样让它形成呢？非常简单，加句话就行了。hi.next就等于hi。因为你要保证它是环形啊，就形成啊，形成一个环形环绕啊。

行程。一个环状。我们看四卷子，Node点这个啊，给他了，然后呢，Node，呃，Node的名字也有了，Hadde也有了，他的next，哦，这个还不行，这个应该指向它才行。啊，只用它才行，你headde指向之前，那不就有病了吗？这样子就说相当于说把headde给它了，Headde那行这样子headde头headde这个它指向这个地方也是用包，这样就形成一个环状了，啊这样就是一个环状。就是形成一个环形。哎，形成形成一个环形。构构成一个环形啊，构成一个环形。好，环形我们就做完了第一次么，那么下面呢，就直接return就完了，就赶紧就走路了啊return。在第一只猫就形成了，那你可以打句话说第一只猫已经来了啊，可以说一句话说第一只猫已经创建起来了，那么我们写一句话，猫猫。

哎，编号为多少的猫，我就直接这样写，直接把它输出来就行了，说这只猫已经加入到我们的团队啊，加入到加入到这个环形列表啊醒。环形的这个什么呢，就是链表中。好，第一次猫有了，但是你这是第一次猫，你第二次猫了，怎么办呢？对第二只猫，第二只猫来的话呢。这有一个问题了，就说你要考虑什么情况呢？就是你要找到这个缓冲的最后。而你因为我们现在呢，只考虑啊，我们现在目前只考虑他，呃，加的时候他加到最后，加到最后我们先不考虑排队这个问题了，就说他来了过后，假设已已经有一只猫了，它有一只猫呢，我们先让一个temp步指向它找到最后把它加进去就行了，非常简单，好，非常简单，我就加句话。那么现在呢，我们。

如果是第二只猫，我们就可以这样做了啊。同学们这样写。就是呃，先定义一个，定一个临时的，临时的变量。变量，这个变量呢，也是一个帮忙的，他是一个帮忙的啊，他帮帮助我们干什么呢？去找到最后这个节点找到什么呢？找到。找到环形的，环形的最后最后这个节点。那有时说他怎么找到最后一个这个这个这个呢，东西也很简单，这样子，我先让temp指向head。对，指向head，那指向head过后呢，我就开始用for循环去做，如果temp.next等于呢near。啊，他啊。啊对，等于等于头节点啊，这是写错了，等于头节点。因为它最后走走走形成头节点，走到这个头节点过后呢，好，我们就认为他找到了。

然后呢，下面这个动作不要忘了，就是temp等于temp.next。我就不停找，好等到它出来过后呢，Temp到了这个缓冲，最后然后把它加进去，好加入。加入到这个呃列表中，那就说是最后这个怎么加进去呢？大家想一想啊，这个环状的列表怎么加进去，其实挺简单，比如说现在已经有一个了，我又来了一个节点。说有只猫猫来了。有一只猫猫来了，那注意听讲好，有一只猫猫来了，我们要加进怎么办呢？现在的情况是这样子的啊，就说已经有一个temp，有一个这个节点。啊，有个temp这个指针，他已经找到了这个环中的最后这个。啊，他已经找到这个环中的最后这个了。也就是说他已经找到了环众。最后这个。

好，那现在你要做的一些事情，就让他加入到我们团队里面去。怎么了，嫁进去呢？那其实也很简单，就是让我这个temp的next先指向它，你你temp的next就是先让它。你现在是自我指向啊，先让这根线。指向他。对，指向它，然后再让你自己这个这个下面它不是自己也有个next吗？让它指向它。好，你看这样子就形成一个环状了。对，这样就行缓冲，那我把这个图上往上画一点，那也就是说他做做两个工作，那两个工作注意看啊，第一个动作就是temp.next。等于你的这个新的毛毛节点。紧接着让猫猫这个节点。The next指向这个头径里。

形成环状代码细纹。好，那写完过后呢，我们来遍历一下，我们来显示一下，看看到底有没有能够把这个环状形成呢？对，我们看看有没有形成环状，好显示一下。输出输出这个环形的。环形的。这个链表。好的，那我就写一个function对不对，那么我们叫做list吧。历史的circle。环形的link。那你要做这个工作，你肯定跑不了，要给我一一个头，你不给我头，我没有办法往下继续走。好，我拿到头了啊，拿到头老规矩，还是要来一个临时帮忙的这个头。这点我就不再多说了。那就开始便利呗，便利负循环。或循环，首先我们看到它是不是空间点，如果它是一个，它是一个空链表就不要走了，就它如果是个空链表就没有必要。

在输出了直接杀一句话，我们知道怎么是它是空间表呢？如果它的next等于near。等于逆，那说明你现在还是个空的一个环形列表，那就直接打印出一句话走人，对，说什么呢，这个空的。空空如也，如也的一个环形列表。对，你是一个空的环形列表，对不对，那么就不玩了。那我就不玩了，如果你不是一空链表，那至少说明你你这个temp呢，肯定可以先输一下，就说至少你自己还能把自己输出来，所以说我们先输出自己。好，我们现在说有个猫，猫ID是什么，名字是什么，我把它输出来啊，同学们那很简单，我就直接这块我就不啰嗦了，我就直接把它把这个temp输出来就行了，Temp因为它已经是个猫了啊，我就直接输出一个猫啊猫的信息。

我没有去一个一个一个取了啊猫的信息为啊它是个结构体，所以它取出来能够看到，也能看到它信息。好好看一点的话呢，我们可以在这边写一个箭头。啊，让它形成一个环状。好，就这个猫指向下一个。好，嗯，那么这个时候一旦输出来过后呢，就要去判断一下你现在是不是已经到了对尾了啊，那就说如果你temp next。等于脑损害。这说明你已你已经是咱们环状里面的那个对最后的那个那个节点，所以说呢，这个就不用再走了，输输出退出好，如果没有的话呢，就temp步继续往下走一下，这个有点不好理解，对吧，写完了代码。好，最后它整个出来的时候，其实就把这个全部打打印完了，那么我们看看现在行不行呢，来看打第一个能不能打出来。

Link，好，第一只猫，我已经加进去了，把hide给他。输出一下，我这为了好看呢，我这打印出一句话说环形链表的具体情况是。走好，我们叫环形链表的，情况如下。好玩一把。走CD点点，好，我们来CD到刚才我们写的就是那个circle。好，Go run没点go应该有意思么？好看，是不是死在这边了？诶，不对，我们没有提示这些信息啊，好，那可能我打错了，打到队列里面去了啊，退出。CD。点点。CD到我们的circle。然后呢，Single。诶，我看一下啊，同学们DRCD到我们的这个circle。

Single circle cle。SI。CCS。叫L啊single好，然后go命令go跑。好，我们看看这个情况是什么样子的，好，我们看到有问题啊。他说第一个呢，就是说你这个猫加入到环形电表，环形电表情况是它打出一只猫过后。打把他地址打出来了，然后他就跑，哦，我明白这是为什么了，不能这么输。这样说是很危险的。因为你在输这个temp的时候，Temp里面有下一个节点，它不停要走的话，会死在这里面。因为它现在已经是环状了，不是单列表，它会自己找找，找完里面又来一个next，又来，它已经形成环状，它找到这个next，他又去，它的便利的时候，它会找next，然后再打出这个节奏，它又next就死在里面了，其实我代码没错，明白我的意思吧，因为你这个next temp里面有一个这个东西。

而这个next呢，它又指向下一个，而下一个指向他自己死在里面。但是代码本身是没有毛病的，所以你要取呢，你就只能把这个猫的信息具体的取出来了啊，那就这样写一下吧，无所谓啊，猫的信息呢，我们把它ID和名字打出来就可以了。ID等于百分D好，名字等于百分D好，来我们看是不是刚才老师说的东西，那我只能格式化一下。F。好，为了好看呢，来一个斜杠。然后呢，我们这个地方就不用写到这儿了。直接写到这个位置就可以。好点。首先把它ID取出来，对，把它的IO，他没有ID no，然后呢，Temp点他的名字取出来可以了。

猫嘛，这个吞喷就是猫吗？哎，吞不就是猫，好，我们再来取一把，这里面有个F，然后这一个两个好名字是S。没问题，名字是S没问题，跑一下。好，看一下效果。嗯，这个地方还是一样，我们看看问题在哪里啊，同学们哪个地方没有写对。好，我们看一下，首先我们看是添加还是显示的问题，先把这个添加这一块先执行一下。看看死在这面没有。好添加好像是没有毛病啊，但是这个逆。啊，它是这个音标，然后呢，我们看看添加，再把这个流程再走一下，添加是怎么走的，说hide。等于空说明第一只猫把值附进去，附进去，附进去，OK。

然后呢，让这个head next指向六，好像这地方是有问题，不能指向六。不能指向六。我试试看啊，应该是有问题，好，我们这样子再试一下。这样吃它应该才形形成一个环状。好，这个这个再把它打印出来看一下。中。把这个打开。走，再跑。这是对的，为什么刚才那个错了？对，刚才有有同学应该可以看到，为什么刚才我这个就不能指向六，如果指向六的话是这样子的啊。质量六的话是虽然它们值相同，但是你的head next相当于你想headde本身它是有空间的。

它是指向一个自己的一个独立的空间，然后呢，你相当于把hide里面的，把那个六猫里面的子给它附进去，然后你让headde干什么，你让hide的next指向那个猫，相当于说你你不是一个环状，你是那个ne指向另外一个猫了，就是headde.next指向另外一个猫。而其实你要应该让head指向自己，所以刚才呢，这个地方仍然是应该指向head啊，在大家能想能想一下这是为什么啊，同学们，那不管怎么样，这个呢，咱们这个显添加和显示就算是做完了啊，这方一一定要注意这个细节。好，那刚才那个问题能不能解决呢？就是就是刚才我说的这个问题，大家可以想象啊，我刚才这样打了一下，这样子能不能自已打的这个地方应该还是很有风险的，因为他自己打自己，他是便利自己，好这个应该也会死在这儿。我看看啊，看看我的推测对不对。应该会是个无穷的曲。还行，他这自己能够能够控制住了。

按理说是这样子的啊，因为他打一个hi，但大家想啊，像Java这地方可能就会就会报错，它这样子的，我打印出temp干什么，打印出temp里面是这样子的hide，名字next，但是这个light指向一个猫猫指向这个猫猫指向的是谁呢？指向的是自己，自己里面右照里面，它会死在这儿，有些编程语言这样写一定会报错。如果你们有兴趣，你们看看这说明这个，这说明这个勾物语言它是什么呢？它是只要发现纸上指针，它就把尺针打出来，它并没有去取里面的这个值啊，但是有些语言它是要往里面追的啊，他往里面追，追到里面他就死在这了，所以他这个地方应该是还是尽量。避免这个这种用法吧，好，同学们，那关于环形链表的一个创建和。创建和显示就讲完了，我们先给大家说到这儿。