❶ java循环单链表实现约瑟夫环
看了你的代码，不是很明白，给你提几个建议吧：
1、不需要tail节点
2、remove方法应该对删除节点前面的节点操作，而不是使用数字找
给你我修改的LinkList类，你参考一下：
publicclassLinkList{
privateNodehead;
intcurlen=0;
//创建链表
publicvoidcreatelist(intcode)throwsException{
insert(curlen,code);
}
publicvoidinsert(inti,intcode)throwsException{
Nodes=newNode(code);
if(i==0){
s.setNext(head);
head=s;
}
Nodep=head;
intj=0;
while(p!=null&&j<i-1){
p=p.getNext();
j++;
}
if(j>i||p==null){
thrownewException("插入位置不合理");
}
s.setNext(p.getNext());
p.setNext(s);
// tail=s;
// tail.setNext(head);
curlen=curlen+1;
}
publicvoidremove(inti)throwsException{
Nodep=head,q=null;
intj=0;
i=i-1;
while(j<i){
q=p;
p=p.getNext();
j++;
}
if(j>i||p==null)
thrownewException("删除位置不合法");
if(q==null){
// tail.setNext(p.getNext());
head=head.getNext();
}else
q.setNext(p.getNext());
curlen=curlen-1;
}
/**
*按照节点删除
*@parami
*@throwsException
*/
publicvoidremove(Nodep)throwsException{
if(p.getNext()==p){
p=null;
head=null;
}
else{
Nodeq=p.getNext();
p.setNext(q.getNext());
}
curlen=curlen-1;
}
publicvoidout(intm)throwsException{
Nodep=head;
if(m==1){
System.out.print("按照顺序出列");
return;
}
intcount=1;
intn=m-1;
while(curlen>0){
if(count==n){
System.out.print(p.getNext().getData()+"");
remove(p);
count=1;
}else{
count++;
}
p=p.getNext();
}
}
publicvoiddisplay(){
Nodenode=head;
for(inti=0;i<2*curlen;i++){
System.out.print(node.getData()+"");
node=node.getNext();
}
System.out.println();
}
}
❷ 求解约瑟夫环问题(Java)
package 约瑟夫环;
import java.util.LinkedList;
import java.util.List;
/**
* 约瑟夫环问题的一种描述是：编号为1.2.3…….n的n个人按顺时针方向围坐一圈 ，每人手持一个密码（正整数），
* 开始任意选一个整数作为报数上限值，从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，
* 将他的密码作为新的m值，从他顺时针下一个人开始重新从1开始报数，
* 如此下去直到所有的人全部都出列为止。试设计程序实现，按照出列的顺序打印各人的编号。
* @author Administrator
*
*/
public class Question2 {
class person {
int password;
int number;
int state = 1;
public person(int password, int number) {
this.password = password;
this.number = number;
}
public person(int number){
this.number = number;
}
}
public int ListLength(List<person> list) {
int count = 0;
if (list != null) {
for (person p : list) {
if (p.state != 0) {
count++;
}
}
}
return count;
}
public void cacle() {
// 初始化数据
List<person> list = new LinkedList<person>();
list.add(new person(3,1));
list.add(new person(1,2));
list.add(new person(7,3));
list.add(new person(2,4));
list.add(new person(4,5));
list.add(new person(8,6));
list.add(new person(4,7));
int position = -1;//初始位置
int m = 20; //第一次报多少的人出来
int count = 0;//已经报了多少人
while (ListLength(list) != 0) {
position = (position + 1) % list.size();// 位置定位
if (((person) list.get(position)).state != 0) {
count++;
}
if (count == m) {
person p = list.get(position);
System.out.print(p.number+" ");
p.state = 0;
m = p.password;
list.set(position, p);
count = 0;
}
}
}
public static void main(String[] args) {
Question2 q= new Question2();
q.cacle();
}
}
跟这差不多的。
❸ 数据结构— 循环链表、双向(循环)链表
链表的两头连接，形成了一个环状链表，称为循环链表。
约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（以编号1，2，3，…，n分别表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，要求找到最后出列的那个人。
例如有 5 个人，要求从编号为 3 的人开始，数到 2 的那个人出列：
出列顺序依次为：
编号为 3 的人开始数 1，然后 4 数 2，所以 4 先出列；
4 出列后，从 5 开始数 1，1 数 2，所以 1 出列；
1 出列后，从 2 开始数 1，3 数 2，所以 3 出列；
3 出列后，从 5 开始数 1，2 数 2，所以 2 出列；
最后只剩下 5 自己，所以 5 出列。
循环链表和动态链表唯一不同在于它的首尾连接，这也注定了在使用循环链表时，附带的最多的操作就是遍历链表。在遍历的过程中，尤其要注意循环链表虽然首尾相连，但并不扰山表示该链表没有第一个节点和最后一个结点。所以，不要随意改变头指针的指向。
整个链表只能单方向从表头访问到表尾，这种结构的链表统称为 “单向链表”或“单链表”。
如果算法中需要频繁地找某结点的前趋结点，单链表的解决方式是遍历整个链表，增加算法的时间复杂度，影响整体效率。
为了快速便捷地解决这类问题，在单向链表的基础上，给各个结点额外配备一个指针变量，用于指向每个结点的直接前趋元素。这样的链表被称为“双向链表”或者“双链表”。
双向链表中的结点有两个指针域，一个指向直接前趋，一个指向直接后继。（链表中第一个结点的前趋结点为NULL，最后一个结点的后继结点为NULL）
结点的具体构成：
双向链表创建的过程中，每一个结点需要初始化数据域和两个指针域，一个指向直接前趋结点，另一个指向直接后继结点。
创建一个双向链表line（1，2，3）：
比如在（1，2，3）中插入一个结点 4，变成（1，4，2，3）。
实现效果图：
在双向链表中插入数据时，首先完成图中标注为 1 的两步操作，然后完成标注为 2 的两步操作；反之，如果先完成 2，就无法通过头指针访问结点 2，需要额外增设指针，虽然能实现，但较前一种麻烦。
双链表删除结点时，直接遍历链表，找到要删除的结点，然后利用该结点的两个指针域完成删除操作。
在（1，4，2，3）中删除结点 2：
双向链表的查找操作和单链表的实现方法完全一样，从链表的头结点或者首元结点开始遍历，正氏这里不做过多解释。
更改链表中某结点的数据域的操作是在查找的基础上完成的。通过遍历找到存储有该数据元素的结点后，直接更改其数据域就可以。
其实举李散就是双向链表和循环链表的结合体
例如：约瑟夫环问题其实还可以这样玩：如果顺时针报数，有人出列后，顺时针找出出列位置的下一个人，开始反方向（也就是逆时针）报数，有人出列后，逆时针找出出列位置的下一个人，开始顺时针报数。依次重复，直至最后一个出列。
有兴趣可以自行尝试，这里就不再分析了，因为本质就是双向链表和循环链表。