约瑟夫环的c++实现

概述本文章向大家介绍约瑟夫环的c++实现，主要包括约瑟夫环的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;

}

测试结果：

总结

以上是内存溢出为你收集整理的约瑟夫环的c++实现全部内容，希望文章能够帮你解决约瑟夫环的c++实现所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。