日拱一卒，伯克利教你数据结构
大家好，日拱一卒，我是梁唐。
我们同样继续来做伯克利CS61A公开课的实验，这一次是实验7，话题关于链表和树，这也是数据结构当中最重要的两个概念，几乎没有之一。
这次的作业都在lab07.py和lab07_extra.py两个文件当中完成。
Topics
Linked Lists
我们学过，在Python当中list是一种存储序列值的工具。另外一种list叫做链表。Python中的list将所有数据存在一个对象里，list中的每一个元素可以通过下标获取。而链表是一种递归式的对象，它只会保存两个东西：存储的值和list中剩下的值（另外一个链表）。
我们可以实现一个类Link，它实现链表对象。每一个Link的实例都拥有两个实例属性，first和rest。first为存储的值，rest为剩下元素的链表。
class Link:
"""A linked list.
>>> s = Link(1)
>>> s.first
1
>>> s.rest is Link.empty
True
>>> s = Link(2, Link(3, Link(4)))
>>> s.second
3
>>> s.first = 5
>>> s.second = 6
>>> s.rest.rest = Link.empty
>>> s # Displays the contents of repr(s)
Link(5, Link(6))
>>> s.rest = Link(7, Link(Link(8, Link(9))))
>>> s
Link(5, Link(7, Link(Link(8, Link(9)))))
>>> print(s) # Prints str(s)
<5 7 <8 9>>
"""
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest
@property
def second(self):
return self.rest.first
@second.setter
def second(self, value):
self.rest.first = value
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 + ')'
def __str__(self):
string = '<'
while self.rest is not Link.empty:
string += str(self.first) + ' '
self = self.rest
return string + str(self.first) + '>'
一个有效的链表应该满足下列其中之一的条件：
- 空链表（
Link.empty） Link对象包含链表的第一个值，以及一个指向剩余链表的引用。rest属性是剩余元素组成的另外一个链表的引用，这样让整个链表变成了递归的形式。从宏观来说，链表的每一个实例都存储了一个单独的元素。多个Link通过rest属性链接在了一起，组成了完整的序列。
注意：这个定义表明了任何Link实例的rest属性要么是一个Link.empty要么是另外一个Link的实例。这在Link__.init__当中做了限制，如果传给rest属性的值不符合的话，将会抛出AssertionError
我们还通过@property装饰器定义了一个伪属性second，它将会返回链表中的第二个元素。注意，第二个元素其实就是rest属性上的first属性的值。你可以不必关心这里setter方法的语法。查看注释文本近距离观察如何使用property。
通过和Link.empty进行比较可以判断链表是否为空。比如，下方的函数会打印出当前的链表是否为空：
def test_empty(link):
if link is Link.empty:
print('This linked list is empty!')
else:
print('This linked list is not empty!')
Motivation: Why linked lists
你已经熟悉了Python原生的list，你可能好奇，为什么我们要教你另外一个list的实现方式。这是有历史和实际的原因的。在之后的课程当中，你将会使用Scheme语言编程，这是一个几乎全都由链表实现的语言。
目前为止，让我们通过插入元素和索引这两个序列中标准的操作来对比一下链表和Python中原生的list。
Python原生的list是以序列的方式存储元素的，每一个元素有对应的下标。
链表是一个串联方式实现的，每一个节点都指向它的后一位元素，因此没办法直接获得每一个元素的索引。
假设我们希望在list的头部插入一个元素。
- 对于原生的list，如果想要在下标0处插入元素，那么你需要将所有的元素向后移动一位来腾出位置给插入的元素。
- 对于链表来说，你只需要将新的元素的下一位指向原先的链表头即可：
我们可以比较一下这两种方式运行的时间来感受一下差异。在你的终端输入以下命令来进行测试：
python3 timing.py insert 100000
现在，再让我们看看索引。假设我们希望序列当中下标是3的item。
- 在list当中，我们可以直接通过下标来索引，比如
lst[3] - 在链表当中，我们需要从第一个元素开始重复访问
rest属性，比如：link.rest.rest.first。如果我们尝试访问的下标非常大，这个方法会达到什么规模？
我们也可以在终端运行一下命令来测试：
python3 timing.py index 10000
这个程序比较了从list和链表当中随机获取10000个item（总长10000）的运行速度。
从这个测试当中，你可以得到什么结论？当你想要使用的时候，你能根据情况想清楚应该选择哪一个数据结构吗？在这节课上，我们不需要太过担心性能的问题。然而在未来的计算机科学的课程当中，你将会学到在选择数据结构的时候，如何根据性能做取舍。
Trees (Again)
我们之前看过了之前，如何把树当做抽象类型。简单回忆一下，树是一个递归结构，它拥有一个label（表示节点的值）和branches（以当前节点为根的子树的list）。
我们之前学的是树结构的一种简单的表达，在之前的场景当中，这是通过Python中的list实现的。
现在，我们将要把树当做是拥有属性和方法的对象。接下来是类的代码：
class Tree:
def __init__(self, label, branches=[]):
for c in branches:
assert isinstance(c, Tree)
self.label = label
self.branches = list(branches)
def __repr__(self):
if self.branches:
branches_str = ', ' + repr(self.branches)
else:
branches_str = ''
return 'Tree({0}{1})'.format(self.label, branches_str)
def is_leaf(self):
return not self.branches
def __eq__(self, other):
return type(other) is type(self) and self.label == other.label \
and self.branches == other.branches
def __str__(self):
def print_tree(t, indent=0):
tree_str = ' ' * indent + str(t.label) + "\n"
for b in t.branches:
tree_str += print_tree(b, indent + 1)
return tree_str
return print_tree(self).rstrip()
def copy_tree(self):
return Tree(self.label, [b.copy_tree() for b in self.branches])
你会发现Tree这个类和之前的ADT非常相似，这是因为类在用抽象数据结构表示实体的问题上非常方便。下面是ADT和面向对象的一些差异：
| - | Tree ADT | Tree class |
|---|---|---|
| 构建一棵树 | 调用构造函数tree(...)返回一个树的ADT | 调用类构造函数Tree(...)返回一个Tree的对象 |
| label和branches | 使用选择器label(...)和branches(...)获取 | 存储在实例属性label和branches中 |
| 修改性 | 树的ADT不可修改 | 树的label和branches属性可以被重赋值或修改 |
| 检查一棵树是否是叶子 | is_leaf(...)函数会返回一个tree ADT是不是叶子 | 树对象绑定的t.is_leaf()返回树对象是否是叶子。这个方法只能被Tree的对象调用 |
Required Questions
What Would Python Display?
必答题，阅读Python代码给出输出结果
Q1: WWPD: Linked Lists
阅读lab07.py中的Link类，确保你理解了注释中的测试样例。使用ok命令来回答问题：python3 ok -q link -u
如果程序运行时返回的是一个函数，那么输入Function。如果运行时报错，输入Error。如果程序什么也不会展示，输入Nothing。
如果你被困住了，你可以使用命令python3 -i lab07.py进行实际演示。
一共有17题，难度不大，需要先阅读一下lab07.py代码。
>>> from lab07 import *
>>> link = Link(1000)
>>> link.first
______
>>> link.rest is Link.empty
______
>>> link = Link(1000, 2000)
______
>>> link = Link(1000, Link())
______
>>> from lab07 import *
>>> link = Link(1, Link(2, Link(3)))
>>> link.first
______
>>> link.rest.first
______
>>> link.rest.rest.rest is Link.empty
______
>>> link.first = 9001
>>> link.first
______
>>> link.rest = link.rest.rest
>>> link.rest.first
______
>>> link = Link(1)
>>> link.rest = link
>>> link.rest.rest.rest.rest.first
______
>>> link = Link(2, Link(3, Link(4)))
>>> link2 = Link(1, link)
>>> link2.first
______
>>> link2.rest.first
______
>>> from lab07 import *
>>> link = Link(5, Link(6, Link(7)))
>>> link.second
______
>>> link.rest.second
______
>>> link.second = 10
>>> link # Look at the __repr__ method of Link
______
>>> link.second = Link(8, Link(9))
>>> link.second.first
______
>>> print(link) # Look at the __str__ method of Link
______
Q2: WWPD: Trees
使用OK命令来测试对树结构的理解：python3 ok -q trees -u
如果程序运行时返回的是一个函数，那么输入Function。如果运行时报错，输入Error。如果程序什么也不会展示，输入Nothing。
>>> from lab07 import *
>>> t = Tree(1, Tree(2))
______
>>> t = Tree(1, [Tree(2)])
>>> t.label
______
>>> t.branches[0]
______
>>> t.branches[0].label
______
>>> t.label = t.branches[0].label
>>> t
______
>>> t.branches.append(Tree(4, [Tree(8)]))
>>> len(t.branches)
______
>>> t.branches[0]
______
>>> t.branches[1]
______
Coding Practice
Q3: Link to List
编写一个函数link_to_list，它接收一个链表返回一个Python list。你可以假设输入的list是浅层的，即没有嵌套，list的每个元素不会是另外一个list。
试着写出递归和非递归的版本。
def link_to_list(link):
"""Takes a linked list and returns a Python list with the same elements.
>>> link = Link(1, Link(2, Link(3, Link(4))))
>>> link_to_list(link)
[1, 2, 3, 4]
>>> link_to_list(Link.empty)
[]
"""
"*** YOUR CODE HERE ***"
测试命令：python3 ok -q link_to_list
答案
首先非递归版本很好写，我们只需要使用while循环来遍历链表，每一次移动时将当前的link指向它的rest即可。
def link_to_list(link):
ret = []
while link is not Link.empty:
ret.append(link.first)
link = link.rest
return ret
我们已经做了这么多关于递归的问题，到这里已经是洒洒水了。
def link_to_list(link):
if link is Link.empty:
return []
return [link.first] + link_to_list(link.rest)
Q4: Store Digits
编写函数store_digits，它接收一个整数n，返回一个链表。链表中的每一个节点存储了n的每一个数字
def store_digits(n):
"""Stores the digits of a positive number n in a linked list.
>>> s = store_digits(1)
>>> s
Link(1)
>>> store_digits(2345)
Link(2, Link(3, Link(4, Link(5))))
>>> store_digits(876)
Link(8, Link(7, Link(6)))
"""
"*** YOUR CODE HERE ***"
测试命令：python3 ok -q store_digits
答案
不使用递归很简单，我们只需要每次从n的末尾取出数字，然后放入链表当中去。由于我们遍历n的顺序是从右往左，所以我们搭建链表也需要从右往左，也就是从后往前，每次向链表的头部插入元素。
理解了链表的工作原理，这并不难。
def store_digits(n):
ret = Link.empty
while n > 0:
cur = Link(n % 10)
cur.rest = ret
ret = cur
n //= 10
return ret
如果要使用递归，则会有一些麻烦。
最麻烦的点在于，我们最后要返回的结果是链表的头部。而我们递归的时候，每次拿到的是n的最右侧的数字，需要往递归得到的结果的尾部添加。要返回的是头部，但是要修改的却是尾部。
这两个信息都是必要的，所以没办法，只能让函数同时返回头尾。这样的话，我们需要使用高阶函数。在函数内部创建helper函数，它会同时返回生成的链表的头部和尾部。我们在尾部修改，头部用来作为结果返回。
还有一点要注意，递归的基础条件：n < 10，此时只有一个数字，对应的链表只有一个元素。也就是头尾是一样的。这里我们不能返回Link(n), Link(n)，而需要先创建Link(n)再返回两次。这是因为前者会返回两个对象，而后者只会返回一个。虽然看起来它们的值一样，但在物理存储空间是不同的两个实例，会导致链表的结构出错，千万要当心。
def store_digits(n):
def helper(n):
if n < 10:
cur = Link(n)
return cur, cur
head, tail = helper(n // 10)
tail.rest = Link(n % 10)
return head, tail.rest
return helper(n)[0]
Q5: Cumulative Sum
编写一个函数cumulative_sum用来修改树，让树上的每一个节点的值变成以它为子树的所有节点的总和。
def cumulative_sum(t):
"""Mutates t where each node's root becomes the sum of all entries in the
corresponding subtree rooted at t.
>>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> cumulative_sum(t)
>>> t
Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
"""
"*** YOUR CODE HERE ***"
使用ok命令来进行测试：python3 ok -q cumulative_sum
答案
简单递归
def cumulative_sum(t):
tot = 0
for b in t.branches:
cumulative_sum(b)
tot += b.label
t.label += tot
Optional Questions
接下来的问题都是附加题，在lab07_extra.py中。
Linked List Practice
Q6: Remove All
实现函数remove_all，它接收一个List和一个value。删除链表当中所有包含value的节点。你可以假设，链表当中至少包含一个value，并且第一个元素永远不会删除。注意，你不需要返回任何结果，只需要修改链表。
def remove_all(link , value):
"""Remove all the nodes containing value. Assume there exists some
nodes to be removed and the first element is never removed.
>>> l1 = Link(0, Link(2, Link(2, Link(3, Link(1, Link(2, Link(3)))))))
>>> print(l1)
<0 2 2 3 1 2 3>
>>> remove_all(l1, 2)
>>> print(l1)
<0 3 1 3>
>>> remove_all(l1, 3)
>>> print(l1)
<0 1>
"""
"*** YOUR CODE HERE ***"
答案
我们要删除掉链表中的一些元素，可以创建两个指针。
一个指针用来遍历链表，一个指针指向删除元素之后保留的链表的最末尾的节点。这样当我们遍历到了新的不被删除的节点时，就可以直接将它拼接在末尾了。
def remove_all(link , value):
last = link
pnt = link.rest
while pnt is not Link.empty:
if pnt.first != value:
last.rest = pnt
last = last.rest
pnt = pnt.rest
last.rest = Link.empty
Q7: Mutable Mapping
实现deep_map_mut(fn, link)函数，它会将fn应用在给定的链表link上的所有元素。
如果链表的元素依然是链表，我们需要继续将fn应用在它上面的元素上。同样，你只需要实现逻辑在原链表上修改即可，不需要返回任何值。
提示：原生isinstance 函数可能会很有用
>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> isinstance(s, Link)
True
>>> isinstance(s, int)
False
测试命令：python3 ok -q deep_map_mut
答案
因为我们开发的这个deep_map_mut本身就是为了将fn映射到链表的。所以如果我们发现链表的某一个元素也是一个链表，那么直接调用deep_map_mut即可。
如果不是的话，我们递归往后调用，即传入link.rest。
def deep_map_mut(fn, link):
if link is Link.empty:
return
if isinstance(link.first, Link):
deep_map_mut(fn, link.first)
else:
link.first = fn(link.first)
deep_map_mut(fn, link.rest)
Q8: Cycles
Link类可以用来表示有环的链表，也就是说存在一个链表它是它自身的子链表。比如这个例子：
>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> s.rest.rest.rest.rest.rest.first
3
实现has_cycle函数，返回传入的链表是否包含环。
def has_cycle(link):
"""Return whether link contains a cycle.
>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> has_cycle(s)
True
>>> t = Link(1, Link(2, Link(3)))
>>> has_cycle(t)
False
>>> u = Link(2, Link(2, Link(2)))
>>> has_cycle(u)
False
"""
"*** YOUR CODE HERE ***"
测试命令：python3 ok -q has_cycle
作为额外挑战，实现has_cycle_constant函数，它只用常数级的空间。（如果你刚才跟着提示的话，应该会使用线性空间）。这个解法非常短（少于20行代码），但非常机智。
使用OK命令来进行测试：python3 ok -q has_cycle_constant
答案
可以适用线性空间很容易想到，我们可以使用一个set来存储链表当中的所有元素。如果有遇到之前出现过的节点，那么就说明了链表中存在环。
def has_cycle(link):
st = set()
while link is not Link.empty:
if link in st:
return True
st.add(link)
link = link.rest
return False
使用常数级空间复杂度来判断链表是否有环是微软知名的笔试题，思路非常巧妙，我们之前写过，这里就不过多赘述了。
原理就是我们使用两个指针，一个快指针一个慢指针。快指针每次移动两个元素，慢指针每次移动一个位置。如果快慢指针相遇，那么说明链表中有环，如果快指针遍历到了链表结束仍然没有相遇，说明没有环。可以证明，如果有环，一定会相遇。
思路比较巧妙，代码并不难写。
def has_cycle_constant(link):
quick, slow = link, link
while quick is not Link.empty:
quick = quick.rest
if quick is Link.empty:
return False
quick = quick.rest
slow = slow.rest
if quick is slow:
return True
return False
Tree Practice
Q9: Reverse Other
实现一个函数reverse_other，它使得树上奇数层的branch被翻转（树根深度为0）。比如Tree(1, [Tree(2), Tree(3)])变成Tree(1, [Tree(3), Tree(2)])。
def reverse_other(t):
"""Mutates the tree such that nodes on every other (even_indexed) level
have the labels of their branches all reversed.
>>> t = Tree(1, [Tree(2), Tree(3), Tree(4)])
>>> reverse_other(t)
>>> t
Tree(1, [Tree(4), Tree(3), Tree(2)])
>>> t = Tree(1, [Tree(2, [Tree(3, [Tree(4), Tree(5)]), Tree(6, [Tree(7)])]), Tree(8)])
>>> reverse_other(t)
>>> t
Tree(1, [Tree(8, [Tree(3, [Tree(5), Tree(4)]), Tree(6, [Tree(7)])]), Tree(2)])
"""
"*** YOUR CODE HERE ***"
使用ok命令来进行测试：python3 ok -q reverse_other
答案
题目有一点难懂，我们在逆序的时候，并不是把节点反序就行了，而是要将节点当中的label进行反序，节点的branches要保持不变。所以我们需要单独对节点中的label进行修改。
理解了题意之后，剩下的难度就是我们怎么知道什么时候应该反序呢？这就要求我们得知道当前的层数的奇偶性，我们可以设计另外一个参数flag来表示当前层的奇偶性。如果是奇数，那么则进行反序操作，否则就直接跳过。
每次在递归的时候，我们传入1 - flag就可以保证每两层会触发一次反序操作，这也是常用的套路。
同样，由于我们修改了函数签名，额外加上了一个参数，所以我们需要使用高阶函数，在reverse_other函数当中再实现一个函数reverse用来递归。
def reverse_other(t):
def reverse(t, flag):
if t.is_leaf():
return
if flag:
n = len(t.branches)
for i in range(n // 2):
t.branches[i].label, t.branches[n-i-1].label = t.branches[n-i-1].label, t.branches[i].label
for b in t.branches:
reverse(b, 1-flag)
reverse(t, 1)
好了，这次的内容就到这里，感谢大家的阅读~
转载自:https://juejin.cn/post/7102307178479878175