约瑟夫环问题循环单链表(约瑟夫问题数据结构循环链表)
java循环单链表实现约瑟夫环
看了你的代码，不是很明白，给你提几个建议吧：
1、不需要tail节点
2、remove方法应该对删除节点前面的节点操作，而不是使用数字找
给你我修改的LinkList类，你参考一下：
public?class?LinkList?{
private?Node?head;
int?curlen?=?0;
//?创建链表
public?void?createlist(int?code)?throws?Exception?{
insert(curlen,?code);
}
public?void?insert(int?i,?int?code)?throws?Exception?{
Node?s?=?new?Node(code);
if?(i?==?0)?{
s.setNext(head);
head?=?s;
}
Node?p?=?head;
int?j?=?0;
while?(p?!=?null??j??i?-?1)?{
p?=?p.getNext();
j++;
}
if?(j??i?||?p?==?null)?{
throw?new?Exception("插入位置不合理");
}
s.setNext(p.getNext());
p.setNext(s);
// tail?=?s;
// tail.setNext(head);
curlen?=?curlen?+?1;
}
public?void?remove(int?i)?throws?Exception?{
Node?p?=?head,?q?=?null;
int?j?=?0;
i?=?i?-?1;
while?(j??i)?{
q?=?p;
p?=?p.getNext();
j++;
}
if?(j??i?||?p?==?null)
throw?new?Exception("删除位置不合法");
if?(q?==?null)?{
// tail.setNext(p.getNext());
head?=?head.getNext();
}?else
q.setNext(p.getNext());
curlen?=?curlen?-?1;
}
/**
?*?按照节点删除
?*?@param?i
?*?@throws?Exception
?*/
public?void?remove(Node?p)?throws?Exception?{
if(p.getNext()==p){
p=null;
head=null;
}
else{
Node?q?=?p.getNext();
p.setNext(q.getNext());
}
curlen?=?curlen?-?1;
}
public?void?out(int?m)?throws?Exception?{
Node?p?=?head;
if(m==1){
System.out.print("按照顺序出列");
return;
}
int?count?=?1;
int?n=m-1;
while?(curlen??0)?{
if?(count?==?n)?{
System.out.print(p.getNext().getData()?+?"??");
remove(p);
count?=?1;
}?else?{
count++;
}
p?=?p.getNext();
}
}
public?void?display()?{
Node?node?=?head;
for?(int?i?=?0;?i??2?*?curlen;?i++)?{
System.out.print(node.getData()?+?"?");
node?=?node.getNext();
}
System.out.println();
}
}
c语言链表写约瑟夫环问题
C语言的约瑟夫环问题，利用单循环链表，代码如下：
#includestdio.h??//利用单循环链表！！！！！
#includestdlib.h
#includemalloc.h
typedef?int?ElemType;
typedef?struct?SingleNode
{
?ElemType?data;
?struct?SingleNode?*next;
}SLL,*LinkList;
int?main()
{
?SLL?*head?,*use,*temp;
?int?i,n,m,k,a=0;
?printf("请输入总人数n：");?
?scanf("%d",n);
?????
?printf("从第m个人开始数起，请输入m:");?
?scanf("%d",m);
?????
?printf("数到第k个人，该人出列，请输入k:");?
?scanf("%d",k);
??
?head?=?use?=?(SLL?*)?malloc(sizeof(SLL));//建立链表，形成链表头
???head-data?=?1;
??
???for?(i?=?2;?i?=?n;?i++)//形成其余的n-1个
???{
????use-next?=?(SLL?*)?malloc(sizeof(SLL));
????use?=?use-next;
????use-data?=?i;//第i个置编号i
???}
???use-next?=?head;//末首相连，形成环
?printf("人员序号为：");??//输出人员的序号
?temp=head;
?for(i=0;in;i++)
?{
??printf("%d?",temp-data);
??temp=temp-next;
?}
?printf("\n");
??
?for(i=0;im-1;i++)//use指向第m-1个，为了从m位开始数
?{
??use=use-next;
?}
printf("人员出列顺序为：");
while?(n)?{
?for?(i?=?1;?i??k;?i++)//掠过k－1个
??use?=?use-next;
?temp?=?use-next;//temp指向第k个
?use-next?=?temp-next;//第k个从环中脱钩
?printf("%d?",?temp-data);
?free(temp);//释放第k个表元占用的空间
?n--;
}
printf("\n");
?return?0;
}
单链表实现代码如下：
#includestdio.h??//这是使用单链表做的约瑟夫环
#includestdlib.h
#includemalloc.h
typedef?int?ElemType;
typedef?struct?SingleNode
{
ElemType?data;
struct?SingleNode?*next;
}SLL,*LinkList;
void?ListInitialize(SLL?**head)???//初始化
{
if?((*head=(SLL?*)malloc(sizeof(SLL)))==NULL)
exit(1);
(*head)-next=NULL;
}
int?ListInsert(SLL?*head,int?i,ElemType?x)??//插入
{
SLL?*p,*q;
int?j;
p=head;
j=-1;
while(p-next!=NULLji-1)
{
p=p-next;
j++;
}
if(j!=i-1)
{
printf("the?i?is?wrong!");
return?0;
}
if((q=(SLL?*)malloc(sizeof(SLL)))==NULL)
exit(1);
q-data=x;
q-next=p-next;
p-next=q;
return?1;
}
int?ListGet(SLL?*head,int?i,ElemType?*x)???//取
{
SLL?*p;
int?j;
p=head;
j=-1;
while(p-next!=NULLji)
{
p=p-next;
j++;
}
????if(j!=i)
{
printf("ERROR!");
return?0;
}
??*x=p-data;
return?1;
}
void?yuesefu(SLL?*head,?ElemType?n,ElemType?m,ElemType?k)??//约瑟夫删除操作
{ElemType?x;
SLL?*p,*s;
????p=head;
int?i=0,j=0,b=0;
while(b!=m-1)??//将指针指到第m-1个元素
{
p=p-next;
b=b+1;
}
while(p-next!=NULL)??
{while(i!=k-1)
{i=i+1;
p=p-next;
if(p==NULL)??p=head-next;??//控制循环
}
??????
??if(p-next==NULL)??p-next=head-next;???//控制循环
s=p-next;??//删除第k个元素
???x=s-data;
????????if(s-next==NULL)??s-next=head-next;??//控制循环??
p-next=s-next;
printf("%d?",x);??//输出第k个元素
j=j+1;???//用以统计总共输出了多少个元素
free(s);
if(j==n)?break;
i=0;???//i清零
}
}
void?main()
{
SLL?*head;
int?x,i,n,m,k,a=0;
ListInitialize(head);?//调用初始化函数
printf("请输入总人数n：");?
scanf("%d",n);
????
printf("从第m个人开始数起，请输入m:");?
scanf("%d",m);
????
printf("数到第k个人，该人出列，请输入k:");?
scanf("%d",k);
for(i=0;in;i++)???//生成人员的序号
{???a=a+1;
ListInsert(head,i,a);
}
printf("人员序号为：");??//输出人员的序号
for(i=0;in;i++)
{
ListGet(head,i,x);
printf("%d?",x);
}
printf("\n");
printf("人员出列顺序为：");
????yuesefu(head,n,m,k);
printf("\n");
}
约瑟夫环（单循环链表）
m个人围成一个圈，指定一个数字n,从第一个人开始报数，每轮报到n的选手出局，由下一个人接着从头开始报，最后一个人是赢家。其中m1，n2。
用一个不带头节点的循环链表来处理，先构成一个有m个节点的单循环链表，然后由n节点开始计数，每计数到n时对应节点从链表中删除，然后再从删除节点的下一个节点又从1开始计数，直到最后一个节点从链表中删除算法结束。
1.创建一个空指针first，这个first暂时不动，只指向第一个加入进来的对象。
2.先创建第一个节点，并用first指向它，同时它的next是它自己，形成一个闭环。同时创建一个currentNode节点指向最后一个节点，为增加其它节点做准备。
3.加入其它节点时，首先将currentNode的next设置为新的节点node，然后把新节点的next指向回没有动的first节点形成闭环，最后将currentNode指向新的节点。
建立一个重要的指针helper，辅助弹出功能
first 当前计数的节点，helper则指向first的上一个节点
first和helper指针同时前移的时候，first数到对应的数字n,helper还是到它的前一个。弹出first后，first前移以为，helper的next指向first，就弹出了对应的那个节点