数据结构（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