实验 8：链表

截止时间：7 月 23 日（星期四）晚上 11:59。

起始文件

下载 lab08.zip.

出勤要求

要获得实验课学分，除了到场参加实验课外，你还需要提交实验题目。

如果你因合理原因（例如生病或时间冲突）缺席实验课，或者由于某种原因未能完成签到，请在一周内发送邮件至 cs61a@berkeley.edu ，以补记出勤学分。

链表

如果需要复习链表，可以展开本节。也可以直接开始做题，遇到困难时再回来查阅。

链表是一种用于存储值序列的数据结构。对于某些操作，例如在很长的列表中间插入一个值，它比 Python 内置列表更高效。Python 没有内置链表，因此我们定义了一个名为 Link 的类来表示链表。一个链表要么是 Link 实例，要么是 Link.empty （表示空链表）。

一个 Link 实例有两个实例属性： first 和 rest.

其中 rest 实例的 Link 属性必须始终是链表：要么是另一个 Link 实例，要么是 Link.empty。它绝不能是 None.

要判断链表是否为空，请把它与 Link.empty比较。因为空链表只有唯一一个对象，所以可以用 is 比较，不过使用 == 也可以。

def is_empty(s):
    """Return whether linked list s is empty."""
    return s is Link.empty:

可以通过两种方式改变 Link 对象 s ：

  • 使用下面的赋值修改第一个元素： s.first = ...
  • 使用下面的赋值修改其余元素： s.rest = ...

可以通过调用 Link 创建新的对象： Link:

  • Link(4) 创建一个长度为 1、只含 4 的链表。
  • Link(4, s) 创建一个以 4 开头、后面接链表中各元素的新链表 s.

下面是 Link 类的实现：

class Link:
    """A linked list is either a Link object or Link.empty

    >>> s = Link(3, Link(4, Link(5)))
    >>> s.rest
    Link(4, Link(5))
    >>> s.rest.rest.rest is Link.empty
    True
    >>> s.rest.first * 2
    8
    >>> print(s)
    (3 4 5)
    """
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest:
            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) + ')'

提示： 在 VS Code 中，可以按 Control + ` （Tab 键上方的按键）打开终端。

必做题

链表可视化

如果希望借助工具观察链表结构，请前往 code.cs61a.org，选择 启动 Python 解释器，然后调用 autodraw().

问题 1：WWPD：链表

阅读 Link 类，确保你理解其中的 doctest。

使用 Ok 完成下面的“Python 会显示什么？”（WWPD）题，检查你对知识的掌握情况：

python3 ok -q link -u

输入 Function ，请输入 <function ...>, Error ；如果会报错，输入 Nothing ；如果没有任何显示，则输入

如果遇到困难，可以在纸上画出链表的盒指针图，或者用下面的命令把 Link 类载入解释器： python3 -i lab07.py.

>>> link = Link(1000)
>>> link.first

______
1000

>>> link.rest is Link.empty

______
True

>>> link = Link(1000, 2000)

______
AssertionError

>>> link = Link(1000, Link())

______
TypeError
>>> link = Link(1, Link(2, Link(3)))
>>> link.first

______
1

>>> link.rest.first

______
2

>>> link.rest.rest.rest is Link.empty

______
True

>>> link.first = 9001
>>> link.first

______
9001

>>> link.rest = link.rest.rest
>>> link.rest.first

______
3

>>> link = Link(1)
>>> link.rest = link
>>> link.rest.rest is Link.empty

______
False

>>> link.rest.rest.rest.rest.first

______
1

>>> link = Link(2, Link(3, Link(4)))
>>> link2 = Link(1, link)
>>> link2.first

______
1

>>> link2.rest.first

______
2
>>> link = Link(5, Link(6, Link(7)))
>>> link                 # Look at the __repr__ method of Link

______
Link(5, Link(6, Link(7)))

>>> print(link)          # Look at the __str__ method of Link

______
(5 6 7)

问题 2：移除一项

实现 without，它接收链表 s 和非负整数 i。它返回一个新链表，其中包含 s 的所有元素，但不包含索引为 i的元素。（规定 s.first 是索引 0 处的元素。）

原链表 s 不应被改变。

Hint: 递归写法可能比迭代写法更容易。

def without(s: Link, i: int) -> Link:
    """Return a new linked list like s but without the element at index i.

    >>> s = Link(3, Link(5, Link(7, Link(9))))
    >>> without(s, 0)
    Link(5, Link(7, Link(9)))
    >>> without(s, 2)
    Link(3, Link(5, Link(9)))
    >>> without(s, 4)  # There is no index 4, so all of s is retained.
    Link(3, Link(5, Link(7, Link(9))))
    """
    "*** YOUR CODE HERE ***"

使用 Ok 测试你的代码：

python3 ok -q without

编写函数 duplicate_link ，它接收链表 s 和值 val。该函数会 改变 s ，使每个等于 val 的元素后面都紧跟一个额外的 val （即复制一份），并返回 None。注意不要陷入不断复制新副本的无限循环！

注意：要向链表插入一个节点，需要重新赋值那些 rest 实例的 Link 属性；这些实例的 val 为 first。可以画出某个 doctest 的盒指针图来帮助理解！

def duplicate_link(s: Link, val: int) -> None:
    """Mutates s so that each element equal to val is followed by another val.

    >>> x = Link(5, Link(4, Link(5)))
    >>> duplicate_link(x, 5)
    >>> x
    Link(5, Link(5, Link(4, Link(5, Link(5)))))
    >>> y = Link(2, Link(4, Link(6, Link(8))))
    >>> duplicate_link(y, 10)
    >>> y
    Link(2, Link(4, Link(6, Link(8))))
    >>> z = Link(1, Link(2, Link(2, Link(3))))
    >>> duplicate_link(z, 2) # ensures that back to back links with val are both duplicated
    >>> z
    Link(1, Link(2, Link(2, Link(2, Link(2, Link(3))))))
    """
    "*** YOUR CODE HERE ***"

使用 Ok 测试你的代码：

python3 ok -q duplicate_link

问题 4：切片

实现函数 slice_link ，对给定链表进行切片。它应当从索引 link. slice_link 开始切取 link ，并在索引 start 之前一个元素处结束 end，行为与普通 Python 列表切片相同。此外，它应返回一个新链表，不修改原链表。

def slice_link(link: Link, start: int, end: int) -> Link:
    """Slices a linked list from start to end (as with a normal Python list) and returns
    a linked list. You do NOT have to support negative indices.

    >>> link = Link(3, Link(1, Link(4, Link(1, Link(5, Link(9))))))
    >>> new = slice_link(link, 1, 4)
    >>> print(new)
    (1 4 1)
    >>> print(slice_link(link, 0, 2))
    (3 1)
    >>> print(slice_link(link, 0, 6))
    (3 1 4 1 5 9)
    >>> print(slice_link(link, 2, 2))
    ()
    >>> print(slice_link(link, 2, 3))
    (4)
    >>> print(slice_link(link, 3, 100))
    (1 5 9)
    >>> print(slice_link(link, 10, 12))
    ()
    """
    "*** YOUR CODE HERE ***"

使用 Ok 测试你的代码：

python3 ok -q slice_link

问题 5：环

其中 Link 类可以表示带环的链表，也就是说，一个链表可能把自身包含为子链表。

>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> s.rest.rest.rest.rest.rest.first
3

实现 has_cycle，判断传入的 Link 实例是否包含环。

提示：遍历链表，同时记录已经访问过哪些 Link 对象。

def has_cycle(link: Link) -> bool:
    """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 ***"

使用 Ok 测试你的代码：

python3 ok -q has_cycle

额外挑战（选做）：实现 has_cycle ，但不要记录所有已经访问过的 Link 对象。答案很短（少于 20 行代码），但需要一个巧妙的思路。向别人求助前，先试着自己发现这个方法。

def has_cycle_constant(link: Link) -> bool:
    """Return whether link contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle_constant(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle_constant(t)
    False
    """
    "*** YOUR CODE HERE ***"

使用 Ok 测试你的代码：

python3 ok -q has_cycle_constant

在本地检查得分

你可以运行以下命令，在本地检查本次作业每道题的得分：

python3 ok --score

这不会提交作业！ 确认得分符合预期后，请将作业提交到 Gradescope，以获得作业学分。

提交作业

请上传所有你修改过的文件，将本次作业提交到 对应的 Gradescope 作业入口。 实验 00 中提供了详细说明。

正确完成所有题目可得 1 分。 Please ensure your TA has taken your attendance before leaving.