5. 資料結構

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

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

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

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)

刪除 list 中第一個值等於 x 的元素。若 list 中無此元素則會觸發 ValueError。

list.pop([i])

移除 list 中給定位置的項目，並回傳它。如果沒有指定位置， a.pop() 將會移除 list 中最後的項目並回傳它。若 list 是空的或是索引值超出範圍，則會引發 IndexError 例外。

list.clear()

刪除 list 中所有項目。與 del a[:] 類似。

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

回傳 list 中第一個值等於 x 的項目之索引值（從零開始的索引）。若 list 中無此項目，則丟出 ValueError 錯誤。

引數 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)  # 從位置 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'

你可能會注意到一些方法，像是 insert、remove 或者是 sort，並沒有印出回傳值，事實上，他們回傳預設值 None [1]。這是一個用於 Python 中所有可變資料結構的設計法則。

另外你可能也會發現，不是所有資料都可以被排序或比較。例如，[None, 'hello', 10] 就不可排序，因為整數不能與字串比較，而 None 不能與其他型別比較。有些型別根本就沒有被定義彼此之間的大小順序，例如，3+4j < 5+7j 就是一個無效的比較。

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 加進來
>>> queue.append("Graham")          # Graham 加進來
>>> queue.popleft()                 # 第一個加進來的現在離開
'Eric'
>>> queue.popleft()                 # 第二個加進來的現在離開
'John'
>>> queue                           # queue 裡剩下的會按照加進來的順序排列
deque(['Michael', 'Terry', 'Graham'])

5.1.3. List Comprehensions（串列綜合運算）

List comprehension（串列綜合運算）讓你可以用簡潔的方法建立 list。常見的應用是基於一個序列或 iterable（可疊代物件），將每一個元素經過某個運算的結果串接起來成為新的 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 子句。結果會是一個新的 list，內容是在後面的 for 和 if 子句情境下，對前面運算式求值的結果。例如，這個 list comprehension 組合了兩個 list 中彼此相異的元素：

>>> [(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
    [x, x**2 for x in range(6)]
     ^^^^^^^
SyntaxError: did you forget parentheses around the comprehension target?
>>> # 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 會依據後面的 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):
...     # 下面這三行實作了巢狀的 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)]

關於星號的更多細節，請參考拆解引數列表（Unpacking Argument Lists）。

5.2. del 陳述式

有一個方法可以藉由索引而不是值來刪除 list 中的項目：del 陳述式。這和 pop() method 傳回一個值不同，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)

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

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

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Tuple 可以為巢狀的：
>>> u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))
>>> # Tuple 為不可變的：
>>> 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 中的個別項目是不行的，但是可以建立含有可變物件（譬如 list）的 tuple。

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

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

>>> empty = ()
>>> singleton = 'hello',    # <-- 注意後面有個逗號
>>> 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 也包含了一種用在 set（集合）的資料類型。一個 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 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'}

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

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

5.5. 字典（Dictionary）

下一個常用的 Python 內建資料類型為 dictionary（請參考Mapping Types --- dict）。 Dictionary 有時被稱為「關聯記憶體」(associative memories) 或「關聯陣列」(associative arrays)。不像序列是由一個範圍內的數字當作索引，dictionary 是由鍵 (key) 來當索引，鍵可以是任何不可變的類型；字串和數字都可以當作鍵。Tuple 也可以當作鍵，如果他們只含有字串、數字或 tuple；若一個 tuple 直接或間接地含有任何可變的物件，它就不能當作鍵。你無法使用 list 當作鍵，因為 list 可以經由索引指派 (index assignment)、切片指派 (slice assignment) 或是像 append() 和 extend() 等 method 被修改。

思考 dictionary 最好的方式是把它想成是一組鍵值對 (key: value pair) 的 set，其中鍵在同一個 dictionary 裡必須是獨一無二的。使用一對大括號可建立一個空的 dictionary：{}。將一串由逗號分隔的鍵值對置於大括號則可初始化字典的鍵值對。這同樣也是字典輸出時的格式。

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

對 dictionary 使用 list(d) 會得到一個包含該字典所有鍵的 list，其排列順序為插入時的順序。（若想要排序，則使用 sorted(d) 代替即可）。如果想確認一個鍵是否已存在於字典中，可使用關鍵字 in。

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

>>> 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() 可直接透過一串鍵值對序列來建立 dictionary：

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

此外，dict comprehensions 也可以透過任意鍵與值的運算式來建立 dictionary ：

>>> {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, 'guido': 4127, 'jack': 4098}

5.6. 迴圈技巧

當對 dictionary 作迴圈時，鍵以及其對應的值可以藉由使用 items() method 來同時取得：

>>> 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 i in sorted(basket):
...     print(i)
...
apple
apple
banana
orange
orange
pear

對序列使用 set() 可去除重複元素。對序列使用 sorted() 加上 set()，則是對經過排序後的非重複元素跑迴圈的慣用方法：

>>> 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. 深入了解條件 (Condition)

使用在 while 和 if 陳述式的條件句可以包含任何運算子，而不是只有比較運算子 (comparisons) 。

比較運算子 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 也被稱為短路 (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 語言裡常見的一種問題：想要打 == 卻在運算式裡輸入 =。

5.8. 序列和其他資料類型之比較

序列物件通常可以拿來和其他相同類型的物件做比較。這種比較使用詞典式 (lexicographical) 順序：首先比較各自最前面的那項，若不相同，便可決定結果；若相同，則比較下一項，以此類推，直到其中一個序列完全用完。如果被拿出來比較的兩項本身又是相同的序列類型，則詞典式比較會遞迴地執行。如果兩個序列所有的項目都相等，則此兩個序列被認為是相等的。如果其中一個序列是另一個的子序列，則較短的那個序列為較小的序列。字串的詞典式順序使用 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 錯誤而不是提供一個任意的排序。

註解