Skip to content

链表

约 511 个字 127 行代码 1 张图片 预计阅读时间 3 分钟

每一个链表节点都有一个值和一个指向下一个节点的指针。链表的最后一个节点的指针指向一个特殊的值，如None。

在python中,最后一个叫Link empty,指向None.

我们判断链表到头的方法其实是Link_name==Link.list

第一个元素实际上是零元素,是一个attribute value.

Python
1
Link(1, Link(2, Link(3, Link.empty)))

这些结构在python中是通过类来实现的。

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Link:
    empty = ()
    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest
    class Link:
    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 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) + '>'

__str__和__repr__具体是打印输出链表的时候调用的方法.不影响链表的操作.

关于link.empty是什么,在实现上有选择的余地,可以是None,也可以是().

isinstance() 函数来判断一个对象是否是一个已知的类型，类似 type()。

Python
1
isinstance(object, classinfo)

返回 True 如果 object 是 classinfo 的实例，否则返回 False。

object -- 实例对象。

classinfo -- 可以是直接或间接类名、基本类型或者由它们组成的元组。

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
>>> Link(3,Link(4,Link(5)))
<__main__.Link object at 0x0000023C93E3DCA0>
>>> s = Link(3,Link(4,Link(5))) 
>>> s.first
3
>>> s.rest
<__main__.Link object at 0x0000023C93E3DF10>
>>> s.rest.first
4
>>> s.rest.rest 
<__main__.Link object at 0x0000023C93E3CC80>
>>> s.rest.rest.first
5
>>> s.rest.rest.rest 
()
>>> s.rest.rest.rest is Link.empty
True
>>>

也可以更改链表的值

Python
1
2
3
4
5
6
>>> s.first = 6
>>> s.first
6
>>> s.rest.first = 7
>>> s.rest.first
7
Python
1
2
3
4
5
6
7
8
9
>>> s = Link(1, Link(2, Link(3)))
>>> Link(0, s)
<__main__.Link object at 0x0000023C93E3DCA0>
>>> Link(0, s).first
0
>>> Link(0, s).rest
<__main__.Link object at 0x0000023C93E3DF10>
>>> Link(0, s).rest.first
1

链表的操作

递归在链表中很有用

Range函数,map函数,filter函数都是python内置的,但是不能操作用户定义的Link类.

我们需要自己定义这些函数.

例子

首先我们回顾一下我们之前定义过的square函数和odd函数

Python
1
2
square = lambda x: x * x
odd = lambda x: x % 2 == 1

odd函数返回一个布尔值,表示是否是奇数.

square函数返回一个数的平方.

Python
1
list(map(square, fliter(odd, range(6))))

这个表达式的意思是,对于range(5)中的每一个数,如果是奇数,就返回它的平方,否则返回None.

返回None的情况map函数会自动忽略.

Python
1
2
>>> list(map(square, filter(odd, range(6))))
[1, 9, 25]

我们可以自己写一个map_link,fliter_link,range_link函数,来操作链表.

Python
1
map_link(square, fliter_link(odd, range_link(6)))

我们一个一个写

Python
1
2
3
4
5
6
7
8
def range_link(start, end):
    """Return a Link list of 0, 1, 2, ..., n-1.
    >>> range_link(3,6)
    Link(3, Link(4, Link(5)))
    """
    if start >= end:
        return Link.empty
    return Link(start, range_link(start+1, end))

return Link(start, range_link(start+1, end))这一句是递归的关键.

调用了递归,并且做好了结尾的时候返回Link.empty的结束条件.

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def map_link(fn, s):
    """Return a Link that contains f(x) for each x in Link s.
    >>> s = range_link(3, 6)
    >>> s
    Link(3, Link(4, Link(5)))
    >>> map_link(lambda x: x*x, s)
    Link(9, Link(16, Link(25)))
    """
    if s is Link.empty:
        return Link.empty
    return Link(fn(s.first), map_link(fn, s.rest))
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def filter_link(fn, s):
    """Return a Link containing only elements of Link s for which fn returns True.
    >>> s = range_link(3, 6)
    >>> s
    Link(3, Link(4, Link(5)))
    >>> filter_link(lambda x: x % 2 == 1, s)
    Link(3, Link(5))
    """
    if s is Link.empty:
        return Link.empty
        #如果s是空的,直接返回空.
    fliter_rest = filter_link(fn, s.rest)
    #递归调用
    if fn(s.first):
        return Link(s.first, fliter_rest)
        #如果fn通过,把这个值加入Link,并且继续递归
    else:
        return fliter_rest
    #如果fn不通过,这个值跳过,直接返回剩下的部分继续递归

链表可变性

链表是可变的,我们可以改变链表的值,包括第一个元素和剩下的元素.

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
>>> s = Link(1, Link(2, Link(3)))
>>> s.first = 6
>>> s.first
6
>>> s.rest.first = 7
>>> s.rest.first
7
>>> s
Link(6, Link(7, Link(3)))
>>> s = s.rest.rest
>>> s.rest.rest.rest.rest.rest.first
7

注意,是s.rest.rest=s,而不是s=s.rest.rest

链表排序

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def add(s, v):
    """Add a value to an ordered s with no repeats,returning modified s."""
    assert s is 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:
        s.rest = add(s.rest, v)
    return s

Comments