约瑟夫环 问题描述：约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 基本要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 测试数据 M的初值为20；n=7，7各人的密码依次为3，1，7，2，4，8，4，首先m值为6（正确出栈顺6，1，4，7，2，3，5） 下面是代码

1 #include
     
       2 #include
      
        3 using namespace std;  4 struct node  5 { 6    int no; //代表编号结点的数据 7    int code;//代表密码结点的数据 8    node *next;//代表后一个结点的地址 9 };10 int main() 11 { 12    int m,n,i,j;13    node *p,*q,*first;14    cout<<"请输入m的初始值 m:";15    cin>>m;16    cout<<"请输入人数 n:";17    cin>>n;18    for(i=1;i<=n;i++)19    {20         if(i==1)21         {22             first=p=(node*)malloc(sizeof(node));23             if(p==0)24                 return 0;25         }26         else27         {28             q=(node*)malloc(sizeof(node));29             if(q==0)30                 return 0;31             p->next=q;32             p=q;33         }34         cout<<"请输入第 "<
       <<" 个人的密码: ";35         cin>>(p->code);36         p->no=i;37    }38    p->next=first; //让表尾指向表头形成循环链表39    p=first;40    cout<<"出列顺序为: ";41    for (j=1;j<=n;j++)42    {43         for(i=1;i
        
         next);44         m=p->code;45         cout<
         
          no<<" ";46         p->no=p->next->no;47         p->code=p->next->code;48         q=p->next;49         p->next=p->next->next;50         free(q);51    }52    cout<
         
        
      
     

简单约瑟夫问题，即从0开始删除第m个数字，直至只剩最后一个数字。

方法一：自己构建循环链表，时间复杂度O(MN)，空间复杂度O(N)。

1 #include 
     
       2 using namespace std; 3 typedef struct node 4 { 5     int data; 6     struct node *next; 7 }list; 8 int main () 9 {10     int n,m;11     cin>>n>>m;12     list *p,*q,*first;13     for(int i=0;i
      
       data = 0;19             p = first;20             if(p==NULL)21                 return ;22         }else{23             q = (list*)malloc(sizeof(list));24             q->data = i;25             p->next=  q;26             p = q;27         }28     }29     p->next = first;30     p = first;31     int c ;32     for(int i=1;i
       
        next);35         c = p->data;36         cout<
        
         <
         
          data = p->next->data;38         q = p->next;39         p->next = p->next->next;40         free(q);　　　　　　//  记得释放空间41     }42     cout<
          
           data<
          
         
        
       
      
     

方法二：用C++中STL库的list来模拟循环链表，每当迭代器扫描到链表末尾的时候就把迭代器移到链表的头部。

1 #include 
     
       2 #include 
      
        3 using namespace std; 4  5  6 int main() 7 { 8     int n,number; 9     cin>>n>>number;10     list
       
         *table = new list
        
         ();11     for(int i=0;i
         
          push_back(i);13     14     int last = 0;15     int count = 1;16     list
          
           ::iterator current = num.begin();17 while(num.size()>1)18 {19 for(int i=1;i
           

::iterator next = ++current;26 if(next == num.end())27 next = num.begin();28 --current;29 num.erase(current);30 current = next;31 }32 33 cout<<*current<