数据结构总结系列（三）——循环链表之约瑟夫问题

印度阿三17 2019-06-01

展开全文

约瑟夫问题简介：

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。分析：（1）由于对于每个人只有死和活两种状态，因此可以用布朗型数组标记每个人的状态，可用true表示死，false表示活。（2）开始时每个人都是活的，所以数组初值全部赋为false。（3）模拟杀人过程，直到所有人都被杀死为止。（由于博主懒癌犯了导致随便截取了某度百科的内容，或许更新之后会用这种方法呢~~~）

我们现在确定了使用循环链表，那么就开始定义：

由于循环链表尾部指针指向头部，所以循环链表的定义和单链表一致，只有表示时有些许差别。

show code：

typedef struct node
{
    int data;
    struct node *next;//指向下一个节点
}LinkNode;

typedef LinkNode *RollList;//重定义了循环链表的头节点

插入：

void Creat(RollList &R,int length)
{
    RollList tmp=R;//这里修改了tmp，避免直接对头结点修改
    for(int i=2;i<=length;i  )//由于确定了每个节点的数据，单独将第一个节点拿出来定义
    {
        LinkNode *L=new LinkNode;
        L->data=i;
        L->next=R;
        tmp->next=L;//这里的插入也很简单
        tmp=tmp->next;
    }
}

Kill的函数：

void Kill(RollList &R,int m,int length)
{
    RollList tmp=R;
    for(int i=1;i<=length-1;i  )//循环n-1次。
    {
        for(int j=1;j<=m-2;j  )//这里首先走到要删除节点的前一个节点
        {
            tmp=tmp->next;
        }
        cout << "Kill the " << tmp->next->data << "people " << endl;
        tmp->next=tmp->next->next;//这里对指针进行修改（直接跳过了删除节点）
        tmp=tmp->next;
    }
    cout << endl;
    cout << "Survive people :" << endl;
    cout << tmp->data << endl;
}

那么，我们的约瑟夫问题已经可以求解了：

直接上代码：

#include <bits/stdc  .h>

using namespace std;

int arr[200];

typedef struct node
{
    int data;
    struct node *next;//指向下一个节点
}LinkNode;

typedef LinkNode *RollList;//重定义了循环链表的头节点

void Creat(RollList &R,int length)
{
    RollList tmp=R;//这里修改了tmp，避免直接对头结点修改
    for(int i=2;i<=length;i  )//由于确定了每个节点的数据，单独将第一个节点拿出来定义
    {
        LinkNode *L=new LinkNode;
        L->data=i;
        L->next=R;
        tmp->next=L;//这里的插入也很简单
        tmp=tmp->next;
    }
}


//下面的注释代表了另一种显示存活的人的方法（快排是真的牛皮）
/*void Kill(RollList &R,int m,int length,int arr[])
{
    RollList tmp=R;
    for(int i=1;i<=length-1;i  )//循环n-1次。
    {
        for(int j=1;j<=m-2;j  )
        {
            tmp=tmp->next;
        }
        cout << "Kill the " << tmp->next->data << "people " << endl;
        arr[i]=tmp->next->data;
        tmp->next=tmp->next->next;
        tmp=tmp->next;
    }
}*/

void Kill(RollList &R,int m,int length)
{
    RollList tmp=R;
    for(int i=1;i<=length-1;i  )//循环n-1次。
    {
        for(int j=1;j<=m-2;j  )//这里首先走到要删除节点的前一个节点
        {
            tmp=tmp->next;
        }
        cout << "Kill the " << tmp->next->data << "people " << endl;
        tmp->next=tmp->next->next;//这里对指针进行修改（直接跳过了删除节点）
        tmp=tmp->next;
    }
    cout << endl;
    cout << "Survive people :" << endl;
    cout << tmp->data << endl;
}

int main()
{
    RollList R=new LinkNode;
    R->data=1;
    R->next=R;
    int length,m;
    cout << "input people :" << endl;
    cin >> length;
    Creat(R,length);
    cout << "input death :" << endl;
    cin >> m;
    cout << endl;
    /*Kill(R,m,length,arr);
    cout << "Survive people :" << endl;
    sort(arr,arr length);
    for(int i=1;i<=length-1;i  )
    {
        if(arr[i]!=i)
        {
            cout << i << endl;
            break;
        }
    }*/
    Kill(R,m,length);
    return 0;
}

不得不说（快排牛皮！！！！）