Question

c语言实现约瑟夫环

利用带头结点单链表解决 约瑟夫环问题

Answer 1

用指针实现的循环单链表。
#include <iostream>
using namespace std;

struct Node
{
int m,num;//m是密码，num是他的编号
Node *next;
};

Node *head;
int M,N;

void Build()
{
cin>>N>>M;
Node *p=head;
for(int i=1;i<=N;i++)
{
Node *tmp=new Node;
cin>>tmp->m;
tmp->num=i;
if(i==1)head=p=tmp;
else p->next=tmp;
p=tmp;
}
p->next=head;
}

Node* Move(int step,Node* from)
{
Node *p=from;
for(int i=0;i<step;i++)
p=p->next;
return p;
}

void GO()
{
Node *p=head;
int step=M-1;
for(int i=1;i<N;i++)
{
p=Move(step-1,p);
step=p->next->m;
cout<<p->next->num<<endl;
p->next=p->next->next;
}
cout<<p->num<<endl;
}

int main()
{
Build();
GO();
return 0;
}

追问

用头插入法建表

追答

头插入法如下：
#include
using namespace std;

struct Node
{
int m,num;//m是密码，num是他的编号
Node *next;
};

Node *head;
int M,N;

void Build()
{
cin>>N>>M;
Node *p=head;
for(int i=1;i>tmp->m;
tmp->num=i;
if(i==1)
{
head=p=tmp;
p->next=NULL;
}
else
{
tmp->next=head;
head=tmp;
}
}
p->next=head;
}

Node* Move(int step,Node* from)
{
Node *p=from;
for(int i=0;inext;
return p;
}

void GO()
{
Node *p=head;
int step=M-1;
for(int i=1;inext->m;
coutnext->numnext=p->next->next;
}
coutnum<<endl;
}

int main()
{
Build();
GO();
return 0;
}