约瑟夫环问题源代码(C语言).doc

约瑟夫环问题如下：已知n个人(n>=1)围桌一园桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列。他的下一个人又从1开始报数，数到m的那个人又出列。依此规则重复下去，直到所有人全部出列。求解最后一个出列的人的编号。
本次实验是以顺序表求解约瑟夫环问题，程序流程图及程序运行结果如下：
存储并建立一个约瑟夫环
通过循环结构依次查找每次出列的人的编号并输出

输入人数、所报数、第一个报数人编号

输出最后一个出列的人的编号

程序代码如下：
#include<iostream>
#include<process.h>
#include<stdlib.h>
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() //主函数
{
system("color 75"); //设置颜色以美观
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<<"尾指针异常!"<<endl; //尾指针异常处理
}

void Joseph(Node *L,int n,int m) //输出每次出列的人
{
int k;
cout<<"请输入第一个报数人：";
cin>>k;
if(k<1||k>n){cout<<"请输入1-"<<n<<"之间的数"<<endl;}
else
{
cout<<"\n出列顺序:\n";

for(int i=1;i<n;i++)
{
Node *q = new Node;
if(i==1) q=DeleteList(&L,k+m-1,q); //第一个出列人的号数
else q=DeleteList(&L,m,q);
cout<<"号数："<<q->number<<endl;
delete q; //释放出列人的存储空间
}
cout<<"最后一个出列号数是："<<L->number<<endl; //输出最后出列人的号数
}
}

Node *DeleteList(Node **L,int i,Node *q) //寻找每次出列的人
{
if(i==1) i+=LengthList(*L); //顺序依次出列情况的处理方式
Node *p;
p=*L;
int j=0;
while(j<i-2) {p=p->next;j++;}
q = p->next;
p->next=p->next->next;
*L = p->next;
return(q);
}

int LengthList(Node *L) //计算环上的人数
{
if(L){cout<<"尾指针错误!"<<endl;} //异常处理
else
{
int i=1;
Node *p=L->next;
while(p!=L)
{
i++;
p=p->next;
}
return(i);
}
}

实验体会：
通过对本问题的分析，我进一步熟悉了对各种逻辑表达式的判断和指针的使用。
本程序分为输入模块、处理模块、输出模块，主函数按运行流程依次调用各方法。本程序可以很好地运行，还具有一定的排错能力，稳定性好，如下图所示：