序列

序列是有顺序的值集合，支持选取元素，并且具有长度。我们已经使用过列表；包括字符串在内的其他 Python 类型也属于序列。

下面通过一个例子看看可以对字符串进行哪些操作。

>>> x = 'Hello there Oski!'
>>> x
'Hello there Oski!'
>>> len(x)
17
>>> x[6:]
'there Oski!'
>>> x[::-1]
'!iksO ereht olleH'

字符串既然是序列，就能进行许多与列表相同的操作。我们甚至可以像遍历列表一样遍历字符串：

>>> x = 'I am not Oski.'
>>> vowel_count = 0
>>> for i in range(len(x)):
...     if x[i] in 'aeiou':
...         vowel_count += 1
>>> vowel_count
5

for 语句会对列表、range 等序列中的每个元素执行一次代码。每次执行时，紧跟在 for 后面的名称都会绑定到序列中的一个不同元素。

for <name> in <expression>:
    <suite>

首先，对 <expression> 求值，其结果必须是一个序列。随后按顺序遍历序列中的每个元素，并把

1. <name> 绑定到当前元素。
2. <suite> 会被执行。

下面是一个例子：

for x in [-1, 4, 2, 0, 5]:
    print("Current elem:", x)

它会显示：

Current elem: -1
Current elem: 4
Current elem: 2
Current elem: 0
Current elem: 5

字典由键值对组成，可以使用方括号按键查找对应的值。字典中的每个键必须唯一。

>>> d = {2: 4, 'two': ['four'], (1, 1): 4}
>>> d[2]
4
>>> d['two']
['four']
>>> d[(1, 1)]
4

可以分别使用 .keys() 或 .values() 或 .items().

>>> for k in d.keys():
...     print(k)
...
2
two
(1, 1)
>>> for v in d.values():
...     print(v)
...
4
['four']
4
>>> for k, v in d.items():
...     print(k, v)
...
2 4
two ['four']
(1, 1) 4

默认情况下，遍历字典就是遍历它的键。

>>> for x in d:
...     print(x)
...
2
two
(1, 1)

可以使用 in检查字典中是否包含某个键：

>>> 'two' in d
True
>>> 4 in d
False

尝试访问字典中不存在的键会引发错误。可以使用 .get(<key>, <default>)；它会返回字典中与 <key> 对应的值，如果该键不存在则返回 <default>.

>>> d[3]
KeyError: 3
>>> d.get(3, "fun")
"fun"
>>> d.get(2, "fun")
4

可以使用下面的方式修改字典内容： =检查字典中是否包含某个键：

>>> d
{2: 4, 'two': ['four'], (1, 1): 4}
>>> d[(1, 1)] = "61a"
>>> d[(1, 1)]
'61a'

字典推导式是一种求值得到新字典的表达式。

>>> {3*x: 3*x + 1 for x in range(2, 5)}
{6: 7, 9: 10, 12: 13}

树递归

树递归函数会在一次执行中多次调用自身，从而形成树状的调用过程。

例如，下面是 Virahanka-Fibonacci 数列： 0, 1, 1, 2, 3, 5, 8, 13, ....

每一项都是前两项之和。下面这个树递归函数用于计算第 n个 Virahanka-Fibonacci 数。

def virfib(n):
    if n == 0 or n == 1:
        return n
    return virfib(n - 1) + virfib(n - 2)

调用 virfib(6) 会产生一个形似倒置树的调用结构（其中 f 为 virfib）：

每次递归调用 f(i) 都会调用 f(i-1) 以及 f(i-2)。每当遇到 f(0) 或 f(1) 调用时，都可以直接返回 0 或 1 ，无须继续递归。这些调用就是基本情况。

基本情况不依赖其他调用的结果就能直接返回答案。到达基本情况后，我们便可以逐层返回，求出此前引向它的递归调用。

之后会看到，树递归通常很适合处理存在多个分支选择的问题：每个选择对应一次递归调用。

数据抽象

数据抽象 是一组用于组合和拆分复合值的函数。其中，称为 构造器 的函数把两个或更多部分组合成一个整体（例如有理数，也就是分数）；而称为 选择器 的函数则返回整体中的某个部分（例如分子或分母）。

def rational(n, d):
    "Return a fraction n / d for integers n and d."

def numer(r):
    "Return the numerator of rational number r."

def denom(r):
    "Return the denominator of rational number r."

关键在于，即使不知道这些函数如何实现，也可以使用数据抽象。例如，只要知道 mul_rationals 的行为，就能判断 rational、 numer和 denom 是否实现正确，而不需要了解这些函数的内部实现。

def mul_rationals(r1, r2):
    "Return the rational number r1 * r2."
    return rational(numer(r1) * numer(r2), denom(r1) * denom(r2))

不过，要让 Python 真正运行程序，数据抽象仍然需要具体实现。使用实现细节就越过了抽象屏障；这道屏障把依赖数据抽象实现的程序部分与不依赖实现的部分分隔开来。良好的程序会尽量减少依赖具体实现的代码，使以后更换实现时无须重写大量代码。

使用已经提供的数据抽象时，应让程序即使在数据抽象的具体实现发生变化后仍然正确。

树

tree 是一种表示信息层级关系的数据结构。文件系统就是树结构的典型例子。例如，在你的 cs61a 文件夹中，会有分别存放 projects、 lab 作业以及 homework的文件夹。下一层又按不同作业分为 hw01、 lab01、 hog等文件夹，里面才是起始文件和 ok等具体文件。下面是不完整的 cs61a 目录结构示意图。

可以看到，与自然界中的树不同，树抽象数据类型通常把根画在顶部，把叶节点画在底部。

对于树 t检查字典中是否包含某个键：

• ，根节点的标签可以是任意值，使用 label(t) 可以返回这个标签。
• 它的分支本身也是树，使用 branches(t) 可以返回分支列表。
• 可以用以下代码构造一棵完全相同的树： tree(label(t), branches(t)).
• 可以调用接收树作为参数的函数，例如 is_leaf(t).
• 这就是操作树的方式，不要使用 t == x 或 t[0] 或 x in t 或 list(t)等实现细节。
• 在不违反抽象屏障的前提下，不能直接修改一棵树。

下面是一棵示例树 t1，它的分支 branches(t1)[1] 为 t2.

t2 = tree(5, [tree(6), tree(7)])
t1 = tree(3, [tree(4), t2])

路径 是一个树序列，其中每棵树都是下一棵树的父节点。

我们的 tree 抽象数据类型由一个根节点及其 branches列表组成。创建树以及访问根值和分支时，应使用下面的构造器与选择器接口：

• 构造器

  • tree(label, branches=[])：创建一个树对象，其根节点使用给定的 label 值，并具有给定的 branches列表。请注意，构造器的第二个参数 branches是可选的；如果要创建没有分支的树，可以省略这个参数。

• 选择器

  • label(tree)：返回 tree.
  • branches(tree)：返回给定 tree 的分支列表（其中每个分支也都是树）。

• 便捷函数

  • is_leaf(tree)：如果 True ，则返回 tree的 branches 列表为空；否则返回 False 。

例如，由下面代码生成的树

number_tree = tree(1,
         [tree(2),
          tree(3,
               [tree(4),
                tree(5)]),
          tree(6,
               [tree(7)])])

如下所示：

   1
 / | \
2  3  6
  / \  \
 4   5  7

要从这棵树中取出数字 3 ，也就是第二个分支根节点的标签，可以这样做：

label(branches(number_tree)[1])

print_tree 函数会以便于阅读的形式打印树。格式与上图一致：根节点不缩进，每深入一层分支就多缩进一级。

def print_tree(t, indent=0):
    """Print a representation of this tree in which each node is
    indented by two spaces times its depth from the root.

    >>> print_tree(tree(1))
    1
    >>> print_tree(tree(1, [tree(2)]))
    1
      2
    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    """
    print('  ' * indent + str(label(t)))
    for b in branches(t):
        print_tree(b, indent + 1)