数据结构与算法(04)
程序员文章站
2024-01-27 14:27:22
...
数据结构与算法(04)—Josepfu问题
Josephu问题为:设编号为1,2,...n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。
提示:用一个不带头结点的循环链表来处理Josephu问题:先构成一个有n个结点的单循环链表,然后由k结点起从1开始计数,计数到m时,对应结点从链表中删除,然后再从被删除结点的下一个结点又从1开始计数,直到最后一个结点从链表中删除算法结束。
1.约瑟夫问题--创建环形链表的思路
a.先创建第一个结点,让first指向该节点,并形成环形
b.后面当每创建一个新的节点,就把该节点,加入到已有的环形链表中即可
2.遍历环形链表
a.先让一个辅助指针(变量)curBoy,指向first节点
b.然后通过一个while循环遍历该环形链表即可curBoy.next==first结束
代码实现:
约瑟夫问题--小孩出圈的思路分析图
根据用户的输入,生成一个小孩出圈的顺序
n=5,即有5个人
k=1,从第一个人开始报数
m=2,数2下
1.需求创建一个辅助指针(变量)helper,事先应该
指向环形链表的最后这个节点。
补充:小孩报数前,先让first和helper移动k-1次
2.当小孩报数时,让first和helper指针同时的移动m-1次
3.这时就可以将first指向的小孩节点出圈
first=first.next
helper.next=first
原来first指向的节点就没有任何引用,就会被回收
出圈的顺序
2->4->1->5->3
代码的实现
整个约瑟夫问题代码实现