【数据结构】1-2 约瑟夫环问题

这里放出两种不同的代码，一个是老师给的（较为复杂），还有一个是自己写的。

自己写的：

#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;
}