约瑟夫环的c++实现

//约瑟夫环

#include

using namespace std;

template

struct Node //结点结构

{

T data; //结点数据

Node *next;

};

template

class linklist//循环链表

{

Node *current,*front;

public:

linklist() :current(NULL),front(NULL) {}//无参构造

linklist(T a[],int maxsize)//有参构造

{

int i;

Node *p;

current = new Node;

current->data = a[maxsize - 1];

front = current;

for (i = maxsize - 2; i >= 0; i--)//前移

{

p = new Node;

p->data = a[i];

p->next = current;

current = p;

}

front->next = current;

}

~linklist();//析构

bool insert(T &x);//插入

T Delete(T &x);//删除

void Output();//输出元素

bool toLocatioin(T &t);//定位元素

void move(int t);//后移

T GetCurrentData() { return current->data; }//返回

};

template

linklist::~linklist()

{

while (current != front)

{

Node *r = current;

current = current->next;

delete r;

}

delete current;

}

template

bool linklist::insert(T &x)

{

Node *s = new Node;

s->data = x;

if (!s)

return false;

if (!current) //原循环链表为空

current = front = s->next = s;

else //原循环链表非空

{

s->next = current->next;

current->next = s;

front = current;

current = s;

}

return true;

}

template

T linklist::Delete(T &x)

{

if (!current)//循环链表为空

return false;

x = current->data;

if (current == front)//链表中只有一个元素

{

delete current;

current = front = NULL;

}

else

{

front->next = current->next;//修改链表指针

delete current;

current = front->next;

}

return true;

}

template

void linklist::Output()

{

if (!current)//循环链表为空

return;

Node *p = current;

do

{

cout << p->data << " ";

p = p->link;

} while (p != current);

cout << endl;

}

template

void linklist::move(int t)

{

for (int i = 1; i <= t; i++)

{

front = current; // front后移

current = current->next; //current后移

}

}

template

bool linklist::toLocatioin(T &t)//将current指向元素为t的结点，若没有则current不移动

{

if (!current)//循环链表为空

return false;

Node *current1 = current,*front1 = front;

while (current1->data != t) //寻找元素t

{

front1 = current1;

current1 = current1->next;

if (current1 == current)// 已寻找一圈没有元素为t的结点

return false;

}

current = current1; //current指向元素为t的结点

front = front1;

return true;

}

class Joseph // 约瑟夫环类

{

private:

int numOfBoy; //圈中人数

int startPosition; //报数起始点

int interval; //报数间隔

public:

Joseph(int boys,int start,int m) :numOfBoy(boys),startPosition(start),interval(m) {}//构造函数

void setNumOfBoy(int num) { numOfBoy = num; }//重置圈中人数

void setStartPosition(int start) { startPosition = start; }//重置起始点

void setInterval(int inter) { interval = inter; }//重置报数间隔

int GetWinner();//求得最终优胜者编号

void print(); //输出约瑟夫环

};

int Joseph::GetWinner()

{

linklist boys;

for (int i = 1; i <= numOfBoy; i++)//创建循环链表,编号依次为1~numOfBoy

{

boys.insert(i);

}

boys.toLocatioin(startPosition); //找到报数起点

cout << endl << "依次出列的小孩是：" << endl;

for (int i = 1; i < numOfBoy; i++) //numOfBoy-1个小孩出圈

{

int x;

boys.move(interval - 1); //报数

boys.Delete(x); //出圈

cout << x << " "; //输出出圈编号

}

return boys.GetCurrentData(); //返回优胜者编号

}

void Joseph::print() //输出约瑟夫环

{

cout << "圈中人数:" << numOfBoy << endl;

cout << "报数起始点:" << startPosition << endl;

cout << "报数间隔:" << interval << endl;

}

int main()

{

int total,interv,startboy;

cout << "请输入初始数据：小孩数，起始小孩号码，间隔数：n";

cin >> total >> startboy >> interv;

Joseph jose(total,startboy,interv);

jose.print();

cout << "优胜者编号为： " << jose.GetWinner() << endl;

system("pause");

return 0;

}

测试结果：

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!