5. 資料結構

這個章節將會更深入的介紹一些你已經學過的東西的細節上，並且加入一些你還沒有接觸過的部分。

5.1. 進一步了解 List（串列）

List（串列）這個資料型態，具有更多操作的方法。下面條列了所有關於 list 的物件方法：

list.append(x)

將一個新的項目加到 list 的尾端。等同於 a[len(a):] = [x]。

list.extend(iterable)

將 iterable（可列舉物件）接到 list 的尾端。等同於 a[len(a):] = iterable。

list.insert(i, x)

將一個項目插入至 list 中給定的位置。第一個引數為插入處前元素的索引值，所以 a.insert(0, x) 會插入為 list 首位，而 a.insert(len(a), x) 則相當於 a.append(x)。

list.remove(x)

Remove the first item from the list whose value is x. It is an error if there is no such item.

list.pop([i])

移除 list 中給定位置的項目，並回傳它。如果沒有指定位置， a.pop() 將會移除 list 中最後的項目並回傳它。（在 i 周圍的方括號代表這個參數是選用的，並不代表你應該在該位置輸入方括號。你將會常常在 Python 函式庫參考指南中看見這個表示法）

list.clear()

刪除 list 中所有項目。這等同於 del a[:] 。

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

Return zero-based index in the list of the first item whose value is x. Raises a ValueError if there is no such item.

引數 start 和 end 的定義跟在 slice 表示法中相同，搜尋的動作被這兩個引數限定在 list 中特定的子序列。但要注意的是，回傳的索引值是從 list 的開頭開始算，而不是從 start 開始算。

list.count(x)

回傳數值為 x 在 list 中所出現的次數。

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

將 list 中的項目排序。（有參數可以使用來進行客製化的排序，請參考 sorted() 部分的解釋）

list.reverse()

將 list 中的項目前後順序反過來。

list.copy()

回傳一個淺複製 (shallow copy) 的 list 。等同於 a[:]。

以下是一個使用到許多 list 物件方法的例子：

>>> 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 中所有可變資料結構的設計法則。

5.1.1. 將 List 作為 Stack（堆疊）使用

List 的操作方法使得它非常簡單可以用來實作 stack（堆疊）。Stack 為一個遵守最後加入元素最先被取回（後進先出，」last-in, first-out」）規則的資料結構。你可以使用方法 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. 將 List 作為 Queue（佇列）使用

我們也可以將 list 當作 queue（佇列）使用，即最先加入元素最先被取回（先進先出，」first-in, first-out」）的資料結構。然而，list 在這種使用方式下效率較差。使用 append 和 pop 來加入和取出尾端的元素較快，而使用 insert 和 pop 來插入和取出頭端的元素較慢（因為其他元素都需要挪動一格）。

如果要實作 queue，請使用 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. List Comprehensions（串列綜合運算）

List Comprehension（串列綜合運算）讓你可以用簡潔的方法創建 list。常見的應用是基於一個 list 或 iterable（可列舉物件），將每一個元素經過某個運算的結果串接起來成為一個新的 list 。或是創建一個 list 的子序列，其每一個元素皆滿足一個特定的條件。

舉例來說，假設我們要創建一個「平方的 list」：

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

注意這是創建（或複寫）一個變數叫 x 其在迴圈結束後仍然存在。我們可以這樣產生平方串列而不造成任何 side effects（副作用）：

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

或與此相等的：

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

這樣更簡潔和易讀。

一個 list comprehension 的組成，是包含著一個 expression（運算式）和一個 for 語句，再接著零個或多個 for 或 if 語句的一對方括號。結果會是一個新的串列，內容是在接著的 for 和 if 語句的環境下，執行前面 expression 的結果。例如，這個 list comprehension 是由兩個串列中互相不同的元素組合所組成：

>>> [(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 在這兩段程式裡的順序是相同的。

如果 expression 是一個 tuple（例如上面例子中的 (x, y)），它必須加上小括弧：

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

List comprehensions 可以含有複雜的 expression 和巢狀的函式呼叫：

>>> 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. 巢狀的 List Comprehensions

最初放在 list comprehesion 中的 expression 可以是任何形式的 expression，包括再寫一個 list comprehension。

考慮以下表示 3x4 矩陣的範例，使用 list 包含 3 個長度為 4 的 list ：

>>> matrix = [
...     [1, 2, 3, 4],
...     [5, 6, 7, 8],
...     [9, 10, 11, 12],
... ]

以下的 list comprehesion 會將矩陣的行與列作轉置：

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

如同我們在上一節看到的，此巢狀的 list comprehension 為一個 list comprehension在 for 之前先被計算，接著再作一次 list comprehension，所以，這個例子和下者相同：

>>> 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):
...     # 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]]

在實際運用上，我們傾向於使用內建函式 (built-in functions) 而不是複雜的流程控制陳述式。在這個例子中，使用 zip() 函式會非常有效率：

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

關於星號的更多細節，請參考 解包参数列表 。

5.2. del 陳述式

有一個方法可以藉由索引而不是值來刪除 list 中的項： del 陳述式。這和 pop() 方法傳回一個值不同， del 陳述式可以用來刪除 list 中的片段或者清空整個 list（我們之前藉由指派一個空的 list 給想刪除的片段來完成這件事）。例如：

>>> 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 的參照將會造成錯誤（至少在另一個值又被指派到它之前）。我們將在後面看到更多關於 del 的其他用法。

5.3. Tuples 和序列 (Sequences)

我們看到 lists 和 strings 有許多共同的特性，像是索引操作 (indexing) 以及切片操作 (slicing) 。他們是 序列 資料結構中的兩個例子（請參考 序列类型 — list, tuple, range ）。由於 Python 是個持續發展中的語言，未來可能還會有其他的序列資料結構加入。接著要介紹是下一個標準序列資料結構： tuple 。

一個 tuple 是由若干個值藉由逗號區隔而組成，例如：

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

如同我們看到的，被輸出的 tuple 總是以括號包著，如此巢狀的 tuple 才能被正確的直譯 (interpret)；他們可以是以被括號包著或不被包著的方式當作輸入，雖然括號的使用常常是有其必要的（譬如此 tuple 是一個較大的陳述式的一部分）。指派東西給 tuple 中個別的項是不行的，但是可以在 tuple 中放入含有可變項的物件，譬如 list 。

雖然 tuple 和 list 看起來很類似，但是他們通常用在不同的情況與不同目的。 tuple 是 immutable （不可變的），通常儲存異質的序列元素，並可經由拆解(unpacking) （請參考本節後段）或索引 (indexing) 來存取（或者在使用 namedtuples 的時候藉由屬性 (attribute) 來存取）。 list 是 mutable （可變的），其元素通常是同質的且可藉由迭代整個串列來存取。

一個特別的議題是，關於創建一個含有 0 個或 1 個項目的 tuple：語法上會採納一些奇怪的用法。空的 tuple 藉由一對空括號來創建；含有一個項目的 tuple 經由一個值加上一個逗點來創建（不需要用括號把一個單一的值包住）。醜，但有效率。例如：

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

陳述式 t = 12345, 54321, 'hello!' 就是一個 tuple packing 的例子： 12345 ， 54321 和 'hello!' 一起被放進 tuple 裡。反向操作也可以：

>>> x, y, z = t

這個正是我們所說序列拆解 (sequence unpacking) ，可運用在任何位在等號右邊的序列。序列拆解要求等號左邊的變數數量必須與等號右邊的序列中的元素數量相同。注意，多重指派就只是 tuple packing 和序列拆解的結合而已。

5.4. 集合 (Sets)

Python 也包含了一種用在集合 (sets) 的資料結構。一個 set 是一組無序且沒有重複的元素。基本的使用方式包括了成員測試和消除重複項。 Set 物件也支援聯集，交集，差集和互斥等數學操作。

大括號或 set() 函式都可以用來創建 set 。注意：要創建一個空的 set ，我們必須使用 set() 而不是 {} ；後者會創建一個空的 dictionary ，一種我們將在下一節討論的資料結構。

這裡是一個簡單的演示：

>>> 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 either a or b
{'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'}

和 list comprehensions 類似，也有 set comprehensions （集合綜合運算）：

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

5.5. 字典（Dictionary）

下一個常用的 python 內建資料結構為 dictionary （請參考 映射类型 — dict ）。 Dictionary 有時被稱為 「關聯記憶體」 (associative memories) 或 「關聯矩陣」 (associative arrays) 。不像序列是由一個範圍內的數字當作索引， dictionary 是由 key （鍵）來當索引， key 可以是任何不可變的型態；字串和數字都可以當作 key 。 Tuple 也可以當作 key 如果他們只含有字串、數字或 tuple；若一個 tuple 直接或間接地含有任何可變的物件，它就不能當作 key 。我們無法使用 list 當作 key ，因為 list 可以經由索引操作、切片操作或是方法像是 append() 和 extend() 來修改。

It is best to think of a dictionary as an unordered set of key: value pairs, with the requirement that the keys are unique (within one dictionary). A pair of braces creates an empty dictionary: {}. Placing a comma-separated list of key:value pairs within the braces adds initial key:value pairs to the dictionary; this is also the way dictionaries are written on output.

Dict 主要的操作為藉由鍵來儲存一個值並且可藉由該鍵來取出該值。也可以使用 del 來刪除鍵值對。如果我們使用用過的鍵來儲存，該鍵所對應的較舊的值會被覆蓋。使用不存在的鍵來取出值會造成錯誤。

Performing list(d.keys()) on a dictionary returns a list of all the keys used in the dictionary, in arbitrary order (if you want it sorted, just use sorted(d.keys()) instead). [2] To check whether a single key is in the dictionary, use the in keyword.

這是個使用一個字典的簡單範例：

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'sape': 4139, 'guido': 4127, 'jack': 4098}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'guido': 4127, 'irv': 4127, 'jack': 4098}
>>> list(tel.keys())
['irv', 'guido', 'jack']
>>> sorted(tel.keys())
['guido', 'irv', 'jack']
>>> 'guido' in tel
True
>>> 'jack' not in tel
False

函式 dict() 可直接透過一串鍵值對序列來創建 dict：

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

此外， dict comprehensions 也可以透過鍵與值的陳述式來創建 dict ：

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

當鍵是簡單的字串時，使用關鍵字引數 (keyword arguments) 有時會較為簡潔：

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

5.6. 迴圈技巧

當對 dict 作迴圈時，鍵以及其對應的值可以藉由使用 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() 函式會得到一個新的經排序過的 list ，但不會改變原本的序列：

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

有時我們會想要以迴圈來改變的一個 list，但是，通常創建一個新的 list 會更簡單且安全：

>>> 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 內的陳述式可以包含任何運算子，而不是只有比較運算子 (comparisons) 。

比較運算子 in 和 not in 檢查一個數值是否存在（不存在）於一個序列中。運算子 is 和 not is 比較兩個物件是否真的是相同的物件；這對可變物件例如 list 來說很重要。所有的比較運算子優先度都相同且都低於數值運算子。

比較運算是可以串連在一起的。例如， 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 也被稱為短路 (short-circuit) 運算子：會將其引數從左至右進行運算，當結果出現時即結束運算。例如，若 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. 序列和其他資料結構之比較

序列物件可以拿來和其他相同型態的物件做比較。這種比較使用詞典式順序 (lexicographical ordering) ：首先比較各自最前面的那項，若不相同，便可決定結果，若相同，則比較下ㄧ項，以此類推，直到其中一個序列完全用完。如果被拿出來比較的兩項本身又是相同的序列型態，則詞典式順序的比較會遞迴處理。如果兩個序列所有的項都相等，則此兩個序列被認為是相等的。如果其中一個序列是另一個的子序列，則較短的那個序列為較小的序列。字串的詞典式順序使用 Unicode 的碼位 (code point) 編號來排序個別字元。以下是一些相同序列型態的比較：

(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，等等。否則直譯器會選擇丟出一個 TypeError 錯誤而不是提供一個任意的排序。

註解

[1]	其他語言可能可以回傳可變的物件並允許方法串連，例如 d->insert("a")->remove("b")->sort(); 。

[2]	Calling d.keys() will return a dictionary view object. It supports operations like membership test and iteration, but its contents are not independent of the original dictionary – it is only a view.