转 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的元素链表。

如:

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->1 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)

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->1 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语句，然后推导出一个链表，如：

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->1 [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语句

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

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->1a = 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() 函数。如：

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->1 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表，是以键值来保存的，键必须是不可变的，一般是字符串或者数字，也可以是只包含字符串或数字的元组，假如元组中包含了可变对象，那该元组不能作为键。

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->1 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()方法同时读出来。

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->1 h = {1:1, 2:2}
2 for k,v in h.iteritems():
3  print k,v
4 
5 

 

在序列中循环时，索引位置和对应值可以使用enumerate()函数同时读出来。

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->1 for i,v in enumerate(['a','b','c'])
2  print i,v
3
4

 

同时循环多个序列，可以使用zip()整体解读。

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->1 a = [1,2,3]
2 b = [2,4,6]
3 for v1,v2 in zip(a,b):
4  print v1,v2

 

需要逆向循环序列，需要先正向定位序列，再调用reversed()函数。

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->1 for i in reversed(range(1,100))
2  print i
3 
4 

 

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

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->1 for i in sorted([1,3,2,5,9,7])
2  print i
3 
4