- 論壇徽章:
- 1
|
Python 指南
5. 數(shù)據(jù)結(jié)構(gòu)
本章節(jié)深入講述一些你已經(jīng)學(xué)習(xí)過的東西,并且還加入了新的內(nèi)容。
5.1 深入鏈表
鏈表類型有很多方法,這里是鏈表類型的所有方法:
append(
x)
把一個(gè)元素添加到鏈表的結(jié)尾,相當(dāng)于 a[len(a):] = [x]。
extend(
L)
通過添加指定鏈表的所有元素來擴(kuò)充鏈表,相當(dāng)于 a[len(a):] = L 。
insert(
i, x)
在指定位置插入一個(gè)元素。第一個(gè)參數(shù)是準(zhǔn)備插入到其前面的那個(gè)元素的索引,例如 a.insert(0, x) 會(huì)插入到整個(gè)鏈表之前,而 a.insert(len(a), x) 相當(dāng)于 a.append(x)。
remove(
x)
刪除鏈表中值為x的第一個(gè)元素。如果沒有這樣的元素,就會(huì)返回一個(gè)錯(cuò)誤。
pop(
)
從鏈表的指定位置刪除元素,并將其返回。如果沒有指定索引,a.pop() 返回最后一個(gè)元素。元素隨即從鏈表中被刪除。(方法中i兩邊的方括號(hào)表示這個(gè)參數(shù)是可選的,而不是要求你輸入一對(duì)方括號(hào),你會(huì)經(jīng)常在Python 庫參考手冊(cè)中遇到這樣的標(biāo)記。)
index(
x)
返回鏈表中第一個(gè)值為x的元素的索引。如果沒有匹配的元素就會(huì)返回一個(gè)錯(cuò)誤。
count(
x)
返回x在鏈表中出現(xiàn)的次數(shù)。
sort(
)
對(duì)鏈表中的元素進(jìn)行適當(dāng)?shù)呐判颉?br />
reverse(
)
倒排鏈表中的元素。
下面這個(gè)示例演示了鏈表的大部分方法:
>;>;>; a = [66.6, 333, 333, 1, 1234.5]
>;>;>; print a.count(333), a.count(66.6), a.count('x')
2 1 0
>;>;>; a.insert(2, -1)
>;>;>; a.append(333)
>;>;>; a
[66.6, 333, -1, 333, 1, 1234.5, 333]
>;>;>; a.index(333)
1
>;>;>; a.remove(333)
>;>;>; a
[66.6, -1, 333, 1, 1234.5, 333]
>;>;>; a.reverse()
>;>;>; a
[333, 1234.5, 1, 333, -1, 66.6]
>;>;>; a.sort()
>;>;>; a
[-1, 1, 66.6, 333, 333, 1234.5]
5.1.1 把鏈表當(dāng)作堆棧使用
鏈表方法使得鏈表可以很方便的做為一個(gè)堆棧來使用,堆棧是這樣的數(shù)據(jù)結(jié)構(gòu),最先進(jìn)入的元素最后一個(gè)被釋放(后進(jìn)先出)。用 append() 方法可以把一個(gè)元素添加到堆棧頂。用不指定索引的 pop() 方法可以把一個(gè)元素從堆棧頂釋放出來。例如:
>;>;>; 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 把鏈表當(dāng)作隊(duì)列使用
你也可以把鏈表當(dāng)做隊(duì)列使用,隊(duì)列是這樣的數(shù)據(jù)結(jié)構(gòu),最先進(jìn)入的元素最先釋放(先進(jìn)先出)。使用 append()方法可以把元素添加到隊(duì)列最后,以0為參數(shù)調(diào)用 pop() 方法可以把最先進(jìn)入的元素釋放出來。例如:
>;>;>; queue = ["Eric", "John", "Michael"]
>;>;>; queue.append("Terry" # Terry arrives
>;>;>; queue.append("Graham" # Graham arrives
>;>;>; queue.pop(0)
'Eric'
>;>;>; queue.pop(0)
'John'
>;>;>; queue
['Michael', 'Terry', 'Graham']
5.1.3 函數(shù)化編程工具
對(duì)于鏈表來講,有三個(gè)內(nèi)置函數(shù)非常有用:filter(), map(), 和 reduce()。
“filter(function, sequence)” 返回一個(gè)序列(sequence),包括了給定序列中所有調(diào)用function(item)后返回值為true的元素。(如果可能的話,會(huì)返回相同的類型)。例如,以下程序可以計(jì)算部分素?cái)?shù):
>;>;>; 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)” 為每一個(gè)元素依次調(diào)用 function(item) 并將返回值組成一個(gè)鏈表返回。例如,以下程序計(jì)算立方:
>;>;>; def cube(x): return x*x*x
...
>;>;>; map(cube, range(1, 11))
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]
可以傳入多個(gè)序列,函數(shù)也必須要有對(duì)應(yīng)數(shù)量的參數(shù),執(zhí)行時(shí)會(huì)依次用各序列上對(duì)應(yīng)的元素來調(diào)用函數(shù)(如果某些序列比其它的短,就用None來代替)。如果把None做為一個(gè)函數(shù)傳入,則直接返回參數(shù)做為替代。
組合這兩種情況,我們會(huì)發(fā)現(xiàn)“map(None, list1, list2)”是把一對(duì)序列變成元素對(duì)序列的便捷方式。例如:
>;>;>; seq = range(
>;>;>; def square(x): return x*x
...
>;>;>; map(None, seq, map(square, seq))
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25), (6, 36), (7, 49)]
"reduce(func, sequence)" 返回一個(gè)單值,它是這樣構(gòu)造的:首先以序列的前兩個(gè)元素調(diào)用函數(shù),再以返回值和第三個(gè)參數(shù)調(diào)用,依次執(zhí)行下去。例如,以下程序計(jì)算1到10的整數(shù)之和:
>;>;>; def add(x,y): return x+y
...
>;>;>; reduce(add, range(1, 11))
55
如果序列中只有一個(gè)元素,就返回它,如果序列是空的,就拋出一個(gè)異常。
可以傳入第三個(gè)參數(shù)做為初始值。如果序列是空的,就返回初始值,否則函數(shù)會(huì)先接收初始值和序列的第一個(gè)元素,然后是返回值和下一個(gè)元素,依此類推。例如:
>;>;>; def sum(seq):
... def add(x,y): return x+y
... return reduce(add, seq, 0)
...
>;>;>; sum(range(1, 11))
55
>;>;>; sum([])
0
不要像示例中這樣定義 sum():因?yàn)楹嫌?jì)數(shù)值是一個(gè)通用的需求,在新的2.3版中,提供了內(nèi)置的 sum(sequence) 函數(shù)。
5.1.4 鏈表推導(dǎo)式
鏈表推導(dǎo)式提供了一個(gè)創(chuàng)建鏈表的簡單途徑,無需使用 map(), filter() 以及 lambda。返回鏈表的定義通常要比創(chuàng)建這些鏈表更清晰。每一個(gè)鏈表推導(dǎo)式包括在一個(gè)for語句之后的表達(dá)式,零或多個(gè)for或if語句。返回值是由for或if子句之后的表達(dá)式得到的元素組成的鏈表。如果想要得到一個(gè)元組,必須要加上括號(hào)。
>;>;>; 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 >; 3]
[12, 18]
>;>;>; [3*x for x in vec if x < 2]
[]
>;>;>; [[x,x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]
>;>;>; [x, x**2 for x in vec] # error - parens required for tuples
File "<stdin>;", line 1, in ?
[x, x**2 for x in vec]
^
SyntaxError: invalid syntax
>;>;>; [(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+y for x in vec1 for y in vec2]
[6, 5, -7, 8, 7, -5, 10, 9, -3]
>;>;>; [vec1*vec2 for i in range(len(vec1))]
[8, 12, -54]
為使鏈表推導(dǎo)式匹配for循環(huán)的行為,可以在推導(dǎo)之外保留循環(huán)變量:
>;>;>; x = 100 # this gets overwritten
>;>;>; [x**3 for x in range(5)]
[0, 1, 8, 27, 64]
>;>;>; x # the final value for range(5)
4
5.2 del 語句
有一個(gè)方法可從鏈表中刪除指定索引的元素:del語句。這個(gè)方法也可以從鏈表中刪除切片(之前我們是把一個(gè)空鏈表賦給切片)。例如:
>;>;>; a = [-1, 1, 66.6, 333, 333, 1234.5]
>;>;>; del a[0]
>;>;>; a
[1, 66.6, 333, 333, 1234.5]
>;>;>; del a[2]
>;>;>; a
[1, 66.6, 1234.5]
del 也可以用于刪除整個(gè)變量:
>;>;>; del a
此后再引用這個(gè)名字會(huì)發(fā)生錯(cuò)誤(至少要到給它賦另一個(gè)值為止)。后面我們還會(huì)發(fā)現(xiàn)del的其它用法。
5.3 元組(Tuples)和序列(Sequences )
我們知道鏈表和字符串有很多通用的屬性,例如索引和切片操作。它們是序列類型中的兩種。因?yàn)镻ython是一個(gè)在不停進(jìn)化的語言,也可以加入其它的序列類型,這里有另一種標(biāo)準(zhǔn)序列類型:元組。
一個(gè)元組由數(shù)個(gè)逗號(hào)分隔的值組成,例如:
>;>;>; 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))
如你所見,元組在輸出時(shí)總是有括號(hào)的,以便于正確表達(dá)嵌套結(jié)構(gòu)。在輸入時(shí)可能有或沒有括號(hào)都可以,不過經(jīng)常括號(hào)都是必須的(如果元組是一個(gè)更大的表達(dá)式的一部分)。
元組有很多用途。例如(x, y)坐標(biāo)點(diǎn),數(shù)據(jù)庫中的員工記錄等等。元組就像字符串,不可改變:不能給元組的一個(gè)獨(dú)立的元素賦值(盡管你可以通過聯(lián)接和切片來模仿)。也可以通過包含可變對(duì)象來創(chuàng)建元組,例如鏈表。
一個(gè)特殊的問題是構(gòu)造包含零個(gè)或一個(gè)元素的元組:為了適應(yīng)這種情況,語法上有一些額外的改變。一對(duì)空的括號(hào)可以創(chuàng)建空元組;要?jiǎng)?chuàng)建一個(gè)單元素元組可以在值后面跟一個(gè)逗號(hào)(在括號(hào)中放入一個(gè)單值是不夠的)。丑陋,但是有效。例如:
>;>;>; empty = ()
>;>;>; singleton = 'hello', # <-- note trailing comma
>;>;>; len(empty)
0
>;>;>; len(singleton)
1
>;>;>; singleton
('hello',)
語句 t = 12345, 54321, 'hello!' 是元組封裝(sequence packing)的一個(gè)例子:值 12345, 54321 和 'hello!' 被封裝進(jìn)元組。其逆操作可能是這樣:
>;>;>; x, y, z = t
這個(gè)調(diào)用被稱為序列拆封非常合適。序列拆封要求左側(cè)的變量數(shù)目與序列的元素個(gè)數(shù)相同。要注意的是可變參數(shù)(multiple assignment
)其實(shí)只是元組封裝和序列拆封的一個(gè)結(jié)合!
這里有一點(diǎn)不對(duì)稱:封裝多重參數(shù)通常會(huì)創(chuàng)建一個(gè)元組,而拆封操作可以作用于任何序列。
5.4 字典(Dictionaries)
另一個(gè)非常有用的Python內(nèi)建數(shù)據(jù)類型是字典(Dictionaries)。字典在某些語言中可能稱為“聯(lián)合內(nèi)存”(``associative memories'')或“聯(lián)合數(shù)組”(``associative arrays'')。序列是以連續(xù)的整數(shù)為索引,與此不同的是,字典以關(guān)鍵字為索引,關(guān)鍵字可以是任意不可變類型,通常用字符串或數(shù)值。如果元組中只包含字符串和數(shù)字,它可以做為關(guān)鍵字,如果它直接或間接的包含了可變對(duì)象,就不能當(dāng)做關(guān)鍵字。不能用鏈表做關(guān)鍵字,因?yàn)殒湵砜梢杂盟鼈兊?append() 和 extend() 方法,或者用切片、或者通過檢索變量來即時(shí)改變。
理解字典的最佳方式是把它看做無序的關(guān)鍵字:值對(duì)( key:value pairs )集合,關(guān)鍵字必須是互不相同的(在同一個(gè)字典之內(nèi))。一對(duì)大括號(hào)創(chuàng)建一個(gè)空的字典:{}。初始化鏈表時(shí),在大括號(hào)內(nèi)放置一組逗號(hào)分隔的關(guān)鍵字:值對(duì),這也是字典輸出的方式。
字典的主要操作是依據(jù)關(guān)鍵字來存儲(chǔ)和析取值。也可以用del來刪除關(guān)鍵字:值對(duì)。如果你用一個(gè)已經(jīng)存在的關(guān)鍵字存儲(chǔ)值,以前為該關(guān)鍵字分配的值就會(huì)被遺忘。試圖析取從一個(gè)不存在的關(guān)鍵字中讀取值會(huì)導(dǎo)致錯(cuò)誤。
字典的keys() 方法返回由所有關(guān)鍵字組成的鏈表,該鏈表的順序不定(如果你需要它有序,只能調(diào)用關(guān)鍵字鏈表的sort()方法)。使用字典的 has_key() 方法可以檢查字典中是否存在某一關(guān)鍵字。
這是一個(gè)關(guān)于字典應(yīng)用的小示例:
>;>;>; tel = {'jack': 4098, 'sape': 4139}
>;>;>; tel['guido'] = 4127
>;>;>; tel
{'sape': 4139, 'guido': 4127, 'jack': 4098}
>;>;>; tel['jack']
4098
>;>;>; del tel['sape']
>;>;>; tel['irv'] = 4127
>;>;>; tel
{'guido': 4127, 'irv': 4127, 'jack': 4098}
>;>;>; tel.keys()
['guido', 'irv', 'jack']
>;>;>; tel.has_key('guido')
True
鏈表中存儲(chǔ)關(guān)鍵字-值對(duì)元組的話,字典可以從中直接構(gòu)造。關(guān)鍵字-值對(duì)來自一個(gè)模式時(shí),可以用鏈表推導(dǎo)式簡單的表達(dá)關(guān)鍵字-值鏈表。
>;>;>; dict([('sape', 4139), ('guido', 4127), ('jack', 409 ])
{'sape': 4139, 'jack': 4098, 'guido': 4127}
>;>;>; dict([(x, x**2) for x in vec]) # use a list comprehension
{2: 4, 4: 16, 6: 36}
5.5 循環(huán)技巧
在字典中循環(huán)時(shí),關(guān)鍵字和對(duì)應(yīng)的值可以使用 items() 方法同時(shí)解讀出來。
>;>;>; knights = {'gallahad': 'the pure', 'robin': 'the brave'}
>;>;>; for k, v in knights.items():
... print k, v
...
gallahad the pure
robin the brave
在序列中循環(huán)時(shí),索引位置和對(duì)應(yīng)值可以使用 enumerate() 函數(shù)同時(shí)得到。
>;>;>; for i, v in enumerate(['tic', 'tac', 'toe']):
... print i, v
...
0 tic
1 tac
2 toe
同時(shí)循環(huán)兩個(gè)或更多的序列,可以使用 zip() 整體解讀。
>;>;>; questions = ['name', 'quest', 'favorite color']
>;>;>; answers = ['lancelot', 'the holy grail', 'blue']
>;>;>; for q, a in zip(questions, answers):
... print 'What is your %s? It is %s.' % (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.
5.6 深入條件控制
用于while和if語句的條件包括了比較之外的操作符。
in和not比較操作符審核值是否在一個(gè)區(qū)間之內(nèi)。操作符is和is not比較兩個(gè)對(duì)象是否相同;這只和諸如鏈表這樣的可變對(duì)象有關(guān)。所有的比較操作符具有相同的優(yōu)先級(jí),低于所有的數(shù)值操作。
比較操作可以傳遞。例如 a < b == c 審核是否a小于b并b等于c。
比較操作可以通過邏輯操作符and和or組合,比較的結(jié)果可以用not來取反義。這些操作符的優(yōu)先級(jí)又低于比較操作符,在它們之中,not具有最高的優(yōu)先級(jí),or的優(yōu)先組最低,所以A and not B or C 等于 (A and (not B)) or C。當(dāng)然,表達(dá)式可以用期望的方式表示。
邏輯操作符and 和or 也稱作短路操作符:它們的參數(shù)從左向右解析,一旦結(jié)果可以確定就停止。例如,如果A和C為真而B為假,A and B and C 不會(huì)解析C。作用于一個(gè)普通的非邏輯值時(shí),短路操作符的返回值通常是最后一個(gè)變量。
可以把比較或其它邏輯表達(dá)式的返回值賦給一個(gè)變量,例如:
>;>;>; string1, string2, string3 = '', 'Trondheim', 'Hammer Dance'
>;>;>; non_null = string1 or string2 or string3
>;>;>; non_null
'Trondheim'
需要注意的是Python與C不同,內(nèi)部表達(dá)式不能分配值。C 程序員經(jīng)常對(duì)此抱怨,不過它避免了一類在C程序中司空見慣的錯(cuò)誤:想要在解析式中使==時(shí)誤用了=操作符。
5.7 比較序列和其它類型
序列對(duì)象可以與相同類型的其它對(duì)象比較。比較操作按字典序進(jìn)行:首先比較前兩個(gè)元素,如果不同,就決定了比較的結(jié)果;如果相同,就比較后兩個(gè)元素,依此類推,直到所有序列都完成比較。如果兩個(gè)元素本身就是同樣類型的序列,就遞歸字典序比較。如果兩個(gè)序列的所有子項(xiàng)都相等,就認(rèn)為序列相等。如果一個(gè)序列是另一個(gè)序列的初始子序列,較短的一個(gè)序列就小于另一個(gè)。字符串的字典序按照單字符的ASCII順序。下面是同類型序列之間比較的一些例子:
(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)
需要注意的是不同類型的對(duì)象比較是合法的。輸出結(jié)果是確定而非任意的:類型按它們的名字排序。因而,一個(gè)鏈表(list)總是小于一個(gè)字符串(string),一個(gè)字符串(string)總是小于一個(gè)元組(tuple)等等。數(shù)值類型比較時(shí)會(huì)統(tǒng)一它們的數(shù)據(jù)類型,所以0等于0.0,等等。5.1 |
|