（一）基本问题
1.问题描述
设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。建立模型，确定存储结构。对任意n个人，密码为m，实现约瑟夫环问题。
2.数据结构设计
首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：
struct Node
{
    int data;
    Node *next;
};
其次，建立一个不带头结点的循环链表并由头指针first指示
3.算法设计
1、工作指针first，r，s，p，q初始化
2、输入人数（n）和报数（m）
3、循环n次，用尾插法创建链表
        Node *q;
          for(int i=1;i<=n;i++)
          {
          Node *p;
          p=new Node;
          p-> data =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);}
      4、输入报数的起始人号数k;
      5、Node *q = new Node;计数器初始化i=1;
6、循环n次删除结点并报出位置（其中第一个人后移k个）
  当i<n时
      移动指针m-2次p=p->next;
      删除p结点的后一结点q
q=p->next;
            p->next=q->next;
            *L = p->next;
            报出位置后Delete q;
      计数器i++;
运行流程图
代码和相关解释
c语言listinsert函数
#include<iostream>
using namespace std;
struct Node//循环节点的定义
{
int data;//编号
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()//主函数
//在主函数中，完成人数（n）和报数（m）的输入和工作指针的初始化
{ 
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->data=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->data<<endl;
  delete q;//释放出列人的存储空间
  }
  cout<<"最后一个出列号数是："<<L->data<<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);

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。