这次我们来看一门悉尼大学USYD的核心课程——COMP9123数据结构与算法。这门课是计算机科学及相关专业的基石无论是准备求职面试、提升编程能力还是为后续的算法竞赛和高级课程打基础都至关重要。对于许多同学来说数据结构与算法既是难点也是必须攻克的堡垒。本文将基于COMP9123课程第一周公开课的内容为你系统梳理数据结构与算法的核心入门知识、学习路径以及高效实践方法。课程的核心目标不是让你死记硬背代码而是理解数据如何组织、算法如何运作并能在实际问题中灵活应用。本文将重点拆解第一周的关键概念包括抽象数据类型ADT、算法复杂度分析大O表示法、以及数组、链表等基础数据结构的实现与对比。我们不仅会讲解理论更会提供清晰的代码示例和实战练习思路帮助你从“知道”过渡到“会用”。如果你正在学习COMP9123或者任何一门类似的数据结构与算法课程这篇文章将为你提供一个清晰的学习框架和自查清单。我们将从最基础的环境准备编程语言与IDE选择开始逐步深入到复杂度分析、数据结构实现和算法设计最后给出常见问题的排查与高效学习建议。1. 核心能力速览数据结构与算法入门要点在深入细节之前我们先通过一个表格快速了解学习数据结构与算法需要掌握的核心能力和关注点。这能帮助你判断自己的起点和本篇文章的覆盖范围。能力项说明与课程重点课程定位计算机科学基础核心课强调理论理解与编程实践的结合。核心语言通常使用 Java, C, 或 Python。COMP9123 可能以 Java 或 Python 为主。本文示例将采用 Python 和 Java 进行对比演示因其语法清晰易于理解概念。先修知识至少掌握一门编程语言的基础语法变量、循环、条件、函数。核心理论抽象数据类型ADT、算法时间复杂度与空间复杂度大O表示法、递归。基础数据结构数组Array、链表Linked List、栈Stack、队列Queue。实践重点手动实现数据结构、分析不同操作的复杂度、比较不同数据结构的适用场景。评估方式通常包含作业实现与应用、期中/期末考试理论与分析。学习产出获得用代码描述和操作数据的能力为学习树、图、排序、查找等高级内容打下坚实基础。2. 适用场景与学习目标学习数据结构与算法绝不是为了应付某一次考试。它的价值体现在多个层面学术深造这是所有高级计算机课程如操作系统、数据库、编译原理、机器学习的前置知识。不理解数据如何高效组织就无法理解更复杂的系统。求职面试国内外一线科技公司的技术面试几乎必考数据结构与算法。面试官通过它来考察候选人的问题分析、逻辑思维和编码能力。 |场景|具体应用|涉及的数据结构/算法| | :--- | :--- | :--- | |软件开发| 实现一个浏览器的“后退”功能。 |栈Stack| | | 处理打印任务的队列。 |队列Queue| | | 高效管理内存中的对象引用。 |链表Linked List| | | 快速查询用户信息。 |数组Array、哈希表后续| |算法竞赛/在线判题| 解决LeetCode、HackerRank等平台上的问题。 | 所有基础及高级数据结构和算法。 | |性能优化| 分析程序为什么在数据量大时变慢如何优化。 |复杂度分析大O|对于COMP9123 Week1我们的学习目标非常明确理解抽象数据类型ADT的概念明确“接口”与“实现”的分离。掌握大O表示法能够分析和比较不同算法/操作的时间、空间复杂度。实现并对比数组和链表理解它们在内存中的存储方式以及增删改查操作的性能差异。3. 环境准备与前置条件工欲善其事必先利其器。开始动手实践前你需要准备好编程环境。3.1 编程语言选择COMP9123课程可能指定某种语言。如果没有建议选择Python语法简洁适合快速验证想法理解概念。但在理解底层内存管理如链表指针时略显抽象。Java强类型、面向对象更贴近数据结构课本的描述对理解引用指针概念有帮助。C提供最底层的控制如指针、内存分配是理解数据结构“本源”的最佳语言但学习曲线较陡。本文为了兼顾清晰与通用性关键示例会同时提供 Python 和 Java 版本。3.2 开发环境搭建安装语言解释器/编译器Python从 python.org 下载安装。确保将Python添加到系统环境变量PATH中。Java安装 JDK (Java Development Kit)推荐 OpenJDK 11 或以上版本。选择代码编辑器或IDE轻量级VS Code、Sublime Text。需要安装相应的语言扩展包。集成开发环境IDEPythonPyCharm (Community版免费)。JavaIntelliJ IDEA (Community版免费)、Eclipse。在线环境如果本地配置困难可以使用 Replit、GitHub Codespaces 等在线编程环境临时练习。验证安装 打开终端Windows: CMD/PowerShell; Mac/Linux: Terminal输入以下命令验证# 验证 Python python --version # 或 python3 --version # 验证 Java java -version javac -version成功显示版本号即表示环境就绪。4. 核心概念解析与代码实现现在我们进入第一周的核心内容。我们将遵循“概念 - 实现 - 分析”的路径。4.1 抽象数据类型ADTADT 定义了一个数据类型的逻辑行为能做什么而不关心其具体实现怎么做。它是接口Interface或规范Specification。以“栈Stack”为例ADT 定义的操作push(入栈),pop(出栈),peek/top(查看栈顶),is_empty(是否为空)。可能的实现方式可以用数组实现也可以用链表实现。用户只需要调用push和pop无需关心底层是数组还是链表。代码示例栈的ADT接口// Java 接口定义栈的ADT public interface StackADTT { void push(T item); // 入栈 T pop(); // 出栈并返回元素 T peek(); // 查看栈顶元素 boolean isEmpty(); // 判断栈是否为空 int size(); // 返回栈的大小 }# Python 中通常用类来约定ADT虽然没有严格的接口语法 class StackADT: def push(self, item): 将元素item压入栈顶 raise NotImplementedError def pop(self): 弹出并返回栈顶元素栈为空时抛出异常 raise NotImplementedError def peek(self): 返回栈顶元素但不弹出栈为空时抛出异常 raise NotImplementedError def is_empty(self): 判断栈是否为空 raise NotImplementedError def size(self): 返回栈中元素个数 raise NotImplementedError4.2 算法复杂度分析大O表示法这是评估算法效率的理论工具。我们关注时间复杂度运行时间随数据规模增长的趋势和空间复杂度内存占用随数据规模增长的趋势。核心规则忽略常数和低阶项O(3n² 10n 100) 简化为 O(n²)。关注最坏情况通常用最坏情况下的复杂度作为算法性能的保证。常见复杂度从优到劣O(1): 常数时间。例如访问数组索引。O(log n): 对数时间。例如二分查找。O(n): 线性时间。例如遍历链表。O(n log n): 线性对数时间。例如快速排序、归并排序。O(n²): 平方时间。例如嵌套循环的简单排序冒泡、选择。O(2^n), O(n!): 指数级、阶乘级通常不可接受。实战分析查找数组中的最大值def find_max(arr): max_val arr[0] # O(1) for num in arr: # 循环 n 次 if num max_val: # 每次循环操作是 O(1) max_val num # O(1) return max_val # O(1)总时间O(1) n * O(1) O(1) O(n)空间只用了固定数量的变量 (max_val)与输入数组arr的大小n无关所以是O(1)。4.3 基础数据结构实现与对比数组 vs. 链表这是Week1的实践重点。我们通过实现“动态数组”类似Python的list/Java的ArrayList和“单向链表”来深入理解。4.3.1 动态数组Dynamic Array核心思想底层使用静态数组当容量不足时分配一个更大的新数组通常是原容量的2倍并将旧数据拷贝过去。Python 实现要点模拟class DynamicArray: def __init__(self): self._capacity 10 # 初始容量 self._size 0 # 当前元素数量 self._data [None] * self._capacity def append(self, value): 在末尾添加元素若容量不足则扩容 if self._size self._capacity: self._resize(2 * self._capacity) self._data[self._size] value self._size 1 def _resize(self, new_capacity): 内部扩容方法 new_data [None] * new_capacity for i in range(self._size): new_data[i] self._data[i] self._data new_data self._capacity new_capacity def get(self, index): if 0 index self._size: return self._data[index] raise IndexError(Index out of range) # ... 其他方法如 insert, delete 等复杂度分析访问get(i)O(1)。因为数组支持随机访问。末尾追加append平均O(1)。虽然扩容时是 O(n)但分摊到多次操作后平均成本是常数。中间插入/删除O(n)。因为需要移动后续所有元素。4.3.2 单向链表Singly Linked List核心思想数据存储在节点Node中每个节点包含值value和指向下一个节点的引用next。通过头节点head来访问整个链表。Java 实现要点// 节点类 class NodeT { T data; NodeT next; Node(T data) { this.data data; this.next null; } } // 链表类 public class SinglyLinkedListT { private NodeT head; private int size; public SinglyLinkedList() { head null; size 0; } // 在链表头部添加节点 O(1) public void addFirst(T item) { NodeT newNode new Node(item); newNode.next head; head newNode; size; } // 在链表末尾添加节点 O(n)因为需要遍历到尾部 public void addLast(T item) { if (head null) { addFirst(item); return; } NodeT current head; while (current.next ! null) { current current.next; } current.next new Node(item); size; } // 根据索引查找节点 O(n) public NodeT getNode(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(); } NodeT current head; for (int i 0; i index; i) { current current.next; } return current; } // ... 其他方法 }复杂度分析访问get(i)O(n)。必须从头节点开始逐个遍历。头部插入addFirstO(1)。只需修改头节点引用。尾部插入addLastO(n)。需要遍历到尾部如果未维护尾指针。中间插入/删除在找到目标位置后操作本身是 O(1)但查找过程是 O(n)。4.3.3 数组与链表对比总结操作动态数组 (ArrayList)单向链表 (LinkedList)说明随机访问O(1)O(n)数组的绝对优势。头部插入/删除O(n)O(1)链表的优势。尾部插入/删除O(1)(摊销)O(n) (若无尾指针) / O(1) (有尾指针)数组通常更快。中间插入/删除O(n)O(n) (查找) O(1) (操作)平手但链表操作部分更快。空间占用可能浪费预留容量每个节点有额外指针开销数组通常更紧凑。内存连续性连续对CPU缓存友好非连续缓存不友好数组在迭代时性能往往更好。选择依据需要频繁按索引访问 -用数组。需要频繁在头部或中间插入/删除 -用链表。数据规模变化大难以预估 -链表或动态数组数组扩容有成本。追求极致迭代性能 -数组。5. 功能测试与效果验证理论学习后必须通过编码来验证。我们设计几个测试来巩固对数组和链表的理解。5.1 测试1实现并测试一个栈使用数组和链表两种方式目的理解同一ADT的不同实现并验证其行为一致。步骤分别用DynamicArray和SinglyLinkedList作为底层存储实现StackADT接口。编写相同的测试代码对两个栈实现进行测试。验证push,pop,peek,is_empty操作是否正确。测试代码示例Pythondef test_stack(stack_impl): 测试栈的基本功能 s stack_impl assert s.is_empty() s.push(10) s.push(20) assert not s.is_empty() assert s.peek() 20 assert s.pop() 20 assert s.pop() 10 assert s.is_empty() print(f{stack_impl.__class__.__name__} 测试通过) # 测试 test_stack(ArrayStack()) # 假设你实现了ArrayStack test_stack(LinkedStack()) # 假设你实现了LinkedStack5.2 测试2复杂度实验——对比数组和链表的插入性能目的直观感受 O(1) 和 O(n) 操作的性能差异。步骤向动态数组的末尾连续添加 N 个元素例如 N100000记录时间。这应该是接近 O(1) 的摊销时间。向动态数组的头部连续添加 N 个元素记录时间。这将是 O(n) 每次总时间约为 O(n²)。向单向链表的头部连续添加 N 个元素记录时间。这应该是 O(1) 每次总时间 O(n)。对比三组时间数据。代码思路import time def benchmark_insertions(data_structure, positionend, num_elements10000): 基准测试插入操作 start time.time() if position end: for i in range(num_elements): data_structure.append(i) # 假设有append方法 elif position beginning: for i in range(num_elements): data_structure.insert(0, i) # 假设有insert方法 end time.time() return end - start # 执行测试 arr DynamicArray() linked_list SinglyLinkedList() time_arr_end benchmark_insertions(arr, end, 50000) time_arr_begin benchmark_insertions(arr, beginning, 5000) # 数量减少因为太慢 time_list_begin benchmark_insertions(linked_list, beginning, 50000) print(f数组尾部插入: {time_arr_end:.4f} 秒) print(f数组头部插入: {time_arr_begin:.4f} 秒 (仅5000次)) print(f链表头部插入: {time_list_begin:.4f} 秒)预期结果数组头部插入的时间会远高于其他两者尤其是当数据量增大时差异会呈平方级增长。这直观地验证了复杂度分析。6. 接口设计与批量任务思考虽然第一周不涉及复杂的系统但建立良好的接口思维对后续学习至关重要。6.1 清晰的接口API设计为你实现的数据结构设计清晰的方法签名和文档字符串Docstring。这能让你和你的合作者或未来的你更容易理解和使用代码。好的示例Pythonclass ListADT: def insert(self, index: int, value: any) - None: 在指定索引位置插入一个值。 参数 index (int): 要插入位置的索引。必须满足 0 index size()。 value (any): 要插入的值。 异常 IndexError: 如果索引超出有效范围。 # ... 实现细节6.2 批量任务处理思路想象你需要处理一个日志文件每行是一个记录。你需要频繁地在序列中间插入新的日志按时间排序。你会选择数组还是链表分析频繁的中间插入是链表的潜在优势场景O(1)插入但前提是你能快速定位到插入位置。如果每次都需要从头遍历查找位置O(n)查找则总复杂度仍是O(n)。此时更高级的数据结构如跳表或平衡二叉搜索树可能更合适。这引出了后续课程的内容。简单的批量处理框架def process_logs_with_list(log_entries, data_structure): 使用给定的数据结构处理日志条目 for entry in log_entries: # 假设需要根据entry的timestamp找到插入位置 index find_insertion_index(data_structure, entry.timestamp) data_structure.insert(index, entry) return data_structure通过这个框架你可以轻松替换不同的data_structure实现如你的DynamicArray或SinglyLinkedList来测试性能。7. 资源占用与性能观察在数据结构学习中“资源占用”主要指空间复杂度。你需要关注额外空间开销链表每个节点除了数据还有至少一个指针8字节。对于存储小对象如一个整数指针开销占比可能很大。内存碎片链表节点在内存中分散存储可能导致缓存命中率低影响遍历速度。动态数组的扩容成本虽然摊销复杂度是 O(1)但单次扩容的 O(n) 操作可能导致某次append有明显的延迟。在实时性要求高的系统中需要考虑。观察方法空间对于简单练习可以通过计算来估算。例如存储 N 个整数数组约N * sizeof(int) 少量管理开销。单向链表约N * (sizeof(int) sizeof(pointer))。时间使用像上面benchmark_insertions这样的函数进行计时。使用更大的 N如10万、100万来观察增长趋势。8. 常见问题与排查方法初学数据结构实现时很容易遇到一些典型错误。问题现象可能原因排查方式解决方案NullPointerException(Java) 或AttributeError(Python)试图访问null或None对象的属性。在链表中常见。检查指针/引用在移动current current.next之前current是否已为null/None。在循环条件中增加判空检查如while current ! null current.next ! null。索引越界 (IndexOutOfBounds)访问数组或链表时索引值i不在有效范围[0, size-1]内。在get(i),insert(i, v),delete(i)等方法开头检查i是否满足0 i size。添加参数合法性校验并抛出清晰的异常信息。链表操作后丢失节点或形成环修改节点指针next时顺序错误。例如在插入新节点时先断开了原有链接。画图在纸上画出操作前后节点的链接关系。单步调试Debug观察指针变化。记住链表操作的口诀“先接后断”或“先设置新节点的next再修改原节点的next”。动态数组扩容后数据错误或索引错乱扩容时旧数组数据没有正确拷贝到新数组。或者size和capacity变量未正确更新。在_resize方法后打印数组内容。检查拷贝循环的边界i in range(self._size)。确保拷贝循环正确并在扩容后更新self._capacity。递归操作导致栈溢出在实现链表打印、反转时使用了递归链表过长。对于链表遍历等操作优先使用迭代循环。如果必须用递归确保递归基线条件正确。将递归算法改为迭代算法。复杂度分析与实际运行时间不符忽略了常数因子、硬件差异、或测试数据规模太小。增大测试数据规模N。关注增长趋势而非绝对时间。使用大O表示法时忽略常数。确保测试数据足够大例如 N 10000以抵消常数开销的影响。9. 最佳实践与学习建议从画图开始在编码实现链表、树等指针结构前务必在纸上画出节点的链接关系。这是理解指针操作最有效的方法。先写测试再写实现TDD定义好接口方法签名后先写一些简单的测试用例。这能帮你明确目标并在实现后快速验证。理解优于记忆不要死记硬背代码。理解每个操作为什么是那个复杂度理解数组和链表在内存模型上的根本区别。主动探索变体实现了单向链表后尝试实现双向链表或循环链表。实现了动态数组后思考如何实现稀疏数组。善用调试器使用IDE的调试功能设置断点、单步执行、查看变量直观地观察程序执行时数据结构和变量的变化。连接到实际问题每学一个数据结构就去LeetCode或课本上找一个相关的简单题目如用栈实现括号匹配、用队列实现BFS练习。重视代码风格和文档为你的类和方法编写清晰的注释。良好的命名和结构能让你在几周后回顾代码时依然能看懂。10. 总结与下一步COMP9123第一周的内容为整个课程搭建了坚实的脚手架。抽象数据类型ADT教会我们如何定义规范大O表示法给了我们分析算法效率的标尺而数组和链表的对比则深刻地揭示了程序设计中“权衡”Trade-off的思想——没有完美的数据结构只有适合特定场景的选择。最值得你立刻动手尝试的就是完整实现一遍动态数组和单向链表并完成我们上面提到的性能对比测试。这个过程中最容易踩的坑是指针操作链表和索引边界数组务必对照第8节的排查表仔细检查。掌握了这些基础下一步的学习路径就非常清晰了Week2 及以后你会基于栈和队列它们可以用数组或链表轻松实现学习更复杂的结构如树二叉树、二叉搜索树、图以及经典的排序和查找算法。深化理解探索为什么哈希表能在平均情况下实现 O(1) 的查找这背后又是数组和链表的结合。实战应用开始刷题。从LeetCode的“简单”难度开始重点练习数组和链表标签下的题目。将理论应用于解决具体问题是巩固知识的最佳方式。建议将本文作为一份实践指南收藏备用。当你实现数据结构遇到困难或者对复杂度分析感到疑惑时可以随时回来查阅具体的代码示例和排查步骤。记住理解数据结构和算法的唯一捷径就是不断地思考、画图和编码。 数据结构与算法入门：从ADT、大O到数组与链表的实现与对比
这次我们来看一门悉尼大学USYD的核心课程——COMP9123数据结构与算法。这门课是计算机科学及相关专业的基石无论是准备求职面试、提升编程能力还是为后续的算法竞赛和高级课程打基础都至关重要。对于许多同学来说数据结构与算法既是难点也是必须攻克的堡垒。本文将基于COMP9123课程第一周公开课的内容为你系统梳理数据结构与算法的核心入门知识、学习路径以及高效实践方法。课程的核心目标不是让你死记硬背代码而是理解数据如何组织、算法如何运作并能在实际问题中灵活应用。本文将重点拆解第一周的关键概念包括抽象数据类型ADT、算法复杂度分析大O表示法、以及数组、链表等基础数据结构的实现与对比。我们不仅会讲解理论更会提供清晰的代码示例和实战练习思路帮助你从“知道”过渡到“会用”。如果你正在学习COMP9123或者任何一门类似的数据结构与算法课程这篇文章将为你提供一个清晰的学习框架和自查清单。我们将从最基础的环境准备编程语言与IDE选择开始逐步深入到复杂度分析、数据结构实现和算法设计最后给出常见问题的排查与高效学习建议。1. 核心能力速览数据结构与算法入门要点在深入细节之前我们先通过一个表格快速了解学习数据结构与算法需要掌握的核心能力和关注点。这能帮助你判断自己的起点和本篇文章的覆盖范围。能力项说明与课程重点课程定位计算机科学基础核心课强调理论理解与编程实践的结合。核心语言通常使用 Java, C, 或 Python。COMP9123 可能以 Java 或 Python 为主。本文示例将采用 Python 和 Java 进行对比演示因其语法清晰易于理解概念。先修知识至少掌握一门编程语言的基础语法变量、循环、条件、函数。核心理论抽象数据类型ADT、算法时间复杂度与空间复杂度大O表示法、递归。基础数据结构数组Array、链表Linked List、栈Stack、队列Queue。实践重点手动实现数据结构、分析不同操作的复杂度、比较不同数据结构的适用场景。评估方式通常包含作业实现与应用、期中/期末考试理论与分析。学习产出获得用代码描述和操作数据的能力为学习树、图、排序、查找等高级内容打下坚实基础。2. 适用场景与学习目标学习数据结构与算法绝不是为了应付某一次考试。它的价值体现在多个层面学术深造这是所有高级计算机课程如操作系统、数据库、编译原理、机器学习的前置知识。不理解数据如何高效组织就无法理解更复杂的系统。求职面试国内外一线科技公司的技术面试几乎必考数据结构与算法。面试官通过它来考察候选人的问题分析、逻辑思维和编码能力。 |场景|具体应用|涉及的数据结构/算法| | :--- | :--- | :--- | |软件开发| 实现一个浏览器的“后退”功能。 |栈Stack| | | 处理打印任务的队列。 |队列Queue| | | 高效管理内存中的对象引用。 |链表Linked List| | | 快速查询用户信息。 |数组Array、哈希表后续| |算法竞赛/在线判题| 解决LeetCode、HackerRank等平台上的问题。 | 所有基础及高级数据结构和算法。 | |性能优化| 分析程序为什么在数据量大时变慢如何优化。 |复杂度分析大O|对于COMP9123 Week1我们的学习目标非常明确理解抽象数据类型ADT的概念明确“接口”与“实现”的分离。掌握大O表示法能够分析和比较不同算法/操作的时间、空间复杂度。实现并对比数组和链表理解它们在内存中的存储方式以及增删改查操作的性能差异。3. 环境准备与前置条件工欲善其事必先利其器。开始动手实践前你需要准备好编程环境。3.1 编程语言选择COMP9123课程可能指定某种语言。如果没有建议选择Python语法简洁适合快速验证想法理解概念。但在理解底层内存管理如链表指针时略显抽象。Java强类型、面向对象更贴近数据结构课本的描述对理解引用指针概念有帮助。C提供最底层的控制如指针、内存分配是理解数据结构“本源”的最佳语言但学习曲线较陡。本文为了兼顾清晰与通用性关键示例会同时提供 Python 和 Java 版本。3.2 开发环境搭建安装语言解释器/编译器Python从 python.org 下载安装。确保将Python添加到系统环境变量PATH中。Java安装 JDK (Java Development Kit)推荐 OpenJDK 11 或以上版本。选择代码编辑器或IDE轻量级VS Code、Sublime Text。需要安装相应的语言扩展包。集成开发环境IDEPythonPyCharm (Community版免费)。JavaIntelliJ IDEA (Community版免费)、Eclipse。在线环境如果本地配置困难可以使用 Replit、GitHub Codespaces 等在线编程环境临时练习。验证安装 打开终端Windows: CMD/PowerShell; Mac/Linux: Terminal输入以下命令验证# 验证 Python python --version # 或 python3 --version # 验证 Java java -version javac -version成功显示版本号即表示环境就绪。4. 核心概念解析与代码实现现在我们进入第一周的核心内容。我们将遵循“概念 - 实现 - 分析”的路径。4.1 抽象数据类型ADTADT 定义了一个数据类型的逻辑行为能做什么而不关心其具体实现怎么做。它是接口Interface或规范Specification。以“栈Stack”为例ADT 定义的操作push(入栈),pop(出栈),peek/top(查看栈顶),is_empty(是否为空)。可能的实现方式可以用数组实现也可以用链表实现。用户只需要调用push和pop无需关心底层是数组还是链表。代码示例栈的ADT接口// Java 接口定义栈的ADT public interface StackADTT { void push(T item); // 入栈 T pop(); // 出栈并返回元素 T peek(); // 查看栈顶元素 boolean isEmpty(); // 判断栈是否为空 int size(); // 返回栈的大小 }# Python 中通常用类来约定ADT虽然没有严格的接口语法 class StackADT: def push(self, item): 将元素item压入栈顶 raise NotImplementedError def pop(self): 弹出并返回栈顶元素栈为空时抛出异常 raise NotImplementedError def peek(self): 返回栈顶元素但不弹出栈为空时抛出异常 raise NotImplementedError def is_empty(self): 判断栈是否为空 raise NotImplementedError def size(self): 返回栈中元素个数 raise NotImplementedError4.2 算法复杂度分析大O表示法这是评估算法效率的理论工具。我们关注时间复杂度运行时间随数据规模增长的趋势和空间复杂度内存占用随数据规模增长的趋势。核心规则忽略常数和低阶项O(3n² 10n 100) 简化为 O(n²)。关注最坏情况通常用最坏情况下的复杂度作为算法性能的保证。常见复杂度从优到劣O(1): 常数时间。例如访问数组索引。O(log n): 对数时间。例如二分查找。O(n): 线性时间。例如遍历链表。O(n log n): 线性对数时间。例如快速排序、归并排序。O(n²): 平方时间。例如嵌套循环的简单排序冒泡、选择。O(2^n), O(n!): 指数级、阶乘级通常不可接受。实战分析查找数组中的最大值def find_max(arr): max_val arr[0] # O(1) for num in arr: # 循环 n 次 if num max_val: # 每次循环操作是 O(1) max_val num # O(1) return max_val # O(1)总时间O(1) n * O(1) O(1) O(n)空间只用了固定数量的变量 (max_val)与输入数组arr的大小n无关所以是O(1)。4.3 基础数据结构实现与对比数组 vs. 链表这是Week1的实践重点。我们通过实现“动态数组”类似Python的list/Java的ArrayList和“单向链表”来深入理解。4.3.1 动态数组Dynamic Array核心思想底层使用静态数组当容量不足时分配一个更大的新数组通常是原容量的2倍并将旧数据拷贝过去。Python 实现要点模拟class DynamicArray: def __init__(self): self._capacity 10 # 初始容量 self._size 0 # 当前元素数量 self._data [None] * self._capacity def append(self, value): 在末尾添加元素若容量不足则扩容 if self._size self._capacity: self._resize(2 * self._capacity) self._data[self._size] value self._size 1 def _resize(self, new_capacity): 内部扩容方法 new_data [None] * new_capacity for i in range(self._size): new_data[i] self._data[i] self._data new_data self._capacity new_capacity def get(self, index): if 0 index self._size: return self._data[index] raise IndexError(Index out of range) # ... 其他方法如 insert, delete 等复杂度分析访问get(i)O(1)。因为数组支持随机访问。末尾追加append平均O(1)。虽然扩容时是 O(n)但分摊到多次操作后平均成本是常数。中间插入/删除O(n)。因为需要移动后续所有元素。4.3.2 单向链表Singly Linked List核心思想数据存储在节点Node中每个节点包含值value和指向下一个节点的引用next。通过头节点head来访问整个链表。Java 实现要点// 节点类 class NodeT { T data; NodeT next; Node(T data) { this.data data; this.next null; } } // 链表类 public class SinglyLinkedListT { private NodeT head; private int size; public SinglyLinkedList() { head null; size 0; } // 在链表头部添加节点 O(1) public void addFirst(T item) { NodeT newNode new Node(item); newNode.next head; head newNode; size; } // 在链表末尾添加节点 O(n)因为需要遍历到尾部 public void addLast(T item) { if (head null) { addFirst(item); return; } NodeT current head; while (current.next ! null) { current current.next; } current.next new Node(item); size; } // 根据索引查找节点 O(n) public NodeT getNode(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(); } NodeT current head; for (int i 0; i index; i) { current current.next; } return current; } // ... 其他方法 }复杂度分析访问get(i)O(n)。必须从头节点开始逐个遍历。头部插入addFirstO(1)。只需修改头节点引用。尾部插入addLastO(n)。需要遍历到尾部如果未维护尾指针。中间插入/删除在找到目标位置后操作本身是 O(1)但查找过程是 O(n)。4.3.3 数组与链表对比总结操作动态数组 (ArrayList)单向链表 (LinkedList)说明随机访问O(1)O(n)数组的绝对优势。头部插入/删除O(n)O(1)链表的优势。尾部插入/删除O(1)(摊销)O(n) (若无尾指针) / O(1) (有尾指针)数组通常更快。中间插入/删除O(n)O(n) (查找) O(1) (操作)平手但链表操作部分更快。空间占用可能浪费预留容量每个节点有额外指针开销数组通常更紧凑。内存连续性连续对CPU缓存友好非连续缓存不友好数组在迭代时性能往往更好。选择依据需要频繁按索引访问 -用数组。需要频繁在头部或中间插入/删除 -用链表。数据规模变化大难以预估 -链表或动态数组数组扩容有成本。追求极致迭代性能 -数组。5. 功能测试与效果验证理论学习后必须通过编码来验证。我们设计几个测试来巩固对数组和链表的理解。5.1 测试1实现并测试一个栈使用数组和链表两种方式目的理解同一ADT的不同实现并验证其行为一致。步骤分别用DynamicArray和SinglyLinkedList作为底层存储实现StackADT接口。编写相同的测试代码对两个栈实现进行测试。验证push,pop,peek,is_empty操作是否正确。测试代码示例Pythondef test_stack(stack_impl): 测试栈的基本功能 s stack_impl assert s.is_empty() s.push(10) s.push(20) assert not s.is_empty() assert s.peek() 20 assert s.pop() 20 assert s.pop() 10 assert s.is_empty() print(f{stack_impl.__class__.__name__} 测试通过) # 测试 test_stack(ArrayStack()) # 假设你实现了ArrayStack test_stack(LinkedStack()) # 假设你实现了LinkedStack5.2 测试2复杂度实验——对比数组和链表的插入性能目的直观感受 O(1) 和 O(n) 操作的性能差异。步骤向动态数组的末尾连续添加 N 个元素例如 N100000记录时间。这应该是接近 O(1) 的摊销时间。向动态数组的头部连续添加 N 个元素记录时间。这将是 O(n) 每次总时间约为 O(n²)。向单向链表的头部连续添加 N 个元素记录时间。这应该是 O(1) 每次总时间 O(n)。对比三组时间数据。代码思路import time def benchmark_insertions(data_structure, positionend, num_elements10000): 基准测试插入操作 start time.time() if position end: for i in range(num_elements): data_structure.append(i) # 假设有append方法 elif position beginning: for i in range(num_elements): data_structure.insert(0, i) # 假设有insert方法 end time.time() return end - start # 执行测试 arr DynamicArray() linked_list SinglyLinkedList() time_arr_end benchmark_insertions(arr, end, 50000) time_arr_begin benchmark_insertions(arr, beginning, 5000) # 数量减少因为太慢 time_list_begin benchmark_insertions(linked_list, beginning, 50000) print(f数组尾部插入: {time_arr_end:.4f} 秒) print(f数组头部插入: {time_arr_begin:.4f} 秒 (仅5000次)) print(f链表头部插入: {time_list_begin:.4f} 秒)预期结果数组头部插入的时间会远高于其他两者尤其是当数据量增大时差异会呈平方级增长。这直观地验证了复杂度分析。6. 接口设计与批量任务思考虽然第一周不涉及复杂的系统但建立良好的接口思维对后续学习至关重要。6.1 清晰的接口API设计为你实现的数据结构设计清晰的方法签名和文档字符串Docstring。这能让你和你的合作者或未来的你更容易理解和使用代码。好的示例Pythonclass ListADT: def insert(self, index: int, value: any) - None: 在指定索引位置插入一个值。 参数 index (int): 要插入位置的索引。必须满足 0 index size()。 value (any): 要插入的值。 异常 IndexError: 如果索引超出有效范围。 # ... 实现细节6.2 批量任务处理思路想象你需要处理一个日志文件每行是一个记录。你需要频繁地在序列中间插入新的日志按时间排序。你会选择数组还是链表分析频繁的中间插入是链表的潜在优势场景O(1)插入但前提是你能快速定位到插入位置。如果每次都需要从头遍历查找位置O(n)查找则总复杂度仍是O(n)。此时更高级的数据结构如跳表或平衡二叉搜索树可能更合适。这引出了后续课程的内容。简单的批量处理框架def process_logs_with_list(log_entries, data_structure): 使用给定的数据结构处理日志条目 for entry in log_entries: # 假设需要根据entry的timestamp找到插入位置 index find_insertion_index(data_structure, entry.timestamp) data_structure.insert(index, entry) return data_structure通过这个框架你可以轻松替换不同的data_structure实现如你的DynamicArray或SinglyLinkedList来测试性能。7. 资源占用与性能观察在数据结构学习中“资源占用”主要指空间复杂度。你需要关注额外空间开销链表每个节点除了数据还有至少一个指针8字节。对于存储小对象如一个整数指针开销占比可能很大。内存碎片链表节点在内存中分散存储可能导致缓存命中率低影响遍历速度。动态数组的扩容成本虽然摊销复杂度是 O(1)但单次扩容的 O(n) 操作可能导致某次append有明显的延迟。在实时性要求高的系统中需要考虑。观察方法空间对于简单练习可以通过计算来估算。例如存储 N 个整数数组约N * sizeof(int) 少量管理开销。单向链表约N * (sizeof(int) sizeof(pointer))。时间使用像上面benchmark_insertions这样的函数进行计时。使用更大的 N如10万、100万来观察增长趋势。8. 常见问题与排查方法初学数据结构实现时很容易遇到一些典型错误。问题现象可能原因排查方式解决方案NullPointerException(Java) 或AttributeError(Python)试图访问null或None对象的属性。在链表中常见。检查指针/引用在移动current current.next之前current是否已为null/None。在循环条件中增加判空检查如while current ! null current.next ! null。索引越界 (IndexOutOfBounds)访问数组或链表时索引值i不在有效范围[0, size-1]内。在get(i),insert(i, v),delete(i)等方法开头检查i是否满足0 i size。添加参数合法性校验并抛出清晰的异常信息。链表操作后丢失节点或形成环修改节点指针next时顺序错误。例如在插入新节点时先断开了原有链接。画图在纸上画出操作前后节点的链接关系。单步调试Debug观察指针变化。记住链表操作的口诀“先接后断”或“先设置新节点的next再修改原节点的next”。动态数组扩容后数据错误或索引错乱扩容时旧数组数据没有正确拷贝到新数组。或者size和capacity变量未正确更新。在_resize方法后打印数组内容。检查拷贝循环的边界i in range(self._size)。确保拷贝循环正确并在扩容后更新self._capacity。递归操作导致栈溢出在实现链表打印、反转时使用了递归链表过长。对于链表遍历等操作优先使用迭代循环。如果必须用递归确保递归基线条件正确。将递归算法改为迭代算法。复杂度分析与实际运行时间不符忽略了常数因子、硬件差异、或测试数据规模太小。增大测试数据规模N。关注增长趋势而非绝对时间。使用大O表示法时忽略常数。确保测试数据足够大例如 N 10000以抵消常数开销的影响。9. 最佳实践与学习建议从画图开始在编码实现链表、树等指针结构前务必在纸上画出节点的链接关系。这是理解指针操作最有效的方法。先写测试再写实现TDD定义好接口方法签名后先写一些简单的测试用例。这能帮你明确目标并在实现后快速验证。理解优于记忆不要死记硬背代码。理解每个操作为什么是那个复杂度理解数组和链表在内存模型上的根本区别。主动探索变体实现了单向链表后尝试实现双向链表或循环链表。实现了动态数组后思考如何实现稀疏数组。善用调试器使用IDE的调试功能设置断点、单步执行、查看变量直观地观察程序执行时数据结构和变量的变化。连接到实际问题每学一个数据结构就去LeetCode或课本上找一个相关的简单题目如用栈实现括号匹配、用队列实现BFS练习。重视代码风格和文档为你的类和方法编写清晰的注释。良好的命名和结构能让你在几周后回顾代码时依然能看懂。10. 总结与下一步COMP9123第一周的内容为整个课程搭建了坚实的脚手架。抽象数据类型ADT教会我们如何定义规范大O表示法给了我们分析算法效率的标尺而数组和链表的对比则深刻地揭示了程序设计中“权衡”Trade-off的思想——没有完美的数据结构只有适合特定场景的选择。最值得你立刻动手尝试的就是完整实现一遍动态数组和单向链表并完成我们上面提到的性能对比测试。这个过程中最容易踩的坑是指针操作链表和索引边界数组务必对照第8节的排查表仔细检查。掌握了这些基础下一步的学习路径就非常清晰了Week2 及以后你会基于栈和队列它们可以用数组或链表轻松实现学习更复杂的结构如树二叉树、二叉搜索树、图以及经典的排序和查找算法。深化理解探索为什么哈希表能在平均情况下实现 O(1) 的查找这背后又是数组和链表的结合。实战应用开始刷题。从LeetCode的“简单”难度开始重点练习数组和链表标签下的题目。将理论应用于解决具体问题是巩固知识的最佳方式。建议将本文作为一份实践指南收藏备用。当你实现数据结构遇到困难或者对复杂度分析感到疑惑时可以随时回来查阅具体的代码示例和排查步骤。记住理解数据结构和算法的唯一捷径就是不断地思考、画图和编码。