约瑟夫环的c++实现
//约瑟夫环
#include<iostream>
using namespace std;
template<class T>
struct Node //结点结构
{
T data; //结点数据
Node<T> *next;
};
template<class T>
class linklist//循环链表
{
Node<T> *current, *front;
public:
linklist() :current(NULL), front(NULL) {}//无参构造
linklist(T a[], int maxsize)//有参构造
{
int i;
Node<T> *p;
current = new Node<T>;
current->data = a[maxsize - 1];
front = current;
for (i = maxsize - 2; i >= 0; i--)//前移
{
p = new Node<T>;
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<class T>
linklist<T>::~linklist()
{
while (current != front)
{
Node<T> *r = current;
current = current->next;
delete r;
}
delete current;
}
template<class T>
bool linklist<T>::insert(T &x)
{
Node<T> *s = new Node<T>;
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<class T>
T linklist<T>::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<class T>
void linklist<T>::Output()
{
if (!current)//循环链表为空
return;
Node<T> *p = current;
do
{
cout << p->data << " ";
p = p->link;
} while (p != current);
cout << endl;
}
template<class T>
void linklist<T>::move(int t)
{
for (int i = 1; i <= t; i++)
{
front = current; // front后移
current = current->next; //current后移
}
}
template<class T>
bool linklist<T>::toLocatioin(T &t)//将current指向元素为t的结点,若没有则current不移动
{
if (!current)//循环链表为空
return false;
Node<T> *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<int> 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;
}
测试结果: