5. 数据结构

这个章节将更详细地描述一些你已经了解的内容,并且添加了一些新的内容。

5.1. 深入列表对象

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

list.append(*x*)

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

list.extend(*iterable*)

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

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

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

list.remove(*x*)

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

list.pop([*i*])

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

list.clear()

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

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

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

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

list.count(*x*)

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

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

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

list.reverse()

原地翻转列表。

list.copy()

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

一个用到了列表大部分方法的例子:

>>> 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'

你可能注意到像 insertremove 或者 sort 这样的方法只是改动了列表但是没有打印出返回值,因为它们返回了默认的 None [1]。这是一个 Python 中所有可变数据结构的设计理念。

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 进入
>>> queue.append("Graham")          # Graham 进入
>>> queue.popleft()                 # 现在弹出第一个进入的元素
'Eric'
>>> queue.popleft()                 # 现在弹出第二个进入的元素
'John'
>>> queue                           # 按进入顺序维护队列
deque(['Michael', 'Terry', 'Graham'])

5.1.3. 列表初始化表达式

列表初始化表达式为创建列表提供了一个简单的方法。一个常见的应用就是对于一个序列,将其中的每个元素进行一些操作,产生新的列表,或者是从原序列按照一定条件创建出子列表。

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

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

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

squares = list(map(lambda x: x**2, range(10)))

或者使用如下等价形式:

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

上述两段代码,意思更明确,也更具可读性。

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

>>> [(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)]

这种写法等价于:

>>> 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 语句的执行顺序是相同的。

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

>>> 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]

列表初始化表达式可以包含复杂语句和嵌套的函数调用。

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

5.1.4. 嵌套列表

列表初始化时,里面的元素可以是任何类型的表达式,甚至可以是一个列表。

例如,下面的例子用 3 个长度为 4 的列表,表示了一个 3x4 的矩阵:

>>> 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]]

就如同我们在上一节看到的,嵌套的列表可以用  for 语句进行遍历,所以上面的例子就等价于:

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

再对这种写法做展开,就等同于:

>>> transposed = []
>>> for i in range(4):
...     # 下面3行实现了嵌套列表的遍历
...     transposed_row = []
...     for row in matrix:
...         transposed_row.append(row[i])
...     transposed.append(transposed_row)
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

事实上,有很多内置函数可以处理复杂的问题。例如 zip() 方法用来做这件事再适合不过了:

>>> list(zip(*matrix))
[(1, 5, 9), (2, 6, 10), (3, 7, 11), (4, 8, 12)]

参见 参数列表分拆 得到更多关于上面代码中 * 的细节。

5.2. del 语句

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

>>> 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 也可用于删除整个变量:

>>> del a

如果再次对变量 a 进行引用将引起错误 (至少在对变量 a 再次赋值前)。在后文中我们将发现 del 的其他用途。

5.3. 元组和序列

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

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

>>> 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])

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

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

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

>>> empty = ()
>>> singleton = 'hello',    # <-- 注意后面的逗号
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('hello',)

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

>>> x, y, z = t

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

5.4. 集合

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

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

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

>>> 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支持类似于 递推式构造列表 的递推式构造集合:

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

5.5. 字典

字典是 Python 中另外一种常用的数据类型(参考 Mapping Types --- dict). 其他编程语言中也会把字典叫做 “联合存储” 或者 “联合数组”。 字典这种数据类型与序列类数据结构不同的是通过 来进行索引, 可以是任何不可变类型,而序列类的数据类型通常使用数字进行索引。如果元组内只含有字符串,数字或者元组,那这个元组也可以作为键,但是如果元组内直接或间接的含有任何的可变类型的数据,则不可以作为键。一般不能使用列表来作为键,因为我们可以通过赋值,切片或者类似于 append()extend() 方法来修改其中的数据。

可以把字典当成 键:值 对的集合类理解,字典要求一个字典内的键是不能重复的。我们可以通过一对大括号 {} 来产生一个空的字典。可以通过在大括号内写多个键值对并以逗号分隔来初始化一个字典,同时字典也会以这样的形式输出其中的内容。

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

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

下面是一个使用字典数据类型的小例子:

>>> 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() 函数会直接通过一系列的 键值对产生一个字典:

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

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

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

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

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

5.6. 遍历的技巧

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

>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}
>>> for k, v in knights.items():
...     print(k, v)
...
gallahad the pure
robin the brave

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

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

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

>>> 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() 方法来将一个正的序列倒序。

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

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

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for f in sorted(set(basket)):
...     print(f)
...
apple
banana
orange
pear

有时需要在遍历的过程中修改列表,但这种时候创建一个新的列表会更方便也更安全。

>>> import math
>>> raw_data = [56.2, float('NaN'), 51.7, 55.3, 52.5, float('NaN'), 47.8]
>>> filtered_data = []
>>> for value in raw_data:
...     if not math.isnan(value):
...         filtered_data.append(value)
...
>>> filtered_data
[56.2, 51.7, 55.3, 52.5, 47.8]

5.7. 判断条件进阶

被用在 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 的值。当不作为布尔值使用,而是作为普通的值来使用时,短路运算符的返回值将会是最后一个被计算的参数。

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

>>> string1, string2, string3 = '', 'Trondheim', 'Hammer Dance'
>>> non_null = string1 or string2 or string3
>>> non_null
'Trondheim'

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

5.8. 序列及其他类型的比较

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

(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  的异常,而非给出一个随机的排序。

脚注

本文章首发在 LearnKu.com 网站上。
上一篇 下一篇
贡献者:1
讨论数量: 0
发起讨论 只看当前版本


暂无话题~