【c语言习题】使用链表解决约瑟夫问题

创作不易，本篇文章如果帮助到了你，还请点赞 关注支持一下♡>𖥦<)!!
主页专栏有更多知识，如有疑问欢迎大家指正讨论，共同进步！
🔥c语言系列专栏：c语言之路重点知识整合 🔥
给大家跳段街舞感谢支持！ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ

链表有关知识点：【c语言】链表

题目：

约瑟夫问题

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后， 39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从。

首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。

Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

数组方法：【c语言习题】使用数组解决约瑟夫问题

---

过程分析：

定义链表节点类型Node，包含两个域：data和指向下一个节点的指针next。

typedef struct node //定义链表 节点
{int data;struct node* next;
}Node;

定义函数void fun(int n, int m)，参数n为总人数，m为报数出局的数字

void fun(int n, int m)  //总共有n个人，报数为m的人出局 

初始化循环链表:

创建头结点head
head->data赋值为1
head->next赋值为NULL

然后用p和q两个指针完成插入操作，让p指向head，q表示新插入的节点。

	//初始化循环链表Node* head = NULL;	//头节点head = malloc(sizeof(Node));  head->data = 1;       //起始编号head->next = NULL;    Node* p = head;Node* q = NULL;

尾插法创建链表并构造循环链表：

从2开始遍历创建剩下的N-1个结点，每个结点依次插入到链表的尾部，即将p->next=r; q=p;
最后将最后一个节点p的next指针指向头节点head，完成循环链表的构建

for (int i = 2; i <= n; i++)//创建链表的n-1个节点{q = malloc(sizeof(Node));q->data = i;q->next = NULL;p->next = q;//插入节点p = q;}p->next = head;   //最后一个节点的next指向头节点p = head;  //记录头节点      

找到需要淘汰的节点：

计数器m每次加一，同时移动p指针，当m变成选定的淘汰数字时,
保留p指针位置（即将要淘汰的同学的位置），然后将p指向下一个同学
将淘汰同学输出，并将p指向下一个同学继续报数

while (p->next != p)  //链表中只剩下最后一个节点{for (int i = 1; i < m; i++)  //报数为m出局 {q = p;   //通过临时指针保存所对应节点的前一个节点的地址，最终找到需要删除的节点p，并输出节点datap = p->next; }printf("%d ", p->data);q->next = p->next;p = p->next;  //重置p重新报数}

当只有一个节点时，结束淘汰循环

printf("%d\n", p->data);printf("存活最后的%d位\n", m-1);free(q);free(head);q = NULL;head = NULL;

淘汰过程图解

完整代码：

#include <stdio.h>
typedef struct node //定义链表 节点
{int data;struct node* next;
}Node;void fun(int n, int m)  //总共有n个人，报数字为m的人出局 
{//初始化循环链表Node* head = NULL;	//头节点head = malloc(sizeof(Node));  head->data = 1;       //起始编号head->next = NULL;    Node* p = head;Node* q = NULL;for (int i = 2; i <= n; i++)//创建链表的n-1个节点{q = malloc(sizeof(Node));q->data = i;q->next = NULL;p->next = q;//插入节点p = q;}p->next = head;   //最后一个节点的next指向头节点p = head;  //记录头节点      while (p->next != p)  //链表中只剩下最后一个节点{for (int i = 1; i < m; i++)  //报数为m出局 {q = p;   //通过临时指针保存所对应节点的前一个节点的地址，最终找到需要删除的节点p，并输出节点datap = p->next; }printf("%d ", p->data);q->next = p->next;p = p->next;  //重置p重新报数}printf("%d\n", p->data);printf("存活最后的%d位\n", m-1);free(q);free(head);q = NULL;head = NULL;
}int main()
{int n, m;printf("请输入总人数：");scanf_s("%d", &n);printf("请输入报数的数字：");scanf_s("%d", &m);fun(n, m);system("pause");return 0;
}

结果：

---

大家的点赞、收藏、关注将是我更新的最大动力！ 欢迎留言或私信建议或问题。

大家的支持和反馈对我来说意义重大，我会继续不断努力提供有价值的内容！如果本文哪里有错误的地方还请大家多多指出(●'◡'●)