欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-08-18 09:19:15
这里放出两种不同的代码,一个是老师给的(较为复杂),还有一个是自己写的。 自己写的: 测试代码: 其实原理很简单,就是通过循环链表不断循环然后删除就OK 标准代码: 测试代码 ......

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

自己写的:

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