Composition

Linked List

用Python实现链表 - 每个节点由first与rest组成，前者表示值，后者表示链接的剩余链表 - 将每个节点当作一堆二元组看待 - 最后一个节点指向空链表Link.empty，使用类属性表示 - 构造方式：Link(3, Link(4, Link(5, Link.empty))) ### 创建链表

class Link:
    # 使用空元组实现空节点，类属性
    empty = ()
    def __init__(self, first, rest=empty):
        # 判断rest是否是空节点或是一个Link类
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest


s = Link(3, Link(4, Link(5)))
print(s.first)
print(s.rest.first)
print(s.rest.rest.first)
print(s.rest.rest.rest is Link.empty)

操作列表

实现如下行为：range, map, filter 我们使用递归实现

class Link:
    # 使用空元组实现空节点，类属性
    empty = ()
    def __init__(self, first, rest=empty):
        # 判断rest是否是空节点或是一个Link类
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest
def range_link(start, end):
    if start>=end:
        return Link.empty
    else:
        return Link(start, range_link(start+1, end))

def map_link(f, s):
    if s is Link.empty:
        return s
    else:
        return Link(f(s.first), map_link(f, s.rest))

def filter_link(f, s):
    if s is Link.empty:
        return s
    filter_rest = filter(f, s.rest)
    if f(s.first):
        return Link(s.first, filter_rest)
    else:
        return filter_rest

链表的改变

可以通过对属性赋值来改变链表的first和rest属性

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

此赋值将s的后段与前段相接，创建了一个循环链表

插入节点

向一个有序链表中添加节点，保证链表仍有序

def add(s, v):
    assert s is not Link.empty
    if s.first > v:
        s.first, s.rest = v, Link(s.first, s.rest)
    elif s.first < v and s.rest is Link.empty:
        s.rest = Link(v)
    elif s.first < v:
        add(s.rest, v)
    return s

Tree Class

使用类实现树 ### 创建树

class Tree:
    def __init__(self, label, branches = []):
        self.label = label
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = list(branches)
    def __repr__(self):
        if self.branches:
            branches_str = ', '+ repr(self.branches)
        else:
            branch_str = ''
        return 'Tree({0}{1})'.format(repr(self.label), branch_str)
    def __str__(self):
        return '\n'.join(self.indented())

    def indented(self):
        lines = []
        for b in self.branches:
            for line in b.indented():
                lines.append('    '+line)
        return [str(self.label)] + lines
    def is_leaf(self):
        return not self.branches

实现一些操作

如下代码实现了创建斐波那契树以及输出叶子节点

def fib_tree(n):
    if n==0 or n==1:
        return Tree(n)
    else:
        left = fib_tree(n-2)
        right = fib_tree(n-1)
        fib_n = left.label + right.label
        return Tree(fib_n, [left, right])

def leaves(t):
    if t.is_leaf():
        return [t.label]
    else:
        all_leaves = []
        for b in t.branches:
            all_leaves.extend(leaves(b))
        return all_leaves

剪枝

# 通过每次重新构建branches列表，将等于n的值排除在列表外以实现
def prune(t, n):
    t.branches = [b for b in t.branches if b.label!=n]
    for b in t.branches:
        prune(b, n)

红魔咖啡馆

【CS61A】CS61A——Composition