好的，我们来逐题解决这两个实验课作业问题。我会为每个问题提供： 1. **算法步骤描述** 2. **Python 代码实现** 3. **时间复杂度分析** --- ## ✅ 问题 1：合并两个非递减顺序表 A 和 B，得到新的非递减顺序表 C ### （1）算法步骤（归并排序中的“合并”思想） 由于 A 和 B 都是**非递减排列**（即升序或相等），我们可以使用**双指针法**进行高效合并： - 初始化三个指针： - `i` 指向 A 的当前元素（初始为 0） - `j` 指向 B 的当前元素（初始为 0） - `k` 指向结果列表 C 的当前位置（初始为 0） - 循环比较 A[i] 和 B[j]： - 如果 A[i] ≤ B[j]，将 A[i] 加入 C，i++ - 否则，将 B[j] 加入 C，j++ - 当其中一个数组遍历完后，将另一个数组剩余元素全部追加到 C 中。 - 最终 C 即为合并后的非递减序列。 > 注意：题目要求“利用线性表的基本运算”，这里我们用 Python 列表模拟顺序表，操作包括访问、追加等。 --- ### （2）Python 代码实现 ```python def merge_sorted_lists(A, B): i = j = 0 C = [] # 双指针合并 while i < len(A) and j < len(B): if A[i] <= B[j]: C.append(A[i]) i += 1 else: C.append(B[j]) j += 1 # 添加剩余元素 while i < len(A): C.append(A[i]) i += 1 while j < len(B): C.append(B[j]) j += 1 return C # 测试数据 A = [6, 11, 11, 23] B = [2, 10, 12, 12, 21] C = merge_sorted_lists(A, B) print("合并后结果:", C) ``` ✅ 输出： ``` 合并后结果: [2, 6, 10, 11, 11, 12, 12, 21, 23] ``` --- ### （3）时间复杂度分析 - 我们只遍历了 A 和 B 各一次，总操作次数为 `len(A) + len(B)` - 所以时间复杂度为：**O(m + n)**，其中 m = len(A), n = len(B) - 空间复杂度：O(m + n)，用于存储结果列表 C --- ## ✅ 问题 2：单链表中删除绝对值重复的结点（仅保留第一次出现） ### （1）算法步骤 目标：对于链表中 data 的**绝对值相等**的结点，只保留第一个出现的，其余删除。 例如：`21 → -15 → -15 → -7 → 15` → 绝对值：`21, 15, 15, 7, 15` → 保留第一个 21、第一个 -15、第一个 -7；第二个 -15 和最后一个 15 要删掉。 **思路：使用哈希集合记录已见过的绝对值** - 创建一个空集合 `seen_abs` 存储已经遇到过的绝对值。 - 从头结点开始遍历链表： - 计算当前结点数据的绝对值 `abs_val = abs(node.data)` - 如果 `abs_val` 已在 `seen_abs` 中 → 删除该结点（跳过它） - 否则 → 将 `abs_val` 加入 `seen_abs`，继续下一个结点 - 注意：因为是单链表，删除结点需要维护前驱指针。 > 为了简化，我们可以用虚拟头结点（dummy head）避免处理头结点被删的情况。 --- ### （2）Python 代码实现（定义链表结构 + 算法） ```python class ListNode: def __init__(self, data=0, next=None): self.data = data self.next = next def remove_duplicate_abs(head): if not head: return None seen_abs = set() dummy = ListNode(0, head) # 虚拟头结点 prev = dummy curr = head while curr: abs_val = abs(curr.data) if abs_val in seen_abs: # 删除当前结点 prev.next = curr.next else: # 保留当前结点，更新 seen_abs seen_abs.add(abs_val) prev = curr # 只有保留时才移动 prev curr = curr.next return dummy.next # 辅助函数：打印链表 def print_list(head): vals = [] while head: vals.append(str(head.data)) head = head.next print(" -> ".join(vals) if vals else "空链表") # 构建测试链表：21 -> -15 -> -15 -> -7 -> 15 head = ListNode(21) head.next = ListNode(-15) head.next.next = ListNode(-15) head.next.next.next = ListNode(-7) head.next.next.next.next = ListNode(15) print("原链表:") print_list(head) new_head = remove_duplicate_abs(head) print("删除后链表:") print_list(new_head) ``` ✅ 输出： ``` 原链表: 21 -> -15 -> -15 -> -7 -> 15 删除后链表: 21 -> -15 -> -7 ``` > 注意：虽然 15 的绝对值是 15，但前面已经有 -15（绝对值也是 15），所以 15 被删除。符合题意！ --- ### （3）时间复杂度分析 - 遍历整个链表一次：O(n)，n 是链表长度 - 每次访问结点时，计算绝对值和集合查找/插入都是 O(1) 平均情况 - 所以总时间复杂度：**O(n)** - 空间复杂度：O(k)，k 是不同绝对值的个数（最坏 O(n)） --- ## 📌 总结 | 问题 | 算法核心 | 时间复杂度 | 空间复杂度 | |------|----------|------------|------------| | 1. 合并有序表 | 双指针归并 | O(m+n) | O(m+n) | | 2. 删除绝对值重复结点 | 哈希集 + 单链表遍历 | O(n) | O(n) | --- 如果你希望我帮你把这两段代码整合成一个完整的 `.py` 文件，或者加上输入输出交互、图形化展示等功能，也可以告诉我！欢迎继续提问 😊