约瑟夫环问题 用C语言数据结构数组实现....

#include
using namespace std;
struct Node//循环节点的定义
{
int number;//编号
Node *next;
};
Node *CreateList(Node *L,int &n,int &m);//建立约瑟夫环函数
void Joseph(Node *L,int n,int m);//输出每次出列号数函数
Node *DeleteList(Node **L,int i,Node *q);//寻找每次出列人的号数
int LengthList(Node *L);//计算环上所有人数函数
void main()//主函数
{
Node *L;
L=NULL;//初始化尾指针
int n, m;
cout<<"请输入人数N：";
cin>>n;//环的长度
if(n<1){cout<<"请输入正整数!";}//人数异常处理
else
{
cout<<"请输入所报数M：";
cin>>m;
if(m<1){cout<<"请输入正整数!";}//号数异常处理
else
{
L=CreateList(L,n,m);//重新给尾指针赋值
Joseph(L,n,m);
}
}
system("pause");
}
Node *CreateList(Node *L,int &n,int &m)//建立一个约瑟夫环（尾插法）
{
Node *q;
for(int i=1;i<=n;i++)
{
Node *p;
p=new Node;
p->number=i;
p->next=NULL;
if(i==1) L=q=p;//工作指针的初始化
else
{
q->next=p;
q=q->next;
}
}
q->next=L;
if(L!=NULL){return(L);}//返回尾指针
else cout<<"尾指针异常!"<}
void Joseph(Node *L,int n,int m)//输出每次出列的人
{
int k;
cout<<"请输入第一个报数人：";
cin>>k;
if(k<1||k>n){cout<<"请输入1-"<else
{
cout<<"\n出列顺序:\n";
for(int i=1;i{
Node *q = new Node;
if(i==1) q=DeleteList(&L,k+m-1,q);//第一个出列人的号数
else q=DeleteList(&L,m,q);
cout<<"号数："<number<delete q;//释放出列人的存储空间
}
cout<<"最后一个出列号数是："<number<}
}
Node *DeleteList(Node **L,int i,Node *q) //寻找每次出列的人
{
if(i==1) i+=LengthList(*L);//顺序依次出列情况的处理方式
Node *p;
p=*L;
int j=0;
while(jnext;j++;}
q = p->next;
p->next=p->next->next;
*L = p->next;
return(q);
}
int LengthList(Node *L)//计算环上的人数
{
if(L){cout<<"尾指针错误!"<else
{
int i=1;
Node *p=L->next;
while(p!=L)
{
i++;
p=p->next;
}
return(i);
}
}

0