循环链表

p people sitting around a table and count from 1 to m. the one counts m will be kicked

out, output the order of them.

 

 

#include <stdio.h>
#include <iostream>
using namespace std;

class PeopleOnTable
{
public:
    int id;
    bool status;  // FALSE means quit
    PeopleOnTable *next;
    PeopleOnTable(int _id);
    ~PeopleOnTable();
protected:
private:
};

PeopleOnTable::PeopleOnTable(int _id)
{
    id = _id;
    status = 1;    
    next = NULL;
}

PeopleOnTable::~PeopleOnTable()
{
    cout << "deconstruction \n";
}

class CircleTable
{
public:
    PeopleOnTable *ptr; // indicate current people
    PeopleOnTable *head;
    CircleTable();
    ~CircleTable();

};

CircleTable::CircleTable()
{
    head = NULL;
    ptr = NULL;
}

CircleTable::~CircleTable()
{
    PeopleOnTable *_ptr = ptr;
    PeopleOnTable *temp_ptr;
    while(_ptr)
    {
        temp_ptr = _ptr->next;
        _ptr = _ptr->next;
        delete temp_ptr;
    }
}


void main()
{
    CircleTable *tab = new CircleTable();
    tab->head = new PeopleOnTable(0);
    tab->ptr = tab->head;
    int p = 10;
    for (int i = 1; i < p; i++)
    {
        tab->ptr->next = new PeopleOnTable(i);
        tab->ptr = tab->ptr->next;
    }
    tab->ptr->next = tab->head;

    int m = 3;    // 1~3报数
    int cnt;    // 报的数
    int c = 0;  // 一共p个人，所以一共只要p个人出局就结束循环。
    PeopleOnTable *call = tab->head;
    while(c < p)
    {
        cnt = 0;
        while(1)
        {
            if (call->status == 1)
            {
                cnt++;
            }
            if (cnt == m)    // 一轮报数结束
            {
                break;
            }
            call = call->next;
        }

        cout << call->id << "\n";
        call->status = 0;
        
        c++;
    }
    
}