线性表（四）——循环链表

循环链表

构造原理

循环链表是指链表中最后那个链结点的指针域存放指向链表最前面那个结点的指针，整个链表形成一个环。分为不带头结点的循环链表和带头结点的循环链表，最长使用的是不带头结点的（p=list）。

基本操作

1、求循环链表的长度

int LENGTH( LinkList list ){
    LinkList p=list;
    int n=0;            /* 链表的长度置初值0*/
    do{
         p=p->link;
         n++;
   }while( p != list);
   return n; /* 返回链表的长度n */
}

2、约瑟夫(JOSEPHU)问题
已知n个人(不妨分别以编号1，2，3，…，n代表)围坐在一张圆桌周围，编号为k的人从1开始报数，数到m的那个人出列，他的下一个人又从1开始继续报数，数到m的那个人出列，…,依此重复下去，直到圆桌周围的人全部出列。直到圆桌周围只剩一个人。

需要做的工作：
1、建立一个不带头结点的循环链表；
2、找到第一个出发点；
3、反复删除一个链结点；

void JOSEPHU( int n, int m, int k ){ 
    LinkList list,p,r;
    int i;
    list=NULL;
    for(i=1;i<=n;i++) { 
        p = (LinkList)malloc(sizeof(LNode));
        p->data=i;
        if (list==NULL) 
            list=p;
        else
            r->link=p;
        r=p;
    }
    p->link=list; 
    /* 至此建立循环链表步骤完成*/
    p=list;
    for(i=1;i<=k-1;i++) {       /* 找到第一个点，此时p指向第一个出发节点*/
         r=p;
         p=p->link;
    }             
    while(p->link != p) {
        for(i=1;i<=m-1;i++){
            r=p;                         //不多余，当k!=1但m=1时没有此句话删除动作无法进行
            p=p->link;
        }                                    //p指向第m个节点，r指向第m-1个节点
        r->link=p->link;             //删除第m个节点
        printf(“%3d”,p->data);    //输出一个节点编号
        free(p);                          //释放被删除节点的空间
        p=r->link;                      //p指向新的出发节点
    }
    printf(“\n最后被删除的节点是%4d”, p->data);      //输出最后被删除节点的编号
}