从约瑟夫环看循环链表 约瑟夫环问题是这样: 描述 编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。...正好我最近也在自己看数据结构的书，所以这里就借这一题实践一下循环链表。...（我的方向从来不是NOI和ACM，写的东西可能比较业余，不伦不类，请大家见谅……） 循环链表就是把我们线性链表的最后一个节点的指针域指向第一个有效节点。...我们完全可以先造一个非循环单链表，然后再把它的尾指针指向首节点。 首先定义一个结构体，用它来做我们的节点。...当m==1时就把循环链表走一遍，走到p之前的那个节点，再执行DeleteNode函数。 改正的代码已经传到附件里了。
演示样例输入 5 3 演示样例输出 4 首先说一下写这个之前我是准备徒手艹链表的，可惜意志力实在不咋滴，再加上手头上没课本，之前我有看过C语言版的链表实现，但没动手敲过，都是偷懒用list水过，list...是双向链表，但约瑟夫这个问题吧，明显是用循环链表来完毕的，问题来了，本渣不会艹链表啊，木办法仅仅能用list来胡搞了 #include #include #include...:iterator j; for(i=1;i<=n;i++) node.push_back(i); //编号 j=node.begin(); while(node.size()>1) //当链表中仅仅剩一个元素时结束...//重点来了 { j=node.begin(); j++; //一開始忘记写这个了 事实上当j=node.end()时就意味着j已经指向node.begin()了，仅仅是由于这不是循环链表
循环链表的存在很难想象他的应用范围到底是哪里，本文主要介绍的是通过循环链表处理解决约瑟夫问题，让大家更深刻的理解循环链表的使用和应用场景。...假设： m = 8，n=3 最后我们得出的结果便是 ： 3 6 1 5 2 8 4 7 很明显，如果用循环链表来处理这个问题，将非常简单。...大致的思路如下： 生成一个有 8 个数据的循环链表 无限循环遍历链表 无限循环中增加for循环，每次循环 n - 1 次，每循环一次移动一次游标，将for循环完成后游标指向的数据删除 依次执行，直到链表为空为止...【实现代码】 注意：需要用到上一篇文章我们编写的 CircleList.h 和 CircleList.c 文件。...(list, (CircleListNode*)&val[i], i); } //遍历循环链表 printf(“插入数据:\n”); for (i = 0; i < CircleList_Length(
约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从...(Person)); /*准备一个头结点*/ head->number=1; head->next=NULL; Person * cyclic=head; /*循环创建...->number=i; body->next=NULL; /*连接*/ cyclic->next=body; /*cyclic继续用作循环变量...=k) { tail=p; p=p->next; } /*从编号为k的人开始，只有符合p->next==p时，说明链表中除了p结点，所有编号都出列了...{ /*存储下上一个位置*/ tail=p; p=p->next; } /*从链表上将
这个游戏的实现只需将每个人的信息作为一个结点，节点中存放每个人的编号和密码，由于要反复做删除操作，所以采用单项循环链表实现较为方便。...算法分析: 采用单向循环链表的数据结构，即将链表的尾元素指针指向链首元素。每个结点除了指针域外，还有两个分别存放每个人的编号和所持有的密码。...解决问题的基本步骤如下： 1.建立n个结点(无头结点)的单向循环链表 2.从链表第一个结点开始循环计数寻找第m个结点。.../测试链表是否为空 void JosephusOperate(NodeType **,int);//运行约瑟夫环问题 int main(void) { int n=0; int m=0; NodeType...printf("\n-----------------打印循环链表---------------\n"); PrntList(pHead); //打印循环链表 printf("
1.什么是约瑟夫问题？...2.约瑟夫问题的解决方式 通过单向循环链表解决，具体思路如下： /** * @author shengjk1 * @date 2020-02-06 */ public class Josephus...first); } } //展示所有的小孩编号 public void show() { if (first == null) { System.out.println("单向循环链表表为...public Boy getNext() { return next; } public void setNext(Boy next) { this.next = next; } } 3.单向循环链表的使用场景...音乐 APP 中的循环播放 kafka 的时序( 具体是否为单向循环链表需要确定，肯定使用的循环链表) 4.关于单向循环链表的面试题 约瑟夫问题
利用单向循环链表实现 C++代码如下：（参考书籍：数据结构与算法实验指导书） ?...Jose { private: NodeType* p_head; public: Jose() { p_head = new NodeType; //带空头的链表...p_head->next = p_head; //空的循环链表 } ~Jose(){} void creat(); void print(); };...= del) //链表节点个数不为1 { for(i = 1; i < m; ++i) //del往后移动m位 {...tempNode->next; } cout num name << endl; delete del; //链表只剩一个节点直接删除
已知有5个人围坐在一张圆桌的周围，从编号为3的人开始顺时针数数，数到2的那个人出列淘汰，然后从出列的下个一人继续数，依次循环，直到只剩下最后一个人。...（使用循环链表实现约瑟夫环） 代码如下： #include "pch.h" #include #include #include #include... using namespace std; //循环链表基本实现 //typedef struct LNode //{ // int date; // LNode*...; //} // 给链表增加节点 //void GetLinkList(LinkList &L, int n) //{ // LNode *p; // LNode *r; // r = L;...endl; // // InitList(lc); // MergeLinkList(la, lb, lc); // OutPutList(lc); // // return 0; //} // //约瑟夫环实现
pNode->next=NULL; return pNode; delete pNode; } void init_list(Linklist*plist)//用第一个节点初始化循环单链表...plist->phead=p; plist->ptail=p; p->next=plist->phead; plist->len=1; } //把其余数据添加到循环单链表中... plist->ptail=pNew; pNew->next=plist->phead; plist->len++; } } //输出链表内容...one is:” data<< endl; } int main(int argc, char * argv[]) { int n=0; cout <<“约瑟夫环长度为
目录 一、双链表 初始化（带头结点）： 双链表的插入： 双链表的遍历 循环链表 循环单链表的初始化 循环双链表的初始化 双链表的插入 双链表的删除 静态链表 定义静态链表 插入 删除 ---- 一...，这就是循环链表。...循环链表和普通链表的区别就是最后一个节点的后继指向了头节点。下面看看单链表和单向循环链表的区别。...单向循环链表最后一个节点的next域不为空，而是指向了头节点， 而单链表和单向循环链表判断空表的条件也发生了变化，单链表为空表时，L ->next=NULL；单向循环链表为空表时，L ->next=L...双向循环链表除了要让最后一个节点的后继指向第1个节点，还要让头节点的前驱指向最后一个节点 双向循环链表为空表时，L ->next=L ->prior=L ，如下图所示。
循环、非循环 ---- 无头单向非循环：结构简单，一般不会单独用来存数据，实际中更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等，另外这种数据结构在笔试面试中出现很多。...带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头循环双向链表，另外，这个结构虽然复杂，但是使用代码代码实现的以后会发现结构带来许多优势，实现反而简单了。...---- 带头双向循环链表 结构体创建 typedef int LSTNodeData; typedef struct ListNode { LSTNodeData data; struct ListNode...= phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); } 尾插 双向带头循环链表，结构虽然复杂了，但是更容易操作了...空 return true; } else { //不为空 return false; } } 优化 为了更快的实现一个双向循环的带头链表，我们可以直接利用Insert和Erase。
约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 m的人开始顺时针报数，数到 n 的那个人被干掉；他的下一个人又从 1...stdio.h> #include typedef struct node{ int id; struct node *next; }person; //创建节点 //建立循环链表
,int elem,int add){ link * temp=p;//创建临时结点temp //首先找到要插入位置的上一个结点 for (int i=1; inext; } //创建插入结点c...link * c=(link*)malloc(sizeof(link)); c->elem=elem; //向链表中插入结点 c->next=temp->next; temp->next=c; return...p; } 注意：首先要保证插入位置的可行性，例如图 5 中单向循环链表，原本只有 5 个结点，插入位置可选择的范围为：1-6，如果超过6，本身不具备任何意义单向循环链表，程序提示插入位置无效。...p,int elem,int add){ link * temp=p;//创建临时结点temp //首先找到要插入位置的上一个结点 for (int i=1; inext; } //创建插入结点c...link * c=(link*)malloc(sizeof(link)); c->elem=elem; //向链表中插入结点 c->next=temp->next; temp->next=c; return
带头双向循环链表 结点结构与头结点的创建 头插尾插 打印链表 头删与尾删 链表的查找 在pos的前面进行插入与删除pos位置的结点 销毁链表 完整代码 结点结构与头结点的创建 创建两个源文件和一个头文件...test.c linked_list.c linked_list.h 带头双向循环链表，那么，结点的结构就要有两个指针域，分别指向前一个结点和后一个结点。...，所以也要让头结点的前指针和后指针都指向自己才符合循环结构。...这里尾插就很方便了，不像之前需要遍历找尾，因为是循环链表，尾的next就是头结点。 当然这里要先写一个创建新结点的函数。...这里就要遍历链表了，因为是循环结构，所以结尾就不用空指针进行判断了。
单链表 设计思路 实现增删查改的准备工作 头插尾插 头删尾删 查找与销毁 在pos之后插入数据为x的结点与删除pos后面的结点 完整代码 设计思路 链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表...实现增删查改的准备工作 分两个源文件，一个头文件： linked.h linked.c test.c 结点类型的定义 //linked.h typedef int type;//重新定义数据类型的名字...}ct; 定义一个头节点 //test.c ct* head = NULL;//头结点指针 默认指向为空，如果没有数据就为空 开辟结点空间 //linked.c ct* crunode(type x...这里不能断言是否为空指针，因为没有数据的时候头节点的指向的地方就是空指针，所以空指针我们也要打印（因为更形象，实际上并不需要打印NULL） //linked.c void SListPrint(ct...cur->next; } printf("NULL\n");//打印末尾的NULL } 头插尾插 下面这些函数都是在linked.c文件中 尾插 void SListPushBack(ct**
三、循环链表的应用---约瑟夫问题模拟 据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到...这里我做了一个效果图，模拟下约瑟夫问题： ? 接下来我们如何用链表来模拟约瑟夫问题。...新的循环双向链表完整设计代码： /** * 在循环双向链表的基础上，增加1个属性，3个方法（属性内部使用，方法对外开放）,让循环链表发挥更大的效果： * current: 指向当前节点，默认指向首节点...用循环链表来模拟这个游戏 */ console.log("\n\n........test3约瑟夫题目。。。....")...其余单向循环链表、单向循环链表增强、双向循环链表等代码Demo见github地址：https://github.com/xiaotanit/Tan_DataStruct
【算法分析】 本题我们可以用数组建立标志位等方法求解，但如果用上数据结构中循环链的思想，则更贴切题意，解题效率更高。...这就是单循环链的数据结构。当ｍ人出列时，将ｍ结点的前继结点指针指向ｍ结点的后继结点指针，即把ｍ结点驱出循环链。 1、建立循环链表。
} return first } func ShowKid(first *Kid) { if first.next == nil { fmt.Println("链表已空...} } func Play(first *Kid, start int, count int) { if first.next == nil { fmt.Println("空链表
约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的，他参加并记录了公元66—70年犹太人反抗罗马的起义。...解法一：用循环链表实现 #include #include typedef struct Node { int data; struct Node...为当前结点，pre为辅助结点，指向pcur的前驱结点，head为头节点 Node *pcur, *pre, *head; head = NULL; int i; // 建立循环链表...pre->next = pcur; } pre = pcur; } pcur->next = head; // 尾节点连到头结点，使整个链表循环起来...为了讨论方便，先根据原意将问题用数学语言进行描述。 问题：将编号为0～（N–1）这N个人进行圆形排列，按顺时针从0开始报数，报到M–1的人退出圆形队列，剩下的人继续从0开始报数，不断重复。
【要求】 输入：一个环形单向链表的头节点 head 和报数 m. 返回：最后生存下来的节点，且这个节点自己组成环形单向链表，其他节点都删除掉。...【难度】 士：★☆☆☆ 【解答】 方法1：时间复杂度为 O( n * m) 这道题如果不考虑时间复杂度的话还是挺简单的，就遍历环形链表，每遍历 m 个节点就删除一个节点，知道链表只剩下一个节点就可以了。...方法二：时间复杂度为 O(n) 这个方法的难度为： 校：★★★☆ 我们可以给环形链表的节点编号，如果链表的节点数为 n, 则从头节点开始，依次给节点编号，即头节点为 1， 下一个节点为2， 最后一个节点为...我们用 f(n) 表示当环形链表的长度为n时，生存下来的人的编号为 f(n)，显然当 n = 1 时，f(n) = 1。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM
