数据结构¶
列表¶
- 元素个数：
len(<list>) - 测试元素是否在列表中：
<element> in <list> - 列表推导：
[expression for item in iterable if condition] - 元素求和：
sum(<list>[, start])其中不指定 start 则默认为 0，可以指定 start 为空list，则可以结合列表 - 最大值：
max(<list>[, key=function])，其中 key 参数可以指定一个函数，把函数作用到每个元素上再比较大小 - 加入元素：
<list>.append(<element>)在列表末尾添加元素 - 插入元素：
<list>.insert(index, <element>)在指定位置插入元素 - 删除元素：
<list>.remove(<element>)删除第一个匹配的元素 - 弹出元素：
<list>.pop([index])删除并返回指定位置的元素，默认删除最后一个 - 查找元素位置：
<list>.index(<element>[, start, end]) - 计数：
<list>.count(<element>)返回元素在列表中出现的次数 - 排序：
<list>.sort(key=function, reverse=bool)就地排序，修改原列表 - 反转：
<list>.reverse()就地反转，修改原列表 - 延展列表：
<list>.extend(<iterable>)将元素添加到列表末尾 - 连接：
<char>.join(<list>)将列表中的字符串连接成一个字符串，元素之间用指定字符<char>分隔 - all()：
all(<iterable>)如果 iterable 中的所有元素都为真值（或 iterable 为空），返回 True，否则返回 False - any()：
any(<iterable>)如果 iterable 中至少有一个元素为真值，返回 True，否则返回 False
字符串¶
-
转义字符：
\n换行，\t制表符，\\反斜杠，\'单引号，\"双引号 -
f字符串：在字符串前加
f或F，可以在字符串中嵌入表达式，表达式用花括号{}包围。
注意：字符串本身（在Python里）是不带引号的，只有在表示字符串的代码里才需要引号。
字典¶
- 形式：
{key1: value1, key2: value2} - 获取值：
<dict>[key] - 显示所有键：
list(<dict>)，返回一个list - 显示所有值：
<dict>.values()，返回dict_values对象，可以转换为list - 键的类型只能是不可变类型，如字符串、数字、元组等，不能是列表、字典等可变类型
- 使用表达式创建字典：
{<key_expression>: <value_expression> for <item> in <iterable> if <condition>}
元组¶
- 形式：
(<element1>, <element2>, ...) - 获取元素：
<tuple>[index] - 元组不可变，不能修改、添加或删除元素，但如果元组内部的元素是可变类型（如列表），则可以修改这些元素
- 单元素元组：
(<element>,)注意逗号
数据抽象¶
抽象数据类型（ADT）的核心思想：把“数据怎么存”和“数据怎么用”分开。使用数据的程序里应当分离两部分：
- 数据如何表示/存储：内部结构是什么（用列表、元组、字典、类……）、字段怎么放。
- 数据如何被操作/使用：外部提供哪些操作（加法、比较、打印等），使用者只调用这些操作。
需要保证：构造器函数和选择器函数能一起正常工作，从而实现正确的行为。
例如，用分子 n 和分母 d 构造出一个有理数 x，那么再用选择器取出它的分子 numer(x) 和分母 denom(x) 时，应当满足：
numer(x)/denom(x)=n/d
也就是：“构造出来的东西”再被“取出来”后，表示的数值要和原来的 n/d 相同。
树¶
树是一种递归的数据结构，由节点（node）和边（edge）组成。每个节点包含一个值（label）和指向其子节点的引用，节点有parent和child属性。树的顶端节点称为根节点（root），没有子节点的节点称为叶节点（leaf）。
一棵树是一个 Python
list，第 0 个元素是label，后续元素都是子树（branches）。
构造器（constructor）¶
def tree(label, branches=[]):
for branch in branches:
assert is_tree(branch)
return [label] + list(branches)
- 根据“树”的抽象定义创建一个树值。
- 维护 ADT 的不变式（invariant）：每个分支也必须是树。
选择器（selector）¶
- 提供“取树的标签”的抽象操作。
- 提供“取树的所有分支”的抽象操作。
- 调用者通过它读数据，而不是写
tree[0]。 - 封装“分支存放在 tree[1:]”这一表示细节。
判定器/验证器（predicate/validator）¶
def is_tree(tree):
if type(tree) != list or len(tree) < 1:
return False
for branch in branches(tree):
if not is_tree(branch):
return False
return True
def is_leaf(tree):
return not branches(tree)
- 判断一个对象是否符合“树 ADT”的表示不变式（representation invariant），让构造器、调试、边界检查更可靠。
链表¶
链表是一种线性数据结构，由节点（node）组成，每个节点是一个link实例，包含一个值（value/first）和指向下一个节点的引用（next/rest->node）。链表的第一个节点称为头节点（head），最后一个节点的 next 引用为 None，具有link.empty属性，表示链表的结束。
class Link:
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest
def __repr__(self):
if self.rest is not Link.empty:
rest_repr = ', ' + repr(self.rest)
else:
rest_repr = ''
return 'Link(' + repr(self.first) + rest_repr + ')'
缓存¶
缓存是一种存储数据的机制，用于提高数据访问速度。通过将频繁访问的数据存储在快速存取的存储介质中，减少重复计算次数，从而提升性能。下面是记忆化的一个简单实现：