C语言循环队列解决约瑟夫环问题

击左上方蓝色“一口Linux”，选择“设为星标”

第一时间看干货文章 

☞【干货】嵌入式驱动工程师学习路线
☞【干货】Linux嵌入式知识点-思维导图-免费获取
☞【就业】一个可以写到简历的基于Linux物联网综合项目
☞【就业】简历模版

作者:编程探索者

在C语言中，使用循环队列解决约瑟夫环问题需要结合队列的环形特性模拟人员围坐一圈的场景。本文详解该问题实现思路和代码解析：

title

约瑟夫环问题描述

n个人围成一圈，从第k个人开始报数，每数到m的人出列，剩余人继续从1报数，直到最后一人存活。目标是确定出列顺序及最终存活者编号11252。

循环队列实现思路

1. 数据结构设计
定义循环队列结构体，包含动态数组、队首/队尾指针及队列容量：

typedef struct {
   int *base;    // 存储元素的数组
   int front;    // 队首指针
   int rear;     // 队尾指针
   int MAXSIZE;  // 队列容量（总人数+1）
} SqQueue;

循环队列

2. 初始化队列
队列容量设为n+1，留出一个空位以区分队满和队空：

bool InitQueue(SqQueue &Q, int n) {
   Q.base = (int*)malloc(100 * sizeof(int)); // 示例中固定分配100空间
   Q.front = Q.rear = 0;
   Q.MAXSIZE = n + 1;  // 容量为n+1，容纳n人
   return true;
}

3. 入队与出队操作

• 入队：检查队满条件(rear+1) % MAXSIZE == front，元素存入base[rear]并移动rear指针。

• 出队：元素从base[front]取出，移动front指针，并将原位置标记为0（表示已出列）152。

约瑟夫环核心算法

1. 初始化与填充队列
将编号1~n的人依次入队：

for (int i = 1; i <= n; i++) {
   EnQueue(Q, i);
}

2. 模拟报数淘汰过程

• 外层循环：剩余人数Count从n递减至1。

• 内层循环：移动front指针，跳过已出列（标记为0）的位置，找到第m个有效位置。

• 出队处理：调用DeQueue函数，记录出列编号，并调整指针至下一个有效起点152。

void JosephCircle(SqQueue &Q, int n, int m) {
   int e, Count = n;
   while (Count > 1) {
       int i = 1;
       while (i < m) {  // 移动m-1次找到目标位置
           Q.front = (Q.front + 1) % (Q.MAXSIZE - 1);
           if (Q.base[Q.front] != 0) i++;  // 仅有效位置计数
       }
       DeQueue(Q, e);  // 出列并记录编号
       printf("%d ", e);
       // 调整指针至下一个有效起点
       while (Q.base[Q.front] == 0) {
           Q.front = (Q.front + 1) % (Q.MAXSIZE - 1);
       }
       Count--;
   }
   DeQueue(Q, e);  // 输出最后存活者
   printf("存活者：%d", e);
}

关键点解析

1. 循环队列的容量设计
通过MAXSIZE = n + 1避免队满与队空条件冲突，利用取模运算实现环形移动。

2. 跳过已出列元素
出列后标记位置为0，后续移动指针时自动跳过无效位置，确保每次报数基于有效成员。

3. 时间复杂度优化
直接通过数组索引操作实现O(n*m)的时间复杂度，优于链表实现的多次遍历。

示例运行

输入n=10, m=3时，输出出列顺序为3 6 9 2 7 1 8 5 10，存活者为43652。

完整代码参考

#include 
#include 

typedef struct {
    int *base;
    int front, rear, MAXSIZE;
} SqQueue;

bool InitQueue(SqQueue &Q, int n) {
    Q.base = (int*)malloc(100 * sizeof(int));
    if (!Q.base) return false;
    Q.front = Q.rear = 0;
    Q.MAXSIZE = n + 1;
    return true;
}

bool EnQueue(SqQueue &Q, int e) {
    if ((Q.rear + 1) % Q.MAXSIZE == Q.front) return false;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % Q.MAXSIZE;
    return true;
}

bool DeQueue(SqQueue &Q, int &e) {
    if (Q.front == Q.rear) return false;
    e = Q.base[Q.front];
    Q.base[Q.front] = 0;  // 标记为已出列
    Q.front = (Q.front + 1) % (Q.MAXSIZE - 1);
    return true;
}

void JosephCircle(SqQueue &Q, int n, int m) {
    int e, Count = n;
    while (Count > 1) {
        int i = 1;
        while (i < m) {
            Q.front = (Q.front + 1) % (Q.MAXSIZE - 1);
            if (Q.base[Q.front] != 0) i++;
        }
        DeQueue(Q, e);
        printf("%d ", e);
        while (Q.base[Q.front] == 0) {
            Q.front = (Q.front + 1) % (Q.MAXSIZE - 1);
        }
        Count--;
    }
    DeQueue(Q, e);
    printf("\n存活者：%d\n", e);
}

int main() {
    SqQueue Q;
    int n = 10, m = 3;
    InitQueue(Q, n);
    for (int i = 1; i <= n; i++) EnQueue(Q, i);
    JosephCircle(Q, n, m);
    free(Q.base);
    return 0;
}

还是那句话：干中学，学中干

如果觉得不错的话，麻烦点个关注，收藏谢谢。