算法 | 求解约瑟夫环问题（循环单链表）

问题

利用循环单链表求解约瑟夫环问题（即n个人围成一个圆圈，然后从第一个人开始，按：1,2,3,…,m报数，数到m的人出圈，并有出圈者的下一个人重新开始报数，数到m又要出圈，如此类推，直到所有人都出圈，打印出圈的次序，其中n和m为输入数据）

测试用例

 输入 9 3 
 输出 3,6,9,4,8,5,2,7,1

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
typedef struct Node    /*结点类型定义*/
{
    int data;
    struct Node* next;
}Node, * link;  /* LinkList为结构指针类型*/
void josephus(link joseling, int n, int m);//用循环链表求解约瑟夫环
link creatlink(int n);//创建值为1~n的n个结点的不带头结点的循环单链表
void printlink(link head);//打印循环链表
Node* move(Node* p, int i);//p指针向前走i步
int main()
{
    int n, m, count, number;//count用于报数计数，number用于出列人数计数
    link joselink, current, s;
    printf("输入总人数n和报数规律m：\n");
    scanf("%d %d", &n, &m);
    joselink = creatlink(n);
    //不带头结点的循环单练表存储的约瑟夫环问题求解
    josephus(joselink, n, m);
    return 0;
}

link creatlink(int n)//创建值为1~n的n个结点的不带头结点的循环单链表
{
    link a = (link)malloc(sizeof(Node));
    a->data = 1;
    link k = a;
    for (int m = 2; m <= n; m++)
    {
        link p;
        p = (link)malloc(sizeof(Node));
        p->data = m;
        k->next = p;
        p->next = a;
        k = p;
    }
    return k;
}

void josephus(link joselink, int n, int m)
{
    for (int a = 0; a < n - 1; a++)
    {
        joselink = move(joselink, m);
        link e = joselink->next;
        joselink->next = e->next;
        printf("%d ", e->data);
        free(e);
    }
    printlink(joselink);
}

Node* move(Node* p, int i)//p指针向前走i步
{
    for (int a = 0; a < i - 1; a++)
    {
        p = p->next;
    }
    return p;
}

void printlink(link head)
{
    Node* current = head;
    do {
        printf("%d  ", current->data);
        current = current->next;
    } while (current != head);
    printf("\n");
    return;
}

运行结果