Data Structures
數據結構
4 數據結構
4.1 深入鏈表
append(x) 把一個元素添加到鏈表的結尾。
extend(L) 通過添加指定鏈表的所有元素來擴充鏈表。
insert(i,x) 在指定位置插入一個元素。
remove(x) 刪除鏈表中值為x的第一個元素。如果沒有這樣的元素，就會返回一個錯誤。
pop([i]) 從鏈表的指定位置刪除元素，并將其返回。如果沒有指定索引，a.pop()返回最后一個元素。元素隨即從鏈表中被刪除。
index(x) 返回鏈表中第一個值為x的元素的索引。如果沒有匹配的元素就會返回一個錯誤。
count(x) 返回x在鏈表中出現的次數。
sort() 就地對鏈表中的元素進行排序。
reverse() 就地對鏈表中的元素進行倒排序。
4.1.1 把鏈表當作堆棧使用
鏈表方法使得鏈表可以很方便的作為一個堆棧來使用。堆棧為后進先出。用append()方法可以把一個元素添加到堆棧頂。用不指定索引的pop()方法可以把一個元素從堆棧頂釋放出來。
>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack
[3, 4, 5, 6]
>>> print stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack
[3, 4, 5]
>>>
4.1.2 把鏈表當作隊列使用
也可以把鏈表當作隊列使用，隊列作為特定的數據結構，最先進入的元素最先釋放。使用append()方法可以把元素添加到隊列最后，以0為參數調用pop()方法可以把最先進入的元素釋放出來。
>>> queue = ["Eric", "John", "Michael"]
>>> queue.append("Terry")
>>> queue.append("Graham")
>>> queue
['Eric', 'John', 'Michael', 'Terry', 'Graham']
>>> queue.pop(0)
'Eric'
>>> queue
['John', 'Michael', 'Terry', 'Graham']
>>>
4.1.3 函數化編程工具
鏈表中有三個內置函數非常有用：filter(),map()和reduce()。
filter(function, sequence)返回一個sequence，包括了給定序列中所有調用function后返回值為true的元素。如果sequence是一個string或者tuple，返回值必行是同一類型，否則，它總是list。
>>> def f(x):return x % 2 != 0 and x%3 != 0
...
>>> filter(f, range(2, 25))
[5, 7, 11, 13, 17, 19, 23]
>>>
map(function, sequence)為每一個元素依次調用function(item)并將返回值組成一個鏈表返回。
>>> def cube(x): return x*x*x
...
>>> map(cube, range(1, 11))
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]
>>>
可以傳入多個序列，函數也必須要有對應數量的參數，執行時會依次用各序列上對應的元素來調用函數。如果某些序列比其它的短，就用None來代替。如果把None做為一個函數傳入，則直接返回參數做為替代。
>>> seq = range(8)
>>> def add(x, y): return x+y
...
>>> map(add, seq, seq)
[0, 2, 4, 6, 8, 10, 12, 14]
>>>
reduce(func, sequence)返回一個單值，它是這樣構造的：首先以序列的前兩個元素調用函數，再以返回值和第三個參數調用，依次執行下去。
>>> def add(x, y): return x+y
...
>>> reduce(add, range(1, 11))
55
>>>
如果序列中只有一個元素，就返回它，如果序列是空的，就拋出一個異常。
可以傳入第三個參數做為初始值。如果序列是空的，就返回初始值，否則函數會先接收初始值和序列的第一個元素，然后是返回值和下一個原色，依次類推。例如：
>>> def sum(seq):
... def add(x,y): return x+y
... return reduce(add, seq, 0)
...
>>> sum(range(1,11))
55
>>> sum([])
0
>>>
4.1.4 鏈表推導式
鏈表推導式提供了一個創建鏈表的簡單途徑，無須使用map(),filter()以及lambda。返回鏈表的定義通常比創建這些鏈表更清晰。每一個鏈表推導式包括一個for語句之后的表達式，零或多個for或if語句。返回值是由for或if字句之后的表達式得到的元素組成的鏈表。如果想得到一個元組，必須要加上括號。
>>> freshfruit = ['banana','loganberry','passion fruit']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']
>>> vec = [2, 4, 6]
>>> [3*x for x in vec]
[6, 12, 18]
>>> [3*x for x in vec if x<2]
[]
>>> [3*x for x in vec if x<4]
[6]
>>> [[x,x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]
>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [x*y for x in vec1 for y in vec2]
[8, 6, -18, 16, 12, -36, 24, 18, -54]
>>> [[x,x*2] for x in vec]
[[2, 4], [4, 8], [6, 12]]
>>> [x+y for x in vec1 for y in vec2]
[6, 5, -7, 8, 7, -5, 10, 9, -3]
>>> [vec1[i]*vec2[i] for i in range(len(vec1))]
[8, 12, -54]
>>>
鏈式推導式比map()更復雜，可使用復雜的表達式和嵌套函數。
>>> [str(round(355/113.0,i)) for i in range(1,6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']
>>>
4.2 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]
>>> a
[1, 66.25, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.25]
>>>
del也可以用于刪除整個變量：
>>> del a
>>> a
Traceback (most recent call last):
File "<interactive input>", line 1, in <module>
NameError: name 'a' is not defined
>>>
此后再引用這個名字會發生錯誤（至少要到給它賦另外一個值為止）。
4.3 元組和序列
鏈表和字符串有很多通用的屬性，如索引和切割操作。它們是序列類型中的兩種。
有一種標準序列類型：元組。一個元組由數個逗號分隔的值組成。
>>> t = 12345, 54321, 'hello'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello')
>>> u = t, (1, 2, 3)
>>> u
((12345, 54321, 'hello'), (1, 2, 3))
>>>
元組也可能是容器
元組在輸出時總是有括號的，以便于正確表達嵌套結構。在輸入時可能有或沒有括號都可以，不過經常括號都是必須的。
元組由很多用途。例如(x,y)坐標點，數據庫中的員工記錄等等。元組就像字符串，不可改變：不能給元組的一個獨立的元素賦值（盡管可以通過聯接和切割來模仿）。也可以通過包含可變對象來創建元組，例如鏈表。
構造零個元素的元組，使用空的括號創建。構造有一個單元素元組可以在值后面跟一個逗號。例如：
>>> empty = ()
>>> singletuple = 'hello',
>>> len(empty)
0
>>> len(singletuple)
1
>>> singletuple
('hello',)
>>>
語句t = 123, 321, 'niky'是元組封裝的一個例子：值123,321，‘niky’被封裝進元組。其逆操作可能是這樣：
>>> t = 123, 321, 'niky'
>>> x, y, z = t
>>> x
123
>>> y
321
>>> z
'niky'
>>>
這個調用被稱為序列拆封非常合適。序列拆封要求左側的變量數目與序列的元素個數相同。要注意的是可變參數其實只是元組封裝和序列拆封的一個結合。
這里有一點不對稱：封裝多重參數通常會創建一個元組，而拆封操作可以作用于任何序列。
4.4 集合
Python還包含了一個數據類型set。集合是一個無序不重復元素的集。基本功能包括關系測試和消除重復元素。集合對象還支持union、intersection、difference和sysmmetric difference(對稱差集)等數學運算。
>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> fruit = set(basket)
>>> fruit
set(['orange', 'pear', 'apple', 'banana'])
>>> 'orange' in fruit
True
>>> # 演示集合操作
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a
set(['a', 'r', 'b', 'c', 'd'])
>>> b
set(['a', 'c', 'z', 'm', 'l'])
>>> a - b # a中有，而b中沒有
set(['r', 'b', 'd'])
>>> a | b # a 或者 b
set(['a', 'c', 'b', 'd', 'm', 'l', 'r', 'z'])
>>> a & b
set(['a', 'c'])
>>> a ^ b # 在a或b中，但不會同時在a和b中
set(['b', 'd', 'm', 'l', 'r', 'z'])
>>>
4.5 字典
字典在某些語言中可能稱為“聯合內存”或“聯合數組”。序列是以連續的整數位索引，與此不同的是，字典以關鍵字為索引，關鍵字可以是任意不可變類型，通常用字符串或數值。如果元組中只包含字符串和數字，它可以做為關鍵字，如果它直接或間接的包含了可變對象，就不能當作關鍵字。不能用鏈表做關鍵字，因為鏈表可以用索引、切割或者append()和extend()等方法改變。
字典可以看做是無序的關鍵字:值對集合，關鍵字必須是互不相同的。一對大括號創建一個空的字典{}。初始化鏈表時，在大括號內放置一組逗號分隔的關鍵字:值對，這也是字典輸出的方式。
字典的主要操作是依據關鍵字來存儲和析取值。也可以用del來刪除關鍵字:值對。如果用一個存在的關鍵字存儲值，以前為該關鍵字分配的值會被遺忘。試圖從一個不存在的關鍵字中析取值會導致錯誤。
keys()返回由所有關鍵字組成的鏈表，該鏈表順序不定。使用字典的has_key（）方法或in關鍵字可以檢查字典中是否存在某一關鍵字。
>>> tel = {'jack':4088, 'sivan':8888}
>>> tel
{'sivan': 8888, 'jack': 4088}
>>> tel['niky'] = 6666
>>> tel
{'sivan': 8888, 'niky': 6666, 'jack': 4088}
>>> tel['niky']
6666
>>> del tel['jack']
>>> tel
{'sivan': 8888, 'niky': 6666}
>>> tel.keys()
['sivan', 'niky']
>>> tel.has_key('niky')
True
>>> 'niky' in tel
True
>>>
鏈表中存儲關鍵字-值對元組的話，dict()可以從中直接構造字典。關鍵字-值對來自某個特定模式時，可以用鏈表推導式簡單的生成關鍵字-值鏈表。
>>> dict([('sape',4139),('guido',4127),('jack',4098)])
{'sape': 4139, 'jack': 4098, 'guido': 4127}
>>> dict([(x,x**2) for x in (2,4,6)])
{2: 4, 4: 16, 6: 36}
>>> [(x,x**2) for x in (2,4,6)]
[(2, 4), (4, 16), (6, 36)]
>>>
使用簡單字符串作為關鍵字的話，通常用關鍵字參數更簡單
>>> dict(sape=4139, guido=4127, jack=4098)
{'sape': 4139, 'jack': 4098, 'guido': 4127}
>>>
4.6 循環技術
在字典中循環時，關鍵字和對應的值可以使用iteritems()方法同時解讀出來
>>> knight = {'gallahad':'the pure','robin':'the brave'}
>>> for k, v in knight.iteritems():
... print k, v
...
gallahad the pure
robin the brave
>>>
在序列中循環時，索引位置和對應值可以使用enumerate()函數同時得到。
>>> for i, v in enumerate(['a','b','c']): # 在鏈表中
... print i, v
...
0 a
1 b
2 c
>>> t = 'a', 'b', 'c'
>>> for m, n in enumerate(t): #在元組中
... print m, n
...
0 a
1 b
2 c
>>>
同時循環兩個或更多的序列，可以使用zip()整體解讀。
>>> seq1 = ['1', '2', '3']
>>> seq2 = ['a', 'b', 'c']
>>> for m, n in zip(seq1, seq2):
... print 'L-%s,R-%s' % (m,n)
...
L-1,R-a
L-2,R-b
L-3,R-c
>>>
需要逆向循環序列的話，先正向定位序列，然后調用reversed()函數
>>> for i in reversed(xrange(1,10,2)):
... print i
...
9
7
5
3
1
>>> for i in reversed(range(1,10,2)):
... print i
...
9
7
5
3
1
>>>
要俺排序后的順序循環序列的話，使用sorted()函數，它不改動原序列，而是生成一個新的排好序的序列
>>> seq = ['c','a','b','e','d']
>>> for i in sorted(set(seq)):
... print i
...
a
b
c
d
e
>>>
4.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也稱作短路操作符：它們的參數從左向右解析，一旦結果可以確定就停止。作用域一個普通的非邏輯值時，短路操作符的返回值通常是最后一個變量。
可以把比較或其它邏輯表達式的返回值賦給一個變量。
>>> string1,string2,string3 = '', 'Trondheim', 'Hammer Dance'
>>> non_null = string1 or string2 and string3
>>> non_null
'Hammer Dance'
>>> non_null = string1 or string2 or string3
>>> non_null
'Trondheim'
>>> string4 = 'hello'
>>> non_null = string1 or string2 or string3 or string4
>>> non_null
'Trondheim'
>>> non_null = string1 or string2 or string3 and string4
>>> non_null
'Trondheim'
>>> non_null = string1 and string2 or string3
>>> non_null
'Hammer Dance'
>>>
Python與C不同，在表達式內部不能賦值。所以在Python中不會出現這樣的錯誤：想要在解析式中使用==時誤用了=操作符。
4.8 不同序列類型的比較
序列對象可以與相同類型的其它對象比較。比較操作按字典序列進行：首先比較前兩個元素，如果不同，就決定了比較的結果；如果相同，就比較厚兩個元素，依此類推，直到所有序列都完成比較。如果兩個元素本身就是同樣類型的序列，就遞歸字典序比較。如果兩個序列的所有子項都相等，就認為序列相等。如果一個序列是另一個序列的初始子序列，較短的一個序列就小于另一個。字符串的字典序按照單字符的ASCII順序。
>>> seq1 = 1, 2, 3
>>> seq2 = 1, 2, 5
>>> print seq1 < seq2
True
>>> seq3 = [1, 2, 3]
>>> seq4 = [1, 2, 5]
>>> print seq3 < seq4
True
>>> seq5 = 1, 2, 3
>>> seq6 = 1.0, 2.0, 3.0
>>> print seq5 == seq6
True
>>> print (1, 2, ('aa', 'ab')) < (1, 2, ('abc', 'a'), 4)
True
>>>
不同類型的對象比較是合法的。輸出結果是確定而非任意的：類型按它們的名字排序。因此，一個鏈表list總是小于一個字符串string，一個字符串string總是小于一個元組等等。數值比較時會統一它們的數據類型，所以0等于0.0，等等。