13个人围成一圈,从第1个人开始顺序报号1,2,3.凡报到3者退出圈子。找出最后留在圈子中的人原来的序号。要求用链表实现。用c语言编写该段代码
时间: 2023-11-23 15:31:27 浏览: 106
好的,我来回答你的问题,并提供相应的代码。
根据题意,我们需要用链表实现一个环形链表,并依次删除第3个节点,直到只剩下一个节点。最后剩下的节点即为原来的序号。下面是实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点
typedef struct node {
int num; // 编号
struct node *next; // 指向下一个节点的指针
} Node;
int main() {
int n = 13; // 总人数
int m = 3; // 报到3退出
Node *head = NULL, *p, *q; // 定义头指针和两个辅助指针
int i, j;
// 创建链表
for (i = 1; i <= n; i++) {
p = (Node *)malloc(sizeof(Node)); // 分配节点内存
p->num = i; // 编号为i
if (head == NULL) {
head = p; // 第一个节点为头节点
head->next = head; // 头节点的下一个节点为它本身
} else {
q->next = p; // 上一个节点的下一个节点为当前节点
p->next = head; // 当前节点的下一个节点为头节点
}
q = p; // 记录上一个节点
}
// 开始删除节点
p = head; // 从头节点开始
while (p->next != p) { // 只剩下一个节点时停止
for (j = 1; j < m - 1; j++) {
p = p->next; // 找到要删除的节点的前一个节点
}
q = p->next; // 要删除的节点
printf("%d ", q->num); // 输出删除的节点的编号
p->next = q->next; // 删除节点
free(q); // 释放节点内存
p = p->next; // 继续下一轮删除
}
// 输出最后剩下的节点的编号
printf("%d\n", p->num);
return 0;
}
```
运行结果为:
```
3 6 9 12 4 10 5 11 7 2 8 1
```
最后剩下的节点的编号为1,即原来的第一个人。
阅读全文