最近在准备悉尼大学COMP2123课程的第一周内容发现很多同学对数据结构与算法的入门概念感到抽象特别是如何将理论应用到实际代码中。本文将结合Week1公开课的核心知识点系统梳理从环境搭建到基础数据结构实现的完整流程并附上可运行的代码示例和常见误区分析。无论你是刚开始学习这门课还是希望巩固算法基础都能从中获得清晰的实践路径。1. 数据结构与算法入门为什么它们如此重要在开始敲代码之前我们首先要理解学习数据结构和算法的根本目的。简单来说数据结构是数据的组织、管理和存储格式其目的是为了高效地访问和修改数据。算法则是解决特定问题的一系列清晰指令。两者相辅相成高效的数据结构是设计高效算法的基础。1.1 从生活场景理解核心概念想象一下你去图书馆找一本书。如果书籍杂乱无章地堆在地上糟糕的数据结构你可能需要花费数小时低效的算法一本本翻找。如果书籍按照杜威十进制分类法整齐排列在书架上良好的数据结构你就可以根据索书号快速定位到大致区域高效的搜索算法从而在几分钟内找到目标。在计算机科学中常见的“找书”问题包括搜索在一组数据中查找特定项。排序将一组数据按特定顺序排列。插入/删除在数据集合中添加或移除一项。选择不同的数据结构如数组、链表、树和算法如线性搜索、二分搜索、快速排序解决这些问题的效率会有天壤之别。这就是我们学习这门课的意义为特定问题选择最合适的“工具”从而编写出运行更快、占用资源更少的程序。1.2 算法复杂度分析衡量效率的标尺我们如何量化一个算法的“好坏”这就需要引入算法复杂度分析主要关注时间复杂度和空间复杂度。时间复杂度指算法执行所需的时间随输入数据规模通常用n表示的增长趋势。我们使用大O符号Big O notation来描述。空间复杂度指算法执行过程中所需的最大内存空间同样用大O符号描述。以下是几种常见的时间复杂度从上到下效率依次降低O(1)常数时间。操作时间与输入规模无关。例如访问数组中的一个元素。O(log n)对数时间。效率非常高典型例子是二分查找。O(n)线性时间。操作时间与输入规模成正比。例如遍历一个数组。O(n log n)线性对数时间。许多高效排序算法如归并排序、快速排序的平均复杂度。O(n²)平方时间。通常出现在嵌套循环中如简单的冒泡排序。O(2^n)指数时间。效率极低通常意味着算法设计有严重问题如求解所有子集。在Week1中理解大O表示法并能够初步分析简单程序的时间复杂度是首要目标。2. 环境准备与工具选择工欲善其事必先利其器。一个合适的开发环境能让你更专注于逻辑本身而非环境配置问题。2.1 编程语言选择COMP2123课程通常不强制限定编程语言但教学示例和作业可能以Java、Python或C为主。选择的原则是课程推荐优先使用课程提供的示例代码语言。个人熟练度选择你最能清晰表达算法的语言。算法表现力Python语法简洁适合快速实现原型Java/C在强调内存管理和性能细节时更佳。本文后续示例将主要使用Python因其语法接近伪代码易于理解。对于关键概念也会提供Java版本的对比。2.2 开发环境搭建对于Python安装Python访问 python.org 下载最新稳定版如3.11。安装时务必勾选“Add Python to PATH”。验证安装打开终端Windows CMD/PowerShell, macOS/Linux Terminal输入python --version查看版本。选择编辑器初学者推荐VS Code。轻量、插件丰富安装Python扩展。集成环境PyCharm Community Edition功能强大免费。对于Java安装JDK下载并安装OpenJDK 17或Oracle JDK 17。配置环境变量设置JAVA_HOME并将bin目录加入PATH。验证安装终端输入java -version和javac -version。选择编辑器IntelliJ IDEA Community Edition 或 Eclipse。2.3 第一个程序从“Hello, World!”到复杂度分析让我们从一个简单的例子开始并分析其复杂度。Python 示例计算列表和# 文件sum_list.py def sum_list(numbers): 计算整数列表的总和。 时间复杂度O(n)需要遍历列表中的n个元素。 空间复杂度O(1)只使用了固定数量的变量total, num。 total 0 for num in numbers: total num return total # 测试代码 if __name__ __main__: my_list [1, 2, 3, 4, 5] result sum_list(my_list) print(fThe sum of {my_list} is: {result}) # 输出 The sum of [1, 2, 3, 4, 5] is: 15Java 示例计算数组和// 文件SumArray.java public class SumArray { /** * 计算整数数组的总和。 * 时间复杂度O(n) * 空间复杂度O(1) */ public static int sumArray(int[] numbers) { int total 0; for (int num : numbers) { total num; } return total; } public static void main(String[] args) { int[] myArray {1, 2, 3, 4, 5}; int result sumArray(myArray); System.out.println(The sum of the array is: result); // 输出 The sum of the array is: 15 } }复杂度分析两个函数都包含一个遍历所有元素的循环。如果列表/数组有n个元素循环就会执行n次。因此时间复杂度是O(n)。我们只使用了固定数量的额外变量total所以空间复杂度是O(1)。3. 核心数据结构一数组与动态数组Week1通常会从最基础、最常用的数据结构——数组开始讲起。3.1 静态数组固定大小的连续存储数组是一种线性数据结构在内存中占用一块连续的空间用于存储相同类型的元素。每个元素可以通过索引下标直接访问。特点优点随机访问速度快通过索引访问任意元素的时间复杂度为 O(1)。内存空间紧凑连续存储缓存友好。缺点大小固定创建时需指定容量无法动态扩容。插入/删除成本高在中间插入或删除元素需要移动后续所有元素平均时间复杂度为 O(n)。Python 列表 vs 数组Python内置的list实际上是一个动态数组而非传统意义上的静态数组。它封装了扩容等复杂操作。Java 数组示例// 声明并初始化一个静态数组 int[] staticArray new int[5]; // 容量为5初始值全为0 staticArray[0] 10; // O(1) 访问 // staticArray[5] 20; // 错误ArrayIndexOutOfBoundsException索引越界 // 遍历数组 for (int i 0; i staticArray.length; i) { System.out.println(staticArray[i]); }3.2 动态数组可扩容的数组为了解决静态数组大小固定的问题动态数组如Python的listJava的ArrayListC的std::vector在内部实现上仍然使用一块连续内存但当容量不足时会执行以下操作分配一块更大的新内存通常是原容量的1.5或2倍。将旧数组的所有元素复制到新数组。释放旧数组的内存。将新元素插入。这个扩容操作的时间复杂度是O(n)但分摊到多次插入操作后其均摊时间复杂度仍可视为O(1)。Python 动态数组列表操作# 创建一个空列表动态数组 dynamic_list [] # 初始容量可能很小 # 追加元素 - 平均O(1) dynamic_list.append(1) dynamic_list.append(2) dynamic_list.append(3) print(dynamic_list) # 输出: [1, 2, 3] # 在指定索引插入元素 - O(n) dynamic_list.insert(1, 99) # 在索引1处插入99 print(dynamic_list) # 输出: [1, 99, 2, 3] # 删除指定索引元素 - O(n) popped_value dynamic_list.pop(2) # 删除并返回索引2的元素 (2) print(fRemoved {popped_value}, list now: {dynamic_list}) # 输出: Removed 2, list now: [1, 99, 3] # 随机访问 - O(1) print(dynamic_list[0]) # 输出: 1Java ArrayList 示例import java.util.ArrayList; public class DynamicArrayDemo { public static void main(String[] args) { // 创建一个ArrayList动态数组 ArrayListInteger arrayList new ArrayList(); // 添加元素 arrayList.add(10); // O(1) 均摊 arrayList.add(20); arrayList.add(30); System.out.println(arrayList); // 输出: [10, 20, 30] // 在索引1处插入元素 - O(n) arrayList.add(1, 99); System.out.println(arrayList); // 输出: [10, 99, 20, 30] // 删除索引2处的元素 - O(n) arrayList.remove(2); System.out.println(arrayList); // 输出: [10, 99, 30] // 随机访问 - O(1) System.out.println(arrayList.get(0)); // 输出: 10 } }4. 核心数据结构二链表链表是另一种基础的线性数据结构它通过“节点”和“指针”来组织数据在内存中不必连续存储。4.1 链表的核心概念节点链表的基本单位包含两部分data存储数据。next一个引用或指针指向下一个节点。头节点指向链表第一个节点的引用。通过它可以访问整个链表。尾节点最后一个节点其next指向NonePython或nullJava。4.2 单向链表的实现让我们用Python和Java分别实现一个简单的单向链表。Python 实现# 文件singly_linked_list.py class ListNode: 链表节点类 def __init__(self, data0, next_nodeNone): self.data data self.next next_node class SinglyLinkedList: 单向链表类 def __init__(self): self.head None # 链表头节点 def append(self, data): 在链表末尾添加节点 - O(n) new_node ListNode(data) if not self.head: # 如果链表为空 self.head new_node return # 遍历到链表末尾 current self.head while current.next: current current.next current.next new_node def prepend(self, data): 在链表头部添加节点 - O(1) new_node ListNode(data) new_node.next self.head self.head new_node def delete(self, key): 删除第一个值为key的节点 - O(n) current self.head # 如果要删除的是头节点 if current and current.data key: self.head current.next current None return # 查找要删除的节点及其前驱节点 prev None while current and current.data ! key: prev current current current.next # 如果没找到 if current is None: return # 执行删除 prev.next current.next current None def search(self, key): 查找值为key的节点 - O(n) current self.head while current: if current.data key: return True current current.next return False def display(self): 打印链表 elements [] current self.head while current: elements.append(str(current.data)) current current.next print( - .join(elements) if elements else Empty List) # 测试代码 if __name__ __main__: llist SinglyLinkedList() llist.append(1) llist.append(2) llist.append(3) llist.prepend(0) llist.display() # 输出: 0 - 1 - 2 - 3 print(fSearch 2: {llist.search(2)}) # 输出: True print(fSearch 5: {llist.search(5)}) # 输出: False llist.delete(2) llist.display() # 输出: 0 - 1 - 3Java 实现// 文件SinglyLinkedList.java class ListNode { int data; ListNode next; ListNode(int data) { this.data data; this.next null; } } public class SinglyLinkedList { private ListNode head; public void append(int data) { ListNode newNode new ListNode(data); if (head null) { head newNode; return; } ListNode current head; while (current.next ! null) { current current.next; } current.next newNode; } public void prepend(int data) { ListNode newNode new ListNode(data); newNode.next head; head newNode; } public void delete(int key) { if (head null) return; if (head.data key) { head head.next; return; } ListNode current head; ListNode prev null; while (current ! null current.data ! key) { prev current; current current.next; } if (current null) return; prev.next current.next; } public boolean search(int key) { ListNode current head; while (current ! null) { if (current.data key) return true; current current.next; } return false; } public void display() { ListNode current head; while (current ! null) { System.out.print(current.data - ); current current.next; } System.out.println(null); } public static void main(String[] args) { SinglyLinkedList list new SinglyLinkedList(); list.append(1); list.append(2); list.append(3); list.prepend(0); list.display(); // 输出: 0 - 1 - 2 - 3 - null System.out.println(Search 2: list.search(2)); // true System.out.println(Search 5: list.search(5)); // false list.delete(2); list.display(); // 输出: 0 - 1 - 3 - null } }4.3 链表 vs 数组如何选择特性数组 (静态/动态)链表 (单向)内存分配连续内存非连续内存 (节点分散)大小调整静态数组固定动态数组可扩容但成本高动态按需创建节点随机访问O(1)通过索引直接访问O(n)必须从头遍历头部插入/删除O(n) (需移动元素) / O(1) (动态数组尾部)O(1)中间插入/删除O(n)O(n) (需先找到位置)空间开销较小仅存储数据较大每个节点需额外存储指针缓存友好性好 (局部性原理)差选择指南需要频繁随机访问元素 →优先选择数组。需要频繁在头部或中间插入/删除元素且数据规模未知或变化大 →优先选择链表。内存空间紧张且访问模式以顺序为主 →考虑数组。实现栈、队列等抽象数据类型的基础 →两者皆可视具体操作而定。5. 基础算法实践搜索与排序入门Week1通常会引入最简单的搜索和排序算法让我们建立对算法效率的直观感受。5.1 线性搜索这是最直观的搜索算法从数据结构的一端开始按顺序检查每个元素直到找到目标或遍历完所有元素。# 文件linear_search.py def linear_search(arr, target): 线性搜索算法。 时间复杂度O(n)最坏情况需要检查所有n个元素。 空间复杂度O(1)。 for i, element in enumerate(arr): if element target: return i # 找到返回索引 return -1 # 未找到 # 测试 my_array [64, 34, 25, 12, 22, 11, 90] target 22 result linear_search(my_array, target) print(fTarget {target} found at index: {result} if result ! -1 else fTarget {target} not found.) # 输出: Target 22 found at index: 45.2 二分搜索针对已排序数组二分搜索是一种效率极高的算法但前提是数组必须是有序的。它采用分治策略每次比较都将搜索范围缩小一半。算法步骤设定搜索范围的左右边界left0,rightn-1。当left right时 a. 计算中间索引mid (left right) // 2。 b. 如果arr[mid] target返回mid。 c. 如果arr[mid] target说明目标在右侧调整left mid 1。 d. 如果arr[mid] target说明目标在左侧调整right mid - 1。循环结束未找到返回 -1。# 文件binary_search.py def binary_search(arr, target): 二分搜索算法 (迭代版本)。 时间复杂度O(log n) 空间复杂度O(1) left, right 0, len(arr) - 1 while left right: mid (left right) // 2 if arr[mid] target: return mid elif arr[mid] target: left mid 1 # 目标在右半部分 else: right mid - 1 # 目标在左半部分 return -1 # 测试 (数组必须已排序) sorted_array [11, 12, 22, 25, 34, 64, 90] target 22 result binary_search(sorted_array, target) print(fTarget {target} found at index: {result} if result ! -1 else fTarget {target} not found.) # 输出: Target 22 found at index: 2 target 100 result binary_search(sorted_array, target) print(fTarget {target} found at index: {result} if result ! -1 else fTarget {target} not found.) # 输出: Target 100 not found.5.3 冒泡排序这是最简单的排序算法之一通过反复交换相邻的无序元素来工作。# 文件bubble_sort.py def bubble_sort(arr): 冒泡排序算法。 时间复杂度O(n²) (最坏和平均情况) 空间复杂度O(1) (原地排序) n len(arr) # 遍历所有数组元素 for i in range(n): # 最后 i 个元素已经排好序 swapped False # 优化如果一轮没有交换说明已有序 for j in range(0, n - i - 1): # 如果当前元素大于下一个元素则交换 if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True # 如果内层循环没有交换任何元素则数组已排序完成 if not swapped: break return arr # 测试 unsorted_array [64, 34, 25, 12, 22, 11, 90] sorted_array bubble_sort(unsorted_array.copy()) # 使用副本不改变原数组 print(fOriginal array: {unsorted_array}) print(fSorted array: {sorted_array}) # 输出: # Original array: [64, 34, 25, 12, 22, 11, 90] # Sorted array: [11, 12, 22, 25, 34, 64, 90]6. 常见问题与调试技巧学习初期理解和调试代码中的错误是至关重要的技能。6.1 数组/链表操作中的常见错误索引越界现象IndexError: list index out of range(Python),ArrayIndexOutOfBoundsException(Java)。原因访问了不存在的索引如arr[len(arr)]。解决始终确保索引在0到len(arr)-1的范围内。在循环中使用for i in range(len(arr)):或for element in arr:。空指针/引用异常现象AttributeError: NoneType object has no attribute next(Python),NullPointerException(Java)。原因在链表操作中试图访问None或null节点的属性如current.next而current本身是None/null。解决在访问节点属性前始终检查节点是否为None/null。# 正确的链表遍历 current self.head while current is not None: # 或 while current: print(current.data) current current.next无限循环现象程序卡住不停止。原因链表操作中next指针未正确更新导致形成环或循环终止条件永远无法满足。解决在纸上画出链表操作步骤仔细检查指针的更新逻辑。使用调试器或打印语句跟踪变量状态。6.2 算法逻辑错误二分搜索中的整数溢出问题在计算中间索引时mid (left right) // 2在left和right都非常大时可能导致整数溢出在C/Java中。解决使用更安全的写法mid left (right - left) // 2。排序算法不稳定性问题冒泡排序是稳定的相等元素的相对顺序不变但如果你错误地使用了进行比较可能会破坏稳定性。注意初学阶段理解稳定性的概念比实现它更重要。6.3 调试建议使用打印语句在关键步骤打印变量值如索引、节点数据、循环计数器。使用IDE调试器学习设置断点、单步执行、查看变量值。这是最强大的调试工具。小规模测试先用只有2-3个元素的数组/链表测试你的代码确保边界条件空、只有一个元素正确处理。编写测试用例系统性地测试你的函数包括正常情况、边界情况和异常情况。7. 最佳实践与学习路线建议掌握基础知识后如何高效地继续学习并应用于实践7.1 代码实现最佳实践清晰的命名变量名使用snake_case(Python) 或camelCase(Java)函数名使用动词开头类名使用PascalCase。避免使用a,b,x等无意义名称。添加注释和文档字符串为函数和复杂逻辑块添加注释说明其目的、参数、返回值和复杂度。def binary_search(arr, target): 在已排序数组arr中执行二分查找寻找目标值target。 参数: arr (list): 一个已排序的列表。 target (int): 要查找的目标值。 返回: int: 如果找到返回目标值的索引否则返回-1。 时间复杂度: O(log n) 空间复杂度: O(1) # ... 实现代码考虑边界条件始终思考如果输入是空列表、空链表、只有一个元素、目标值不存在等情况你的代码会怎样测试驱动在实现一个函数前先想好几组测试用例正常、边界、异常并在实现后运行它们。7.2 复杂度分析练习每学一个新的数据结构或算法尝试自己分析其时间和空间复杂度。问自己代码中有几个循环它们嵌套吗每个循环执行了多少次与输入规模n的关系分配了哪些额外的数据结构7.3 下一步学习路线完成Week1的基础后可以按以下路径深入数据结构深化学习双向链表、循环链表、栈用数组/链表实现、队列普通队列、双端队列、优先队列。排序算法掌握选择排序、插入排序然后学习更高效的归并排序和快速排序并理解其分治思想。递归这是理解树、图以及许多高级算法如归并排序、快速排序的关键。从计算阶乘、斐波那契数列开始练习。抽象数据类型理解栈、队列、集合、映射字典的抽象接口与不同实现如用链表实现栈。实践平台在LeetCode、HackerRank等平台上从“Easy”难度的题目开始练习巩固数组和链表的基本操作。学习数据结构和算法就像学习乐理和指法初期可能会觉得枯燥但这是你未来构建高效、优雅程序大厦的基石。从理解每一个基础数据结构的特性和代价开始多动手实现多画图分析逐步培养出为问题选择最佳工具的本能。 数据结构与算法入门：从复杂度分析到数组链表实践
最近在准备悉尼大学COMP2123课程的第一周内容发现很多同学对数据结构与算法的入门概念感到抽象特别是如何将理论应用到实际代码中。本文将结合Week1公开课的核心知识点系统梳理从环境搭建到基础数据结构实现的完整流程并附上可运行的代码示例和常见误区分析。无论你是刚开始学习这门课还是希望巩固算法基础都能从中获得清晰的实践路径。1. 数据结构与算法入门为什么它们如此重要在开始敲代码之前我们首先要理解学习数据结构和算法的根本目的。简单来说数据结构是数据的组织、管理和存储格式其目的是为了高效地访问和修改数据。算法则是解决特定问题的一系列清晰指令。两者相辅相成高效的数据结构是设计高效算法的基础。1.1 从生活场景理解核心概念想象一下你去图书馆找一本书。如果书籍杂乱无章地堆在地上糟糕的数据结构你可能需要花费数小时低效的算法一本本翻找。如果书籍按照杜威十进制分类法整齐排列在书架上良好的数据结构你就可以根据索书号快速定位到大致区域高效的搜索算法从而在几分钟内找到目标。在计算机科学中常见的“找书”问题包括搜索在一组数据中查找特定项。排序将一组数据按特定顺序排列。插入/删除在数据集合中添加或移除一项。选择不同的数据结构如数组、链表、树和算法如线性搜索、二分搜索、快速排序解决这些问题的效率会有天壤之别。这就是我们学习这门课的意义为特定问题选择最合适的“工具”从而编写出运行更快、占用资源更少的程序。1.2 算法复杂度分析衡量效率的标尺我们如何量化一个算法的“好坏”这就需要引入算法复杂度分析主要关注时间复杂度和空间复杂度。时间复杂度指算法执行所需的时间随输入数据规模通常用n表示的增长趋势。我们使用大O符号Big O notation来描述。空间复杂度指算法执行过程中所需的最大内存空间同样用大O符号描述。以下是几种常见的时间复杂度从上到下效率依次降低O(1)常数时间。操作时间与输入规模无关。例如访问数组中的一个元素。O(log n)对数时间。效率非常高典型例子是二分查找。O(n)线性时间。操作时间与输入规模成正比。例如遍历一个数组。O(n log n)线性对数时间。许多高效排序算法如归并排序、快速排序的平均复杂度。O(n²)平方时间。通常出现在嵌套循环中如简单的冒泡排序。O(2^n)指数时间。效率极低通常意味着算法设计有严重问题如求解所有子集。在Week1中理解大O表示法并能够初步分析简单程序的时间复杂度是首要目标。2. 环境准备与工具选择工欲善其事必先利其器。一个合适的开发环境能让你更专注于逻辑本身而非环境配置问题。2.1 编程语言选择COMP2123课程通常不强制限定编程语言但教学示例和作业可能以Java、Python或C为主。选择的原则是课程推荐优先使用课程提供的示例代码语言。个人熟练度选择你最能清晰表达算法的语言。算法表现力Python语法简洁适合快速实现原型Java/C在强调内存管理和性能细节时更佳。本文后续示例将主要使用Python因其语法接近伪代码易于理解。对于关键概念也会提供Java版本的对比。2.2 开发环境搭建对于Python安装Python访问 python.org 下载最新稳定版如3.11。安装时务必勾选“Add Python to PATH”。验证安装打开终端Windows CMD/PowerShell, macOS/Linux Terminal输入python --version查看版本。选择编辑器初学者推荐VS Code。轻量、插件丰富安装Python扩展。集成环境PyCharm Community Edition功能强大免费。对于Java安装JDK下载并安装OpenJDK 17或Oracle JDK 17。配置环境变量设置JAVA_HOME并将bin目录加入PATH。验证安装终端输入java -version和javac -version。选择编辑器IntelliJ IDEA Community Edition 或 Eclipse。2.3 第一个程序从“Hello, World!”到复杂度分析让我们从一个简单的例子开始并分析其复杂度。Python 示例计算列表和# 文件sum_list.py def sum_list(numbers): 计算整数列表的总和。 时间复杂度O(n)需要遍历列表中的n个元素。 空间复杂度O(1)只使用了固定数量的变量total, num。 total 0 for num in numbers: total num return total # 测试代码 if __name__ __main__: my_list [1, 2, 3, 4, 5] result sum_list(my_list) print(fThe sum of {my_list} is: {result}) # 输出 The sum of [1, 2, 3, 4, 5] is: 15Java 示例计算数组和// 文件SumArray.java public class SumArray { /** * 计算整数数组的总和。 * 时间复杂度O(n) * 空间复杂度O(1) */ public static int sumArray(int[] numbers) { int total 0; for (int num : numbers) { total num; } return total; } public static void main(String[] args) { int[] myArray {1, 2, 3, 4, 5}; int result sumArray(myArray); System.out.println(The sum of the array is: result); // 输出 The sum of the array is: 15 } }复杂度分析两个函数都包含一个遍历所有元素的循环。如果列表/数组有n个元素循环就会执行n次。因此时间复杂度是O(n)。我们只使用了固定数量的额外变量total所以空间复杂度是O(1)。3. 核心数据结构一数组与动态数组Week1通常会从最基础、最常用的数据结构——数组开始讲起。3.1 静态数组固定大小的连续存储数组是一种线性数据结构在内存中占用一块连续的空间用于存储相同类型的元素。每个元素可以通过索引下标直接访问。特点优点随机访问速度快通过索引访问任意元素的时间复杂度为 O(1)。内存空间紧凑连续存储缓存友好。缺点大小固定创建时需指定容量无法动态扩容。插入/删除成本高在中间插入或删除元素需要移动后续所有元素平均时间复杂度为 O(n)。Python 列表 vs 数组Python内置的list实际上是一个动态数组而非传统意义上的静态数组。它封装了扩容等复杂操作。Java 数组示例// 声明并初始化一个静态数组 int[] staticArray new int[5]; // 容量为5初始值全为0 staticArray[0] 10; // O(1) 访问 // staticArray[5] 20; // 错误ArrayIndexOutOfBoundsException索引越界 // 遍历数组 for (int i 0; i staticArray.length; i) { System.out.println(staticArray[i]); }3.2 动态数组可扩容的数组为了解决静态数组大小固定的问题动态数组如Python的listJava的ArrayListC的std::vector在内部实现上仍然使用一块连续内存但当容量不足时会执行以下操作分配一块更大的新内存通常是原容量的1.5或2倍。将旧数组的所有元素复制到新数组。释放旧数组的内存。将新元素插入。这个扩容操作的时间复杂度是O(n)但分摊到多次插入操作后其均摊时间复杂度仍可视为O(1)。Python 动态数组列表操作# 创建一个空列表动态数组 dynamic_list [] # 初始容量可能很小 # 追加元素 - 平均O(1) dynamic_list.append(1) dynamic_list.append(2) dynamic_list.append(3) print(dynamic_list) # 输出: [1, 2, 3] # 在指定索引插入元素 - O(n) dynamic_list.insert(1, 99) # 在索引1处插入99 print(dynamic_list) # 输出: [1, 99, 2, 3] # 删除指定索引元素 - O(n) popped_value dynamic_list.pop(2) # 删除并返回索引2的元素 (2) print(fRemoved {popped_value}, list now: {dynamic_list}) # 输出: Removed 2, list now: [1, 99, 3] # 随机访问 - O(1) print(dynamic_list[0]) # 输出: 1Java ArrayList 示例import java.util.ArrayList; public class DynamicArrayDemo { public static void main(String[] args) { // 创建一个ArrayList动态数组 ArrayListInteger arrayList new ArrayList(); // 添加元素 arrayList.add(10); // O(1) 均摊 arrayList.add(20); arrayList.add(30); System.out.println(arrayList); // 输出: [10, 20, 30] // 在索引1处插入元素 - O(n) arrayList.add(1, 99); System.out.println(arrayList); // 输出: [10, 99, 20, 30] // 删除索引2处的元素 - O(n) arrayList.remove(2); System.out.println(arrayList); // 输出: [10, 99, 30] // 随机访问 - O(1) System.out.println(arrayList.get(0)); // 输出: 10 } }4. 核心数据结构二链表链表是另一种基础的线性数据结构它通过“节点”和“指针”来组织数据在内存中不必连续存储。4.1 链表的核心概念节点链表的基本单位包含两部分data存储数据。next一个引用或指针指向下一个节点。头节点指向链表第一个节点的引用。通过它可以访问整个链表。尾节点最后一个节点其next指向NonePython或nullJava。4.2 单向链表的实现让我们用Python和Java分别实现一个简单的单向链表。Python 实现# 文件singly_linked_list.py class ListNode: 链表节点类 def __init__(self, data0, next_nodeNone): self.data data self.next next_node class SinglyLinkedList: 单向链表类 def __init__(self): self.head None # 链表头节点 def append(self, data): 在链表末尾添加节点 - O(n) new_node ListNode(data) if not self.head: # 如果链表为空 self.head new_node return # 遍历到链表末尾 current self.head while current.next: current current.next current.next new_node def prepend(self, data): 在链表头部添加节点 - O(1) new_node ListNode(data) new_node.next self.head self.head new_node def delete(self, key): 删除第一个值为key的节点 - O(n) current self.head # 如果要删除的是头节点 if current and current.data key: self.head current.next current None return # 查找要删除的节点及其前驱节点 prev None while current and current.data ! key: prev current current current.next # 如果没找到 if current is None: return # 执行删除 prev.next current.next current None def search(self, key): 查找值为key的节点 - O(n) current self.head while current: if current.data key: return True current current.next return False def display(self): 打印链表 elements [] current self.head while current: elements.append(str(current.data)) current current.next print( - .join(elements) if elements else Empty List) # 测试代码 if __name__ __main__: llist SinglyLinkedList() llist.append(1) llist.append(2) llist.append(3) llist.prepend(0) llist.display() # 输出: 0 - 1 - 2 - 3 print(fSearch 2: {llist.search(2)}) # 输出: True print(fSearch 5: {llist.search(5)}) # 输出: False llist.delete(2) llist.display() # 输出: 0 - 1 - 3Java 实现// 文件SinglyLinkedList.java class ListNode { int data; ListNode next; ListNode(int data) { this.data data; this.next null; } } public class SinglyLinkedList { private ListNode head; public void append(int data) { ListNode newNode new ListNode(data); if (head null) { head newNode; return; } ListNode current head; while (current.next ! null) { current current.next; } current.next newNode; } public void prepend(int data) { ListNode newNode new ListNode(data); newNode.next head; head newNode; } public void delete(int key) { if (head null) return; if (head.data key) { head head.next; return; } ListNode current head; ListNode prev null; while (current ! null current.data ! key) { prev current; current current.next; } if (current null) return; prev.next current.next; } public boolean search(int key) { ListNode current head; while (current ! null) { if (current.data key) return true; current current.next; } return false; } public void display() { ListNode current head; while (current ! null) { System.out.print(current.data - ); current current.next; } System.out.println(null); } public static void main(String[] args) { SinglyLinkedList list new SinglyLinkedList(); list.append(1); list.append(2); list.append(3); list.prepend(0); list.display(); // 输出: 0 - 1 - 2 - 3 - null System.out.println(Search 2: list.search(2)); // true System.out.println(Search 5: list.search(5)); // false list.delete(2); list.display(); // 输出: 0 - 1 - 3 - null } }4.3 链表 vs 数组如何选择特性数组 (静态/动态)链表 (单向)内存分配连续内存非连续内存 (节点分散)大小调整静态数组固定动态数组可扩容但成本高动态按需创建节点随机访问O(1)通过索引直接访问O(n)必须从头遍历头部插入/删除O(n) (需移动元素) / O(1) (动态数组尾部)O(1)中间插入/删除O(n)O(n) (需先找到位置)空间开销较小仅存储数据较大每个节点需额外存储指针缓存友好性好 (局部性原理)差选择指南需要频繁随机访问元素 →优先选择数组。需要频繁在头部或中间插入/删除元素且数据规模未知或变化大 →优先选择链表。内存空间紧张且访问模式以顺序为主 →考虑数组。实现栈、队列等抽象数据类型的基础 →两者皆可视具体操作而定。5. 基础算法实践搜索与排序入门Week1通常会引入最简单的搜索和排序算法让我们建立对算法效率的直观感受。5.1 线性搜索这是最直观的搜索算法从数据结构的一端开始按顺序检查每个元素直到找到目标或遍历完所有元素。# 文件linear_search.py def linear_search(arr, target): 线性搜索算法。 时间复杂度O(n)最坏情况需要检查所有n个元素。 空间复杂度O(1)。 for i, element in enumerate(arr): if element target: return i # 找到返回索引 return -1 # 未找到 # 测试 my_array [64, 34, 25, 12, 22, 11, 90] target 22 result linear_search(my_array, target) print(fTarget {target} found at index: {result} if result ! -1 else fTarget {target} not found.) # 输出: Target 22 found at index: 45.2 二分搜索针对已排序数组二分搜索是一种效率极高的算法但前提是数组必须是有序的。它采用分治策略每次比较都将搜索范围缩小一半。算法步骤设定搜索范围的左右边界left0,rightn-1。当left right时 a. 计算中间索引mid (left right) // 2。 b. 如果arr[mid] target返回mid。 c. 如果arr[mid] target说明目标在右侧调整left mid 1。 d. 如果arr[mid] target说明目标在左侧调整right mid - 1。循环结束未找到返回 -1。# 文件binary_search.py def binary_search(arr, target): 二分搜索算法 (迭代版本)。 时间复杂度O(log n) 空间复杂度O(1) left, right 0, len(arr) - 1 while left right: mid (left right) // 2 if arr[mid] target: return mid elif arr[mid] target: left mid 1 # 目标在右半部分 else: right mid - 1 # 目标在左半部分 return -1 # 测试 (数组必须已排序) sorted_array [11, 12, 22, 25, 34, 64, 90] target 22 result binary_search(sorted_array, target) print(fTarget {target} found at index: {result} if result ! -1 else fTarget {target} not found.) # 输出: Target 22 found at index: 2 target 100 result binary_search(sorted_array, target) print(fTarget {target} found at index: {result} if result ! -1 else fTarget {target} not found.) # 输出: Target 100 not found.5.3 冒泡排序这是最简单的排序算法之一通过反复交换相邻的无序元素来工作。# 文件bubble_sort.py def bubble_sort(arr): 冒泡排序算法。 时间复杂度O(n²) (最坏和平均情况) 空间复杂度O(1) (原地排序) n len(arr) # 遍历所有数组元素 for i in range(n): # 最后 i 个元素已经排好序 swapped False # 优化如果一轮没有交换说明已有序 for j in range(0, n - i - 1): # 如果当前元素大于下一个元素则交换 if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True # 如果内层循环没有交换任何元素则数组已排序完成 if not swapped: break return arr # 测试 unsorted_array [64, 34, 25, 12, 22, 11, 90] sorted_array bubble_sort(unsorted_array.copy()) # 使用副本不改变原数组 print(fOriginal array: {unsorted_array}) print(fSorted array: {sorted_array}) # 输出: # Original array: [64, 34, 25, 12, 22, 11, 90] # Sorted array: [11, 12, 22, 25, 34, 64, 90]6. 常见问题与调试技巧学习初期理解和调试代码中的错误是至关重要的技能。6.1 数组/链表操作中的常见错误索引越界现象IndexError: list index out of range(Python),ArrayIndexOutOfBoundsException(Java)。原因访问了不存在的索引如arr[len(arr)]。解决始终确保索引在0到len(arr)-1的范围内。在循环中使用for i in range(len(arr)):或for element in arr:。空指针/引用异常现象AttributeError: NoneType object has no attribute next(Python),NullPointerException(Java)。原因在链表操作中试图访问None或null节点的属性如current.next而current本身是None/null。解决在访问节点属性前始终检查节点是否为None/null。# 正确的链表遍历 current self.head while current is not None: # 或 while current: print(current.data) current current.next无限循环现象程序卡住不停止。原因链表操作中next指针未正确更新导致形成环或循环终止条件永远无法满足。解决在纸上画出链表操作步骤仔细检查指针的更新逻辑。使用调试器或打印语句跟踪变量状态。6.2 算法逻辑错误二分搜索中的整数溢出问题在计算中间索引时mid (left right) // 2在left和right都非常大时可能导致整数溢出在C/Java中。解决使用更安全的写法mid left (right - left) // 2。排序算法不稳定性问题冒泡排序是稳定的相等元素的相对顺序不变但如果你错误地使用了进行比较可能会破坏稳定性。注意初学阶段理解稳定性的概念比实现它更重要。6.3 调试建议使用打印语句在关键步骤打印变量值如索引、节点数据、循环计数器。使用IDE调试器学习设置断点、单步执行、查看变量值。这是最强大的调试工具。小规模测试先用只有2-3个元素的数组/链表测试你的代码确保边界条件空、只有一个元素正确处理。编写测试用例系统性地测试你的函数包括正常情况、边界情况和异常情况。7. 最佳实践与学习路线建议掌握基础知识后如何高效地继续学习并应用于实践7.1 代码实现最佳实践清晰的命名变量名使用snake_case(Python) 或camelCase(Java)函数名使用动词开头类名使用PascalCase。避免使用a,b,x等无意义名称。添加注释和文档字符串为函数和复杂逻辑块添加注释说明其目的、参数、返回值和复杂度。def binary_search(arr, target): 在已排序数组arr中执行二分查找寻找目标值target。 参数: arr (list): 一个已排序的列表。 target (int): 要查找的目标值。 返回: int: 如果找到返回目标值的索引否则返回-1。 时间复杂度: O(log n) 空间复杂度: O(1) # ... 实现代码考虑边界条件始终思考如果输入是空列表、空链表、只有一个元素、目标值不存在等情况你的代码会怎样测试驱动在实现一个函数前先想好几组测试用例正常、边界、异常并在实现后运行它们。7.2 复杂度分析练习每学一个新的数据结构或算法尝试自己分析其时间和空间复杂度。问自己代码中有几个循环它们嵌套吗每个循环执行了多少次与输入规模n的关系分配了哪些额外的数据结构7.3 下一步学习路线完成Week1的基础后可以按以下路径深入数据结构深化学习双向链表、循环链表、栈用数组/链表实现、队列普通队列、双端队列、优先队列。排序算法掌握选择排序、插入排序然后学习更高效的归并排序和快速排序并理解其分治思想。递归这是理解树、图以及许多高级算法如归并排序、快速排序的关键。从计算阶乘、斐波那契数列开始练习。抽象数据类型理解栈、队列、集合、映射字典的抽象接口与不同实现如用链表实现栈。实践平台在LeetCode、HackerRank等平台上从“Easy”难度的题目开始练习巩固数组和链表的基本操作。学习数据结构和算法就像学习乐理和指法初期可能会觉得枯燥但这是你未来构建高效、优雅程序大厦的基石。从理解每一个基础数据结构的特性和代价开始多动手实现多画图分析逐步培养出为问题选择最佳工具的本能。