数据结构¶

列表¶

元素个数： 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>) 将可迭代对象的元素添加到列表末尾

字符串¶

转义字符： \n 换行， \t 制表符， \\ 反斜杠， \' 单引号， \" 双引号

字典¶

形式：{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）和指向其子节点的引用。树的顶端节点称为根节点（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）¶

def label(tree):
    return tree[0]
def branches(tree):
    return tree[1:]

提供“取树的标签”的抽象操作。
提供“取树的所有分支”的抽象操作。
调用者通过它读数据，而不是写 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），让构造器、调试、边界检查更可靠。