00:00
各位同学,下面呢,我们来把我们把这个双向链表应用给大家讲了,我们来看一个另外一种链表叫单向环形链表,也就是说现在讲的这个链表呢,是环形的。那么什么叫环形链表呢?我们先看它的一个应用场景。这个应用场景呢,就是一个著名的约瑟夫问题,这个约瑟夫是这个意思啊,我们先把这个约瑟夫问题的对应的中文写出来,叫约瑟夫,这个问题有些地方叫约瑟夫还。有,有些人叫约瑟夫。叫约瑟夫还。一样的啊,大致的意思呢到大同小异,那么这个题呃,它的一个含义是什么呢?说有一群小孩围成一圈来做游戏。啊,有多少个小孩呢?不确定不确定,然后呢,围成一圈做做游戏呢,规定呃,从K。
01:01
这个人开始编号,K呢是在一到N之间。啊,这个编号数到M,数到M的这个人呢就出列,然后下一个人呢,又从一开始报数,数到M呢又出列,最后他问你出对的这个编号序列是什么。其实这个应用场景呢,最经典的就是用一个。这个循环链表来解决,但这个循环链表呢,可以带表头,也可以不带表头,对不对?好,那么这个就是单向环形链表的一个应用,那说到这儿我们就来看一个单向环形链表长什么样子,大家看这个图。这个图,这个图大家有没有发现,就是它有一个特点,这有四个节点。这有四个节点。这个节点呢?这个节点指向。它这个节点又指向它这个节点呢,指向下一个节点,而下一个节点又指向了这个节点,那大家有没有发现它是一个环状。
02:06
它是一个环状,就是说它是一个闭合的一个链表,而不像我们刚才讲的链表是这样子的,有一个节点指向下一个节点。下一个节点指向下一个节点,那节点最后这个呢就是一个空,而现在不一样的是,不一样的是最后这个节点又反向指向了头一个节点,形成一个环。啊,这个就是单向环形链表的一个最简单的案例,那既然如此,那下面呢,我们就把这个约瑟夫问题的一个具体的一个示意图给大家看一下,约瑟夫问题刚才我已经讲过了,它是一个经典的用一个循环链表来解决,可以带,可以不带节点,头节点也可以带,啊后面我们使用带节点还是不带,带头节点还是不带头节点,我们到时间再来分析。
03:00
哦,不来再来分析,现在呢,假如我们是一个不带头接点的环形链表,就是刚才这这种类似的,我们来看看他的一个大致的含义是什么,来我们画一个示意图。画一个示意图,这个叫什么呢?叫约瑟夫,约瑟夫。问题的问题的一个示意图。哦,示意图,那么我们来针对这个案例来看一个吧,看一个我们就以他这提出的这个问题来画一个示意图。待会儿呢,我们说完了过后我们就用代码来实现。对吧,我们先把这个问题搞清楚,然后我们再说代码,比如说现在呢。他说这个N。我我这样子啊,我我把这块呢,标一个颜色,大家看的比比较清晰,假如这个N等于五什么意思,代表我有五个人及有五个五个人,当然了啊,这个到底有几个人可以是一个变量。
04:03
然后呢,K,假如这个K呢,我约定一就代表从哪呢?从第一个人开始开始报数。开始报数能理解啊报数然后呢,这边还有一个M,假如M呢,我设定为二。就是代表什么呢。数两下,数两下。好,如果数两下,他问最后产生的一个出队列的编编出队列,出对编号的一个序列是什么样子的,那么我们来看一下应该是怎么样来玩的啊说这里有第一个节点。好,第一个节点呢,有一,它当然也有个next域了,肯定它有个next域嘛,这是它的编号,好,然后呢,我们来看一下,这是第二个节点,好吧,然后呢,这是第三一个节点。第三一个节点,我画卷吧。
05:01
啊,比如说编号为三的这个小孩。那还有一个编号为四的小孩,比如说我放在这里编号为四的小孩,然后呢,编号为五的小孩。编号为五的小孩,他们呢,形成了一个环状。它们形成一个环状,也就是说目前的情况是这样子的,这个next域指向它,我换这个颜色啊,然后二号这个小孩呢,又指向三号。A换一个颜色,然后三号呢,它的下next域指向四号节点。然后四号这个小孩呢,他指向五号这个小孩。五号这个小孩呢,他又重新指挥到一号这个小孩,大家看形成一个环状,那形成一个环状以后,我们来看看他的这个初队列的顺序是什么样子的啊,按照这个写出队列的一个顺序。顺序他这样子呢,首先从一开始报数,从第一个人开始报数,他数两下就是一二,那就是这个二号,这个人呢,就出队列了。
06:09
一开始报数吗?好,所以说这个第一个出队列的是二号。二号这个出队列,二号出队列以后,这个环状这个地方就没有了,就删掉了,删掉以后呢,相当于它。一号就指向这个人了,因为二号已经出队列,出队列过后从三这个人再数,注意啊,是从下一个人及从三号再开始报数,报二,他又数一,二号,四号又数到了四号出列。四号出队列过后呢?诶,他就出去了,出去以后,那当然我会让三号再指向五号。好,五号是刚才出队列的这一个节点的下一个节点,那么五号又开始倒数,倒几下呢?倒两下,一二号,下一个就是一号又出队列。
07:02
能理解我的意思啊,我先把这个说清楚,待会再写代码,一号出队了,一号出完队列以后,同学们好,同学们,那现在呢,五号就指向了三号,他仍然是一个环状,是不是?那么三号开始报数,报一报二,好,五号又出队列,注意注意看清楚啊,最后最关键点来了,五号一旦出了队列。那么现在呢,只有一个节点三,那一个三节点它能不能形成环状呢?也可以的,它自己指向自己,仍然是一个环状。仍然是一个换装,是不是他自身只是next只用自己嘛,仍然是换装,然后他自己在数一下,他也队列就是最后,显然就是留下最后一个人,肯定就是最后一个出队列的了。好,所以出队列顺序是24153,就这么来的,能理解我的意思啊,能理解我的意思好了,那既然如此,那既然如此呢,我们这个示意图也分析完了,那下面呢,我们就准备根据刚才老师画的这个示意图给大家来演示它的一个顺序,好吧,好,我把这个呢,先把这个顺序给大家保留一下,然后呢,我把。
08:12
我把刚才的这个图再撤回去。啊,把这个图再撤回,因为待会儿呢,我在写代码的时候,我还需要这个图来给大家解释,我是怎么样一步一步做出来的,我先撤回去啊。这是最原始的吧,这最原始的出队列的顺序是不是这样这个顺序。出队列顺序,刚才我们分析出来是24153,待会儿呢,我们就。根据刚才这个分析,一步一步来实现来,我们这个思路已经有了啊,先把刚才这个思路给大家整理一下,然后待会再写代码。来,刚才呢,我们给同学们讲的是单向环形链表的一些内容。来捋一捋。首先我们举了一个单向环形链表的一个约瑟夫问题的111个提出,啊,这是它的一个问题。
09:06
好,然后具体来说呢,他这个问题是这样子的,还有。这啊,我们把它粘过来就可以了。就是约瑟夫问题。好,放这吧。放这然后呢,这边有一个示意图。啊,也把它放在这儿。好,这是它的一个应用场景,完了,我们给大家讲了一个单向环形链表的最简单的一个案例。哪里呀,诶这个地方写成二号。最简单的那就是这样一个图形,就说这就是一个最为简单的单向环形链表,对吧,四个节点的,然后呢,我们在这里第三个幻灯片,我们给大家分析了一下约瑟夫问题的到底是到底是个什么意思,对吧,做了分析。好,给同学们放到这来。约瑟夫问题的一个示意图,我们粘到这就可以了,这边是他的提的一个要求,下面是一个分析,好,我们把它写到这啊,约瑟夫问题的一个示意图。
10:12
好,我把它呢,拿到我们的笔记中去。拿到MBA中去。好,把这个稍微的挪挪一下啊,挪一下好,这是刚才呢老师举的一个例子。啊,举了一个例子,什么呢?就说假如我们定的MN45K是一,M42,最后它的出对列的顺序我们分析出来是24153,待会写完代码过后呢,我们可以用它来验证我们代码写的对还是不对,还有一点啊,这个地方我们会使用什么来实现呢?我们会使用单向。单向环形链表完成。完成这一个约瑟夫问题。比问题,那有些同学也知道,有些有些人呢,他不用环形链表,他用的是数组来完成也是可以的,按照数组取模的方式也可以完成,但是呢,没有这个形象啊,没有这个形象,所以说这里我采用单线环形裂变完成,大家先清楚好,我把这个分析图给同学们拿到笔记中了。
11:18
哦,拿到笔中来。好,同学们,那关于这个单向环形列表应用场景和约瑟夫问题的说明我们就先讲到这儿,一会呢,我们代码实现之。
我来说两句