约瑟夫环问题

题目:
一圈人围坐，以数字K位第一个个人，叫道 M 的人自动出列，请写出出列顺序

第一种方法：使用单项循环链表实现

//这里是头文件
#ifndef _SQLIST_H__
#define _SQLIST_H__
#define datatype int
typedef struct  sqlist{
  datatype data;//数据域
  struct sqlist *next;//指针域
}sqlist,*linklist;
extern  linklist sqlist_creat ();//创建一个单项循环链表的结点
extern int sqlist_insert(linklist L,int val);//实现循环链表的插入
extern void sqlist_show(linklist L);//显示链表
extern int jhon_show(linklist L,int k,int m);//约瑟夫环算法
#endif

//链表的存储与运算
#include <stdio.h>
#include "./sqlist.h"

#include <stdlib.h>
#include "./02.h"
linklist sqlist_creat()//创建一个空链表
{
    linklist L;
    L= (linklist)malloc(sizeof(sqlist));
    if(L == NULL)
    {
        perror("malloc");
        return NULL;
    }
    else
    {
        L->next=L;
        return L;
    }
}
int sqlist_insert(linklist L,int val)
{
    int i;
    if(L==NULL||val<0)
    {
        puts("argv invaid");
        return -1;
    }
    L->data=1;
    linklist p,r;
    p=r=L;
    for(i=2;i<=val;i++)
    {
        r=sqlist_creat();
        r->data=i;
        p->next=r;
        p=r;
    }
    r->next=L;
}
void sqlist_show(linklist L)
{
    linklist p;
    p=L;
    while(p->next!=L)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("%d\n",p->data);
}

int jhon_show(linklist L,int k,int m) //约瑟夫环算法
{
    int count=1;
    if(L == NULL||k<0 || m<0)
    {
        puts("argv invalid");
        return -1;
    }
    linklist p,r;
    p=L;
    while(p->next->data!=k)
    {
        p=p->next;
    }//找到开始的结点
    printf("开始=%d\n",p->next->data);
    while(p->next != p)
    {
        for(count=0;count<m-1;count++)
        {
            p=p->next;
        }
        r=p->next;
        p->next=r->next;
        printf("%d ",r->data);
        free(r);
        r=NULL;
    }
    printf("%d\n",p->data);
    return 1;
}

//测试样例
#include<stdio.h>
#include "./sqlist.h"
int main(int argc, const char *argv[])
{
    int reval,start,count;
    linklist L=sqlist_creat();
    printf("please input maxsize >");
    fflush(stdout);
    scanf("%d",&reval);
    sqlist_insert(L,reval);
//  sqlist_show( L );
    printf("please input　start >");
    fflush(stdout);
    scanf("%d",&start);
    printf("please input　count >");
    fflush(stdout);
    scanf("%d",&count);
    reval=jhon_show(L,start,count);
    return 0;
}

程序运行结果

运行结果

第二种方法