数据结构实战：从选择题到代码实现，5个经典操作手把手复现

数据结构实战从选择题到代码实现5个经典操作手把手复现1. 单链表删除后继节点链表操作是数据结构中最基础也最考验指针理解能力的内容。让我们从单链表删除后继节点开始这个操作看似简单但隐藏着指针操作的精华。核心逻辑给定节点p非首尾节点需要跳过其直接后继节点将p的next指针指向后继的后继节点。关键是要注意内存管理和指针顺序。// C实现 struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; void deleteNextNode(ListNode* p) { if (!p || !p-next) return; // 边界检查 ListNode* temp p-next; // 保存待删除节点 p-next temp-next; // 跳过后继节点 delete temp; // 释放内存 }测试用例设计# Python测试代码 class TestDeleteNext(unittest.TestCase): def test_normal_case(self): # 构造链表 1-2-3-4 n1 ListNode(1) n2 ListNode(2) n3 ListNode(3) n4 ListNode(4) n1.next, n2.next, n3.next n2, n3, n4 deleteNextNode(n2) # 删除节点3 self.assertEqual(n2.next.val, 4) def test_edge_case(self): # 构造链表 1-2 n1 ListNode(1) n2 ListNode(2) n1.next n2 with self.assertRaises(Exception): deleteNextNode(n2) # 尝试删除尾节点的后继复杂度分析时间复杂度O(1)空间复杂度O(1)内存安全需要特别注意被删除节点的内存释放2. 循环队列判满实现循环队列通过重用数组空间实现高效队列操作其核心难点在于判满条件的判断。我们来看两种常见的实现方式。方案一牺牲一个存储单元class CircularQueue: def __init__(self, capacity): self.capacity capacity 1 # 多分配一个空间 self.queue [None] * self.capacity self.front 0 self.rear 0 def is_full(self): return (self.rear 1) % self.capacity self.front方案二使用size变量// Java实现 public class CircularQueue { private int[] data; private int front, rear, size; public CircularQueue(int k) { data new int[k]; front rear size 0; } public boolean isFull() { return size data.length; } }性能对比方案优点缺点适用场景牺牲单元逻辑简单浪费一个空间嵌入式系统size变量空间利用率高需要维护size通用场景实际应用建议在内存受限的嵌入式系统中推荐方案一现代应用开发推荐方案二。3. 二叉搜索树插入操作二叉搜索树BST的插入操作需要保持左小右大的性质。我们来看递归和迭代两种实现方式。递归实现class TreeNode: def __init__(self, val0): self.val val self.left None self.right None def insertIntoBST(root, val): if not root: return TreeNode(val) if val root.val: root.left insertIntoBST(root.left, val) else: root.right insertIntoBST(root.right, val) return root迭代实现// C迭代版本 TreeNode* insertBST(TreeNode* root, int val) { TreeNode* node new TreeNode(val); if (!root) return node; TreeNode* curr root; while (true) { if (val curr-val) { if (!curr-left) { curr-left node; break; } curr curr-left; } else { if (!curr-right) { curr-right node; break; } curr curr-right; } } return root; }复杂度分析平均情况O(log n)最坏情况退化成链表O(n)空间复杂度递归O(h)迭代O(1)h为树高平衡性优化实际工程中应考虑使用AVL树或红黑树保持平衡避免退化成链表。4. 哈希表线性探测解决冲突哈希表的线性探测法是解决冲突的经典方法。我们实现一个支持插入、查找的基础哈希表。class HashTable: def __init__(self, size10): self.size size self.table [None] * size self.DELETED object() # 删除标记 def _hash(self, key): return key % self.size def insert(self, key): index self._hash(key) for _ in range(self.size): if self.table[index] is None or self.table[index] self.DELETED: self.table[index] key return True index (index 1) % self.size raise Exception(Hash table is full) def search(self, key): index self._hash(key) for _ in range(self.size): if self.table[index] key: return True if self.table[index] is None: # 遇到空位说明不存在 return False index (index 1) % self.size return False性能影响因素装载因子load factor建议保持在0.7以下哈希函数质量应尽量均匀分布聚集现象线性探测可能导致一次聚集工程优化建议动态扩容当装载因子超过阈值时扩大哈希表二次探测使用平方探测减少聚集双重哈希使用第二个哈希函数计算步长5. 快速排序划分算法快速排序的核心在于划分partition操作我们实现Lomuto和Hoare两种经典划分方案。Lomuto划分方案// Java实现 public int partitionLomuto(int[] arr, int low, int high) { int pivot arr[high]; // 选择最后一个元素作为基准 int i low; for (int j low; j high; j) { if (arr[j] pivot) { swap(arr, i, j); i; } } swap(arr, i, high); return i; }Hoare划分方案// C语言实现 int partitionHoare(int arr[], int low, int high) { int pivot arr[low (high - low)/2]; // 选择中间元素 int i low - 1; int j high 1; while (1) { do { i; } while (arr[i] pivot); do { j--; } while (arr[j] pivot); if (i j) return j; swap(arr[i], arr[j]); } }两种方案对比特性LomutoHoare实现复杂度简单较复杂交换次数较多较少基准选择必须选尾部任意位置返回位置基准最终位置分割点位置实际应用建议教学场景推荐Lomuto方案易于理解工程实践推荐Hoare方案性能更优特殊场景对于大量重复元素可使用三路划分在实现这些基础数据结构操作时有几个常见陷阱需要注意指针操作前必须检查空指针循环终止条件要仔细验证边界条件要单独测试内存管理要规范特别是C/C递归实现要注意栈溢出风险