循环链表：约瑟夫环问题

问题：已知n个人（以编号1，2，3，……，n 分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列，他的下一个人又从1开始报数，数到m的那个人又出列，依此规律重复下去，直到圆桌周围的人全部出列。


//////////////list.h/////////////
#include
using namespace std;
typedef struct Lnode
{
Lnode *next;
int data;
}Lnode,*Lnodelist;

class List
{
protected:
    int m_len;
    Lnode* m_pHead;   
    int begin;
    int interval;

public:
    List(int n ,int k ,int m );
    ~List();
    void Print();
    int JOSEPHUS();
   
};


////////////////////list.cc/////////////////
#include"list.h"
List::List(int n ,int k ,int m):m_len(0),begin(k),interval(m)
{   
    m_pHead = new Lnode;
    if(m_pHead)
    {
        m_pHead->next = m_pHead;
    }
    Lnode* pTemp = m_pHead->next;
    for(int i = 0 ; i < n ; i++ )
    {
        Lnode* pNew = new Lnode;
        if(pNew)
        {   
            pNew->data = i+1;
            pTemp->next = pNew;       
        }
        pTemp = pTemp->next ;
        pNew = NULL;
    }
    pTemp->next = m_pHead;
    m_len = n;
    Print();
}
List::~List()
{
    if(m_len)
    {   
       
        while(m_pHead->next != m_pHead )
        {
            Lnode* pTemp = m_pHead->next;
            m_pHead = m_pHead->next;
            delete pTemp;
            pTemp = NULL;
        }
    m_len=0;
    }           
}

void List::Print()
{
    if(0 == m_len)
    {
        cout<<"Print error!"<    }
    Lnode *pTemp = m_pHead->next;
    while (m_pHead != pTemp) 
    {
        cout<data<<" ";
        pTemp = pTemp->next;
    }
    cout<    pTemp = NULL;
}
int List::JOSEPHUS()
{   
    if(!m_len)
    {
        cout<<"JOSEPHUS error!"<        return 0;
    }
    Lnode* pTemp = m_pHead;
    Lnode* pDelete = NULL;
    for(int i = 0 ; i < begin-1 ;  )
    {
        if(pTemp == m_pHead)
        {
        pTemp = pTemp->next;
        continue;
        }
        pTemp = pTemp->next;
        i++;
    }
    cout<data<    while(m_len)
    {
        for(int j = 0 ; j < interval-1 ;  )
        {
            if(pTemp == m_pHead)
            {
            pTemp = pTemp->next;
            continue;
            }
           
            pTemp = pTemp->next;
            j++;
        }
    if(pTemp->next == m_pHead)
    {
    pDelete = pTemp->next->next;
    m_pHead->next = m_pHead->next->next;
    }
    else
    {
    pDelete = pTemp->next;
    pTemp->next = pTemp->next->next;
    }
    m_len--;
    cout<data<    pDelete = NULL;
    }
}

////////////////////main.cc/////////////////
#include"list.h"
int main()
{
List list(20,5,4);
list.JOSEPHUS();
return 0;
}


///////////////Makefile///////////////
CC=g++
main:list.o main.o
list.o:list.h
main.o:list.h
    $(CC) -c main.cc
.PHONE: clean
clean:
    -rm -f main *.o *~


/////////////////结果//////////////
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
5
9
13
17
1
5
10
15
20
6
12
19
7
16
4
18
11
8
14
2
3