大二算法实验一用循环链表解决约瑟夫环

题目 约瑟夫（Joeph）问题的一种描述是：编号为 1,2,…,n 的 n 个人按顺时针方向围坐一圈， 每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从第一个人开始 按顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新 的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部 出列为止。试设计一个程序求出出列顺序。 [基本要求] 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 [测试数据] m 的初值为 20；密码：3，1，7，2，4，8，4（正确的结果应为 6，1，4，7，2，3，5）。 [实现提示] 程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设 n≤30。 分析： 1.此题我遇到的难点在于输出的是拥有密码的人的编号而不是他所持的密码，我刚开始想的是用数组记录拥有这个密码的人的编号，但这个方法在遇到两个重复的数字的时候就会失效，实际只要在结构体中多加一个数据即可。 2.循环链表的头结点容易出错，注意循环的方式。

#include<bits/stdc++.h>
using namespace std;
typedef struct node{
    int date;
    int shunxu;//用以储存编号
    struct node *next;
}Node;
int main(){
    int m,n,a[100000];
    cin>>n>>m;
    Node *head=NULL,*p=NULL,*r=NULL;
    head=(Node*)malloc(sizeof(Node));
    if(NULL==head){
        cout<<"Memory Failed";
        return 0;
    }//创建失败
    for(int i=1;i<=n;i++){cin>>a[i];
    
    }
    /*cout<<"*"<<endl;
    for(int i=1;i<=n;i++){cout<<a[i]<<endl;}
    cout<<"*"<<endl;*/
    p=head;//P指针指到头结点
    for(int i=1;i<=n;i++){
        //cin>>a;
        r=(Node*)malloc(sizeof(Node));
        r->date=a[i];
        r->shunxu=i;
        r->next=NULL;
        p->next=r;
        p=r;
    }
    p->next=head->next;//将末端指到头，形成循环链表，注意头结点没数据所以指到头结点的下一个
    p=head->next;//P指针指向第一个数据
    while(p->next!=p){
        for(int i=1;i<m;i++){//因为指向的是第一个数据相当于第一个人已经读过了
             r=p;
            p=p->next;//cout<<"#"<<p->date<<" ";
        }
        m=p->date;//cout<<p->date<<'$';
        cout<<p->shunxu;
        r->next=p->next;//删除结点
        p=p->next;
    }cout<<r->shunxu;
    

}