吴老师百花 CC 班【链表】作业题解
2025-05-24 09:43:56
发布于：广东
5阅读
0回复
0点赞
吴老师百花 CC 班【链表】作业题解
T1【链表】猴子选大王
题目链接
题目分析
这道题目是经典的 约瑟夫问题（Josephus Problem），可以用 循环链表 来模拟猴子围圈报数的过程。具体步骤如下：
- 构建循环链表：每个猴子是一个节点，
data存储编号，next指向下一个猴子，形成环。 - 模拟报数过程：
- 从编号
1的猴子开始报数。 - 每次数到
m时，当前猴子出圈（删除该节点）。 - 继续从下一个猴子开始重新报数，直到只剩一只猴子。
- 从编号
- 返回结果：最后剩下的猴子的编号就是大王的编号。
代码实现
#include <iostream>
using namespace std;
struct Node {
int data; // 猴子的编号（1~n）
Node *next; // 指向下一个猴子
};
/**
* 找到最后剩下的猴子（大王）
* @param n 猴子总数
* @param m 报数的数字
* @return 大王的编号
*/
int findKing(int n, int m) {
if (n == 1) return 1; // 只有一只猴子时直接返回
// 1. 创建循环链表
Node *head = new Node{1, nullptr}; // 创建第一个猴子
Node *current = head;
// 依次创建剩下的猴子，并连接成链表
for (int i = 2; i <= n; i++) {
current->next = new Node{i, nullptr};
current = current->next;
}
current->next = head; // 最后一个猴子指向第一个，形成环
// 2. 模拟报数过程
Node *prev = current; // prev 初始指向最后一个节点（方便删除操作）
current = head; // current 从第一个猴子开始
while (current->next != current) { // 只剩一个猴子时停止
// 报数 m-1 次，找到第 m 个猴子
for (int count = 1; count < m; count++) {
prev = current;
current = current->next;
}
// 删除当前猴子（current）
prev->next = current->next; // 前一个猴子直接指向下一个猴子
Node *temp = current; // 临时保存要删除的猴子
current = current->next; // current 移动到下一个猴子
delete temp; // 释放被删除猴子的内存
}
int king = current->data; // 最后剩下的猴子编号
delete current; // 释放最后一个猴子的内存
return king;
}
int main() {
int n, m;
cin >> n >> m;
cout << findKing(n, m) << endl;
return 0;
}
T2【链表】删除相等数
题目链接
题目分析
这道题目要求我们使用链表来存储给定的整数，然后删除所有与指定值 m 相等的节点，最后输出剩余的元素。具体步骤如下：
- 构建链表：将输入的
n个整数依次插入到链表中。 - 删除操作：遍历链表，删除所有
data等于m的节点。 - 输出结果：遍历链表，输出剩余的元素。
代码实现
#include <iostream>
using namespace std;
struct Node {
int data; // 存储整数值
Node *next; // 指向下一个节点
};
/**
* 创建链表
* @param arr 整数数组
* @param n 数组长度
* @return 链表的头节点指针
*/
Node* createList(int arr[], int n) {
if (n == 0) return nullptr; // 空数组返回空链表
Node *head = new Node{arr[0], nullptr}; // 创建头节点
Node *current = head;
// 依次创建剩余节点
for (int i = 1; i < n; i++) {
current->next = new Node{arr[i], nullptr};
current = current->next;
}
return head;
}
/**
* 删除链表中所有值为m的节点
* @param head 链表头节点指针
* @param m 要删除的目标值
* @return 可能更新后的头节点指针
*/
Node* removeElements(Node* head, int m) {
// 处理头节点就是目标值的情况（可能连续出现）
while (head != nullptr && head->data == m) {
Node *temp = head;
head = head->next;
delete temp; // 释放内存
}
// 处理后续节点
Node *current = head;
while (current != nullptr && current->next != nullptr) {
if (current->next->data == m) {
Node *temp = current->next;
current->next = current->next->next;
delete temp; // 释放内存
} else {
current = current->next; // 移动到下一个节点
}
}
return head;
}
/**
* 打印链表
* @param head 链表头节点指针
*/
void printList(Node* head) {
Node *current = head;
while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
/**
* 释放链表内存
* @param head 链表头节点指针
*/
void deleteList(Node* head) {
Node *current = head;
while (current != nullptr) {
Node *temp = current;
current = current->next;
delete temp; // 释放内存
}
}
int main() {
int n, m;
cin >> n; // 读取整数个数
int arr[100];
for (int i = 0; i < n; i++) {
cin >> arr[i]; // 读取整数数组
}
cin >> m; // 读取目标值m
Node *head = createList(arr, n); // 创建链表
head = removeElements(head, m); // 删除值为m的节点
printList(head); // 输出结果
deleteList(head); // 释放内存
return 0;
}
T3【链表】序列问题
题目链接
题目分析
这道题目要求我们在链表中所有值为 m 的节点后面插入一个值为 q 的新节点。具体步骤如下：
- 构建链表：将输入的
n个整数依次插入到链表中。 - 插入操作：遍历链表，在每一个
data等于m的节点后面插入一个值为q的新节点。 - 输出结果：遍历链表，输出插入后的序列。
详细注释
#include <iostream>
using namespace std;
struct Node {
int data; // 存储整数值
Node *next; // 指向下一个节点
};
/**
* 创建链表
* @param arr 整数数组
* @param n 数组长度
* @return 链表的头节点指针
*/
Node* createList(int arr[], int n) {
if (n == 0) return nullptr; // 空数组返回空链表
Node *head = new Node{arr[0], nullptr}; // 创建头节点
Node *current = head;
// 依次创建剩余节点
for (int i = 1; i < n; i++) {
current->next = new Node{arr[i], nullptr};
current = current->next;
}
return head;
}
/**
* 在所有值为m的节点后面插入q
* @param head 链表头节点指针
* @param m 目标值
* @param q 要插入的值
* @return 链表的头节点指针（可能不变）
*/
Node* insertAfterM(Node* head, int m, int q) {
Node *current = head;
while (current != nullptr) {
if (current->data == m) {
// 创建新节点并插入
Node *newNode = new Node{q, current->next};
current->next = newNode;
current = newNode->next; // 跳过新插入的节点，避免无限循环
} else {
current = current->next;
}
}
return head;
}
/**
* 打印链表
* @param head 链表头节点指针
*/
void printList(Node* head) {
Node *current = head;
while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
/**
* 释放链表内存
* @param head 链表头节点指针
*/
void deleteList(Node* head) {
Node *current = head;
while (current != nullptr) {
Node *temp = current;
current = current->next;
delete temp; // 释放内存
}
}
int main() {
int n, m, q;
cin >> n; // 读取整数个数
int arr[100];
for (int i = 0; i < n; i++) {
cin >> arr[i]; // 读取整数数组
}
cin >> m >> q; // 读取目标值m和要插入的值q
Node *head = createList(arr, n); // 创建链表
head = insertAfterM(head, m, q); // 在m后面插入q
printList(head); // 输出结果
deleteList(head); // 释放内存
return 0;
}
T4 模拟链表操作
题目链接
题目分析
这道题目要求我们首先构建一个初始链表，然后进行 m 次插入操作，每次将元素 b 插入到元素 a 的后面。由于题目保证元素不重复，我们可以直接通过遍历链表找到对应的节点进行操作。
详细注释
#include <iostream>
using namespace std;
struct Node {
int data; // 存储元素值
Node *next; // 指向下一个节点
};
/**
* 创建链表（尾部插入）
* @param arr 整数数组
* @param n 数组长度
* @return 链表的头节点指针
*/
Node* createList(int arr[], int n) {
if (n == 0) return nullptr; // 空数组返回空链表
Node *head = new Node{arr[0], nullptr}; // 创建头节点
Node *tail = head; // 尾指针初始指向头节点
// 依次创建剩余节点并插入尾部
for (int i = 1; i < n; i++) {
tail->next = new Node{arr[i], nullptr};
tail = tail->next; // 更新尾指针
}
return head;
}
/**
* 在值为a的节点后插入值为b的节点
* @param head 链表头节点指针
* @param a 目标值
* @param b 要插入的值
* @return 链表的头节点指针（可能不变）
*/
Node* insertAfterA(Node* head, int a, int b) {
Node *current = head;
// 遍历链表寻找值为a的节点
while (current != nullptr) {
if (current->data == a) {
// 创建新节点并插入
Node *newNode = new Node{b, current->next};
current->next = newNode;
break; // 找到第一个a就插入，然后退出
}
current = current->next;
}
return head;
}
/**
* 打印链表
* @param head 链表头节点指针
*/
void printList(Node* head) {
Node *current = head;
while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
/**
* 释放链表内存
* @param head 链表头节点指针
*/
void deleteList(Node* head) {
Node *current = head;
while (current != nullptr) {
Node *temp = current;
current = current->next;
delete temp; // 释放内存
}
}
int main() {
int n, m;
cin >> n >> m; // 读取元素个数和操作次数
int arr[100];
for (int i = 0; i < n; i++) {
cin >> arr[i]; // 读取初始元素序列
}
Node *head = createList(arr, n); // 创建初始链表
// 执行m次插入操作
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
head = insertAfterA(head, a, b);
}
printList(head); // 输出最终序列
deleteList(head); // 释放内存
return 0;
}
T5 基础链表插入
题目链接
题目分析
这道题目要求我们使用链表来存储初始的数字序列，然后在指定的数字 a 后面插入一个新的数字 b。由于题目保证数字不重复，我们可以直接遍历链表找到对应的节点进行操作。
详细注释
#include <iostream>
using namespace std;
struct Node {
int data; // 存储数字
Node *next; // 指向下一个节点
};
/**
* 创建链表（尾部插入）
* @param arr 整数数组
* @param n 数组长度
* @return 链表的头节点指针
*/
Node* createList(int arr[], int n) {
if (n == 0) return nullptr; // 空数组返回空链表
Node *head = new Node{arr[0], nullptr}; // 创建头节点
Node *tail = head; // 尾指针初始指向头节点
// 依次创建剩余节点并插入尾部
for (int i = 1; i < n; i++) {
tail->next = new Node{arr[i], nullptr};
tail = tail->next; // 更新尾指针
}
return head;
}
/**
* 在值为a的节点后插入值为b的节点
* @param head 链表头节点指针
* @param a 目标值
* @param b 要插入的值
* @return 链表的头节点指针（可能不变）
*/
Node* insertAfterA(Node* head, int a, int b) {
Node *current = head;
// 遍历链表寻找值为a的节点
while (current != nullptr) {
if (current->data == a) {
// 创建新节点并插入
Node *newNode = new Node{b, current->next};
current->next = newNode;
break; // 找到a就插入，然后退出
}
current = current->next;
}
return head;
}
/**
* 打印链表
* @param head 链表头节点指针
*/
void printList(Node* head) {
Node *current = head;
while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
/**
* 释放链表内存
* @param head 链表头节点指针
*/
void deleteList(Node* head) {
Node *current = head;
while (current != nullptr) {
Node *temp = current;
current = current->next;
delete temp; // 释放内存
}
}
int main() {
int n;
cin >> n; // 读取数字个数
int arr[1000];
for (int i = 0; i < n; i++) {
cin >> arr[i]; // 读取初始数字序列
}
int a, b;
cin >> a >> b; // 读取要插入的位置a和新数字b
Node *head = createList(arr, n); // 创建初始链表
head = insertAfterA(head, a, b); // 执行插入操作
printList(head); // 输出结果
deleteList(head); // 释放内存
return 0;
}
T6 约瑟夫问题2
题目链接
题目分析
这道题目是经典的 约瑟夫问题（Josephus Problem），要求模拟n个人围成一圈，每次数到m的人出列，直到只剩最后一个人。由于n可能很大（1e6），直接模拟会超时，需要使用数学方法优化。
详细注释
#include <iostream>
using namespace std;
/**
* 解决约瑟夫问题（数学方法）
* @param n 总人数
* @param m 报数的数字
* @return 最后剩下的人的编号（0-based）
*/
int josephus(int n, int m) {
if (n == 1) return 0; // 基本情况
// 递归关系：f(n,m) = (f(n-1,m) + m) % n
return (josephus(n - 1, m) + m) % n;
}
int main() {
int n, m;
cin >> n >> m;
cout << josephus(n, m) << endl;
return 0;
}
关键点说明
-
数学递推：
- 当
n=1时，结果显然是0（只有一个人） - 递推关系：
f(n,m) = (f(n-1,m) + m) % n - 时间复杂度
O(n)，可以处理n=1e6的情况
- 当
-
优化思路：
- 避免使用链表模拟，直接计算最后幸存者的位置
- 递归实现简洁，但可以改为迭代防止栈溢出
-
边界处理：
- 当
n=1时直接返回0 - 保证
m > 0且n > 0
- 当
示例解析
输入：
8 3
计算过程：
- f(1,3)=0
- f(2,3)=(f(1,3)+3)%2=1
- f(3,3)=(f(2,3)+3)%3=1
- f(4,3)=(f(3,3)+3)%4=0
- f(5,3)=(f(4,3)+3)%5=3
- f(6,3)=(f(5,3)+3)%6=0
- f(7,3)=(f(6,3)+3)%7=3
- f(8,3)=(f(7,3)+3)%8=6
输出：
6
迭代优化版本
int josephus(int n, int m) {
int res = 0; // f(1,m)=0
for (int i = 2; i <= n; i++) {
res = (res + m) % i;
}
return res;
}
这个版本避免了递归的栈开销，更适合处理大数据量。
T7 排队就餐
题目链接
题目分析
这道题目要求我们模拟食堂排队的过程，初始有n个人排队，其中有m个人离开队伍。我们需要计算在这些人离开后，小明在队伍中的新位置。
详细注释
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m; // 读取队伍人数和离开人数
vector<int> queue(n);
for (int i = 0; i < n; i++) {
cin >> queue[i]; // 读取初始队伍
}
vector<int> left(m);
for (int i = 0; i < m; i++) {
cin >> left[i]; // 读取离开的人
}
int y;
cin >> y; // 读取小明的编号
// 从队伍中移除离开的人
vector<int> new_queue;
for (int person : queue) {
if (find(left.begin(), left.end(), person) == left.end()) {
new_queue.push_back(person);
}
}
// 查找小明的位置
int position = 0;
for (int i = 0; i < new_queue.size(); i++) {
if (new_queue[i] == y) {
position = i + 1; // 位置从1开始计数
break;
}
}
cout << position << endl;
return 0;
}
关键点说明
-
输入处理：
- 读取初始队伍和离开人员名单
- 读取小明的编号
-
队伍更新：
- 创建新队伍，只保留没有离开的人
- 使用
find函数检查人员是否在离开名单中
-
位置查找：
- 遍历新队伍查找小明的编号
- 位置从1开始计数
-
输出结果：
- 输出小明在新队伍中的位置
示例解析
输入：
5 3
1 3 2 5 4
1 4 5
2
执行过程：
- 初始队伍：[1,3,2,5,4]
- 离开的人：[1,4,5]
- 新队伍：[3,2]
- 小明编号2的位置：第2个
输出：
2
T8 站队
题目链接
题目分析
这道题目要求我们根据每个同学前面的人的编号，重建整个队伍的排队顺序。关键在于理解输入数据的含义，并通过建立"前驱-后继"关系来重建队伍顺序。
详细注释
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n; // 读取人数
vector<int> front(n+1); // front[i]表示i号同学前面是谁
vector<int> back(n+1, 0); // back[i]表示i号同学后面是谁
// 读取每个同学前面的人
for (int i = 1; i <= n; i++) {
cin >> front[i];
}
// 建立前后关系
for (int i = 1; i <= n; i++) {
if (front[i] != 0) {
back[front[i]] = i; // 前面的人的后继是当前同学
}
}
// 找到队首（前面没有人的人）
int head = 0;
for (int i = 1; i <= n; i++) {
if (front[i] == 0) {
head = i;
break;
}
}
// 从队首开始输出队伍顺序
int current = head;
while (current != 0) {
cout << current << " ";
current = back[current];
}
return 0;
}
关键点说明
-
数据结构：
front数组存储每个同学前面的人back数组存储每个同学后面的人
-
建立关系：
- 遍历
front数组，填充back数组 - 如果i号同学前面是j号，那么j号后面就是i号
- 遍历
-
寻找队首：
- 队首的特征是前面没有人（front[i] == 0）
-
输出顺序：
- 从队首开始，沿着
back数组依次输出
- 从队首开始，沿着
示例解析
输入：
5
3 1 0 5 2
执行过程：
- front数组：[0,3,1,0,5,2]
- back数组：[3,2,5,1,4,0]
- 队首是3（front[3]==0）
- 输出顺序：3→1→2→5→4
输出：
3 1 2 5 4
优化思路
- 可以合并两个循环，在读取输入时直接建立back关系
- 使用更直观的变量名，如
prev和next代替front和back - 添加输入有效性检查，确保数据合法
这里空空如也
有帮助，赞一个