13个人围成一圈,从第一个人开始顺序报号1,2,3。凡是报到3都退出圈子,找出最后留在圈子中的人原来的序号C代码分析。用链表来实现
时间: 2023-11-23 12:27:52 浏览: 47
以下是使用 C 语言链表方式的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node* next;
} Node;
int last_person(int n, int m) {
int i, count;
Node *p, *prev, *head;
head = (Node*)malloc(sizeof(Node));
head->data = 1;
prev = head;
for (i = 2; i <= n; i++) {
p = (Node*)malloc(sizeof(Node));
p->data = i;
prev->next = p;
prev = p;
}
prev->next = head; // 将链表首尾相连
p = head;
while (p->next != p) { // 当链表只剩一个节点时结束循环
for (count = 1; count < m; count++) {
prev = p;
p = p->next;
}
prev->next = p->next; // 将 p 节点从链表中删除
free(p);
p = prev->next; // 将 p 节点移到下一个节点
}
int result = p->data;
free(p);
return result;
}
int main() {
int n = 13; // 总人数
int m = 3; // 报数到 m 退出
int result = last_person(n, m);
printf("最后留在圈子中的人原来的序号为: %d\n", result);
return 0;
}
```
解释一下代码:`last_person(n, m)` 函数的作用和前面的两个版本相同,即求解在 n 个人围成一圈时,每报到第 m 个人就退出圈子,最后留在圈子中的人原来的序号。这里使用链表来表示围成的圈子,链表中的每个节点代表一个人,节点中的 data 存储人的序号,next 存储下一个节点的指针。首先创建一个带头节点的链表,头节点中的 data 存储第一个人的序号 1。然后从第二个人开始依次创建节点,将它们插入到链表的尾部。最后将链表首尾相连,形成一个环形链表。循环中的变量 p 表示当前报数到第 m 个人的节点,prev 表示 p 的前一个节点。循环中每次报数到第 m 个人,就将该人从链表中删除,然后将 prev 的 next 指针指向下一个节点,当前节点 p 被释放,prev 移到下一个节点。当链表中只剩一个节点时,循环结束。最后,返回链表中唯一剩下的节点的 data 值即可。注意,最后留在圈子中的人原来的序号为返回值加1。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)