數據結構（DataStructures）

2019-11-14 17:00:35

字體：大中小

來源：轉載

供稿：網友

一、List數據類型的方法

定義兩個list，a和b：a=[1,2,3,4]，b=[7,8,9,10]

a.append(x) 在a的末尾附加x元素

a.extend(b) 在a的末尾添加b的所有元素

a.insert(i,x) 在a的第i個元素位置之后插入x元素，即a.insert(len(a),x)等價于a.append(x)

a.remove(x) 在a中移除第一個出現的x元素

a.pop() 返回：a的最后一個元素，并在a中刪除該元素

a.index(x) 返回x元素的索引值，若a中不存在x元素，則返回一個錯誤

a.count(x) 返回x元素在a中出現的次數

a.sort() 對a中的元素進行排序

a.reverse() 將a中的元素逆序

del a[i] 刪除該元素

(以上這些方法都是在原來的表的上進行操作，會對原來的表產生影響，而不是返回一個新表。)

 1 >>> a=[1,2,3,4] 2 >>> a.append(5) 3 >>> a 4 [1, 2, 3, 4, 5] 5 >>> a.insert(5,6) 6 >>> a 7 [1, 2, 3, 4, 5, 6] 8 >>> b=[7,8,9,10] 9 >>> a.extend(b)10 >>> a11 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]12 >>> a.remove(2)13 >>> a14 [1, 3, 4, 5, 6, 7, 8, 9, 10]15 >>> a.pop()16 1017 >>> a18 [1, 3, 4, 5, 6, 7, 8, 9]19 >>> a.index(5)20 321 >>> a.count(5)22 123 >>> a.reverse()24 >>> a25 [9, 8, 7, 6, 5, 4, 3, 1]26 >>> del a[2]27 >>> a28 [9, 8, 6, 5, 4, 3, 1]29 >>> a.sort()30 >>> a31 [1, 3, 4, 5, 6, 8, 9]

二、List作為stacks使用

Stack：堆棧，即后進先出（last-in, first-out），只有一端（稱為棧頂(top)）對數據項進行插入和移除，在棧頂使用append()添加一個元素，在棧頂使用pop()移除一個元素。

 1 >>> stack=[1,2,3] 2 >>> stack.append(4) 3 >>> stack.append(5) 4 >>> stack 5 [1, 2, 3, 4, 5] 6 >>> stack.pop() 7 5 8 >>> stack 9 [1, 2, 3, 4]10 >>> stack.pop()11 412 >>> stack.pop()13 314 >>> stack15 [1, 2]

三、List作為queues使用

Queue：隊列，即先進先出（first-in, first-out），一頭進一頭出，先進去的在前面，自然先從另一邊出來。

注意：此處list作為queue使用，效率不是很高，當往list的結尾處添加（append()）或移除（pop()）元素時是快的，當往list的開始處插入（insert()）或移除（pop()）元素時是慢的，原因是后者所有的其它元素都需要移動。這里建議使用collections.deque，它在前后兩端appends和pops時都很快。

 1 >>> from collections import deque 2 >>> queue = deque(["Eric","John","Michael"]) 3 >>> queue.append("Terry") 4 >>> queue.append("Graham") 5 >>> queue.popleft() 6 'Eric' 7 >>> queue.popleft() 8 'John' 9 >>> queue10 deque(['Michael', 'Terry', 'Graham'])

四、filter()、map()、reduce()方法使用

filter(function,sequence)：對sequence中的item依次執行function(item)，將執行結果為True的item組成一個list/string/tuple(取決于sequence的類型)返回：

1 >>> def f(x):return x % 3 == 0 or x % 5 == 02 >>> filter(f,range(2,25))3 [3, 5, 6, 9, 10, 12, 15, 18, 20, 21, 24]4 >>> def f(x):return x != 'a'5 >>> filter(f,"abcdef")6 'bcdef'

map(function,sequence)：對sequence中的item依次執行function(item)，將執行結果組成一個list返回：

1 >>> def cube(x):return x*x*x2 >>> map(cube,range(1,11))3 [1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]4 >>> def cube(x):return x+x5 >>> map(cube,"abcde")6 ['aa', 'bb', 'cc', 'dd', 'ee']7 >>> def add(x,y):return x+y8 >>> map(add,range(8),range(8))9 [0, 2, 4, 6, 8, 10, 12, 14]

reduce(function,sequence)：對sequence中的item順序迭代調用function，如果有starting_value，還可以作為初始值調用，例如可以用來對list求和：

1 >>> def add(x,y):return x+y2 >>> reduce(add,range(1,11))3 55 （注：1+2+3+4+5+6+7+8+9+10）4 >>> def add(x,y):return x+y5 >>> reduce(add,range(1,11),20)6 75 （注：1+2+3+4+5+6+7+8+9+10+20）

五、List ComPRehensions

列表推導式(list comprehension)是一種方便簡介的語法形式，我們可以利用它將一個list經過過濾后轉換成另一個list，也可以利用它將函數應用于list中的元素。

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

squares = [x**2 for x in range(10)] 等價于以下常規寫法

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

是不是上面看起來更簡潔及可讀性更好，再舉一例如下：

1 >>> [(x,y) for x in [1,2,3] for y in [3,1,4] if x != y]2 [(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

等價于以下常規寫法

1 >>> combs=[]2 >>> for x in [1,2,3]:3 ...     for y in [3,1,4]:4 ...         if x != y:5 ...             combs.append((x,y))6 ...             7 >>> combs8 [(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

具體應用如下：

 1 >>> vec = [-4,-2,0,2,4] 2 >>> [x*2 for x in vec]        #返回一個新的list，新list元素值是原先元素值的2倍 3 [-8, -4, 0, 4, 8] 4 >>> [x for x in vec if x>=0]  #返回一個新的list，值為原list中大于0的元素 5 [0, 2, 4] 6 >>> [abs(x) for x in vec]     #返回一個新的list，值為對原list中的元素值求絕對值 7 [4, 2, 0, 2, 4] 8  9 >>> freshfruit = [' banana',' apple','orange ']10 >>> [weapon.strip() for weapon in freshfruit]   #strip()去掉前后空格11 ['banana', 'apple', 'orange']12 >>> [(x,x**2) for x in range(6)]13 [(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]14 >>> vec = [[1,2,3],[4,5,6],[7,8,9]]15 >>> [num for elem in vec for num in elem]16 [1, 2, 3, 4, 5, 6, 7, 8, 9]

List comprehensions支持復雜的表達式和嵌套函數

 1 >>> from math import pi 2 >>> [str(round(pi,i)) for i in range(1,6)] 3 ['3.1', '3.14', '3.142', '3.1416', '3.14159'] 4  5 >>> matrix=[ 6 ...     [1,2,3,4], 7 ...     [5,6,7,8], 8 ...     [9,10,11,12], 9 ...     ]10 ...     11 >>> [[row[i] for row in matrix] for i in range(4)]12 [[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

六、Tuples和Sequences

sequence(序列)是一組有順序的元素的集合

(嚴格的說，是對象的集合，但鑒于我們還沒有引入“對象”概念，暫時說元素)

序列可以包含一個或多個元素，也可以沒有任何元素。

我們之前所說的基本數據類型，都可以作為序列的元素。元素還可以是另一個序列，以及我們以后要介紹的其他對象。

序列有兩種：tuple（定值表；也有翻譯為元組）和 list (表)

>>>s1 = (2, 1.3, 'love', 5.6, 9, 12, False) # s1是一個tuple

>>>s2 = [True, 5, 'smile'] # s2是一個list

tuple和list的主要區別在于，一旦建立，tuple的各個元素不可再變更，而list的各個元素可以再變更。

七、Sets

Set：創建一個無序不重復的元素集，基本功能包含關系測試和消除重復元素，集合對象還支持union(聯合),intersection(交),difference(差)和sysmmetric difference(對稱差集)等數學運算。

 1 >>> basket = ['apple','orange','apple','pear','orange','banana'] 2 >>> fruit = set(basket) 3 >>> fruit 4 set(['orange', 'pear', 'apple', 'banana']) 5 >>> 'orange' in fruit 6 True 7 >>> 'crabgrass' in fruit 8 False 9 10 >>> a = set('abracadabra')11 >>> b =set('alacazam')12 >>> a13 set(['a', 'r', 'b', 'c', 'd'])14 >>> b15 set(['a', 'c', 'z', 'm', 'l'])16 >>> a-b17 set(['r', 'b', 'd'])18 >>> a|b19 set(['a', 'c', 'b', 'd', 'm', 'l', 'r', 'z'])20 >>> a&b21 set(['a', 'c'])22 >>> a^b23 set(['b', 'd', 'm', 'l', 'r', 'z'])24 25 >>> a = {x for x in 'abracadabra' if x not in 'abc'}26 >>> a27 set(['r', 'd'])

八、字典（Dictionaries）

字典：存儲一對key、value

 1 >>> tel={'jack':4098,'sape':4139} 2 >>> tel['guido'] = 4127 3 >>> tel 4 {'sape': 4139, 'jack': 4098, 'guido': 4127} 5 >>> tel['jack'] 6 4098 7 >>> del tel['sape'] 8 >>> tel['irv'] = 4127 9 >>> tel10 {'jack': 4098, 'irv': 4127, 'guido': 4127}11 >>> tel.keys()12 ['jack', 'irv', 'guido']13 >>> 'guido' in tel14 True15 16 >>> dict([('sape',4139),('guido',4127),('jack',4098)])17 {'sape': 4139, 'jack': 4098, 'guido': 4127}18 >>> dict(sape=4139,guido=4127,jack=4098)19 {'sape': 4139, 'jack': 4098, 'guido': 4127}

dict()構造方法可以從一個key-value序列創建成字典

九、循環技巧

 1 >>> for i,v in enumerate(['tic','tac','toe']): 2 ...     print i,v 3 ...      4 0 tic 5 1 tac 6 2 toe 7 >>> questions = ['name','quest','favorite color'] 8 >>> answers = ['lancelot','the holy grail','blue'] 9 >>> for q,a in zip(questions,answers):10 ...     print 'What is your {0}? It is {1}.'. format(q,a)11 ...     12 What is your name? It is lancelot.13 What is your quest? It is the holy grail.14 What is your favorite color? It is blue.15 16 >>> for i in reversed(xrange(1,10,2)):17 ...     print i18 ...     19 920 721 522 323 124 >>> basket = ['apple','orange','apple','pear','orange','banana']25 >>> for f in sorted(set(basket)):26 ...     print f27 ...     28 apple29 banana30 orange31 pear