数据结构

Learn from python2.7 official documentation

5.1 List

A list of list object methods：

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
26
27
28
29
#在列表末尾添加一个项目
list.append(x)

#向列表末尾附加给定列表的所有项
list.extend(L)

#在列表给定列表的index位置插入新元素
list.insert(index, x)

#从列表中移除value=x的项，当不存在时error
#error信息：ValueError: list.remove(x): x not in list
list.remove(x)

#从列表删除给定index位置的元素并返回它
#如果没有给出index，将删除列表最后一个元素
list.pop([index])

#返回列表种第一个值为x的元素的索引，不存在时error
list.index(x)

#返回值为x的元素在列表中出现的次数
list.count(x)

#对列表元素进行排序，参数可用于自定义排序
#默认从小到大排序
list.sort(cmp=None, key=None, reverse=False)

#翻转列表元素顺序（无返回值）
list.reverse()

5.1.1 List作为stack栈

将列表尾部作为栈顶，使用方法：

1
2
list.append(x)
list.pop()

5.1.2 List作为Queue队列

由于在List的开头(index==0)插入或弹出元素十分低效，若要实现一个Queue，可使用collections.deque。deque结构被设计成可以快速地从两端插入或弹出元素。

1
2
3
4
5
6
7
8
9
10
#添加引用
from collections import deque

#构造方法
deque(["a","b","c"])

#队尾插入
deque.append(x)
#队首弹出
deque.popleft()

5.1.3 函数式编程Functional Programming工具

5.1.3.1 filter(function, sequence)

函数filter()返回sequence中使function返回值为true的元素组成的新List。

注意：sequence为str，unicode或者tuple时，filter()的返回值将会是同样的类型。

1
2
3
4
5
#使用filter返回能被3或5整除的数
def f(x):
    return x % 3 == 0 or x % 5 == 0
filter(f, range(2, 25))
>>> [3, 5, 6, 9, 10, 12, 15, 18, 20, 21, 24]

5.1.3.2 map(function, sequence)

函数map()为sequence中的每个元素item调用function(item)，返回由function(item)结果组成的List。

1
2
3
4
#使用map计算三次方
def cube(x): return x*x*x
map(cube, range(1, 11))
>>> [1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]

一个或多个sequence可以被作为参数传递，这取决于函数function参数列表中的参数数量。如果某个sequence的长度小于其他，相应项取None。

5.1.3.3 reduce(function, sequence [,starting value])

函数reduce()从sequence中选取前两项作为function的参数，之后每次用前一次function的返回值和sequence的下一项作为function的参数，如此迭代整个sequence，返回唯一的结果。

1
2
3
4
#使用reduce计算1-10的和
def add(x, y): return x+y
reduce(add, range(1, 11))
>>> 55

注意：当sequence只有一个元素时，直接返回其值；当sequence为空时，将会引发异常（TypeError: reduce() of empty sequence with no initial value）。

避免sequence=[]时出现异常的做法，是使用reduce()的第三个参数作为starting value，第一次迭代将使用次参数和sequence的第一个值。

使用第三个参数的例子：

1
2
3
4
5
6
7
def sum(seq):
	def add(x,y): return x+y
	return reduce(add, seq, 0)
>>> sum(range(1, 11))
55
>>> sum([])  #此处如果调用reduce方法没使用第三个参数0，将会抛出异常
0

注意：sum(sequence)已作为python的内置函数提供，功能相同。

5.1.4 列表推导式List Comprehensions

列表推导式提供了更简单的创建列表的方法。

语法：[表达式 for子句 零个或多个for子句或if子句]

1
2
3
4
5
6
7
#创建一个平方列表
squares = [x**2 for x in range(10)]
>>> [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

#返回两个序列中不重复元素的组合
[(x, y) for x in [1,2,3] for y in [3,1,4] if x != y]
>>> [(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

应用复杂的表达式和嵌套函数：

1
2
3
from math import pi
[str(round(pi, i)) for i in range(1, 6)]
>>> ['3.1', '3.14', '3.142', '3.1416', '3.14159']

列表推导式的嵌套：

1
2
3
4
5
6
7
matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
]
[[row[i] for row in matrix] for i in range(4)]
>>> [[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

注意：zip([iterable, ...])已作为python的内置函数提供，功能相同。

5.2 del语句

del语句可用于从给定index的列表中删除项item，还可用于从列表中删除切片slices或清除整个列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#删除index==0的item
del lst[0]

#删除2<=index<4的slices
del lst[2:4]

#清空整个列表lst
del lst[:]
>>> lst == []

#清除整个列表lst
del lst
#此后再次引用lst将报错
>>> NameError: name 'lst' is not defined

5.3 元组Tuple和序列Sequence

Tuple和Sequence是两种标准序列类型（standard sequence data type）。

之前介绍的List和Str是属于Sequence数据类型中的两种，所以列表和字符串之间有很多共同特性。

这里介绍元组Tuple，一个元组由几个被逗号隔开的值组成：

1
2
3
4
5
t = 12345, 54321, 'hello!'
print t
>>> (12345, 54321, 'hello!')
print t[0]
>>> 12345

元组可以是嵌套的（nested）：

1
2
3
u = t, (1, 2, 3, 4, 5)
print u
>>> ((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))

元组本身的元素一旦创建将是不可改变的（immutable），给元组中的一个单独的元素赋值将引发异常：

1
2
t[0] = 88888
>>> TypeError: 'tuple' object does not support item assignment

但，元组可以包含可改变的（mutable）对象：

1
2
3
4
v = ([1, 2, 3], [3, 2, 1])
v[0][0] = 0
print v
>>> ([0, 2, 3], [3, 2, 1])

构造包含0个或1个元素的元组：

1
2
3
4
5
#构造空元组
empty = ()

#构造含有一个元素的元组
singleton = 'hello',

之前使用语句t = 12345, 54321, 'hello!'构造元组的例子被称为元组打包（tuple packing），对应的，其逆操作被称为元组解包（sequence unpacking），下面是元组解包的例子：

1
2
3
4
t = 12345, 54321, 'hello!'
x, y, z = t
print x,y,z
>>> 12345 54321 hello!

注意：解包时需要左侧的变量列表具有与序列长度相同的元素数量，否则将引发异常（ValueError: too many values to unpack或ValueError: need more than [num] values to unpack）。

5.4 集合Set

集合Set类型是由不重复元素组成的无序的集，基本用法包括成员查找和消除重复元素。

集合对象也支持并集（union），交集（intersection），差集（difference）和对称差分（symmetric difference）等数学运算。

构造集合可以使用set()函数或花括号，集合在创建时会自动清除重复元素：

1
2
3
4
5
6
7
8
9
10
#使用set()函数
basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
fruit = set(basket)
print fruit
>>> set(['orange', 'pear', 'apple', 'banana'])

#使用花括号
bsk = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
print bsk
>>> set(['orange', 'pear', 'apple', 'banana'])

注意：创建空集合只能使用set()函数

集合提供快速的成员检索：

1
2
3
4
print 'orange' in fruit
>>> True
print 'crabgrass' in fruit
>>> False

集合之间的运算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
a = set('abracadabra')
b = set('alacazam')
print a
>>>set(['a', 'r', 'b', 'c', 'd'])
print b
>>>set(['a', 'c', 'z', 'm', 'l'])

#并集：|
print a | b
>>> set(['a', 'c', 'b', 'd', 'm', 'l', 'r', 'z'])

#交集：&
print a & b
>>> set(['a', 'c'])

#差集：-
print a - b
>>> set(['r', 'b', 'd'])

#对称差分
print a ^ b
>>> set(['b', 'd', 'm', 'l', 'r', 'z'])

类似于列表推导式，集合也支持集合推导式set comprehensions：

1
2
3
a = {x for x in 'abracadabra' if x not in 'abc'}
print a
>>> set(['r', 'd'])

5.5 字典Dictionary

数据类型字典Dictionary以关键字keys为索引，关键字可以是任意不可变类型（immutable type），通常是字符串string或数字number。

如果一个元组只包含字符串、数字或元组，那么这个元组也可以作为关键字。但如果元组直接或间接包含了其他可变对象，那么它就不能用作关键字。

列表不能用作关键字。

构造字典可以使用花括号包含用逗号分隔的键值对（key: value pairs）：

1
2
3
tel = {'jack': 4098, 'sape': 4139}
print tel
>>> {'sape': 4139, 'jack': 4098}

使用新的关键字并赋值，会为字典添加新的键值对；

使用已存在的关键字进行赋值，会修改字典中已存在的键值对：

1
2
3
4
5
6
7
tel['guido'] = 4127
print tel
>>> {'sape': 4139, 'jack': 4098, 'guido': 4127}

tel['sape'] = 6666
print tel
>>> {'sape': 6666, 'jack': 4098, 'guido': 4127}

keys()方法返回字典中所有关键字组成的列表；

del()方法删除字典中已存在的键值对：

1
2
3
4
5
print tel.keys()
>>> ['sape', 'jack', 'guido']
del tel['sape']
print tel
>>> {'jack': 4098, 'guido': 4127}

使用in来判断某个关键字是否存在于字典中：

1
2
3
4
print 'guido' in tel
>>> True
print 'boys' in tel
>>> False

dict()构造函数可以直接使用键值对Sequence来创建字典：

1
2
3
telp = dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
print telp
>>> 'sape': 4139, 'jack': 4098, 'guido': 4127}

字典同样支持字典推导式（dictionary comprehensions）：

1
2
print {x: x**2 for x in (2, 4, 6)}
>>> {2: 4, 4: 16, 6: 36}

当关键字是简单字符串（simple strings）时，可以使用关键字参数来指定键值对，有时这将更加方便：

1
2
print dict(sape=4139, guido=4127, jack=4098)
>>> {'sape': 4139, 'jack': 4098, 'guido': 4127}

5.6 循环的技巧

当在Sequence中循环时，可以使用enumerate()函数将index和value同时取出：

1
2
3
4
5
for i, v in enumerate(['tic', 'tac', 'toe']):
    print i, v
>>> 0 tic
>>> 1 tac
>>> 2 toe

当同时在两个或更多Sequence中循环时，可以用zip()函数将其内元素一一匹配：

1
2
3
4
5
6
7
questions = ['name', 'quest', 'favorite color']
answers = ['lancelot', 'the holy grail', 'blue']
for q, a in zip(questions, answers):
    print 'What is your {0}?  It is {1}.'.format(q, a)
>>> What is your name?  It is lancelot.
>>> What is your quest?  It is the holy grail.
>>> What is your favorite color?  It is blue.

如果要逆向循环一个Sequence，可以先正向定位它，然后调用reversed() 函数：

1
2
3
4
5
6
7
for i in reversed(xrange(1, 10, 2)):
    print i
>>> 9
>>> 7
>>> 5
>>> 3
>>> 1

如果要按某个指定顺序循环一个Sequence，可以用 sorted()函数，它可以在不改动原序列的基础上返回一个排好序的新序列：

1
2
3
4
5
6
7
basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
for f in sorted(set(basket)):
    print f
>>> apple
>>> banana
>>> orange
>>> pear

当在检索Dictionary时，可以使用iteritems()函数同时获取key和value：

1
2
3
4
5
knights = {'gallahad': 'the pure', 'robin': 'the brave'}
for k, v in knights.iteritems():
    print k, v
>>> gallahad the pure
>>> robin the brave

5.7 深入条件控制

5.7.1 优先级

由高到低：数值运算符 –> 比较操作符 –> 布尔运算符

布尔运算符中优先级由高到低：not –> and –> or

5.7.2 短路运算符（short-circuit operators）

布尔运算符中的and 和or也被称为短路运算符，它们的参数从左至右解析，一旦可以确定结果，解析停止。

5.7.3 其他

while 和 if 条件句中可以使用任意操作，而不仅仅是比较操作。

比较操作符 in 和 not in 校验一个值是否在（或不在）一个序列里。

操作符 is 和 is not 比较两个对象是不是同一个对象，这只跟像列表这样的可变对象有关。

Python中，赋值操作不能发生在表达式内部。

5.8 比较序列和其他类型

序列对象（Sequence objects）可以与具有相同序列类型的其他对象进行比较。

比较使用lexicographical ordering：首先比较前两个item，如果它们不同，则决定比较的结果；如果它们相等，则比较后面的两个item，以此类推，直到其中一个序列遍历完成。

如果要比较的两个item本身是同一类型的序列，则递归地进行lexicographical comparison比较。

注意：比较不同类型的对象是合法的。结果是确定的，但是是任意的，类型按它们的名称排序。因此，一个列表总是小于一个字符串，一个字符串总是小于一个元组，等等。