循环链表解决约瑟夫问题

呆呆打Dota

#include<iostream>
#include<cstdlib>
using namespace std;

//循环链表结点类的定义与实现
class CirListNode
{
        int data;
        CirListNode *Next;
public:
        CirListNode():Next(NULL){}
        CirListNode(int Value):data(Value),Next(NULL){}
        ~CirListNode(){};
        void SetNext(CirListNode *next);
        int GetData();
        CirListNode *GetNext();
};

void CirListNode::SetNext(CirListNode *next)
{
        Next=next;
}

int CirListNode::GetData()
{
        return data;
}

CirListNode* CirListNode::GetNext()
{
        return Next;
}


//循环链表的定义与实现
class CirList
{
        CirListNode *head;
        CirListNode *tail;
        CirListNode *cur;          //记录着当前被访问结点的位置
public:
        CirList();
        ~CirList(){};
        void AddTail(int data);
        int GetCount();
        void SetBegin();
        void RemoveThis();           //删除cur所指向的结点
        void RemoveAll();
        int  ListGetNext();               //返回当前结点中的数据，并使cur顺序移动一个位置
};

CirList::CirList()
{
        head=tail=new CirListNode;
        cur=NULL;
        head->SetNext(head);            //创建初始循环
}

void CirList::AddTail(int data)
{
        CirListNode *add=new CirListNode(data);
        tail->SetNext(add);
        tail=tail->GetNext();
        tail->SetNext(head);
}

int CirList::GetCount()
{
        int count=0;
        CirListNode *here=cur;
        while(cur->GetNext()!=here)
        {
                ++count;
                cur=cur->GetNext();
        }
        cur=cur->GetNext();
        return count;
}

void CirList::SetBegin()
{
        cur=head;
}

void CirList::RemoveThis()
{
        if(cur==head)
        {
                cur=cur->GetNext();         //表头结点不可删除
        }
        CirListNode *precur=cur;             //使precur指向cur的前一结点
        for(int i=0;i<GetCount();i++)
        {
                precur=precur->GetNext();
        }
        precur->SetNext(cur->GetNext());
        //删除后cur顺序移动一个结点
        cur=precur->GetNext();
        precur=NULL;
}

void CirList::RemoveAll()
{
        SetBegin();
        int length=GetCount();
        for(int i=0;i<length;i++)
        {
                RemoveThis();
        }
        cur=head;
}

int CirList::ListGetNext()
{
        if(cur==head)
        {
                cur=cur->GetNext();
        }
        int num=cur->GetData();
        cur=cur->GetNext();
        return num;
}

//利用循环链表解决约瑟夫问题

int main()
{
        CirList jos;
       
        for(int i=1;i<16;i++)
        {
                jos.AddTail(i);
        }
        jos.SetBegin();
        int length=jos.GetCount();
        for(int i=1;i<length;i++)
        {
                for(int j=0;j<3;j++)
                {
                        jos.ListGetNext();
                }
                jos.RemoveThis();
        }
        cout<<jos.ListGetNext()<<endl;
       
        system("pause");
        return 0;
}