CS 61A 学习笔记（二）：Lectures 9–14

整合范围：Lecture 9 至 Lecture 14。内容以课堂笔记为主，并进行了 Markdown 格式整理。

Lecture 9: Recursion

递归（Recursion）

一种函数调用自身的行为，通常可与迭代（Iteration）相互转化。

Lecture 10: Tree Recursion

树形递归（Tree Recursion）

在一次函数调用中对自身进行多次递归调用的递归函数，会产生一系列类似树形的调用。

例如，斐波那契数列在 n >= 2 时满足：

f(n) = f(n - 1) + f(n - 2)

并需定义基例。

Lecture 11: Sequences

本节介绍两种常用的序列类型：

列表（List）

一种可以存储有序的元素集合的数据结构（元素可以为任何类型）。

列表推导式（List Comprehension）

[<expression> for <element> in <sequence> if <conditional>]

范围（Range）

用于表示整数序列的不可变序列类型，可通过 list(range(...)) 把 range 对象转换为 list。

`for` 循环

针对序列（Sequences）中的每个元素依次执行代码：

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

Lecture 12: Containers

处理容器值（Processing Container Values）

sum(iterable[, start]) -> value
max(iterable[, key=func]) -> value
all(iterable) -> bool

作为起始值的 start 在某些情况下很重要，例如：

sum([[2], [3]], [])  # [2, 3]

字典（Dictionaries）

按照 key 寻找 value（类似 map）。

字典推导式（Dictionary Comprehension）

{<key exp>: <value exp> for <name> in <iter exp> if <filter exp>}

例如：

{k: [v for v in values if match(k, v)] for k in keys}

Lecture 13: Data Abstraction

构造函数和选择函数（Constructors and Selectors）

构造函数（Constructors）负责把若干部分组合成一个完整的数据对象；选择函数（Selectors）负责从这个数据对象中取出需要的部分。

抽象屏障（Abstraction Barriers）

隐藏实现细节，规定使用接口，让程序不同部分彼此独立，即把数据的底层表示隐藏在构造函数和选择函数之后；在接口保持不变时，更改底层实现无需修改上层代码。

例如：

def add_rational(x, y):
    new_numer = numer(x) * denom(y) + numer(y) * denom(x)
    new_denom = denom(x) * denom(y)
    return rational(new_numer, new_denom)

而非在上层代码中直接按列表形式访问底层表示。

Lecture 14: Tree

树（Tree）

一种表示信息层次结构的数据结构。

目录