转 python 数据结构

huangfen2002

　　一. 深入链表
　　先来介绍一些链表具备的一些常用方法：
　　append(x) : 把一个元素添加到链表的结尾
　　extend(L) : 将另外一个链表合并到该链表中
　　insert(i,x) : 插入一个元素到指定位置的前面
　　remove(x) : 删除链表中第一个值为x的元素 如果没有这样的元素 则返回错误
　　pop() : 删除链表中索引为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 />-->1 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() 函数。如：
<!--<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