5. 數據結構?

本章深入講解之前學(xué)過(guò)的一些內容,同時(shí),還增加了新的知識點(diǎn)。

5.1. 列表詳解?

列表數據類(lèi)型支持很多方法,列表對象的所有方法所示如下:

list.append(x)

在列表末尾添加一個(gè)元素,相當于 a[len(a):] = [x] 。

list.extend(iterable)

用可迭代對象的元素擴展列表。相當于 a[len(a):] = iterable 。

list.insert(i, x)

在指定位置插入元素。第一個(gè)參數是插入元素的索引,因此,a.insert(0, x) 在列表開(kāi)頭插入元素, a.insert(len(a), x) 等同于 a.append(x) 。

list.remove(x)

從列表中刪除第一個(gè)值為 x 的元素。未找到指定元素時(shí),觸發(fā) ValueError 異常。

list.pop([i])

刪除列表中指定位置的元素,并返回被刪除的元素。未指定位置時(shí),a.pop() 刪除并返回列表的最后一個(gè)元素。(方法簽名中 i 兩邊的方括號表示該參數是可選的,不是要求輸入方括號。這種表示法常見(jiàn)于 Python 參考庫)。

list.clear()

刪除列表里的所有元素,相當于 del a[:] 。

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

返回列表中第一個(gè)值為 x 的元素的零基索引。未找到指定元素時(shí),觸發(fā) ValueError 異常。

可選參數 startend 是切片符號,用于將搜索限制為列表的特定子序列。返回的索引是相對于整個(gè)序列的開(kāi)始計算的,而不是 start 參數。

list.count(x)

返回列表中元素 x 出現的次數。

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

就地排序列表中的元素(要了解自定義排序參數,詳見(jiàn) 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)  # Find next banana starting a position 4
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'

insert、remove、sort 等方法只修改列表,不輸出返回值——返回的默認值為 None 。1 這是所有 Python 可變數據結構的設計原則。

還有,不是所有數據都可以排序或比較。例如,[None, 'hello', 10] 就不可排序,因為整數不能與字符串對比,而 None 不能與其他類(lèi)型對比。有些類(lèi)型根本就沒(méi)有定義順序關(guān)系,例如,3+4j < 5+7j 這種對比操作就是無(wú)效的。

5.1.1. 用列表實(shí)現堆棧?

使用列表方法實(shí)現堆棧非常容易,最后插入的最先取出(“后進(jìn)先出”)。把元素添加到堆棧的頂端,使用 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. 用列表實(shí)現隊列?

列表也可以用作隊列,最先加入的元素,最先取出(“先進(jìn)先出”);然而,列表作為隊列的效率很低。因為,在列表末尾添加和刪除元素非???,但在列表開(kāi)頭插入或移除元素卻很慢(因為所有其他元素都必須移動(dòng)一位)。

實(shí)現隊列最好用 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. 列表推導式?

列表推導式創(chuàng )建列表的方式更簡(jiǎn)潔。常見(jiàn)的用法為,對序列或可迭代對象中的每個(gè)元素應用某種操作,用生成的結果創(chuàng )建新的列表;或用滿(mǎn)足特定條件的元素創(chuàng )建子序列。

例如,創(chuàng )建平方值的列表:

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

注意,這段代碼創(chuàng )建(或覆蓋)變量 x,該變量在循環(huán)結束后仍然存在。下述方法可以無(wú)副作用地計算平方列表:

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

或等價(jià)于:

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

上面這種寫(xiě)法更簡(jiǎn)潔、易讀。

列表推導式的方括號內包含以下內容:一個(gè)表達式,后面為一個(gè) for 子句,然后,是零個(gè)或多個(gè) forif 子句。結果是由表達式依據 forif 子句求值計算而得出一個(gè)新列表。 舉例來(lái)說(shuō),以下列表推導式將兩個(gè)列表中不相等的元素組合起來(lái):

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

等價(jià)于:

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

注意,上面兩段代碼中,forif 的順序相同。

表達式是元組(例如上例的 (x, y))時(shí),必須加上括號:

>>>
>>> vec = [-4, -2, 0, 2, 4]
>>> # create a new list with the values doubled
>>> [x*2 for x in vec]
[-8, -4, 0, 4, 8]
>>> # filter the list to exclude negative numbers
>>> [x for x in vec if x >= 0]
[0, 2, 4]
>>> # apply a function to all the elements
>>> [abs(x) for x in vec]
[4, 2, 0, 2, 4]
>>> # call a method on each element
>>> freshfruit = ['  banana', '  loganberry ', 'passion fruit  ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']
>>> # create a list of 2-tuples like (number, square)
>>> [(x, x**2) for x in range(6)]
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]
>>> # the tuple must be parenthesized, otherwise an error is raised
>>> [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
>>> # flatten a list using a listcomp with two '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. 嵌套的列表推導式?

列表推導式中的初始表達式可以是任何表達式,甚至可以是另一個(gè)列表推導式。

下面這個(gè) 3x4 矩陣,由 3 個(gè)長(cháng)度為 4 的列表組成:

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

As we saw in the previous section, the inner list comprehension is evaluated in the context of the for that follows it, so this example is equivalent to:

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

反過(guò)來(lái)說(shuō),也等價(jià)于:

>>>
>>> transposed = []
>>> for i in range(4):
...     # the following 3 lines implement the nested listcomp
...     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]]

實(shí)際應用中,最好用內置函數替代復雜的流程語(yǔ)句。此時(shí),zip() 函數更好用:

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

關(guān)于本行中星號的詳細說(shuō)明,參見(jiàn) 解包實(shí)參列表。

5.2. del 語(yǔ)句?

del 語(yǔ)句按索引,而不是值從列表中移除元素。與返回值的 pop() 方法不同, del 語(yǔ)句也可以從列表中移除切片,或清空整個(gè)列表(之前是將空列表賦值給切片)。 例如:

>>>
>>> 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 也可以用來(lái)刪除整個(gè)變量:

>>>
>>> del a

此后,再引用 a 就會(huì )報錯(直到為它賦與另一個(gè)值)。后文會(huì )介紹 del 的其他用法。

5.3. 元組和序列?

列表和字符串有很多共性,例如,索引和切片操作。這兩種數據類(lèi)型是 序列 (參見(jiàn) 序列類(lèi)型 --- list, tuple, range)。隨著(zhù) Python 語(yǔ)言的發(fā)展,其他的序列類(lèi)型也被加入其中。本節介紹另一種標準序列類(lèi)型:元組。

元組由多個(gè)用逗號隔開(kāi)的值組成,例如:

>>>
>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Tuples may be nested:
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))
>>> # Tuples are immutable:
... t[0] = 88888
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>> # but they can contain mutable objects:
... v = ([1, 2, 3], [3, 2, 1])
>>> v
([1, 2, 3], [3, 2, 1])

輸出時(shí),元組都要由圓括號標注,這樣才能正確地解釋嵌套元組。輸入時(shí),圓括號可有可無(wú),不過(guò)經(jīng)常是必須的(如果元組是更大的表達式的一部分)。不允許為元組中的單個(gè)元素賦值,當然,可以創(chuàng )建含列表等可變對象的元組。

雖然,元組與列表很像,但使用場(chǎng)景不同,用途也不同。元組是 immutable (不可變的),一般可包含異質(zhì)元素序列,通過(guò)解包(見(jiàn)本節下文)或索引訪(fǎng)問(wèn)(如果是 namedtuples,可以屬性訪(fǎng)問(wèn))。列表是 mutable (可變的),列表元素一般為同質(zhì)類(lèi)型,可迭代訪(fǎng)問(wèn)。

構造 0 個(gè)或 1 個(gè)元素的元組比較特殊:為了適應這種情況,對句法有一些額外的改變。用一對空圓括號就可以創(chuàng )建空元組;只有一個(gè)元素的元組可以通過(guò)在這個(gè)元素后添加逗號來(lái)構建(圓括號里只有一個(gè)值的話(huà)不夠明確)。丑陋,但是有效。例如:

>>>
>>> empty = ()
>>> singleton = 'hello',    # <-- note trailing comma
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('hello',)

語(yǔ)句 t = 12345, 54321, 'hello!'元組打包 的例子:值 12345, 54321'hello!' 一起被打包進(jìn)元組。逆操作也可以:

>>>
>>> x, y, z = t

稱(chēng)之為 序列解包 也是妥妥的,適用于右側的任何序列。序列解包時(shí),左側變量與右側序列元素的數量應相等。注意,多重賦值其實(shí)只是元組打包和序列解包的組合。

5.4. 集合?

Python 還支持 集合 這種數據類(lèi)型。集合是由不重復元素組成的無(wú)序容器?;居梅òǔ蓡T檢測、消除重復元素。集合對象支持合集、交集、差集、對稱(chēng)差分等數學(xué)運算。

創(chuàng )建集合用花括號或 set() 函數。注意,創(chuàng )建空集合只能用 set(),不能用 {},{} 創(chuàng )建的是空字典,下一小節介紹數據結構:字典。

以下是一些簡(jiǎn)單的示例

>>>
>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # show that duplicates have been removed
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket                 # fast membership testing
True
>>> 'crabgrass' in basket
False

>>> # Demonstrate set operations on unique letters from two words
...
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a                                  # unique letters in a
{'a', 'r', 'b', 'c', 'd'}
>>> a - b                              # letters in a but not in b
{'r', 'd', 'b'}
>>> a | b                              # letters in a or b or both
{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}
>>> a & b                              # letters in both a and b
{'a', 'c'}
>>> a ^ b                              # letters in a or b but not both
{'r', 'd', 'b', 'm', 'z', 'l'}

列表推導式 類(lèi)似,集合也支持推導式:

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

5.5. 字典?

字典 (參見(jiàn) 映射類(lèi)型 --- dict) 也是一種常用的 Python 內置數據類(lèi)型。其他語(yǔ)言可能把字典稱(chēng)為 聯(lián)合內存聯(lián)合數組。與以連續整數為索引的序列不同,字典以 關(guān)鍵字 為索引,關(guān)鍵字通常是字符串或數字,也可以是其他任意不可變類(lèi)型。只包含字符串、數字、元組的元組,也可以用作關(guān)鍵字。但如果元組直接或間接地包含了可變對象,就不能用作關(guān)鍵字。列表不能當關(guān)鍵字,因為列表可以用索引、切片、append() 、extend() 等方法修改。

可以把字典理解為 鍵值對 的集合,但字典的鍵必須是唯一的?;ɡㄌ?{} 用于創(chuàng )建空字典。另一種初始化字典的方式是,在花括號里輸入逗號分隔的鍵值對,這也是字典的輸出方式。

字典的主要用途是通過(guò)關(guān)鍵字存儲、提取值。用 del 可以刪除鍵值對。用已存在的關(guān)鍵字存儲值,與該關(guān)鍵字關(guān)聯(lián)的舊值會(huì )被取代。通過(guò)不存在的鍵提取值,則會(huì )報錯。

對字典執行 list(d) 操作,返回該字典中所有鍵的列表,按插入次序排列(如需排序,請使用 sorted(d))。檢查字典里是否存在某個(gè)鍵,使用關(guān)鍵字 in。

以下是一些字典的簡(jiǎn)單示例:

>>>
>>> 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() 構造函數可以直接用鍵值對序列創(chuàng )建字典:

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

字典推導式可以用任意鍵值表達式創(chuàng )建字典:

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

關(guān)鍵字是比較簡(jiǎn)單的字符串時(shí),直接用關(guān)鍵字參數指定鍵值對更便捷:

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

5.6. 循環(huán)的技巧?

在字典中循環(huán)時(shí),用 items() 方法可同時(shí)取出鍵和對應的值:

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

在序列中循環(huán)時(shí),用 enumerate() 函數可以同時(shí)取出位置索引和對應的值:

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

同時(shí)循環(huán)兩個(gè)或多個(gè)序列時(shí),用 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.

逆向循環(huán)序列時(shí),先正向定位序列,然后調用 reversed() 函數:

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

按指定順序循環(huán)序列,可以用 sorted() 函數,在不改動(dòng)原序列的基礎上,返回一個(gè)重新的序列:

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

使用 set() 去除序列中的重復元素。使用 sorted()set() 則按排序后的順序,循環(huán)遍歷序列中的唯一元素:

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

一般來(lái)說(shuō),在循環(huán)中修改列表的內容時(shí),創(chuàng )建新列表比較簡(jiǎn)單,且安全:

>>>
>>> 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. 深入條件控制?

whileif 條件句不只可以進(jìn)行比較,還可以使用任意運算符。

The comparison operators in and not in are membership tests that determine whether a value is in (or not in) a container. The operators is and is not compare whether two objects are really the same object. All comparison operators have the same priority, which is lower than that of all numerical operators.

比較操作支持鏈式操作。例如,a < b == c 校驗 a 是否小于 b,且 b 是否等于 c。

比較操作可以用布爾運算符 andor 組合,并且,比較操作(或其他布爾運算)的結果都可以用 not 取反。這些操作符的優(yōu)先級低于比較操作符;not 的優(yōu)先級最高, or 的優(yōu)先級最低,因此,A and not B or C 等價(jià)于 (A and (not B)) or C。與其他運算符操作一樣,此處也可以用圓括號表示想要的組合。

布爾運算符 andor 也稱(chēng)為 短路 運算符:其參數從左至右解析,一旦可以確定結果,解析就會(huì )停止。例如,如果 AC 為真,B 為假,那么 A and B and C 不會(huì )解析 C。用作普通值而不是布爾值時(shí),短路操作符返回的值通常是最后一個(gè)變量。

還可以把比較操作或邏輯表達式的結果賦值給變量,例如:

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

注意,Python 與 C 不同,在表達式內部賦值必須顯式使用 海象運算符 :=。 這避免了 C 程序中常見(jiàn)的問(wèn)題:要在表達式中寫(xiě) == 時(shí),卻寫(xiě)成了 =。

5.8. 序列和其他類(lèi)型的比較?

序列對象可以與相同序列類(lèi)型的其他對象比較。這種比較使用 字典式 順序:首先,比較前兩個(gè)對應元素,如果不相等,則可確定比較結果;如果相等,則比較之后的兩個(gè)元素,以此類(lèi)推,直到其中一個(gè)序列結束。如果要比較的兩個(gè)元素本身是相同類(lèi)型的序列,則遞歸地執行字典式順序比較。如果兩個(gè)序列中所有的對應元素都相等,則兩個(gè)序列相等。如果一個(gè)序列是另一個(gè)的初始子序列,則較短的序列可被視為較?。ㄝ^少)的序列。 對于字符串來(lái)說(shuō),字典式順序使用 Unicode 碼位序號排序單個(gè)字符。下面列出了一些比較相同類(lèi)型序列的例子:

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

注意,對不同類(lèi)型的對象來(lái)說(shuō),只要待比較的對象提供了合適的比較方法,就可以使用 <> 進(jìn)行比較。例如,混合數值類(lèi)型通過(guò)數值進(jìn)行比較,所以,0 等于 0.0,等等。否則,解釋器不會(huì )隨便給出一個(gè)對比結果,而是觸發(fā) TypeError 異常。

備注

1

別的語(yǔ)言可能會(huì )返回可變對象,允許方法連續執行,例如,d->insert("a")->remove("b")->sort();。