从约瑟夫环看循环链表

7 5
3 8 1 22 4 9 15

5 2 6 7 4 3 1

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后面的节点，返回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);
    }

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++)>