商联通卡官网,音速希希,光能使者国语
这里放出两种不同的代码，一个是老师给的（较为复杂），还有一个是自己写的。
自己写的：
我要评论#include<iostream>
using namespace std;
struct node {
int data; //数据单元
node *link; //指向下一个结点
};
class josephus
{
private:
node *head, *current; //head是头结点，current指向当前结点
int sum;//存储链表中元素的个数
public:
josephus(); //无参构造函数，全部初始化为空
josephus(int snumber, int strnumber);//有参构造函数，snumber为总数，strnumber为开始序号
~josephus();//析构函数
void del(node *&p);
void select(int num);//num为间隔数
void print();
};
josephus::josephus()
{
current = null;
head = null;
sum = 0;
}
josephus::josephus(int snumber, int strnumber)
{
sum = snumber;
head = new node;
head->data = strnumber;
current = head;
int dt = strnumber + 1;
for (int i = 1; i < snumber; i++)
{
node *p;
p = new node;
p->data = dt;
current->link = p;
current = p;
dt++;
}
current->link = head;
}
void josephus::del(node *&p)
{
node *d = p->link;
p->link = p->link->link;
delete d;
}
void josephus::select(int num)
{
int sont = 1;
node *p = head;
while (sum!= 1)
{
if (sont % (num-1) == 0)
{
del(p);
sum--;
head = p;
}
sont++;
p = p->link;
}
}
void josephus::print()
{
cout << "剩下的序号有：" << endl;
node *p = head;
for (int i = 0; i < sum; i++)
{
cout << p->data << " ";
p = p->link;
}
cout << endl;
}
josephus::~josephus()
{
/*node *p = head->link;
while (p!=head)
{
node *de = p;
p = p->link;
delete de;
}*/
head = null;
current = null;
}
测试代码：
#include"linklist.h"
int main()
{
int snum, stnum,num;
cout << "请输入总数以及开始序号:";
cin >> snum >> stnum;
josephus a(snum, stnum);
a.print();
cout << "请输入间隔数:";
cin >> num;
a.select(num);
a.print();
system("pause");
return 0;
}
其实原理很简单，就是通过循环链表不断循环然后删除就ok
标准代码：
//circle.h
#include<iostream>
using namespace std;
template<class t>
struct node //结点结构
{
t data; //结点数据
node*link;
node() { link = null; }
node(t e, node*next = null)
{
data = e;
link = next;
}
};
template<class t>
class circlelinklist
{ //不带表头结点的循环链表类
private:
node<t> *current, *front; //current指向某结点，front指向current前驱
public:
circlelinklist() :current(null), front(null) {} //构建空循环链表
circlelinklist(t *d, int msize); //利用d数组元素构建循环链表
~circlelinklist(); //析构函数
bool insertafter(const t&x); //在current所指结点之后插入x
bool removecurrent(t&x); //删除current所指结点
void movenext(int n = 1); //current后移n次
t getcurrentdata() { return current->data; }
bool tolocatioin(t &t);//让current指向t结点，若没有则current不移动
void output() const; //输出循环链表
};
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(); //输出约瑟夫环
};
template<class t>
circlelinklist<t>::circlelinklist(t *d, int msize)
{ //构造函数,将d数组中的msize个元素创建循环链表
//采用前插法创建。
int i;
node<t> *p;
current = new node<t>;
current->data = d[msize - 1];
front = current;
for (i = msize - 2; i >= 0; i--)
{
p = new node<t>(d[i], current);
current = p;
}
front->link = current;
}
template<class t>
circlelinklist<t>::~circlelinklist() //析构函数
{
while (current != front)//销毁循环链表
{
node<t> *r = current;
current = current->link;
delete r;
}
delete current;
}
template<class t>
bool circlelinklist<t>::insertafter(const t&x)
//在current所指结点之后插入x,current指向x结点
{
node<t> *s = new node<t>(x);
if (!s)return false;
if (!current) //原循环链表为空
current = front = s->link = s;
else //原循环链表非空
{
s->link = current->link;
current->link = s;
front = current;
current = s;
}
return true;
}
template<class t>
bool circlelinklist<t>::removecurrent(t&x) //删除current所指结点
{
if (!current)//循环链表为空
return false;
x = current->data;
if (current == front)//链表中只有一个元素
{
delete current;
current = front = null;
}
else
{
front->link = current->link;//修改链表指针
delete current;
current = front->link;
}
return true;
}
template<class t>
void circlelinklist<t>::output() const //输出循环链表
{
if (!current)//循环链表为空
return;
node<t> *p = current;
do
{
cout << p->data << " ";
p = p->link;
} while (p != current);
cout << endl;
}
template<class t>
void circlelinklist<t>::movenext(int k) //current后移k次
{
for (int i = 1; i <= k; i++)
{
front = current; // front后移
current = current->link; //current后移
}
}
template<class t>
bool circlelinklist<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->link;
if (current1 == current)// 已寻找一圈没有元素为t的结点
return false;
}
current = current1; //current指向元素为t的结点
front = front1;
return true;
}
int joseph::getwinner()//获得最终优胜者
{
circlelinklist<int> boys;
for (int i = 0; i < numofboy; i++)//创建循环链表,编号依次为1~numofboy
{
int temp = i + 1;
boys.insertafter(temp);
}
boys.tolocatioin(startposition); //找到报数起点
cout << endl << "依次出列的小孩是：" << endl;
for (int i = 1; i < numofboy; i++) //numofboy-1个小孩出圈
{
int x;
boys.movenext(interval - 1); //报数
boys.removecurrent(x); //出圈
cout << x << " "; //输出出圈编号
}
return boys.getcurrentdata(); //返回优胜者编号
}
void joseph::print() //输出约瑟夫环
{
cout << "圈中人数:" << numofboy << endl;
cout << "报数起始点:" << startposition << endl;
cout << "报数间隔:" << interval << endl;
}
测试代码
//测试代码.cpp
#include"circle.h"
int main()
{
int total, interv, startboy;
cout << "请分别输入人数，起始号码和间隔数"<<endl;
cin >> total >> startboy >> interv;
joseph jose(total, startboy, interv);
jose.print();
cout << "优胜者编号为： " << jose.getwinner() << endl;
system("pause");
return 0;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论