日拱一卒，伯克利教你Python数据结构
大家好，日拱一卒，我是梁唐。
我们继续来上伯克利CS61A的实验课，这一次我们看的是第五次实验。这一次实验的主题关于Python中可变变量类型（list，set，dict）以及树结构的简单介绍。
可以理解成关于Python和数据结构基础的一次融合。还是和之前一样，我们需要先登录实验文档，下载压缩包解压。
我们进行答题和实验的是lab05.py和lab05_extra.py这两个文件，其余都是老师提供的测试文件。我们可以用来测试我们的代码是否正确。
这也是这门课值得推荐的地方，即使我们不是伯克利的学生，也一样可以进行测试和程序验证。
好了，废话不多说，我们开始今天的实验。
Required Questions
What Would Python Display?
读程序推测Python展示结果
Q1: Dictionaries
填空题，以下这些代码片段将会展示什么结果？使用命令: python3 ok -q dicts -u进行答题。
>>> pokemon = {'pikachu': 25, 'dragonair': 148, 'mew': 151}
>>> pokemon['pikachu']
______
>>> len(pokemon)
______
>>> pokemon['jolteon'] = 135
>>> pokemon['mew'] = 25
>>> len(pokemon)
______
>>> 'mewtwo' in pokemon
______
>>> 'pikachu' in pokemon
______
>>> 25 in pokemon
______
>>> 148 in pokemon.values()
______
>>> 151 in pokemon.keys()
______
>>> 'mew' in pokemon.keys()
______
>>> pokemon['ditto'] = pokemon['jolteon']
>>> pokemon['ditto']
______
>>> letters = {'a': 1, 'b': 2, 'c': 3}
>>> 'a' in letters
______
>>> 2 in letters
______
>>> sorted(list(letters.keys()))
______
>>> sorted(list(letters.items()))
______
>>> food = {'bulgogi': 10, 'falafel': 4, 'ceviche': 7}
>>> food['ultimate'] = food['bulgogi'] + food['ceviche']
>>> food['ultimate']
______
>>> len(food)
______
>>> food['ultimate'] += food['falafel']
>>> food['ultimate']
______
>>> food['bulgogi'] = food['falafel']
>>> len(food)
______
>>> 'gogi' in food
______
一共有19题，题目不难，是关于Python中dict的基础应用。
大家了解Python基础应该都能做得出来。
Coding Practice
代码练习
Q2: Map, Filter, Reduce
作为练习，实现三个函数map, filter和reducer
map接收一个单参数函数fn和一个序列seq作为参数，它会将fn应用到seq中的每一个元素上。
filter接收一个判定函数pred和一个序列seq，它会返回一个序列，包含seq中所有使用pred判定为True的元素
reduce接收一个双参数函数combiner和一个非空序列seq，它将seq中的元素使用combiner合并到一起
代码框架如下：
def map(fn, seq):
"""Applies fn onto each element in seq and returns a list.
>>> map(lambda x: x*x, [1, 2, 3])
[1, 4, 9]
"""
"*** YOUR CODE HERE ***"
def filter(pred, seq):
"""Keeps elements in seq only if they satisfy pred.
>>> filter(lambda x: x % 2 == 0, [1, 2, 3, 4])
[2, 4]
"""
"*** YOUR CODE HERE ***"
def reduce(combiner, seq):
"""Combines elements in seq using combiner.
>>> reduce(lambda x, y: x + y, [1, 2, 3, 4])
10
>>> reduce(lambda x, y: x * y, [1, 2, 3, 4])
24
>>> reduce(lambda x, y: x * y, [4])
4
"""
"*** YOUR CODE HERE ***"
完成之后使用ok来进行测试：
python3 ok -q map
python3 ok -q filter
python3 ok -q reduce
答案
map和filter都很简单，我们直接使用list comprehension就可以搞定，只需要一行代码。
reduce稍微复杂一点，因为我们不知道seq中的元素究竟有多少个，我们只知道它非空。如果seq中只有一个元素，那么实际上没有什么好合并的，直接返回。如果超过一个，再使用combiner进行合并。
def map(fn, seq):
return [fn(x) for x in seq]
def filter(pred, seq):
return [x for x in seq if pred(x)]
def reduce(combiner, seq):
if len(seq) == 1:
return seq[0]
ret = seq[0]
for i in range(1, len(seq)):
ret = combiner(ret, seq[i])
return ret
Q3: Acorn Finder
学校里的松鼠需要你的帮助，学校里的树太多了，松鼠们想要知道哪些树有橡果。定义一个函数acorn_finder，它接收一棵树，如果树中有一个节点的value是acorn，那么返回True，否则返回False。
代码框架如下：
def acorn_finder(t):
"""Returns True if t contains a node with the value 'acorn' and
False otherwise.
>>> scrat = tree('acorn')
>>> acorn_finder(scrat)
True
>>> sproul = tree('roots', [tree('branch1', [tree('leaf'), tree('acorn')]), tree('branch2')])
>>> acorn_finder(sproul)
True
>>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
>>> acorn_finder(numbers)
False
"""
"*** YOUR CODE HERE ***"
开发完成之后，使用ok进行测试：python3 ok -q acorn_finder
答案
由于我们无法确定树的大小，可能很大也可能很小，所以直接判断是不行的。一定要用递归，可以当做是递归的入门题。
关于tree相关的一些函数在lab05.py的底部。大家不要直接访问tree中的数据，而是要遵守数据抽象的规范，使用对应的函数获取相应的值。
def acorn_finder(t):
if label(t) == 'acorn':
return True
for b in branches(t):
if acorn_finder(b):
return True
return False
Q4: Replace Leaf
实现replace_leaf函数，它接收一棵树t以及一个value old和一个value new。replace_leaf返回一个新的树，它和之前的树t一样，除了每个value等于old的叶子节点被替换成了new。
代码框架：
def replace_leaf(t, old, new):
"""Returns a new tree where every leaf value equal to old has
been replaced with new.
>>> yggdrasil = tree('odin',
... [tree('balder',
... [tree('thor'),
... tree('loki')]),
... tree('frigg',
... [tree('thor')]),
... tree('thor',
... [tree('sif'),
... tree('thor')]),
... tree('thor')])
>>> laerad = copy_tree(yggdrasil) # copy yggdrasil for testing purposes
>>> print_tree(replace_leaf(yggdrasil, 'thor', 'freya'))
odin
balder
freya
loki
frigg
freya
thor
sif
freya
freya
>>> laerad == yggdrasil # Make sure original tree is unmodified
True
"""
"*** YOUR CODE HERE ***"
使用ok命令来进行测试：python3 ok -q replace_leaf
答案
这题我们之前在作业里见过，本质上一样是一个递归的调用，比上面那题稍微复杂一点。
对于t来说，有两种可能，一种是它是叶子，那么我们只需要判断一下它的value是不是等于old，如果相等替换成new即可。
如果t不是叶子，那么我们不需要考虑t的替换，但需要考虑以t为树根的子树的所有叶子节点的替换。所以我们要继续递归执行。replace_leaf会返回一棵新的树，所以我们就利用这点，进行递归建树。
说起来好像有些复杂，但代码实现非常简单，3行就可以搞定。
def replace_leaf(t, old, new):
if is_leaf(t) and label(t) == old:
return tree(new)
return tree(label(t), [replace_leaf(b, old, new) for b in branches(t)])
Optional Questions
选做题，这部分代码在lab05_extra.py中
Shakespeare and Dictionaries
我们将会使用字典来估计莎士比亚作品集。我们将会使用一个bigram语言模型，下面是它的思想：
我们从某个单词开始，比如以The举例。然后我们会遍历莎士比亚作品集的全部文本，找到所有的The，并且记录下The之后的单词，作为单词The的后继，将它存如list中。假设我们对莎士比亚作品中的每个单词都执行了这个操作。
让我们回到单词The。现在我们随机选择一个list中的单词，比如我们选中了cat。然后我们继续寻找一个cat的后继，持续这个过程，这最终会遇到一个句号。这样我们就生成了一个莎士比亚的句子。
我们要查找的对象称为后继表，虽然它实际上只是一个字典。字典的key都是单词，value是一个后继的list。
Q5: Successor Tables
这里是一个未完成的build_successors_table函数的定义，它的输入是一个单词的list（对应莎士比亚文本），输出是一个后继表。默认情况下，第一个单词是'.'的后继。我们看下下面的例子。
def build_successors_table(tokens):
"""Return a dictionary: keys are words; values are lists of successors.
>>> text = ['We', 'came', 'to', 'investigate', ',', 'catch', 'bad', 'guys', 'and', 'to', 'eat', 'pie', '.']
>>> table = build_successors_table(text)
>>> sorted(table)
[',', '.', 'We', 'and', 'bad', 'came', 'catch', 'eat', 'guys', 'investigate', 'pie', 'to']
>>> table['to']
['investigate', 'eat']
>>> table['pie']
['.']
>>> table['.']
['We']
"""
table = {}
prev = '.'
for word in tokens:
if prev not in table:
"*** YOUR CODE HERE ***"
"*** YOUR CODE HERE ***"
prev = word
return table
使用ok命令来进行测试：python3 ok -q build_successors_table
答案
我们要写的代码只有两行，第一行在判断prev not in table之后，这里我们判断了前导单词是否已经在table当中了，如果没有，那么我们要创建对应的条目。一开始当然是空的，所以我们让table[prev] = []
之后，我们把当前的后继，也就是word插入其中，table[prev].append(word)。
def build_successors_table(tokens):
table = {}
prev = '.'
for word in tokens:
if prev not in table:
"*** YOUR CODE HERE ***"
table[prev] = []
"*** YOUR CODE HERE ***"
table[prev].append(word)
prev = word
return table
Q6: Construct the Sentence
让我们来生成一些句子！假设我们给定了一个起始单词。我们找到这个单词的后继，并且随机挑选一个。然后我们只需要重复这个过程，直到我们遇到一个句号。
提示：从list中随机选择可以使用Python中的random库import random; random.choice(my_list)
这是一个拼接字符串的好机会，让我们一起完善construct_sent函数！
代码框架：
def construct_sent(word, table):
"""Prints a random sentence starting with word, sampling from
table.
>>> table = {'Wow': ['!'], 'Sentences': ['are'], 'are': ['cool'], 'cool': ['.']}
>>> construct_sent('Wow', table)
'Wow!'
>>> construct_sent('Sentences', table)
'Sentences are cool.'
"""
import random
result = ''
while word not in ['.', '!', '?']:
"*** YOUR CODE HERE ***"
return result.strip() + word
使用ok命令来进行测试：python3 ok -q construct_sent
答案
只要能看到题意，代码并不难写。
def construct_sent(word, table):
import random
result = ''
while word not in ['.', '!', '?']:
"*** YOUR CODE HERE ***"
result += word + ' '
word = random.choice(table[word])
return result.strip() + word
Putting it all together
太棒了，现在，让我们试着在真实的数据当中运行一下我们的程序。下面这段代码片段将会返回一个list，当中包含了莎士比亚作品集当中的所有内容。
提示：不要试着打印出这个函数的结果
def shakespeare_tokens(path='shakespeare.txt', url='http://composingprograms.com/shakespeare.txt'):
"""Return the words of Shakespeare's plays as a list."""
import os
from urllib.request import urlopen
if os.path.exists(path):
return open('shakespeare.txt', encoding='ascii').read().split()
else:
shakespeare = urlopen(url)
return shakespeare.read().decode(encoding='ascii').split()
去掉接下来两行代码的注释来运行上面的函数，并且从中创建后继表。
# Uncomment the following two lines
# tokens = shakespeare_tokens()
# table = build_successors_table(tokens)
接下来，让我们创建一个工具函数来从后继表中创建句子。
>>> def sent():
... return construct_sent('The', table)
>>> sent()
" The plebeians have done us must be news-cramm'd ."
>>> sent()
" The ravish'd thee , with the mercy of beauty !"
>>> sent()
" The bird of Tunis , or two white and plucker down with better ; that's God's sake ."
注意，所有的句子都是以The开头。做一些小修改，我们可以让我们的句子从一个随机的单词开始。
下面这个函数将会实现这点：
def random_sent():
import random
return construct_sent(random.choice(table['.']), table)
继续，将你的代码放入Python中执行（记得加上-i的flag）。你可以调用random_sent函数来创建随机的莎士比亚句子！
>>> random_sent()
' Long live by thy name , then , Dost thou more angel , good Master Deep-vow , And tak'st more ado but following her , my sight Of speaking false !'
>>> random_sent()
' Yes , why blame him , as is as I shall find a case , That plays at the public weal or the ghost .'
我试了一下，还挺好玩……
More Trees Practice
Q7: Pruning Leaves
创建函数prune_leaves它接收一个tree t以及一系列value vals。将t中所有value在vals中的叶子全部删除。不要尝试去删除一个非叶子节点，并且不要删除不在vals中的叶子。如果你要删除树根，返回None。
代码框架：
def prune_leaves(t, vals):
"""Return a modified copy of t with all leaves that have a label
that appears in vals removed. Return None if the entire tree is
pruned away.
>>> t = tree(2)
>>> print(prune_leaves(t, (1, 2)))
None
>>> 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_tree(prune_leaves(numbers, (3, 4, 6, 7)))
1
2
3
5
6
"""
"*** YOUR CODE HERE ***"
使用ok命令来进行测试：python3 ok -q prune_leaves
答案
主要逻辑和刚才类似，唯一的区别是我们是删除而不是替换。
所以我们不能直接tree(label(t), [prune_leaves(b, vals) for b in branches(t)])因为这会导致list当中有一些值是None。
解决的方案也很简单，我们把循环展开，判断不是None再加入list。
def prune_leaves(t, vals):
if is_leaf(t) and label(t) in vals:
return None
branchs = []
for b in branches(t):
subtree = prune_leaves(b, vals)
if subtree is not None:
branchs.append(subtree)
return tree(label(t), branchs)
Q8: Sprout leaves
创建sprout_leaves函数，接收一个tree t和一个value的list vals。返回一个tree，它的每一个叶子都有新的分支，包含了vals中的每一项。不要给不是叶子节点的节点添加分支。
Define a function sprout_leaves that, given a tree, t, and a list of values, vals, and produces a tree with every leaf having new branches that contain each of the items in vals. Do not add new branches to non-leaf nodes.
代码框架：
def sprout_leaves(t, vals):
"""Sprout new leaves containing the data in vals at each leaf in
the original tree t and return the resulting tree.
>>> t1 = tree(1, [tree(2), tree(3)])
>>> print_tree(t1)
1
2
3
>>> new1 = sprout_leaves(t1, [4, 5])
>>> print_tree(new1)
1
2
4
5
3
4
5
>>> t2 = tree(1, [tree(2, [tree(3)])])
>>> print_tree(t2)
1
2
3
>>> new2 = sprout_leaves(t2, [6, 1, 2])
>>> print_tree(new2)
1
2
3
6
1
2
"""
"*** YOUR CODE HERE ***"
使用ok命令进行测试：python3 ok -q sprout_leaves
答案
和上面的题目基本上一样的套路，不多说了，看代码吧。
def sprout_leaves(t, vals):
if is_leaf(t):
return tree(label(t), [tree(v) for v in vals])
return tree(label(t), [sprout_leaves(b, vals) for b in branches(t)])
Q9: Add trees
创建函数add_trees，它接收两棵树，返回一棵新树。新树上每个节点都是传入的两棵树上同样位置的节点之和。如果一个节点只在一棵树上出现，在答案中一样也会出现。
提示：你也许想要使用zip函数来遍历两个sequence。注意，如果你觉得这题比上面的问题难得多，这是正常的。但我相信你可以做到！
代码框架：
def add_trees(t1, t2):
"""
>>> numbers = tree(1,
... [tree(2,
... [tree(3),
... tree(4)]),
... tree(5,
... [tree(6,
... [tree(7)]),
... tree(8)])])
>>> print_tree(add_trees(numbers, numbers))
2
4
6
8
10
12
14
16
>>> print_tree(add_trees(tree(2), tree(3, [tree(4), tree(5)])))
5
4
5
>>> print_tree(add_trees(tree(2, [tree(3)]), tree(2, [tree(3), tree(4)])))
4
6
4
>>> print_tree(add_trees(tree(2, [tree(3, [tree(4), tree(5)])]), \
tree(2, [tree(3, [tree(4)]), tree(5)])))
4
6
8
5
5
"""
"*** YOUR CODE HERE ***"
使用ok命令进行测试：python3 ok -q add_trees
答案
这题确实比上面要难一些，难点主要在于递归的关系式理不清楚，以及两个不一样长的list不会处理。
我们一个一个来说，首先是递归关系式，由于我们要将两棵形状可能不太一致的树进行合并。我们仔细思考，可以发现这些不一致的地方体现在树结构上就是某一个位置其中一棵树上有节点，另外一棵没有。对于这种情况，我们可以用None将没有的那棵树缺失的位置补上，这样既不会影响结果，又可以让代码变得简单。
既然我们要用None来修补空缺，那么势必就会导致在递归的时候传入的t1和t2这两个参数可能会有None值出现。处理的方式也很简单，如果t1是None，那么合并之后的结果就是t2。如果t2是None，则是t1。
处理完None的情况，剩下的就是都不为None的情况。接下来要好办一些，对于根节点，我们直接取出来相加即可。但分支可能长度不一致，没关系，前面我们已经说过了，出现空缺的时候用None来弥补就好。弥补过后，我们就可以保证两棵树的分支数量相等了，长度相等就意味着我们可以使用zip来进行遍历了。
由于我们在递归的开头已经处理了入参可能存在None的情况，所以大胆地递归就行了。而且本题不可能出现t1和t2都是None的情况，想想看为什么。
def add_trees(t1, t2):
if t1 is None:
return t2
if t2 is None:
return t1
u = label(t1) + label(t2)
b1, b2 = branches(t1), branches(t2)
b1.extend([None] * (len(b2) - len(b1)))
b2.extend([None] * (len(b1) - len(b2)))
b = []
for n1, n2 in zip(b1, b2):
b.append(add_trees(n1, n2))
return tree(u, b)
到这里，本次实验的所有题目就都做完了。不得不说这一次的实验题目还是挺有意思的，尤其是对于递归掌握得不是很好的同学，相信练习之后一定可以获得长足的进步。
转载自:https://juejin.cn/post/7100180290361884708