约瑟夫问题（C++面向对象--单循环链表实现）

注

本代码只实现了单循环链表的部分操作
参考教材：数据结构（面向对象方法与 C++ 语言描述）（第二版）

//约瑟夫问题（C++面向对象--单循环链表实现）
#include<iostream>
#include<cstdlib>
using namespace std;

template<class T>
struct CircleLinkNode {
    T data;
    CircleLinkNode<T> *link;
    CircleLinkNode<T>(CircleLinkNode<T>*ptr=NULL):link(ptr) {};
    CircleLinkNode<T>(T x,CircleLinkNode<T>*ptr=NULL):data(x),link(ptr) {};
};

template<class T>
class CircleList {
    public:
        CircleList();
        CircleList(T x);//复制构造函数
        bool Insert(T &x);//尾插法插入
        bool Remove(T &x);
        CircleLinkNode<T> *getHead() const {
            return first;
        };
        CircleLinkNode<T> *Locate(int i);
        void output();
    protected:
        CircleLinkNode<T> *first;
        CircleLinkNode<T> *last;
};//定义类

template<class T>
CircleList<T>::CircleList(){
    first = new CircleLinkNode<T>;
    first->link = first;
    last = first;
}

template<class T>
CircleList<T>::CircleList(T x){
    first = new CircleLinkNode<T>(x);
    first->link = first;
    last = first;
}

template<class T>
bool CircleList<T>::Insert(T &x) {
    CircleLinkNode<T> *newNode = new CircleLinkNode<T>(x);
    if(newNode == NULL) {
        cout<<"内存分配错误！\n";
        return false; 
    }
    newNode->link = last->link;
    last->link = newNode;
    last = newNode;
    return true;
}

template<class T>
bool CircleList<T>::Remove(T &x) {
    CircleLinkNode<T> *cur = first->link;
    while(cur->link->data != x){
        cur = cur->link;
    }
    CircleLinkNode<T> *tmp = cur->link;
    cur->link = tmp->link;
    delete tmp;
    return true;
}

template<class T>
CircleLinkNode<T> *CircleList<T>::Locate(int i){
    if(i<=0) return NULL;
    CircleLinkNode<T> *cur = first;
    for(int k=1;k<i;k++){
        if(cur == NULL) break;
        else cur = cur->link;
    }
    return cur;
}

template<class T>
void solveJosephus(CircleList<T> &CL,int n,int m) {
    CircleLinkNode<T> *cur = CL.Locate(1),*pre= NULL;
    for(int i=0; i<n-1; i++) {
        for(int j=1; j<m; j++) {
            pre = cur;
            cur = cur->link;
        }
        cout<<"出队的人是："<<cur->data<<endl;
        pre->link = cur->link;
        delete cur;
        cur = pre->link;
    }
    cout<<endl<<"胜出的人是："<<cur->data<<endl; 
}

template<class T>
void CircleList<T>::output(){
    CircleLinkNode<T> *cur = first->link;
    while(cur!=first){
        cout<<cur->data<<" ";
        cur = cur->link ;
    }
}

int main() {
    CircleList<int> josephus(1);
    int n,m;
    cout<<"请输入数据的个数和循环的个数"<<endl;
    cin>>n>>m;
    for(int i=2; i<=n; i++){
        josephus.Insert(i);
    }
    josephus.output();
    solveJosephus(josephus,n,m) ;
    return 0;
}