【数据结构与算法】循环链表

简介: 【数据结构与算法】循环链表

一.问题引入

据说著名犹太历史学家Josephus(弗拉维奥·约瑟夫斯)有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

感兴趣的可以去搜索一下约瑟夫问题

咱们可以将问题简化,有10个小朋友围圈而坐,当报到9这个数字的小朋友就站起来.如何接着从这个站起来的下一位小朋友从1开始报数,报到9数字的小朋友又战起来.

假设小朋友的编号从1到10,现在问,第5个站起来的小朋友编号是多少?最后一个小朋友站起来的编号是多少?

解决这个问题,很明显是一个一直循环的圈,就引入了我们今天的主题循环链表

二.循环链表初始化

我们知道单链表的最后一个节点的指针域是空,既然指针可以随便的指向其他地址,不防我们将最后一个节点的指针域指向头节点.

有点像奥古斯特·凯库勒做的梦,苯环的结构,蛇的嘴咬着自己的尾巴.

画个图:

三.循环链表插入数据

这里我们使用常见的尾插法,我们需要遍历到最后一个节点,然后进行插入,单链表的遍历条件是看每个节点的指针域是否为空.

那么循环链表的遍历条件就是看每个节点的指针域是否为头节点.

为了能看到我们插入的信息,我们需要遍历链表打印

运行结果:

OK,已经插入了10个小朋友了,接下来就是报到9的站起来了.

四.循环链表删除数据

当遍历到9或者9的倍数的节点我们就需要删除,相当于小朋友站起来了.

所以我们需要一个计算的变量,同时我们还需要记录轮数.

这里就有两重循环,外层循环是每一轮都会删除一个节点,直到只有头结点的时候,内层循环是从1报到9.

因为我们要删除节点,那么就需要找到,要删除节点的上一个节点.

外层循环是do while当头节点的指针域是自己的时候,说明节点已经删除完了.

i是报数要站起来的数,这里是9,我们这里相当于一直对计算器j进行++,会大于9,但是我们将i又+=9,其原理和又从1数到9是一样的.

什么情况下我们才对计数器进行++?那就是不是头节点的时候,因为是循环链表,中间有一个用来衔接的头节点是没有数据的,不需要参与报数.

我们这里的判断是j>=i就跳出报数循环,然后进行删除.

我们是先判断再p=p->next这是有妙处的,我对计数器进行了++,但是

如果到了报数9,我就还没有对p进行赋值指针域所指向的点.

所以这个跳出的p是指向的要删除的上一个节点.

就找到了我们需要的节点,直接进行删除,同时对轮数times进行++,再记录一下要删除的编号.我们的问题就解决了.

在main中调用函数得:

五.总结

循环链表与单链表的不同点就在尾巴上.


相关文章
|
6天前
|
缓存
数据结构之 - 链表数据结构详解: 从基础到实现
数据结构之 - 链表数据结构详解: 从基础到实现
38 6
|
6天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
81 64
|
22小时前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
12 3
|
3天前
|
算法
【链表】算法题(二) ----- 力扣/牛客
【链表】算法题(二) ----- 力扣/牛客
|
21小时前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
16 7
【数据结构】——双向链表详细理解和实现
【数据结构】——双向链表详细理解和实现
|
4天前
|
存储 Java
【数据结构】链表
【数据结构】链表
11 1
|
4天前
|
存储 缓存
数据结构3——双向链表
数据结构3——双向链表
34 1
|
7天前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
1天前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
6 0