数据结构，猴子选大王C语言循环链表

n只猴子要选大王，选举办法如下：所有猴子按1、2、3、……、n编号围坐一圈，从第1号开始按照1、2、3、……、m报数，凡报m号的退出圈外，如此循环报数，直到圈内剩下一只猴子时，这只猴子就是大王。n和m由键盘输入，打印出最后剩下的猴子号码。

如果用单向循环链表实现。

//循环链表
#include
typedef struct node
{
    struct node *next;
    int data;
}Li;
//初始化循环链表
Li *Init()
{
    Li *L;
    L=(Li*)malloc(sizeof(Li));
    L->data=1;
    L->next=L;
    return L;
}
//尾插法 因为顺序和插入顺序一样
Li* Insert(Li *r,int e)
{
    Li *q;//r指向最后结点
    q=(Li*)malloc(sizeof(Li));
    q->data=e;
    //r->next=q;错误 单链表插入先动后在动前 警示
    //q->next=r;错误
    q->next=r->next;
    r->next=q;
    r=q;//r永远指向尾结点
    return r;
}
void Creat(Li *l,int e)
{
    Li *r=l;//r为尾结点
    int n;
    for(n=2;n<=e;n++)
    {
        r=Insert(r,n);
    }
}
void Dawang(Li *l,int k)//k为每次删除的位置 n为多少只猴子
{
    Li *p=l,*q;
    int j;//计数器
    while(p->next!=p)
    {
        j=1;
        while(jnext;
            j++;
        }
        //删除第n个结点
        q=p->next;
        p->next=q->next;
        free(q);
        //
        p=p->next;
    }
    printf("n被选出来的大王为%dn",p->data);

}
int main()
{
    Li *L;
    int j,k,n;
    L=Init();
    printf("输入有多少只猴子和要删除个数");
    scanf("%d%d",&n,&k);
    Creat(L,n);
    Dawang(L,k);
}

 如果用单链表实现，不用循环的写法（实际上也是循环的思路）

#include
#include
typedef struct node
{
    struct node *next;
    int data;
}Li;
//初始化循环链表
Li *Init()
{
    Li *L;
    L=(Li*)malloc(sizeof(Li));
    L->next=NULL;
    return L;
}

//尾插法 因为顺序和插入顺序一样
Li* Insert(Li *r,int e)
{
    Li *q;//r指向最后结点
    q=(Li*)malloc(sizeof(Li));
    q->data=e;
    r->next=q;
    q->next=NULL;
    r=q;//r永远指向尾结点
    return r;
}
void Creat(Li *l,int e)//创建单链表
{
    Li *r=l;//r为尾结点
    int n,j;
    for(n=1;n<=e;n++)
    {
        r=Insert(r,n);
    }
}
void deleted(Li *l,int i)//删除结点使用
{
     Li *p=l,*q;
    int j=0;
    //寻找i-1结点
    while(p->next&&jnext;
        j++;
    }
    //删除点没有找到
    if(j>i-1)
    {
        printf("error");
        return 0;
    }
    q=p->next;
    p->next=q->next;
    free(q);
}
void dawang(Li *l,int k,int n)//k为每次删除的猴子 n为多少只猴子
{
    Li *p=l,*q=l;
    int m=0;//计数器
    int i;
    while(1)
    {
        q=q->next;
        m++;
        //第一 找删除位置 两种情况 在中间某个位置 或要删除的结点在单链表的首结点
        if(m==k-1)//定位到m-1个结点后将m结点删除,然后继续开始从1开始计数
        {
            if(q->next!=NULL)
            {
                deleted(q,1);
                //printf("%d  **n",q->data);
                m=0;
                n--;//猴子数量减去一
            }
            else
            {
                deleted(p,1);//删除首结点位置
                q=p;//p指针指向q的位置
                m=0;
                n--;
            }
        }
        //第二 要看路上计数时到达尾部 那么就重新指向首结点
        if(q->next==NULL)//走到头了以后回到起点
        {
            q=p;//p永远指向首结点，作用就是给q赋
        }
        if(n==1)//当n猴子删成只有一个了就终止循环
        {
            break;
        }
    }
    printf("猴王是：%d号n",p->next->data);
}

int main()
{
    Li *L;
    int j,k,n;
    L=Init();
    printf("输入有多少只猴子和位置");
    scanf("%d%d",&n,&k);
    Creat(L,n);
    dawang(L,k,n);
}

两种方法，都可出来结果

输入有多少只猴子和位置10 4
猴王是：5号

结束；