学步园

循环链表，最后的尾指针指到头结点上，双向循环链表就是再加个pre指针。

约瑟夫环的问题：设编号分别为：1，2,3,...n的n个人围坐在一圈。约定序号为k（1<=k<=n）的人从1开始计数，数m的那个人出列，他的下一位又开始从1开始计数，数到m的那个人又出列，以此类推，直到所有的人都出列。

例如：设 n = 8，k= 3 ， m = 4时，出列序列为：6  2  7  4  3  5  1  8

算法思路:用一个不带头结点的循环链表来处理Josephu问题：先构成一个有n个节点的单循环链表，然后从第k结点起从1计数，记到m时，对应的结点从链表中删除；然后再从被删除结点的下一个结点起又从1开始计数.....，直到所有结点都出列时，算法结束。

#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#define N 10
typedef int datatype;
typedef struct node {

    datatype data;
    struct node * next;
}linknode ,*linklist;

linklist create()
{
    linklist H;
    if((H = (linklist)malloc(sizeof(linknode)))==NULL)
    {
        perror("malloc");
        exit(-1);
    }
    H->next = H;
    H->data = 1;
    printf("create\n");
    return H;
}

int insert(linklist H,datatype data , int pos)
{
    int i;
    linklist q;
    linklist p = NULL;
    p = H;
    if((pos<0))
    {
        printf("insert error\n");
        return -1;
    }
    if((q = (linklist)malloc(sizeof(linknode))) == NULL )
    {
        perror("malloc");
        exit(-1);
    }
    while(pos--)
    p=p->next;
    q->data = data; 
    q->next = p->next;
    p->next = q;
    return 0;
}

int show(linklist H,int k,int m)
{
    int i = k-2;
    linklist p,q;
    p = H;
    while(i--) p = p->next;
    while(p != p->next)
    {
    for(i = 0;i < m-1; i++)
        p = p->next;
        q = p;
        p = p->next;
        q ->next = p->next;
        printf("data =%d\n",p->data);
        free(p);
        p = q->next;
    }
    printf("data =%d\n",p->data);
    return 0;
}
int main(int argc,char * argv[])
{ 
    int n,m,k,i = 0;
    int ret;
    linklist H;
    H = create();
    scanf("%d",&n);
    scanf("%d",&m);
    scanf("%d",&k);
    for(i = 2;i < n+1;i++)
    {
    ret = insert(H,i,i-2);
    if(ret ==-1)
        printf("insert error\n");
    }
    printf("**********create linklist*************\n");
    show(H,m,k);
    return 0;
}