數據結構 · Python3.7.3官方文檔簡體中文

### 導航 - [索引](../genindex.xhtml "總目錄") - [模塊](../py-modindex.xhtml "Python 模塊索引") | - [下一頁](modules.xhtml "6. 模塊") | - [上一頁](controlflow.xhtml "4. 其他流程控制工具") | - ![](https://box.kancloud.cn/a721fc7ec672275e257bbbfde49a4d4e_16x16.png) - [Python](https://www.python.org/) ? - zh\_CN 3.7.3 [文檔](../index.xhtml) ? - [Python 教程](index.xhtml) ? - $('.inline-search').show(0); | # 5. 數據結構本章將詳細介紹一些您已經了解的內容，并添加了一些新內容。 ## 5.1. 列表的更多特性列表數據類型還有很多的方法。這里是列表對象方法的清單： `list.``append`(*x*)在列表的末尾添加一個元素。相當于 `a[len(a):] = [x]` 。 `list.``extend`(*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`](../library/exceptions.xhtml#ValueError "ValueError") 異常。 `list.``pop`(\[*i*\])刪除列表中給定位置的元素并返回它。如果沒有給定位置，`a.pop()` 將會刪除并返回列表中的最后一個元素。（方法簽名中 *i* 兩邊的方括號表示這個參數是可選的，而不是要你輸入方括號。你會在 Python 參考庫中經常看到這種表示方法)。 `list.``clear`()刪除列表中所有的元素。相當于 `del a[:]` 。 `list.``index`(*x*\[, *start*\[, *end*\]\])返回列表中第一個值為 *x* 的元素的從零開始的索引。如果沒有這樣的元素將會拋出 [`ValueError`](../library/exceptions.xhtml#ValueError "ValueError") 異常。可選參數 *start* 和 *end* 是切片符號，用于將搜索限制為列表的特定子序列。返回的索引是相對于整個序列的開始計算的，而不是 *start* 參數。 `list.``count`(*x*)返回元素 *x* 在列表中出現的次數。 `list.``sort`(*key=None*, *reverse=False*)對列表中的元素進行排序（參數可用于自定義排序，解釋請參見 [`sorted()`](../library/functions.xhtml#sorted "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](#id2) 這是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`](../library/collections.xhtml#collections.deque "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. 列表推導式列表推導式提供了一個更簡單的創建列表的方法。常見的用法是把某種操作應用于序列或可迭代對象的每個元素上，然后使用其結果來創建列表，或者通過滿足某些特定條件元素來創建子序列。例如，假設我們想創建一個平方列表，像這樣 ``` >>> squares = [] >>> for x in range(10): ... squares.append(x**2) ... >>> squares [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] ``` 注意這里創建（或被重寫）的名為 `x` 的變量在for循環后仍然存在。我們可以計算平方列表的值而不會產生任何副作用 ``` squares = list(map(lambda x: x**2, range(10))) ``` 或者，等價于 ``` squares = [x**2 for x in range(10)] ``` 上面這種寫法更加簡潔易讀。列表推導式的結構是由一對方括號所包含的以下內容：一個表達式，后面跟一個 `for` 子句，然后是零個或多個 `for` 或 `if` 子句。其結果將是一個新列表，由對表達式依據后面的 `for` 和 `if` 子句的內容進行求值計算而得出。舉例來說，以下列表推導式會將兩個列表中不相等的元素組合起來: ``` >>> [(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`](../reference/compound_stmts.xhtml#for) 和 [`if`](../reference/compound_stmts.xhtml#if) 的順序是相同的。如果表達式是一個元組（例如上面的 `(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] ``` 列表推導式可以使用復雜的表達式和嵌套函數 ``` >>> 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. 嵌套的列表推導式列表推導式中的初始表達式可以是任何表達式，包括另一個列表推導式。考慮下面這個 3x4的矩陣，它由3個長度為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]] ``` 如上節所示，嵌套的列表推導式是基于跟隨其后的 [`for`](../reference/compound_stmts.xhtml#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): ... # 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]] ``` 實際應用中，你應該會更喜歡使用內置函數去組成復雜的流程語句。 [`zip()`](../library/functions.xhtml#zip "zip") 函數將會很好地處理這種情況 ``` >>> list(zip(*matrix)) [(1, 5, 9), (2, 6, 10), (3, 7, 11), (4, 8, 12)] ``` 關于本行中星號的詳細說明，參見 [解包參數列表](controlflow.xhtml#tut-unpacking-arguments)。 ## 5.2. `del` 語句有一種方式可以從列表按照給定的索引而不是值來移除一個元素: 那就是 [`del`](../reference/simple_stmts.xhtml#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`](../reference/simple_stmts.xhtml#del) 也可以被用來刪除整個變量 ``` >>> del a ``` 此后再引用 `a` 時會報錯（直到另一個值被賦給它）。我們會在后面了解到 [`del`](../reference/simple_stmts.xhtml#del) 的其他用法。 ## 5.3. 元組和序列我們看到列表和字符串有很多共同特性，例如索引和切片操作。他們是 *序列* 數據類型（參見 [序列類型 --- list, tuple, range](../library/stdtypes.xhtml#typesseq)）中的兩種。隨著 Python 語言的發展，其他的序列類型也會被加入其中。這里介紹另一種標準序列類型: *元組*。一個元組由幾個被逗號隔開的值組成，例如 ``` >>> 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]) ``` 如你所見，元組在輸出時總是被圓括號包圍的，以便正確表示嵌套元組。輸入時圓括號可有可無，不過經常會是必須的（如果這個元組是一個更大的表達式的一部分）。給元組中的一個單獨的元素賦值是不允許的，當然你可以創建包含可變對象的元組，例如列表。雖然元組可能看起來與列表很像，但它們通常是在不同的場景被使用，并且有著不同的用途。元組是 [immutable](../glossary.xhtml#term-immutable) （不可變的），其序列通常包含不同種類的元素，并且通過解包（這一節下面會解釋）或者索引來訪問（如果是 [`namedtuples`](../library/collections.xhtml#collections.namedtuple "collections.namedtuple") 的話甚至還可以通過屬性訪問）。列表是 [mutable](../glossary.xhtml#term-mutable) （可變的），并且列表中的元素一般是同種類型的，并且通過迭代訪問。一個特殊的問題是構造包含0個或1個元素的元組：為了適應這種情況，語法有一些額外的改變。空元組可以直接被一對空圓括號創建，含有一個元素的元組可以通過在這個元素后添加一個逗號來構建（圓括號里只有一個值的話不夠明確）。丑陋，但是有效。例如 ``` >>> empty = () >>> singleton = 'hello', # <-- note trailing comma >>> len(empty) 0 >>> len(singleton) 1 >>> singleton ('hello',) ``` 語句 `t = 12345, 54321, 'hello!'` 是 *元組打包* 的一個例子：值 `12345`, `54321` 和 `'hello!'` 被打包進元組。其逆操作也是允許的 ``` >>> x, y, z = t ``` 這被稱為 *序列解包* 也是很恰當的，因為解包操作的等號右側可以是任何序列。序列解包要求等號左側的變量數與右側序列里所含的元素數相同。注意可變參數其實也只是元組打包和序列解包的組合。 ## 5.4. 集合 Python也包含有 *集合* 類型。集合是由不重復元素組成的無序的集。它的基本用法包括成員檢測和消除重復元素。集合對象也支持像聯合，交集，差集，對稱差分等數學運算。花括號或 [`set()`](../library/stdtypes.xhtml#set "set") 函數可以用來創建集合。注意：要創建一個空集合你只能用 `set()` 而不能用 `{}`，因為后者是創建一個空字典，這種數據結構我們會在下一節進行討論。以下是一些簡單的示例： ``` >>> 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'} ``` 類似于 [列表推導式](#tut-listcomps)，集合也支持推導式形式 ``` >>> a = {x for x in 'abracadabra' if x not in 'abc'} >>> a {'r', 'd'} ``` ## 5.5. 字典另一個非常有用的 Python 內置數據類型是 *字典* (參見 [映射類型 --- dict](../library/stdtypes.xhtml#typesmapping))。字典在其他語言里可能會被叫做 *聯合內存* 或 *聯合數組*。與以連續整數為索引的序列不同，字典是以 *關鍵字* 為索引的，關鍵字可以是任意不可變類型，通常是字符串或數字。如果一個元組只包含字符串、數字或元組，那么這個元組也可以用作關鍵字。但如果元組直接或間接地包含了可變對象，那么它就不能用作關鍵字。列表不能用作關鍵字，因為列表可以通過索引、切片或 `append()` 和 `extend()` 之類的方法來改變。理解字典的最好方式，就是將它看做是一個 *鍵: 值* 對的集合，鍵必須是唯一的（在一個字典中）。一對花括號可以創建一個空字典：`{}` 。另一種初始化字典的方式是在一對花括號里放置一些以逗號分隔的鍵值對，而這也是字典輸出的方式。字典主要的操作是使用關鍵字存儲和解析值。也可以用 `del` 來刪除一個鍵值對。如果你使用了一個已經存在的關鍵字來存儲值，那么之前與這個關鍵字關聯的值就會被遺忘。用一個不存在的鍵來取值則會報錯。對一個字典執行 `list(d)` 將返回包含該字典中所有鍵的列表，按插入次序排列 (如需其他排序，則要使用 `sorted(d)`)。要檢查字典中是否存在一個特定鍵，可使用 [`in`](../reference/expressions.xhtml#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()`](../library/stdtypes.xhtml#dict "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()`](../library/functions.xhtml#enumerate "enumerate") 函數可以將索引位置和其對應的值同時取出 ``` >>> for i, v in enumerate(['tic', 'tac', 'toe']): ... print(i, v) ... 0 tic 1 tac 2 toe ``` 當同時在兩個或更多序列中循環時，可以用 [`zip()`](../library/functions.xhtml#zip "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()`](../library/functions.xhtml#reversed "reversed") 函數 ``` >>> for i in reversed(range(1, 10, 2)): ... print(i) ... 9 7 5 3 1 ``` 如果要按某個指定順序循環一個序列，可以用 [`sorted()`](../library/functions.xhtml#sorted "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，等等。否則，解釋器將拋出一個 [`TypeError`](../library/exceptions.xhtml#TypeError "TypeError") 異常，而不是隨便給出一個結果。腳注 [1](#id1)別的語言可能會返回一個可變對象，他們允許方法連續執行，例如 `d->insert("a")->remove("b")->sort();`。 ### 導航 - [索引](../genindex.xhtml "總目錄") - [模塊](../py-modindex.xhtml "Python 模塊索引") | - [下一頁](modules.xhtml "6. 模塊") | - [上一頁](controlflow.xhtml "4. 其他流程控制工具") | - ![](https://box.kancloud.cn/a721fc7ec672275e257bbbfde49a4d4e_16x16.png) - [Python](https://www.python.org/) ? - zh\_CN 3.7.3 [文檔](../index.xhtml) ? - [Python 教程](index.xhtml) ? - $('.inline-search').show(0); | ? [版權所有](../copyright.xhtml) 2001-2019, Python Software Foundation. Python 軟件基金會是一個非盈利組織。 [請捐助。](https://www.python.org/psf/donations/) 最后更新于 5月 21, 2019. [發現了問題](../bugs.xhtml)？使用[Sphinx](http://sphinx.pocoo.org/)1.8.4 創建。