企业官网建设流程全解析

简介：一份基于《Python中的数据结构和算法》原书整理的Python源码实现包，适合正在学习数据结构、准备算法面试或希望提升Python面向对象编程能力的开发者。资源以书中各章节为主线，提供123个可运行的.py脚本，涵盖二叉搜索树、红黑树、表达式树、图、链表位置列表、排序映射、欧拉遍历等经典主题，每个文件均保持一致的面向对象设计，便于对照原书理解抽象数据类型与算法设计思想。压缩包仅89KB，总文件数124个，除Python源码外仅含一个gitignore文件，结构轻量清晰。目前已有733人下载学习，适合随书逐章阅读或作为期末复习、上机练习的代码参考。通过阅读这些实现，读者既能掌握各类数据结构接口的分层设计与继承复用技巧，也能学习如何在Python中用简洁代码表达复杂算法逻辑，是一份实用且紧凑的电子资源。

1. 用Python学数据结构和算法：先别急着背答案，把每个容器亲手实现一遍

用Python学数据结构和算法，最容易被低估的不是语法，而是「把数据结构当成类型系统来设计」这件事。很多人直接刷题、背解法，代码能过用例，却说不清底层是数组还是链表，更不敢碰继承、接口这些设计层面的东西。这个方向的核心主张恰恰相反：利用Python的美感和简单性，把每一类抽象数据类型（ADT）用可执行的源代码呈现出来，再用继承最大化代码复用，让读者看清不同容器之间的相似与不同。它适合三类人：想补计算机基础但啃不动大部头的开发者、准备技术面试但只会贴答案的求职者，以及想把自己的代码从脚本升到库的工程师。它解决的是：让你动手实现每一类容器和算法，并对自己的实现有底气。下文从为什么选Python、怎么写一个类开始，一路到避坑和验证，目标是让你看完能自己搭一套可运行、可测试、可对照标准库的小型容器库。

2. 选择Python学数据结构和算法：为什么一致的面向对象视角反而是捷径

2.1 抽象数据类型与Python类：先定接口，再谈实现

抽象数据类型，也就是ADT，核心思路很朴素：先描述「这个类型能做什么操作」，再决定「内部怎么存」。比如栈这个ADT，规定好了push、pop、peek三个操作的语义，至于底层用数组还是链表，调用方根本不关心。这个思路放到Python里，几乎是为类设计量身定做的：类名就是类型名，方法就是操作集合，__init__里隐藏内部表示。

Python的抽象基类模块abc可以把这条约束落到代码上。定义一个Container基类，把「所有容器都应该有」的接口先钉死，子类不实现就实例化不了，从根上减少「漏写方法」的翻车。

from abc import ABC, abstractmethod from typing import Iterator class Container(ABC): """所有容器的抽象基类：定义统一的容器操作。""" @abstractmethod def __len__(self) -> int: """返回元素个数，所有子类必须实现。""" @abstractmethod def __iter__(self) -> Iterator[object]: """返回迭代器，所有子类必须实现。""" @abstractmethod def add(self, value: object) -> None: """向容器加入一个元素，具体语义由子类定义。"""

这里有个值得反复琢磨的细节：基类里的方法叫add，而不是append或push。为什么？因为不同容器的写入语义不一样——数组列表叫append，栈叫push，队列叫enqueue。统一叫add，让外部代码可以写出「只面向抽象基类」的逻辑，不用关心当前具体是哪种容器。这正是ADT设计里「接口与实现分离」在Python里最实在的落地方式。参数value用object类型标注，刻意放宽它，因为容器不该限制元素的具体类型。

2.2 用继承最大化代码复用：一份代码跑通N种容器

有了抽象基类之后，继承真正的价值才显现出来。很多通用行为是可以用基类一次性实现，然后让所有子类免费继承的。最常见的例子是__contains__和__str__：它们只需要依赖__iter__和__len__就能工作，没有必要在每个子类里重写一遍。

from abc import ABC, abstractmethod from typing import Iterator class Container(ABC): # 抽象方法同上一节，此处省略 def __contains__(self, value: object) -> bool: # 基类借助 __iter__ 实现成员判断，子类无需重写 for item in self: if item == value: return True return False def __str__(self) -> str: return f"{type(self).__name__}({list(self)!r})"

这段代码展示了标题里「一致的面向对象观点」的实操含义：把公共行为提升到基类，子类只写自己差异化的部分。__contains__用了线性扫描，虽然对链表和动态数组都适用，但如果你将来实现哈希集合，就应该重写它，这就叫「按需覆盖」。__str__里的type(self).__name__可以自动显示当前子类的名字，ArrayList打印出来就是ArrayList([...])，LinkedList就是LinkedList([...])，同一份代码在不同子类里输出不同的类名，这就是复用的收益。

但这里要补一句提醒：继承是复用手段，不是复用目的。后面第5章会专门讲继承层级过深的坑，现在的克制是为了给后面留余地。这个Container基类只放两三层，足够了。

2.3 搭建最小项目骨架：虚拟环境、目录与第一次测试

动手之前先把工程搭干净。我用一个叫dsa的目录当项目根，里面按职责拆成三个包：containers放数据结构，algorithms放算法，tests放测试。布局越简单，后面每次跑测试时的心智负担越小。

mkdir dsa && cd dsa python -m venv .venv source .venv/bin/activate # Windows 下执行 .venv\Scripts\activate pip install pytest

目录结构长这样：

containers/ ├── __init__.py ├── container.py ├── array_list.py └── linked_list.py algorithms/ ├── __init__.py ├── sorting.py └── recursion.py tests/ ├── __init__.py └── test_containers.py

虚拟环境这一步看着琐碎，但它是所有后续实验的隔离带。不建虚拟环境，等装到第三个第三方库时就会开始踩依赖冲突的坑。测试框架我选pytest，断言语感更接近自然语言，对新手友好。

先写一条最基础的测试，验证Container确实是抽象类：

# tests/test_containers.py from containers.container import Container def test_container_is_abstract(): try: Container() # 抽象基类不允许实例化 except TypeError: pass else: raise AssertionError("Container should be abstract")

在项目根目录运行pytest tests/ -v，看到1 passed就说明骨架通了。这一步很关键：环境、导入路径、测试链路全部验证过，后面每写一个类，都可以立刻用同样的方式验证，不用等写完再回头查为什么import失败。

3. 从数组到链表：亲手实现的容器类与它们的共同接口

3.1 实现ArrayList：扩容策略、负索引与迭代器

第一个完整实现选动态数组，因为它最贴近Python内置list，又有值得拆解的扩容逻辑。先写一个不依赖内置list扩容细节的版本，自己管理capacity，目的是把「翻倍扩容均摊O(1)」这个经典结论变成看得见的代码。

from typing import Iterator, Optional from containers.container import Container class ArrayList(Container): """基于 Python list 的动态数组，展示翻倍扩容的逻辑。""" def __init__(self, capacity: int = 8) -> None: self._data: list = [] self._capacity = capacity def add(self, value: object) -> None: if len(self._data) >= self._capacity: self._capacity *= 2 # 翻倍扩容，均摊后 add 仍是 O(1) self._data.append(value) def __len__(self) -> int: return len(self._data) def __getitem__(self, index: int) -> object: if index < 0: index += len(self._data) if not 0 <= index < len(self._data): raise IndexError("index out of range") return self._data[index] def __iter__(self) -> Iterator[object]: return iter(self._data)

代码逻辑拆开看：add先判断当前元素数是否触及容量上限，触发了就把容量翻倍，再真正追加元素。capacity参数默认8，意思是这个小容器起步就预留8个元素的逻辑容量，这个数值你可以改成4或16，影响的是扩容频率，不影响正确性。__getitem__支持负索引，还做了边界检查，这样外面访问越界时抛的是我们自己定义的IndexError，而不是底层list的原始报错。__iter__直接委托内置list的迭代器，最省事。

这里值得说一句「玄学」之外的道理：为什么扩容要翻倍而不是加固定值？翻倍意味着从空到n个元素的总分配次数是O(log n)，分摊到每次add上约等于O(1)；如果每次固定加8，总分配次数是O(n)，均摊就成了O(n)。同样的操作，扩容策略不同，整体复杂度完全不同，这就是算法分析不是玄学、但确实反直觉的地方。

3.2 单向链表实现：节点与哨兵的设计

链表的实现重点在节点设计和指针维护。节点用内部类_Node声明，外部代码不需要也不应该直接碰它。给_Node加__slots__可以显著减少每个节点的内存占用：每个Python对象默认带__dict__，对海量节点来说那是实打实的开销。

from typing import Iterator, Optional from containers.container import Container class _Node: """链表的私有节点，使用 __slots__ 减少每个节点占用的内存。""" __slots__ = ("value", "next") def __init__(self, value: object, next_node: Optional["_Node"] = None) -> None: self.value = value self.next = next_node class LinkedList(Container): """带头部引用的单向链表。""" def __init__(self) -> None: self._head: Optional[_Node] = None self._size: int = 0 def add(self, value: object) -> None: new_node = _Node(value) if self._head is None: self._head = new_node else: cur = self._head while cur.next is not None: cur = cur.next cur.next = new_node self._size += 1 def __len__(self) -> int: return self._size def __iter__(self) -> Iterator[object]: cur = self._head while cur is not None: yield cur.value cur = cur.next

链表的add是O(n)，因为每次都要从头遍历到尾找到最后一个节点。这不是实现偷懒，而是单向链表的结构天然如此。想要O(1)尾部插入，有两个常见改法：一是维护尾指针，二是改成头插但每次取尾部元素。头插会破坏队列语义，所以这个实现里选了尾指针方向的简单版本。__iter__用yield写成生成器，每yield一次才返回一个值，遍历大链表时内存占用是O(1)的。

对比ArrayList和LinkedList两个实现，能看到标题里说的「明显相似之处和不同之处」：它们实现同一个Container接口，都有add、__len__、__iter__，这是相似；但ArrayList按下标访问O(1)，链表按下标访问必须从头走，这是不同。接口相似、性能不同，正是设计抽象时最需要看清的部分。

3.3 统一的容器接口：为什么三行遍历代码能跑三种结构

接口统一带来的实际收益，写一段绕不开容器类型细节的代码就看得最清楚。假设我们要对容器做同一件事：加两个元素、遍历打印、输出长度。

from containers.array_list import ArrayList from containers.linked_list import LinkedList def show(container: Container) -> None: container.add("python") container.add("dsa") for item in container: print(item) print(len(container)) show(ArrayList()) show(LinkedList())

同一个show函数，传入ArrayList和LinkedList都能正确工作，靠的就是基类约定的add、__iter__、__len__这三个接口。函数不需要知道底层是连续内存还是分散节点。这就是面向对象视角对算法学习最大的帮助：你可以先站在调用方的角度看接口，再切换到实现方看内部，最后用同一套测试验证两个视角的一致性。

这种写法有个边界要明白：show能通用，前提是它只调用基类约定的接口。如果哪天你在show里写了container[2]这种按下标访问，LinkedList就会失效，因为基类根本没有定义__getitem__。所以统一接口的收益是「有限度的通用」，超出约定就要显式判断类型或重新抽象，这也是很多框架设计里接口文档那么重要的原因。

4. 栈、队列与递归：组合优先，还是继承优先？

4.1 栈与队列：用组合包住原生list，暴露最小操作集

到栈和队列这里，要做一个重要的设计决策：继承list，还是组合list？常见的错误是class Stack(list)，然后直接继承所有list方法，结果栈能insert、能reverse、能按下标访问，ADT语义完全被破坏。正确的姿势是组合：内部持有list，外部只暴露栈该有的操作。

from typing import Iterator from containers.container import Container class Stack(Container): """后进先出（LIFO）容器，内部组合一个 list。""" def __init__(self) -> None: self._items: list = [] def add(self, value: object) -> None: self._items.append(value) def pop(self) -> object: if not self._items: raise IndexError("pop from empty stack") return self._items.pop() def peek(self) -> object: if not self._items: raise IndexError("peek from empty stack") return self._items[-1] def __len__(self) -> int: return len(self._items) def __iter__(self) -> Iterator[object]: return reversed(self._items)

class Queue(Container): """先进先出（FIFO）容器，展示一个带有工程缺陷的教学实现。""" def __init__(self) -> None: self._items: list = [] def add(self, value: object) -> None: self._items.append(value) def pop(self) -> object: if not self._items: raise IndexError("pop from empty queue") return self._items.pop(0) # 注意：pop(0) 是 O(n)，工程上应改用 collections.deque def __len__(self) -> int: return len(self._items) def __iter__(self) -> Iterator[object]: return iter(self._items)

两个实现都组合了list，但行为完全不同：栈的__iter__用reversed，从栈顶到底部遍历；队列的__iter__按入队顺序。这个差异不是随便定的，而是由ADT语义决定的——外部看到的是「栈后进先出、队列先进先出」，内部却都只是一个list。组合优于继承在这里体现得最彻底：组合让你精确控制暴露给外部的操作集，继承则会把你不需要的方法也泄露出去。

Queue里pop(0)是O(n)这个坑，教学场景故意保留，是为了让复杂度对比有真实素材。工程上请直接换成collections.deque，它的popleft()是O(1)。学习阶段自己实现一遍，再用标准库替换，印象比直接看文档深得多。

4.2 递归算法与调用栈：用装饰器把递归深度画出来

递归是很多人的知识盲区，因为看不到调用栈。常见做法是直接打印日志，但那样会污染函数逻辑。更好的办法是用装饰器包装函数，在函数对象上记录当前递归深度和最大深度。

import functools def trace_recursion(func): func._depth = 0 func._max_depth = 0 @functools.wraps(func) def wrapper(*args, **kwargs): func._depth += 1 func._max_depth = max(func._max_depth, func._depth) try: return func(*args, **kwargs) finally: func._depth -= 1 return wrapper @trace_recursion def fib(n: int) -> int: if n < 2: return n return fib(n - 1) + fib(n - 2) print(fib(10)) print("max depth:", fib._max_depth)

这个装饰器的关键点有三个：finally保证无论函数是否抛异常，深度都会递减；functools.wraps保留原函数名和文档字符串，调试时不会看到一层wrapper壳；_max_depth记录整个递归过程的峰值，反映出「最深处占了多少层调用栈」。运行结果里max depth是10，恰好等于输入参数，因为fib(n)每次递归只下降一层。

Python的递归深度默认限制在1000左右，这不是玄学，是解释器防止C栈溢出的安全措施。自己实现数据结构和算法时，递归版本通常用来理解思路，工程版本要换成显式栈或迭代。这个装饰器对你的价值在于：把「看不见的调用栈」变成「看得见的数字」，每次写递归都能立刻观测到递归占用情况。

4.3 排序策略的封装：一个可切换策略的Sorter类

排序算法很适合做策略模式的教学案例：接口不变，算法可以运行时替换。先定义两个排序函数，再写一个Sorter类负责调度。

def insertion_sort(data: list) -> None: """插入排序，原地修改列表。""" for i in range(1, len(data)): key = data[i] j = i - 1 while j >= 0 and data[j] > key: data[j + 1] = data[j] j -= 1 data[j + 1] = key def quick_sort(data: list) -> None: """快速排序，教学版使用递归与列表推导。""" if len(data) <= 1: return pivot = data[len(data) // 2] left = [x for x in data if x < pivot] mid = [x for x in data if x == pivot] right = [x for x in data if x > pivot] data[:] = left + mid + right class Sorter: """策略模式：排序算法可以在运行时切换。""" def __init__(self, algorithm=insertion_sort) -> None: self._algorithm = algorithm def set_algorithm(self, algorithm) -> None: self._algorithm = algorithm def sort(self, data: list) -> list: result = data[:] self._algorithm(result) return result

Sorter维护一个_algorithm引用，sort方法先拷贝原数据，再调用当前算法原地排序。为什么拷贝？为了不修改调用方传入的原始列表，这是工程上的防御习惯。set_algorithm允许运行时替换策略：数据量小时用插入排序，数据量大时切到快速排序，调用方完全不用改业务代码。

快速排序的教学版本用了三个列表推导分别收集小于、等于、大于基准值的元素，清晰但空间复杂度是O(n)。这就够用来理解分治思想了。想优化空间可以去实现原地分区版，但那是另一个主题——在刚起步的阶段，先保证「思路写得清楚」比「内存用得最省」更重要。这里的策略切换能力，也为后面做排序算法的性能对比提供了现成的试验台。

5. 算法实现避坑指南：Python对象模型与复杂度误判的血泪经验

5.1 坑1：可变默认参数让所有栈实例共享同一个列表

现象：创建两个Stack实例，往第一个里面push一个元素，第二个实例的len也变成了1，好像两个栈在共享同一块内存。

原因：Python的函数默认参数在定义时只求值一次。写成def __init__(self, items=[])，那个[]是全局唯一的对象，所有实例的_items都指向它。

解决：默认参数一律用None，函数体内再新建列表。

class Stack: def __init__(self, items=None): self._items = items if items is not None else []

这段修正的逻辑是：items is not None才复用传入的列表，否则创建全新列表。代价是几乎为零，收益是杜绝共享状态。这个坑在链表和树这类递归结构里更隐蔽——默认参数是父节点、默认参数是字典，都会踩。写类时凡是默认值涉及可变对象，条件反射改成None加判断。

5.2 坑2：递归深度的天花板与重复计算的浪费

现象：直接实现fib(35)要等好几秒，fib(1000)直接抛RecursionError。代码逻辑没错，但慢到没法用，深到没法跑。

原因：第一个问题的根子是重复计算——fib(n)递归调用fib(n-1)和fib(n-2)，同一个子问题被反复求解，调用次数以指数增长。第二个问题的根子是Python的递归深度限制，默认约1000层，再深就保护性报错。

解决：用记忆化缓存中间结果，把指数级降到线性级。

from functools import lru_cache @lru_cache(maxsize=None) def fib(n: int) -> int: if n < 2: return n return fib(n - 1) + fib(n - 2)

lru_cache把每次调用的入参和返回值存进缓存，maxsize=None表示不限制缓存条目数。代价是用内存换时间：缓存了n个结果，换来fib(1000)秒回。如果不想引入第三方依赖，手写一个字典做缓存也完全可行。这个坑的通用启示是：遇到递归先问自己两个问题，每个子问题是否被重复计算、递归深度是否可控。两个答案都是否，再放心写递归版本。

5.3 坑3：把in list当成O(1)

现象：手写一个成员判断，数据量到几十万以后慢得离谱，但自己觉得只是简单查一下。

原因：item in list对list是线性扫描，复杂度O(n)；对set和dict是哈希查找，平均O(1)。两者差了一个数量级，数据量越大差距越明显。

解决：高频成员判断用set，或者把数据建成索引结构。

import timeit lst = list(range(200_000)) st = set(range(200_000)) t_list = timeit.timeit(lambda: 199_999 in lst, number=100) t_set = timeit.timeit(lambda: 199_999 in st, number=100) print(f"list: {t_list:.4f}s, set: {t_set:.4f}s")

跑出来的结果通常是list比set慢几十到上百倍。这个验证本身是个好习惯：不要凭感觉猜复杂度，timeit一测就知道真实差距。还要注意另一个隐藏点：放进set的元素必须可哈希，list、dict这类可变对象放不进去，这时要么转成不可变类型，要么自己设计索引结构。复杂度分析的结论必须在自己的机器上验证过，才算真正内化。

5.4 坑4：继承层级过深，变成一个黑匣子

现象：容器类三层以上的继承，调用某个方法时不知道走的是哪个父类的实现；想换行为又怕影响旁支子类，改代码像拆雷。

原因：继承最大的问题在于它把多个层级的行为隐式叠加。第2章讲继承复用是有效的，但那是「一两层的复用」。一旦超过三层，每个方法都要沿着MRO链追溯来源，阅读成本成倍上升，重构起来没有后悔药。

解决：优先组合，继承只保留在「is-a」关系明显且层级不超过两层的地方。第4章的Stack和Queue就是组合的正面教材：内部持有一个list，行为完全自己控制，不暴露也不需要暴露list的方法。如果发现自己在用继承只是为了省几行代码，先停一下，想想改成组合是不是更清楚。数据结构和算法的学习阶段，继承的用途应该集中在「抽象接口」和「一两层公共代码复用」，而不是搭建复杂的类型树。

5.5 坑5：测试欠债太多，重构时没有后悔药

现象：改完ArrayList的add逻辑，发现LinkedList的测试也挂了；或者改完某个细节后，自己也说不清是否破坏了原有行为。

原因：测试只覆盖了正常路径，或者每个容器各写各的测试，没有统一的契约。容器之间的行为有一致约定，测试却各搞一套，回归时漏网之鱼特别多。

解决：为所有容器定义一套共用契约测试，让每个实现都跑同一份考卷。

import unittest from containers.array_list import ArrayList from containers.linked_list import LinkedList class ContainerContractTest(unittest.TestCase): """所有容器必须通过同一组契约测试。""" def make(self): raise NotImplementedError def test_add_len_iter(self): c = self.make() c.add("a") c.add("b") self.assertEqual(len(c), 2) self.assertEqual(list(c), ["a", "b"]) class TestArrayListContract(ContainerContractTest): def make(self): return ArrayList() class TestLinkedListContract(ContainerContractTest): def make(self): return LinkedList()

make方法由子类各自实现返回要测试的容器，test_add_len_iter则断言所有容器共有的行为。新增一种容器时，只要继承ContainerContractTest并实现make，立刻获得全部契约测试。这个模式把「接口统一」和「测试复用」绑在了一起，是学习阶段最值得养成的工程习惯。测试不是写完代码之后的装饰，而是你自己改动代码时的安全网。

6. 把这本书读成工程能力：用标准库对照与性能回归验证你的实现

6.1 用标准库验证接口设计：读collections.abc源码

自己实现的Container到底设计得好不好，最好的评判标准是看标准库怎么定义同类接口。用Python一条命令就能调出标准库源码：

import collections.abc, inspect print(inspect.getsource(collections.abc.Container))

读标准库的抽象基类定义，和自己写的版本逐行对照：标准库里Container只要求__contains__，Sized要求__len__，Iterable要求__iter__——它们是按能力拆分的多个小接口，而不是一个大而全的基类。这个观察很重要：标准库分层更细，组合更灵活。你可以保留自己这份简单基类用于学习，但心里要清楚工程上的接口划分应该更精细。这就是把「源码分析」变成学习材料的最短路径，不用找任何外部资料，标准库就在你的解释器里。

6.2 复杂度对照：用timeit验证你学过的每个结论

数据结构学完了，大O分析也背了，但到底对不对，要实测。下面这张表是常见操作的复杂度对比：

用timeit跑一下头部插入的对比，验证表里最后两行的差距：

import timeit from collections import deque lst = list(range(10_000)) dq = deque(range(10_000)) t_list = timeit.timeit(lambda: lst.insert(0, -1), number=1000) t_deque = timeit.timeit(lambda: dq.appendleft(-1), number=1000) print(f"list.insert(0): {t_list:.4f}s, deque.appendleft: {t_deque:.4f}s")

结果必然是deque.appendleft远快于list.insert(0)，差异直接印证复杂度分析的结论。这个验证习惯值得长期保留：每学一个复杂度结论，就写一段timeit去证实它。复杂度分析不是考试题，是你的性能预算表。

6.3 组合与继承的判断标准：一个可持续用的决策习惯

学完这一整套实现，到最后真正沉淀下来的东西是一套决策习惯。遇到一个新容器需求时，我自己的执行顺序是：第一步写出这个ADT必须暴露的操作清单，第二步判断能否用组合包住现有类型，第三步才考虑继承自哪个基类。继承只用在「多个类确实共享同一段行为逻辑」的场合，而且层级不超过两层。这个顺序帮我绕过了很多设计上的弯路，也让每一份容器代码都保持可读、可测、可替换。

复盘整个过程，我最大的教训是：最初学这部分时一心求快，跳过了亲手实现，直接刷题，结果面试时被问到底层结构，一句话都答不上来。后来把每个容器按这个路径——定义接口、实现核心方法、写契约测试、对照标准库——完整过了一遍，才算真正有了底气。希望你也能从亲手实现第一个ArrayList开始，把数据结构和算法变成自己的工程底子，希望帮到你。

本文还有配套的精品资源，点击获取