python 數據結構

一. 深入鏈表

先來介紹一些鏈表具備的一些常用方法：

append(x) : 把一個元素添加到鏈表的結尾

extend(L) : 將另外一個鏈表合并到該鏈表中

insert(i,x) : 插入一個元素到指定位置的前面

remove(x) : 刪除鏈表中第一個值為x的元素 如果沒有這樣的元素 則返回錯誤

pop([i]) : 刪除鏈表中索引為i的元素，并將其返回，如果索引i大于鏈表的最大索引，則返回錯誤，如不提供索引，則刪除并返回最后一個元素

index(x) : 返回鏈表中第一個值為x的元素的索引

count(x) : 返回x在鏈表中出現的次數

sort() : 對鏈表中的元素就地排序??? # 就地的意思就是ruby中以!結尾的函數

reverse() : 就地倒排

?

1. 如何把鏈表當作堆棧使用

堆棧的特點是先進后出，使用append()壓入，使用pop()彈出

?

2. 如何把鏈表當作隊列使用

隊列的特點是先進先出，使用append()將一個對象排到隊尾，使用pop(0)將第一個對象拉出

?

3. 函數化編程工具

對于鏈表來說，有三個函數作用很大：

(1) filter(function, list)

這個函數是過濾函數，返回list中所有經過function函數運算后返回值為true的元素鏈表。

如:

?ls?=?[1,2,3,4]
2?ls2?=?filter(lambda?x:x>1,ls)
3?print?ls???#[1,2,3,4]
4?print?ls2??#[2,3,4]

注意，filter函數不是一個就地處理函數，而是返回執行結果。

?

(2) map(function, list)

這個函數是依次處理函數，使用function函數依次對list中的元素進行計算，將計算結果們組成一個鏈表返回。

?

(3) reduce(function, list)

?reduce(?lambda?x,y:x+y,?range(1,5)?)#?返回10??因為?[1,2,3,4]??1+2=3?3+3=6?6+4=10
2?
3?

該函數極少應用，可以忽略不看。

?

4. 鏈表推導式

就是在一個表達式或一個函數中后綴if或for語句，然后推導出一個鏈表，如：

?[x*2?for?x?in?range(10)]?#?[0,2,4,6,8,10,12,14,16,18]
2?["lee:"+s?for?s?in?['hi','hallo']]?#?["lee:hi",?"lee:hallo"]
3?[(lambda?x:x*2)(x)?for?x?in?range(10)]?#?結果同第一句?只不過第一句用了表達式?該句用函數

?

二. del語句

作用是刪掉指定列表元素，可以刪掉指定切片部分的元素。

a?=?range(5)
2del?a[0]?#?[1,2,3,4]
3del?a[1,3]?#[1,4]
4del?a?#刪除變量

?

?

三. 元組和序列

元組也是一個復合數據結構，可以將多個元素組織在一起，但不能改變其中某個元素的值。

元組是用()括起來的。

構建空元組的時候直接使用? x = () 即可

構建單元素的元組時要使用 x=1, 或者x=(1,)? 只有一個括號是不行的。

?

四. Sets集合

?sets集合的主要作用是：

可以對列表進行“與運算”，得到兩個列表中共有的元素。

可以對列表進行“或運算”，得到兩個列表擁有的所有元素。

可以對列表進行“異或運算”，得到兩個列表互相沒有的元素。

可以對列表進行“減運算”，可以從一個列表中排除另一個列表擁有的元素。

獲取一個set集合的方法是使用 set() 函數。如：

?s1?=?set(range(0,5))?#?([0,1,2,3,4])
2?s2?=?set(range(3,8))?#?([3,4,5,6,7])
3?s1?-?s2?#([0,1,2])
4?s1?|?s2?#([0,1,2,3,4,5,6,7])
5?s1?&?s2?#([3,4])?
6?s1?^?s2?#([0,1,2,5,6,7])

?

五. 字典

字典就是hash表，是以鍵值來保存的，鍵必須是不可變的，一般是字符串或者數字，也可以是只包含字符串或數字的元組，假如元組中包含了可變對象，那該元組不能作為鍵。

?a?=?(1,)
2?hash?=?{a:a}
3?hash[a]?=?1?#ok
4?a?=?1?#ok
5?print?hash?#{(1,):1}

可以用del來刪除一個? 鍵/值?? 如果對已存在的鍵賦值，會覆蓋該鍵的值。

可使用keys()方法返回鍵的列表，

可使用has_key()方法來查詢是否含有一個鍵。

?

六. 循環技術

在字典循環時，關鍵字和對應的值可以用iteritems()方法同時讀出來。

?h?=?{1:1,?2:2}
2?for?k,v?in?h.iteritems():
3??print?k,v
4?
5?

?

在序列中循環時，索引位置和對應值可以使用enumerate()函數同時讀出來。

?for?i,v?in?enumerate(['a','b','c'])
2??print?i,v
3
4

?

同時循環多個序列，可以使用zip()整體解讀。

?a?=?[1,2,3]
2?b?=?[2,4,6]
3?for?v1,v2?in?zip(a,b):
4??print?v1,v2

?

需要逆向循環序列，需要先正向定位序列，再調用reversed()函數。

?for?i?in?reversed(range(1,100))
2??print?i
3?
4?

?

要按排序后的序列循環，可以使用sorted()先排序

?for?i?in?sorted([1,3,2,5,9,7])
2??print?i
3?
4?