python數據結構的應用場景不包括,Python 數據結構學習

Python 數據結構學習

列表

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 異常。

list.pop([i])

刪除列表中給定位置的元素并返回它。如果沒有給定位置，a.pop() 將會刪除并返回列表中的最后一個元素。( 方法簽名中 i 兩邊的方括號表示這個參數是可選的，而不是要你輸入方括號。你會在 Python 參考庫中經常看到這種表示方法)。

list.clear()

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

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

返回列表中第一個值為 x 的元素的從零開始的索引。如果沒有這樣的元素將會拋出 ValueError 異常。

可選參數 start 和 end 是切片符號，用于將搜索限制為列表的特定子序列。返回的索引是相對于整個序列的開始計算的，而不是 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')

>>> fruits.count('tangerine')

>>> fruits.index('banana')

>>> fruits.index('banana', 4) # Find next banana starting a position 4

>>> 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 就不是一個合法的比較。

列表作為棧使用

列表方法使得列表作為堆棧非常容易，最后一個插入，最先取出(“后進先出”)。要添加一個元素到堆棧的頂端，使用 append() 。要從堆棧頂部取出一個元素，使用 pop() ，不用指定索引。例如

>>> stack = [3, 4, 5]

>>> stack.append(6)

>>> stack.append(7)

>>> stack

[3, 4, 5, 6, 7]

>>> stack.pop()

>>> stack

[3, 4, 5, 6]

>>> stack.pop()

>>> stack

[3, 4]

列表作為隊列使用

列表也可以用作隊列，其中先添加的元素被最先取出 (“先進先出”)；然而列表用作這個目的相當低效。因為在列表的末尾添加和彈出元素非常快，但是在列表的開頭插入或彈出元素卻很慢 (因為所有的其他元素都必須移動一位)。

若要實現一個隊列，可使用 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'])

列表推導式

列表推導式提供了一個更簡單的創建列表的方法。常見的用法是把某種操作應用于序列或可迭代對象的每個元素上，然后使用其結果來創建列表，或者通過滿足某些特定條件元素來創建子序列。

例如，假設我們想創建一個平方列表，像這樣

>>> 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 和 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 "", line 1, in

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

嵌套的列表推導式

列表推導式中的初始表達式可以是任何表達式，包括另一個列表推導式。

考慮下面這個 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 進行求值的，所以這個例子等價于:

>>> 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() 函數將會很好地處理這種情況

>>> list(zip(*matrix))

[(1, 5, 9), (2, 6, 10), (3, 7, 11), (4, 8, 12)]

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 時會報錯(直到另一個值被賦給它)。我們會在后面了解到 del 的其他用法。

元組和序列

我們看到列表和字符串有很多共同特性，例如索引和切片操作。他們是序列數據類型(參見序列類型 --- list, tuple, range)中的兩種。隨著 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 "", line 1, in

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 ，其序列通常包含不同種類的元素，并且通過解包(這一節下面會解釋)或者索引來訪問(如果是 namedtuples 的話甚至還可以通過屬性訪問)。列表是 mutable ，并且列表中的元素一般是同種類型的，并且通過迭代訪問。

一個特殊的問題是構造包含0個或1個元素的元組：為了適應這種情況，語法有一些額外的改變。空元組可以直接被一對空圓括號創建，含有一個元素的元組可以通過在這個元素后添加一個逗號來構建(圓括號里只有一個值的話不夠明確)。丑陋，但是有效。例如

>>> empty = ()

>>> singleton = 'hello', #

>>> len(empty)

>>> len(singleton)

>>> singleton

('hello',)

語句 t = 12345, 54321, 'hello!' 是元組打包的一個例子：值 12345, 54321 和 'hello!' 被打包進元組。其逆操作也是允許的

>>> x, y, z = t

這被稱為序列解包也是很恰當的，因為解包操作的等號右側可以是任何序列。序列解包要求等號左側的變量數與右側序列里所含的元素數相同。注意多重賦值其實也只是元組打包和序列解包的組合。

集合

Python也包含有集合類型。集合是由不重復元素組成的無序的集。它的基本用法包括成員檢測和消除重復元素。集合對象也支持像聯合，交集，差集，對稱差分等數學運算。

花括號或 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'}

類似于列表推導式，集合也支持推導式形式

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

>>> a

{'r', 'd'}

字典

另一個非常有用的 Python 內置數據類型是字典 (參見映射類型 --- dict)。字典在其他語言里可能會被叫做聯合內存或聯合數組。與以連續整數為索引的序列不同，字典是以關鍵字為索引的，關鍵字可以是任意不可變類型，通常是字符串或數字。如果一個元組只包含字符串、數字或元組，那么這個元組也可以用作關鍵字。但如果元組直接或間接地包含了可變對象，那么它就不能用作關鍵字。列表不能用作關鍵字，因為列表可以通過索引、切片或 append() 和 extend() 之類的方法來改變。

理解字典的最好方式，就是將它看做是一個鍵: 值對的集合，鍵必須是唯一的(在一個字典中)。一對花括號可以創建一個空字典：{} 。另一種初始化字典的方式是在一對花括號里放置一些以逗號分隔的鍵值對，而這也是字典輸出的方式。

字典主要的操作是使用關鍵字存儲和解析值。也可以用 del 來刪除一個鍵值對。如果你使用了一個已經存在的關鍵字來存儲值，那么之前與這個關鍵字關聯的值就會被遺忘。用一個不存在的鍵來取值則會報錯。

對一個字典執行 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