Python Data Structures

  • 数据结构:
    • 列表、字典、元组、集合。

数据结构（Data Structures）基本上人如其名——它们只是一种结构，能够将一些数据聚合在一起。换句话说，它们是用来存储一系列相关数据的集合。

Python 中有四种内置的数据结构——列表（List）、元组（Tuple）、字典（Dictionary）和集合（Set）

列表(List):

List 数据类型包含更多的方法，下面是 List 对象包含的所有方法：

1
list.append(*x*)

将一个元素添加到列表的末端。相当于 a[len(a):] = [x]。

1
list.extend(*iterable*)

将一个 iterable 的对象中的所有元素添加到列表末端来拓展这个列表。相当于 a[len(a):] =iterable。

1
list.insert(*i*, *x*)

在列表中给定的位置插入一个元素。第一个是要插入的元素的位置。所以 a.insert(0, x) 将元素插入列表最前面，a.insert(len(a), x) 相当于 a.append(x)。

1
list.remove(*x*)

移除列表中第一个值为 x 的元素。如果没有找到这样的元素，抛出 ValueError。

1
list.pop([*1*])

移除并返回列表中给定位置的元素。如果没有指定索引，a.pop() 移除并返回列表的最后一个元素。（i 外的方括号表示这个参数是可选的，而不是要求你在这个位置输入方括号。你会经常在 Python Library Reference 中看到这种标记方式）。

1
list.clear()

移除列表中所有的元素。相当于 del a[:]。

1
list.index(*x*[, *start*[, *end*]])

返回值为 x 的元素在列表中的索引，索引从 0 开始。如果不存在这样的元素，抛出 ValueError。

可选参数 start 和 end 被解释为切片表示法，用于将搜索范围限制在该列表的一个子序列内。返回的索引是该元素在相对于原列表的开端的位置而不是相对于 start 参数的位置。

1
list.count(*x*)

返回列表中值为 x 的元素的数量。

1
list.sort(*key=None*, *reverse=False*)

对列表中的元素进行原地排序（参数可以被用于自定义排序，参见sorted()）

1
list.reverse()

原地翻转列表。

1
list.copy()

返回该列表的一个浅拷贝。相当于 a[:]。

Go! Let‘s We Play!动手练习:

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
classmate = ['tom',13,'boy','student'] #以一个列表形式
classmate #调用list
使用len函数调用list元素个数
len(classmate)
用索引列出位置元素 注意索引是从0开始的0-n
>>> classmates[0]
'Michael'
>>> classmates[1]
'Bob'
>>> classmates[2]
'Tracy'
>>> classmates[3]
当索引超出了范围时，Python会报一个IndexError错误，所以，要确保索引不要越界，记得最后一个元素的索引是len(classmates) - 1。
 如果要取最后一个元素，除了计算索引位置外，还可以用-1做索引，直接获取最后一个元素：
也可以把元素插入到指定的位置，比如索引号为1的位置：
>>> classmates.insert(1, 'Jack')
>>> classmates
['Michael', 'Jack', 'Bob', 'Tracy', 'Adam']
要删除list末尾的元素，用pop()方法：默认pop删除最后一个元素，使用pop(i)数字删除指定的索引位置
>>> classmates.pop()
'Adam'
>>> classmates
['Michael', 'Jack', 'Bob', 'Tracy']

要把某个元素替换成别的元素，可以直接赋值给对应的索引位置：
>>> classmates[1] = 'Sarah'
>>> classmates
['Michael', 'Sarah', 'Tracy']

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
>>> fruits = ['orange', 'apple', 'pear', 'banana', 'kiwi', 'apple', 'banana']
>>> fruits.count('apple')
2
>>> fruits.count('tangerine')
0
>>> fruits.index('banana')
3
>>> fruits.index('banana', 4)  # 从索引 4 开始找 banana
6
>>> fruits.reverse()
>>> fruits
['banana', 'apple', 'kiwi', 'banana', 'pear', 'apple', 'orange']
>>> fruits.append('grape')
>>> fruits
['banana', 'apple', 'kiwi', 'banana', 'pear', 'apple', 'orange', 'grape']
>>> fruits.sort()
>>> fruits
['apple', 'apple', 'banana', 'banana', 'grape', 'kiwi', 'orange', 'pear']
>>> fruits.pop()
'pear'

使用列表作为堆栈:

列表的方法使得可以把列表当成元素后进先出的堆栈来用。使用 append() 来把一个元素加到堆栈的顶部。使用不显示携带索引参数的 pop() 方法来把一个元素从堆栈顶部移除。比如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
>>> 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]

使用列表作为队列:

也可以使用列表作为队列，其中添加的第一个元素是检索的第一个元素（“先入，先出”）；然而，列表对于这一目的并不高效。虽然从列表末尾追加和弹出是高效的，但是从列表的开头开始插入或弹出就低效了（因为所有其他元素都必须移动一个位置）。

实现一个队列，使用 collections.deque 它被设计为从两端都具有快速追加和弹出的能力。例如：

1
2
3
4
5
6
7
8
9
10
>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry")           # Terry 进入
>>> queue.append("Graham")          # Graham 进入
>>> queue.popleft()                 # 现在弹出第一个进入的元素
'Eric'
>>> queue.popleft()                 # 现在弹出第二个进入的元素
'John'
>>> queue                           # 按进入顺序维护队列
deque(['Michael', 'Terry', 'Graham'])

列表表达式/列表解析:

列表推导式（又称列表解析式）提供了一种简明扼要的方法来创建列表。
它的结构是在一个中括号里包含一个表达式，然后是一个for语句，然后是0个或多个for或者if语句。那个表达式可以是任意的，意思是你可以在列表中放入任意类型的对象。返回结果将是一个新的列表，在这个以if和for语句为上下文的表达式运行完成之后产生。

例如，我们可以通过以下方式产生一组平方数。

1
2
3
4
5
6
>>> squares = []
>>> for x in range(10):
...     squares.append(x**2)
...
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

注意到在整个过程中，我们创建并修改了一个 x 变量，并且在循环完成之后依然存在。使用以下方式，我们同样可以生成这个序列，且没有额外的变量生成。

更优的写法，意思更明确，也更具可读性。等价形式:

1
squares = [x**2 for x in range(10)]

列表初始化表达式由方括号 [] 包含，括号内以 for 语句起始，后接任意个 for 语句或 if 语句。其结果是产生一个新的列表，列表内的元素为其中的 for 语句或 if 语句的执行结果。例如，以下表达式创建了一个列表，列表内的每个元素形如 (x, y)，其中 x 和 y 分别来自两个列表，且 x 与 y 不相等。

1
2
>>> [(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
4
5
6
7
8
>>> combs = []
>>> for x in [1,2,3]:
...     for y in [3,1,4]:
...         if x != y:
...             combs.append((x, y))
...
>>> combs
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

在这两段代码中，for 语句和 if 语句的执行顺序是相同的。

如果要使生成列表中的每个元素都是一个元组，则必须给表达式加上圆括号 () 。

Do More Practice:

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
>>> vec = [-4, -2, 0, 2, 4]
>>> # 创建一个新列表，将原列表中的每个元素乘以 2
>>> [x*2 for x in vec]
[-8, -4, 0, 4, 8]
>>> # 去除原列表中的负数
>>> [x for x in vec if x >= 0]
[0, 2, 4]
>>> # 对原列表中的每个元素调用函数
>>> [abs(x) for x in vec]
[4, 2, 0, 2, 4]
>>> # 调用每个元素的成员方法
>>> freshfruit = ['  banana', '  loganberry ', 'passion fruit  ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']
>>> # 创建一个由二元组构成的列表，元素形如 (number, square)
>>> [(x, x**2) for x in range(6)]
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]
>>> # 元组必须以圆括号包含，否则将产生一个错误
>>> [x, x**2 for x in range(6)]
  File "<stdin>", line 1, in <module>
    [x, x**2 for x in range(6)]
               ^
SyntaxError: invalid syntax
>>> # 用一个含有两个 `for` 的列表初始化表达式将一个多维列表降维
>>> vec = [[1,2,3], [4,5,6], [7,8,9]]
>>> [num for elem in vec for num in elem]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

del 语句

有一个方法可以根据索引而不是值从列表中删除一个元素： del 语句。 这和 pop() 方法不同，后者会返回一个值。 del 语句也可用于从列表中删除片段或清除整个列表 （之前我们通过将一个空列表赋值给这个片段来达到此目的）。

例如:

1
2
3
4
5
6
7
8
9
10
>>> a = [-1, 1, 66.25, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.25, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.25, 1234.5]
>>> del a[:]
>>> a
[]

del 也可用于删除整个变量：

1
>>> del a

字典(Dict):

字典是 Python 中另外一种常用的数据类型(参考 Mapping Types — dict).

字典就像一本地址簿，如果你知道了他或她的姓名，你就可以在这里找到其地址或是能够联系上对方的更多详细信息，换言之，我们将键值（Keys）（即姓名）与值（Values）（即地址等详细信息）联立到一起。在这里要注意到键值必须是唯一的，正如在现实中面对两个完全同名的人你没办法找出有关他们的正确信息。

另外要注意的是你只能使用不可变的对象（如字符串）作为字典的键值，但是你可以使用可变或不可变的对象作为字典中的值。基本上这段话也可以翻译为你只能使用简单对象作为键值。

在字典中，你可以通过使用符号构成 d = {key : value1 , key2 : value2} 这样的形式，来成对地指定键值与值。在这里要注意到成对的键值与值之间使用冒号分隔，而每一对键值与值则使用逗号进行区分，它们全都由一对花括号括起。

字典主要的操作符就是通过键来存储对应的数据，以及根据键来取出对应的数据。也可以通过 del 来删除一个键值对。如果在存储数据的时候使用了字典中已有的键，则该键对应的值会被更新为当前新赋给值。如果使用字典中不存在的键来获取值，则会产生 error ，提示不存在这样的键。

list(d) 操作会返回字典中所有键组成的列表，列表中的数据顺序按照这些键存入字典的顺序（如果想得到一个经过排序的键的列表，可以使用 sorted(d) ）。检查字典中是否有某个键，可以使用关键字 in 。

另外需要记住，字典中的成对的键值—值配对不会以任何方式进行排序。如果你希望为它们安排一个特别的次序，只能在使用它们之前自行进行排序。

你将要使用的字典是属于 dict 类下的实例或对象。

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'jack': 4098, 'sape': 4139, 'guido': 4127}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'jack': 4098, 'guido': 4127, 'irv': 4127}
>>> list(tel)
['jack', 'guido', 'irv']
>>> sorted(tel)
['guido', 'irv', 'jack']
>>> 'guido' in tel
True
>>> 'jack' not in tel
False

dict() 函数会直接通过一系列的 键值对产生一个字典：

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

另外，我们可以从任意的键和值得表达式来创建字典：

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

当键是字符串的时候，使用参数赋值的方式来指定键值对更方便：

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

遍历的技巧:

鉴于字典可能包含大量的数据，Python支持对字典的遍历。字典可用于以各种方式存储信息，因此有多种遍历字典的方式:可遍历字典的所有键-值对、键或值(key-value)。

遍历字典时，键和对应的值可以用 items() 方法一次性全部得到。

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

使用keys()方法可以遍历字典中的所有键

1
2
3
4
5
6
7
8
favorite_languages= {
	'jen': 'python',
	'sarah': 'c',
	'edward': 'ruby',
	'phil': 'python'
    }
for name in favorite_languages.keys():
	print(name.title())

使用values()方法可以遍历字典中的所有值

1
2
3
4
5
6
7
8
favorite_languages= {
	'jen': 'python',
	'sarah': 'c',
	'edward': 'ruby',
	'phil': 'python'
    }
for name in favorite_languages.values():
	print(name.title())

这种做法提取字典中的所有值，而没有考虑是否出现重复的问题。如果数据中含大量的重复项就需要使用集合(set)

1
2
for name in set(favorite_languages.values()):
	print(name.title())

遍历一个序列时，位置索引和对应的值可以用 enumerate() 方法一次性全部得到。

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

当需要同时遍历两个或多个序列时，可以使用 zip() 方法将他们合并在一起。

1
2
3
4
5
6
7
8
>>> 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.

当需要反过来遍历一个序列的时候，使用 reversed() 方法来将一个正的序列倒序。

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

需要按顺序遍历一个序列，可以把未排序的序列传到 sorted() 方法中来获得一个新的排好序的列表。

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

元组(tuple)

我们发现列表和字符串有许多共同点，例如可以用索引来访问，以及切割的操作。他们属于序列类型的公共特性。(参见 序列类型 — 列表，元组，区间)。Python 的日益发展，使得其他的序列类型会被逐渐地加入到语言特性中。其中就有另一种序列类型：元组。

列表非常适用于储存在程序运行期间可能变化的数据集。列表是可以修改的，这对处理网站的用户列表或游戏中的角色列表至关重要。然而，有时候你需要创建一系列不可修改的元素，元组可以满足这种需求。python将不能修改的值称为不可变的，而不可变的列表称为元组。元组通常用于保证某一语句或某一用户定义的函数可以安全地采用一组数值，意即元组内的数值不会改变。

元组由一系列被逗号分隔开的值组成，例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # 元组也可以嵌套：
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))
>>> # 元组不可被修改：
... t[0] = 88888
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>> # 但是可以包含可以被修改的对象：
... v = ([1, 2, 3], [3, 2, 1])
>>> v
([1, 2, 3], [3, 2, 1])

元组在输出时总是带有两侧的括号，这样一来，嵌套的元组可以被清楚地区分开；但是在输入时，并不一定要带上两侧的括号，尽管有时带上括号非常有必要（例如元组作为一个很长的表达式的一部分）。不能对元组中的项进行赋值，但在创建元组时，可以传入可修改的对象，例如列表。

虽然元组看起来和列表很像，但它们的使用场合和使用目的往往不同。元组是 不可修改的, 并且经常包含着不同类型的元素，总是通过解包（本章的后面会介绍）或索引（命名元组可以通过属性索引的方式）来访问。而列表是 可修改的，并且往往包含着同样类型的元素，通过遍历的方式来进行访问。

一个特别的问题是如何创建一个空的或只有一个元素的元组：语法上有一些小窍门。空的元组可以用一对空的括号来创建；只有一个元素的元组可以用一个后面跟着逗号的值来创建（只在括号里放一个元素可不行）。这些方法虽然有点丑陋，但挺好用的。例如：

1
2
3
4
5
6
7
8
>>> empty = ()
>>> singleton = 'hello',    # <-- 注意后面的逗号
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('hello',)

语句 t = 12345, 54321, 'hello!'是一个 元组解包的例子：元素 12345， 54321 和 'hello!' 一起组成了一个元组。下面这样的操作也同样可以做到：

1
>>> x, y, z = t

这被称为 序列解包 ，所有右值的序列都可以使用这种语法。序列解包要求在等号的左边有着和序列内元素数量相同的变量。到这里也许你也发现了，多重赋值就是利用元组和序列解包来实现的。

集合(set)

Python 内建集合的数据类型。一个集合是由多个无重复元素构成的无序整体。集合支持的基本功能包括成员检查以及重复元素的去除。集合同时支持求并集、交集、差集以及对称差集等操作。

集合可以通过大括号符号或者调用 set() 函数创建。注意：如果需要创建一个空的集合实例，需使用 set()而非 {} ，因为后者会创建一个空的字典实例。我们将在下一个章节介绍字典类型。

下面我们来看一个简单的示范代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # 可以看到重复的元素被去除
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket                 # 快速成员检查
True
>>> 'crabgrass' in basket
False

>>> # 由两个单词中独特的字母构成的集合进行的集合间操作
...
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a                                  # a 集合中独特的字母
{'a', 'r', 'b', 'c', 'd'}
>>> a - b                              # 在 a 中但是不在 b 中的字母
{'r', 'd', 'b'}
>>> a | b                              # 在 a 中或在 b 中的字母
{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}
>>> a & b                              # a 和 b 共有的字母
{'a', 'c'}
>>> a ^ b                              # 在 a 中或在 b 中但两者不共有的字母
{'r', 'd', 'b', 'm', 'z', 'l'}

Python支持类似于 递推式构造列表 的递推式构造集合：

1
2
3
>>> a = {x for x in 'abracadabra' if x not in 'abc'}
>>> a
{'r', 'd'}

判断条件进阶

被用在 while 和 if 语句中的判断条件不仅仅可以包含比较运算，还可以包含任何的运算符。

比较运算符 in 和 not in 能够检查某个值是否在一个序列里出现（或不出现）。比较运算符 is 和 is not 比较两个对象是否是同一个对象；这只会影响如列表之类可修改的对象。所有的比较运算符的优先级都相同，比所有的算术运算法的优先级都要低。

比较运算符可以采用连写的方式。例如， a < b == c 用来检查是否 a 小于 b 并且 b 等于 c 。

比较运算符可以用布尔运算符 and 和 or 进行组合，然后他们的结果（或者任何其他的布尔表达式）可以被 not 否定。这些布尔运算符的优先级又比比较运算符更低；而在他们之间， not 的优先级最高，而 or 的优先级最低，因此 A and not B or C 就等价于 (A and (not B)) or C。 当然，括号可以用来提升优先级。

布尔运算符 and 和 or 往往被称为 短路 运算符：它们的参数从左往右一个个被计算，而当最终结果已经能够确定时，就不再计算剩余的参数了。举个例子，如果 A 和 C 是真的，而 B 是假的，那么 A and B and C 不会计算表达式 C 的值。当不作为布尔值使用，而是作为普通的值来使用时，短路运算符的返回值将会是最后一个被计算的参数。

也可以把比较运算的结果或其他布尔表达式赋值给一个变量。例如，

1
2
3
4
>>> string1, string2, string3 = '', 'Trondheim', 'Hammer Dance'
>>> non_null = string1 or string2 or string3
>>> non_null
'Trondheim'

注意， Python 和 C 不同，赋值不能在表达式内部进行。 C 程序员们可能会抱怨这一点，但这种特性有效地防止了 C 程序中那种常见的错误发生：把 == 不小心写成了 = 。

序列及其他类型的比较

拥有相同序列类型的序列对象之间可以进行比较。序列间的比较基于
字典排序：首先比较两序列的首项，如果它们不同，那么比较就有了结果；如果它们相同，接下来的两项将继续进行比较，以此类推，直到两者中任何一个序列被遍历完毕。如果比较的项所在的序列是同样的类型，那么可以按照字典排序的方法递归进行下去。如果两序列所有的项比较过后都是相同的，则认为这两个序列相等。如果其中一个序列是另一个序列从头开始的一个子序列，那么更短的一个被认为更小。字符串的字典排序对于单个字符按照 Unicode 的编码大小进行排序。 一些同类型序列的比较示例如下：

1
2
3
4
5
6
7
(1, 2, 3)              < (1, 2, 4)
[1, 2, 3]              < [1, 2, 4]
'ABC' < 'C' < 'Pascal' < 'Python'
(1, 2, 3, 4)           < (1, 2, 4)
(1, 2)                 < (1, 2, -1)
(1, 2, 3)             == (1.0, 2.0, 3.0)
(1, 2, ('aa', 'ab'))   < (1, 2, ('abc', 'a'), 4)

需要注意，如果有适当的比较方法，对于不同类型对象间的比较使用 < 或者 > 也是合法的。例如，混合数字类型可以根据它们的数值大小进行比较，如 0 等于 0.0 ，以此类推。否则，Python解释器会抛出一个TypeError 的异常，而非给出一个随机的排序。

参考资料