前天笔试有个约瑟夫环的问题，怪不得人家没通知我面试，原来我的约瑟夫环做的确实有问题，昨天晚上又重新做了下，下面上源代码：

    /*

    file:osephu.cpp author:www.5dkx.com

    */

    #include <iostream>

    using namespace std;

    typedef struct Node{

    int sort;

    struct Node *next;

    }Link,*List;

    int Init(List *p); //初始化双链表

    int Insert(List *p,int key); //插入节点

    void Print(List p); //打印双链表

    void CreateOsep(List p,int n); //初始化约瑟夫环void osehup(List p,int m,int len,List Re); //计算约瑟夫环出列顺序，并存放在Re链表中

    int main()

    {

    int m,n;

    List p,Re;

    Init(&p);

    Init(&Re);

    cout<<"输入环大小: ";

    cin>>n;

    cout<<"输入地几个人出列: ";

    cin>>m;

    CreateOsep(p,n);

    cout<<"输入为: "<<endl;

    Print(p);

    osehup(p,m,n,Re);

    cout<<"出队顺序为:"<<endl;

    Print(Re);

    return 1;

    }

    //初始化

    int Init(List *p)

    {

    *p = (List)malloc(sizeof(Link));

    if(!(*p))

    {

    cout<<"初始化失败!"<<endl;

    return 0;

    }

    else

    {

    (*p)->next=*p;

    //(*p)->sort=1;

    }

    return 1;

    }

    //插入节点

    int Insert(List *p,int key)

    {

    List tmp = (List)malloc(sizeof(Link));

    if(!tmp)

    {

    cout<<"创建节点失败!"<<endl;

    return 0;

    }

    else

    {

    tmp->sort=key;

    tmp->next=(*p)->next;

    (*p)->next=tmp;

    *p=tmp;

    }

    return 1;

    }

 //创建约瑟夫环

    void CreateOsep(List p,int n)

    {

    List tmp=p;

    tmp->sort=1;

    for(int i=2;i<=n;i++)

    Insert(&tmp,i);

    }

    //约瑟夫环算法

    void osehup(List p,int m,int len,List Re)

    {

    int count=0;

    int allc=0;

    List tmp1=p;

    List tmp2=Re;

    List temp;

    while(allc<len)

    {

    count++;

    if(count == m)

    {

    temp = tmp1->next;

    if(allc==0) //如果是第一次出列

    tmp2->sort=temp->sort;

    else

    Insert(&tmp2,temp->sort);

    tmp1->next=tmp1->next->next;

    // cout<<temp->sort<<" ";

    free(temp);

    temp=NULL;

    allc++;

    count=0;

    }

    else

    {

    tmp1=tmp1->next;

    }

    }

    cout<<endl;

    }

    //打印链表

    void Print(List p)

    {

    List tmp=p->next;

    cout<<p->sort<<" ";

    while(tmp!=p)

    {

    cout<<tmp->sort<<" ";

    tmp=tmp->next;

    }

    cout<<endl;

    }

    运行后效果为：

    输入环大小: 5

    输入地几个人出列: 6

    输入为:

    1 2 3 4 5

    出队顺序为:

    2 4 3 1 5

    Press any key to continue