约瑟夫环是一个数学的应用问题，有这么一个故事：在罗马人占领乔塔帕特后，39 个犹太人与约瑟夫及他的朋友躲到一个洞中，39 个犹太人决定宁死也不要被敌人抓到，于是决定了一个自杀方式：41 个人排成一个圆圈，由第 1 个人开始报数，每次数到 3 的人就必须自杀，然后再由下一个人重新报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从，约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第 16 个与第 31 个位置，于是逃过了这场死亡游戏。
约瑟夫环问题的实现如下：
1、joseph.h 文件
/*
* 线性表的链式存储结构（无头结点的单向循环链表）
*/
#ifndef JOSEPH_H__
#define JOSEPH_H__
/*
* 单向链表结构
*/
typedef struct node_st {
int data; // 数据结点
struct node_st *next; // 指向下一个结点的指针
}joseph;
/*
* 初始化，创建单向链表
*/
joseph * joseph_create(int);
/*
* 遍历单向链表
*/
void joseph_show(joseph *);
/*
* 从单向链表的指定位置删除数据
*/
void joseph_kill(joseph **, int);
#endif
2、joseph.c 文件
#include <stdio.h>
#include <stdlib.h>
#include "joseph.h"
/*
* 初始化，创建单向链表
*/
joseph * joseph_create(int n) {
int i = 1; // 循环索引值
joseph *head, *node, *tail; // 头结点、当前结点、尾结点
head = malloc(sizeof(*head));
if (head == NULL) {
return NULL;
}
// 给结点赋值
head->data = i;
// 刚初始化的单向循环链表的头结点的下一个结点就是本身
head->next = head;
// 从头结点开始往下继续构建其它结点
node = head;
i++;
while (i <= n) {
tail = malloc(sizeof(*tail));
if (tail == NULL) {
return NULL;
}
// 给尾结点赋值
tail->data = i;
// 尾结点的下一个结点必须指向到头结点
tail->next = head;
// 将前一个结点的下一个结点指向到尾结点
node->next = tail;
// 将当前结点指向到尾结点
node = tail;
// 继续
i++;
}
return head;
}
/*
* 遍历单向链表
*/
void joseph_show(joseph *ptr) {
joseph *node = ptr; // 当前结点
for (node = ptr; node->next != ptr; node=node->next) {
printf("%d ", node->data);
}
printf("%d\n", node->data);
return; // 无返回值
}
/*
* 从单向链表的指定位置删除数据
*/
void joseph_kill(joseph **ptr, int n) {
int i = 1; // 循环索引值
joseph *node = *ptr, *prev; // 当前结点，前一个结点
while (node != node->next) {
// 通过 while 循环，走到要删除的位置，并且得到前一个结点
while (i < n) {
prev = node;
node = node->next;
i++;
}
// 输出要删除的数据
printf("%d ", node->data);
// 将前一个结点的下一个结点，指向到要删除结点的下一个结点
prev->next = node->next;
// 释放要删除结点所占内存
free(node);
// 将当前结点指向到前一个结点的下一个结点，即原先要删除结点的下一个结点
node = prev->next;
// 改变循环索引值，重新开始下一轮
i = 1;
}
// 得到最后的一个幸存者
*ptr = node;
return; // 无返回值
}
3、main.c 文件
#include <stdio.h>
#include <stdlib.h>
#include "joseph.h"
int main() {
int num; // 参与人数
int dead; // 出局者编号
joseph *list; // 无头单向环链
printf("请输入参与人数：");
scanf("%d", &num);
printf("请输入出局者编号：");
scanf("%d", &dead);
list = joseph_create(num);
if (list == NULL) {
fprintf(stderr, "初始化无头单向环链 list 失败！\n");
exit(1);
}
printf("参与者：");
joseph_show(list);
printf("出局者顺序：");
joseph_kill(&list, dead);
printf("\n幸存者：");
joseph_show(list);
exit(0);
}
4、Makefile 文件
OBJS=main.o joseph.o
CC=gcc
CFLAGS+=-c -Wall -g
joseph:$(OBJS)
$(CC) $^ -o $@
%.o:%.c
$(CC) $^ $(CFLAGS) -o $@
clean:
$(RM) *.o joseph -r
执行效果：
gcc main.c -c -Wall -g -o main.o
gcc joseph.c -c -Wall -g -o joseph.o
gcc main.o joseph.o -o joseph
root@RicenOS:~# ./joseph
请输入参与人数：41
请输入出局者编号：3
参与者：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
出局者顺序：3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16
幸存者：31
Copyright © 2005-2023 by www.ricensoftwares.com.cn All Rights Reserved.
