C语言已知ABCDEFG共7个人,围成一圈从1开始报数,报到N(0<N≤2147483647)的人是谁?
时间: 2024-05-08 14:17:42 浏览: 9
这道题可以使用循环链表来解决。首先将ABCDEFG这7个人依次放入循环链表中,然后从头结点开始依次报数,每报到N就删除当前结点,直到链表中只剩下一个结点为止,该结点即为报数为N的人。
具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define N 10
typedef struct node {
char data; // 存储人名
struct node *next; // 指向下一个结点
} Node;
// 创建循环链表
Node *createList() {
Node *head = (Node *)malloc(sizeof(Node)); // 创建头结点
head->data = 'A';
head->next = head; // 头结点的next指向自己
Node *p = head;
for (char c = 'B'; c <= 'G'; c++) { // 依次插入B-G
Node *node = (Node *)malloc(sizeof(Node));
node->data = c;
node->next = head; // 新结点的next指向头结点
p->next = node; // 上一个结点的next指向新结点
p = node; // 移动指针到新结点
}
return head;
}
// 报数并删除结点,返回删除结点的下一个结点
Node *deleteNode(Node *node, int n) {
for (int i = 1; i < n; i++) { // 报数
node = node->next;
}
Node *next = node->next; // 记录要删除的结点
printf("%c ", next->data); // 输出删除的人名
node->next = next->next; // 删除结点
free(next);
return node->next; // 返回删除结点的下一个结点
}
int main() {
int n = N;
Node *head = createList();
Node *p = head;
while (p->next != p) { // 当链表中只剩下一个结点时结束循环
p = deleteNode(p, n);
}
printf("\nThe last one is %c.\n", p->data);
free(p);
return 0;
}
```
该程序的时间复杂度为O(NM),其中N为人数,M为报数的次数。虽然时间复杂度较高,但对于本题的数据范围来说是可以接受的。