从约瑟夫环看循环链表-安全小百科

约瑟夫环问题是这样:

描述

编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出圈为止。

输入说明

仅有一组数据，输入数据第一行为两个正整数n(0<n<100)和m(0<m<99999999)，分别表示人的个数及初始随机数，第二行为n个整数Ai(0<Ai<99999999，i=1..n），表示每个人持有的密码。

输入样例

7 5
3 8 1 22 4 9 15

输出样例

5 2 6 7 4 3 1

拿到这一题，潜意识里就想到能不能用循环链表来解决。因为这里所有人都围成一圈，而且要频繁地进行删除的操作，如果用数组来储存数据就显得有些慢了。正好我最近也在自己看数据结构的书，所以这里就借这一题实践一下循环链表。（我的方向从来不是NOI和ACM，写的东西可能比较业余，不伦不类，请大家见谅……）

循环链表就是把我们线性链表的最后一个节点的指针域指向第一个有效节点。我们完全可以先造一个非循环单链表，然后再把它的尾指针指向首节点。

首先定义一个结构体，用它来做我们的节点。这个结构体应该保存这几个数据：1.该人是第几号人 2.该人手里的密码 3.下一个人的地址

于是可以这样定义：

typedef struct Node{
    long data;
    int n;
    struct Node * next;
    }NODE,* pNODE;

创建一个普通的空链表：

pNODE CreateNode(){
    pNODE p = (pNODE)malloc(sizeof(NODE));
    if(NULL == p)
        exit(-1);
    p->next = NULL;
    return(p);
    }

很简单，再像栈一样，向结尾添加数据。(这些我就不写注释了，因为这个是普通链表的操作，学数据结构的时候应该都写过)

void AddNode(pNODE pHead,long data,int n){
    pNODE p = pHead;
    pNODE pNew = (pNODE)malloc(sizeof(NODE));
    if(NULL == pNew)
        exit(-1);
    while(NULL != p->next)
        p = p->next;    
    p->next = pNew;
    pNew->n = n;
    pNew->next = NULL;
    pNew->data = data;
    return ;
    }

这两个函数的使用我们等下再说，他们的功能一个就是创建新的空链表，一个是向链表尾部添加数据。

好，我们还需要一个函数。他的功能是进行删除。因为每报到一个人，这个人就得退出游戏，也就是删除这个人代表的节点。由于链表的特殊性，我们如果要删除p节点，我们得把p前面、后面的两个节点连接。p后面节点的地址很好知道，就是p->next，但是p前面一个人的地址我们并不知道。所以我用了一个方法解决这个问题，只要我们这个函数的功能不是删除p节点，是删除p后面一个节点。这样问题就解决了，至于如何使用，这个等下写main函数的时候再考虑。

函数可以这么写：

//删除p后面的节点，返回val
BOOL DeleteNode(pNODE p,long* val){
    pNODE q;
    if(p == p->next) 
        return(FALSE); 
    //如果循环链表只剩一个节点了，返回false
    q = p->next;
    p->next = q->next; 
    //将p的指针域指向q的指针域，q是p下一个节点
    *val = q->data; 
    //将q的数据(也就是删除的这个人的密码)保存在val里返回
    printf("%d ",q->n); 
    //输出删除的这个人的编号
    free(q);
    //勿忘释放内存
    return(TRUE);
    }

函数写好了，我们可以开始写main函数了。main函数的作用是让这几个子函数协同，完成我们约瑟夫环这道题的目标。

int main(){
    int peo,i;
    long m,tmp;
    pNODE pHead,p,q;
    scanf("%d%d",&peo,&m);
    pHead = InitNode();
    //建立一个空链表，头指针为pHead
    for(i=0;i<peo;i++){
        scanf("%d",&tmp);
        AddNode(pHead,tmp,i+1);
    //每读入一个数据(也就是每个人手里的密码)，就添加到链表的后面
        }
    p = pHead;
    while(NULL != p->next)  
        p = p->next;
    //寻找这个链表最后一个节点
    p->next = pHead->next;
    //将尾指针指向首节点，注意不是指向头结点。(如图1)
    p = pHead->next;
    while(p != p->next){ //开始游戏了，结束条件是只剩下最后一个人
          for(i=1;i<m-1;i++) p="p-">next;
        //找到第m-1个人(报m的人的前一个人)
          q = p;
          DeleteNode(q,&m);
        //输入的是q，的实际上删除的是q->next指向的那个人,因为我们函数是这样定义的
          p = p->next;
        //接着报数则从下一个人开始，故p往后移动
          }
    printf("%dn",p->n);
    //输出最后一个人的编号
    free(p);
    return 0;
    }</m-1;i++)>

大家可以把程序写好拿去试试。我写的东西肯定不规范，比如对链表操作的那几个英文单词我随便写的。我把我写的传到附件里大家可以下载来看。

上面的内容有一些错误，不知道大家发现没有。当我们被删除的那个人手里的密码是1的时候，也就是说下一轮提出的人就是他后面那个。但是这时候指针已经指向这个人了，而我们的DeleteNode函数作用是删除后面一个，所以结果就有问题。我暂时还没想到什么好方法，只能判断一下。当m==1时就把循环链表走一遍，走到p之前的那个节点，再执行DeleteNode函数。

改正的代码已经传到附件里了。