约瑟夫问题：单向循环链表

我们这个规则是这么定的：在一间房间总共有n个人（下标0～n-1），只能有最后一个人活命。

按照如下规则去杀人：

所有人围成一圈
顺时针报数，每次报到q的人将被杀掉
被杀掉的人将从房间内被移走
然后从被杀掉的下一个人重新报数，继续报q，再清除，直到剩余一人

你要做的是：当你在这一群人之间时，你必须选择一个位置以使得你变成那剩余的最后一人，也就是活下来

【解决方法：单向循环链表】维护三个指针，list始终指向链表的头部，r指向前一个删除的数据的位置，p指向删除数据的位置

#include<stdio.h>
#include <stdlib.h>
struct node{
    int data;
    struct node *next;
}node,*list,*p,*r;
void JOSEPHU(int n,int k,int m)
{
    int i,j;
    list=NULL;
    for(i=1;i<=n;i++)
    {
        p=(struct node*)malloc(sizeof(node));
        p->data=i;
        if(list==NULL)
            list=p;
        else
            r->next=p;
        r=p;
    }
    p->next=list;    /*建立一个循环链表*/
    p=list;
    for(i=1;i<=n+1;i++)
    {
        printf("%d  ",p->data);
        p=p->next;
    }
    printf("\n"); /*打印链表,并检查循环链表是不输入正确*/
    p=list;
    i=1;
    while(p&&i<k)
    {  r=p;
        p=p->next;
        ++i;
    }
    for(i=1;i<n;i++)
    {
        for(j=1;j<m;j++)
        {   r=p;
            p=p->next;
        }
        printf("The out=%d\n",p->data);
        r->next=p->next;
        p = p->next;
    }
    printf("The rest is %d\n",p->data);
}
int main()
{
    int x, y, z;
    printf("input the lenth n\n");/*n,k,m分别代表总的人数，第一个报数的人，间隔的人数*/
    scanf("%d",&x);
    printf("input the start k\n");
    scanf("%d",&y);
    printf("input the m\n");
    scanf("%d",&z);
    JOSEPHU(x,y,z);
    return 0;
}

yooocen / dadaLearningBlogs

约瑟夫问题：单向循环链表 #22