题为c程序设计（第五版）谭浩强 课后习题第9章第6题
文章目录
-
目录
文章目录
前言
一、题目复现
二、实现步骤
1.思路分析
2.具体实现
总结
前言
链表是一种常见的基础数据结构，结构体指针在这里得到了充分的利用。链表可以动态的进行存储分配，也就是说，链表是一个功能极为强大的数组，他可以在节点中定义多种数据类型，还可以根据需要随意增添，删除，插入节点。链表都有一个头指针，一般以head来表示，存放的是一个地址。链表中的节点分为两类，头结点和一般节点，头结点是没有数据域的。链表中每个节点都分为两部分，一个数据域，一个是指针域。说到这里你应该就明白了，链表就如同车链子一样，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。
下面，让我们用一道经典例题来开启学习链表的大门。
一、题目复现
二、实现步骤
1.思路分析
1.首先定义了一个节点结构体Node，其中包含一个表示人的编号的整数字段和指向下一个节点的指针。
2.然后，使用createCircularLinkedList函数创建了一个包含n个人的循环链表。
3.接下来，使用removeNode函数从链表中删除指定的节点。
4.最后，findLastPerson函数使用循环链表模拟游戏的过程，并返回最后留在圈子中的人的原始编号。
注：在main函数中，我们可以设置n的值，并打印出最后留在圈子中的人的编号，此代码假设输入的n大于等于1，并且在运行结束后会释放动态分配的内存。
2.具体实现
代码如下（示例）：
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int number;
struct Node* next;
} Node;
Node* createCircularLinkedList(int n) {
Node* head = NULL;
Node* prev = NULL;
for (int i = 1; i <= n; i++) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->number = i;
if (head == NULL) {
head = newNode;
}
else {
prev->next = newNode;
}
prev = newNode;
}
prev->next = head; // 将最后一个节点的下一个指针指向头节点，形成循环链表
return head;
}
void removeNode(Node** head, Node* target) {
if (*head == NULL)
return;
if (*head == target) {
*head = target->next;
}
Node* current = *head;
while (current->next != target) {
current = current->next;
}
current->next = target->next;
free(target);
}
int findLastPerson(int n) {
Node* head = createCircularLinkedList(n);
Node* current = head;
while (current->next != current) {
// 计数到第3个人
for (int i = 1; i < 3; i++) {
current = current->next;
}
// 删除当前节点
Node* nextPerson = current->next;
removeNode(&head, current);
current = nextPerson;
}
int lastPersonNumber = head->number;
free(head);
return lastPersonNumber;
}
int main() {
int n = 13;
int lastPerson = findLastPerson(n);
printf("最后留在圈子中的人原来的序号是: %d\n", lastPerson);
return 0;
}实验结果（示例）：
总结
通过本例，我们可以学习到如何去创建链表、删除链表中指定的节点，以及如何使用链表，除此之外，我们在本例中还用到了动态内存分配的知识，对动态内存分配还不太熟悉的同学，可以去翻翻我之前的博客。
对本例的原理还不清楚的话，可以在纸上模拟一下实际的过程（注意：这里是一直1、2、3的报下去，而不是报完一轮再从头开始）。
转眼间就到七月了，都说七月的风，八月的雨，友友们在学习的过程中，也不要忘了适当地放松自己哈！
最后，如果友友们想在暑假中提升自己的话，可以报名字节跳动的青训营（主讲内容是目前前沿的前端、后端技术），报名链接和具体信息我已经上传到资源中了。加油😊！
文章出处登录后可见！
