笨鸟编程-零基础入门Pyhton教程 › 首页 ›Python2编程手册 › 查看内容

5.1. 关于列表更多的内容

5.1.1. 把链表当作堆栈使用

链表方法使得链表可以很方便的做为一个堆栈来使用，堆栈作为特定的数据结构，最先进入的元素最后一个被释放（后进先出）。用 append() 方法可以把一个元素添加到堆栈顶。用不指定索引的 pop() 方法可以把一个元素从堆栈顶释放出来。例如:

>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

5.1.2. 把链表当作队列使用

你也可以把链表当做队列使用，队列作为特定的数据结构，最先进入的元素最先释放（先进先出）。不过，列表这样用效率不高。相对来说从列表末尾添加和弹出很快；在头部插入和弹出很慢（因为，为了一个元素，要移动整个列表中的所有元素）。

要实现队列，使用 collections.deque ，它为在首尾两端快速插入和删除而设计。例如:

>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry")           # Terry arrives
>>> queue.append("Graham")          # Graham arrives
>>> queue.popleft()                 # The first to arrive now leaves
'Eric'
>>> queue.popleft()                 # The second to arrive now leaves
'John'
>>> queue                           # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])

5.1.3. 函数式编程工具

对于链表来讲，有三个内置函数非常有用: filter(), map(), 以及 reduce()。

filter(function, sequence) 返回一个 sequence（序列），包括了给定序列中所有调用 function(item) 后返回值为 true 的元素。（如果可能的话，会返回相同的类型）。如果该序列（sequence）是一个 string （字符串）或者 tuple （元组），返回值必定是同一类型，否则，它总是 list 。例如，以下程序可以计算部分素数:

>>> def f(x): return x % 2 != 0 and x % 3 != 0
...
>>> filter(f, range(2, 25))
[5, 7, 11, 13, 17, 19, 23]

map(function, sequence) 为每一个元素依次调用 function(item) 并将返回值组成一个链表返回。例如，以下程序计算立方:

>>> def cube(x): return x*x*x
...
>>> map(cube, range(1, 11))
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]

可以传入多个序列，函数也必须要有对应数量的参数，执行时会依次用各序列上对应的元素来调用函数（如果某些序列比其它的短，就用 None 来代替）。如果把 None 做为一个函数传入，则直接返回参数做为替代。例如:

>>> seq = range(8)
>>> def add(x, y): return x+y
...
>>> map(add, seq, seq)
[0, 2, 4, 6, 8, 10, 12, 14]

reduce(function, sequence) 返回一个单值，它是这样构造的：首先以序列的前两个元素调用函数 function，再以返回值和第三个参数调用，依次执行下去。例如，以下程序计算 1 到 10 的整数之和:

>>> def add(x,y): return x+y
...
>>> reduce(add, range(1, 11))
55

如果序列中只有一个元素，就返回它，如果序列是空的，就抛出一个异常。

可以传入第三个参数作为初始值。如果序列是空的，就返回初始值，否则函数会先接收初始值和序列的第一个元素，然后是返回值和下一个元素，依此类推。例如:

>>> def sum(seq):
...     def add(x,y): return x+y
...     return reduce(add, seq, 0)
...
>>> sum(range(1, 11))
55
>>> sum([])
0

不要像示例中这样定义 sum() ：因为合计数值是一个通用的需求，早已有内置的 sum(sequence) 函数，非常好用。

123 / 3 页下一页

上一篇：5. 数据结构下一篇：5.2. del 语句

		自动登录	找回密码
密码			立即注册

5.1. 关于列表更多的内容

5.1.1. 把链表当作堆栈使用

5.1.2. 把链表当作队列使用

5.1.3. 函数式编程工具

最新评论