【BUCT数据结构类库】1.4--约瑟夫问题

#include
#include
using namespace std;

// 约瑟夫问题
//循环链表
typedef struct node{
    int data;
    node *next;
}*linklist;

// 初始化循环链表
void init_linklist(linklist &L){
   L=new node;
   L->next=L;
}

// 判断循环链表是否为空
bool is_empty(linklist L){
    return L->next==L;
}

// 在循环链表L的第i个位置插入元素e(i=1时，插入在链表头)
void insert_linklist(linklist &L, int i, int e){
    linklist p=L;
    linklist s=new node;
    s->data=e;
    s->next=NULL;
    if(i==1){
        L->data=e;
    }else{
        for(int j=1;jnext;  
        }
        s->next=p->next;
        p->next=s;
    }
}


int main(){
    linklist L;
    init_linklist(L);
    int num,interval;
    int kill=0;
    cin>>num>>interval;
    for(int i=1;i<=num;i++){
        insert_linklist(L,i,i);
    }
    linklist p=L;
    while (p->next!=L)
    {
        p=p->next;
    }
    cout<<"不幸遇难的人为：";
    while(p->next!=p){
        if(kill==num-interval){
            cout<<"存活的人为：";
           while(interval--){
               cout<data<<" ";
                p=p->next;
           }
           return 0;
        }
        for(int i=1;i<=interval;i++){
            p=p->next;
        }
        cout<next->data<<" ";
        kill++;
        p->next=p->next->next;
    }
}