SZUOJ - 约瑟夫环 —— 循环链表

一、题面

二、题解 

使用无头结点的循环链表

三、实现代码

#include <iostream>

using namespace std;

class Node{
public:
    int data;
    Node* next;
    Node(){
        next=NULL;
    }
};

class Joseph{
    Node* root;
    int n;
    int k;
    int s;
public:
    Joseph(int _n,int _k,int _s){
        int i;
        Node* p;
        Node* q;
        root=new Node;
        root->data=1;
        q=root;
        //cin>>n>>k>>s;
        n=_n;
        s=_s;
        k=_k;
        for(i=2;i<=n;i++){
            p=new Node;
            p->data = i;
            q->next=p;
            q=p;
        }
        q->next=root;
    }

    void Count(){
        int i,val;
        Node *p,*q,*sp;
        p=root;
        for(i=1;i<s;i++){
            sp=p;
            p=p->next;
        }
        while(1){
            if(p->next == p) break;
            for(i=1;i<k;i++){
                sp=p;
                val=p->data;
                p=p->next;
            }
            cout<<p->data<<" ";
            sp->next=p->next;
            p=p->next;
        }
        cout<<p->data<<" "<<endl;
    }
};

int main(){
    int n,k,s;
    while(cin>>n>>k>>s){
        Joseph J(n,k,s);
        J.Count();
    }
    return 0;
}