Python数据结构--内置数据结构
本文提到的所有内容均是基于Python 2.7，在Python 3.x的环境下可能并不完全适用
什么是数据结构
我们可以看一下在百度百科对于数据结构是怎么定义的：
Data_Structure=(D,R)
其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合。
---来自百度百科
我的理解是：数据结构是对于数据的特定组织形式，具体可分为物理结构和逻辑结构（区别）。
和数据结构经常一起出现的一个词是算法。它们两者之间有什么关系呢？实现一些特定算法是，应该（有时候是必须）采用某些数据结构来简化计算。
知道了以上这些，接下来就一起来看看Python本身自带的数据结构都有哪些吧？
List列表
定义：
a = [1,2,3] #最普通的一个数组
b = [1, 'Hello', 3.1415926] #多种类型混合组成的数组
c = [[[1],[2]],[[3],[4]]] #多层嵌套数组（这里是三层）
访问：
list原则上是循秩访问的，也就是说按下标访问的。
a[0], a[1], a[-1] #访问a的第一个，第二个元素，最后一个元素
a[1:3], a[-3:], a[:], a[:3] #这是list的切片（slice）操作，分别是访问a的第2到3个元素（注意左右标的关系，包含起始位而不包含终止位），访问倒数第3个元素到末尾，访问整个数组，访问第一个元素到第3个元素
a[::2], a[::-1]#分别是访问a的从起始位开始的偶数位元素，逆序访问a的元素
简单总结一下，访问单个元素的时候，直接在 '[]' 中输入需要访问元素的秩（下标）即可，这里的下标包括正常的排序(0,1,2...)和从末尾计数的排序(-1,-2,-3...)，需要注意的是，如果访问的秩并不在list范围内，比如上面的list中的a=[1,2,3]，如果访问a[3]或者a[-6]，就会引发一个IndexError。
访问多个元素时，可以使用切片的方法，list[start, end, step], start和end分别是起始下标（默认值为0和list长度减一），step为访问步长，即每隔几个元素访问一个元素（默认值为1）。需要注意的是，切片时下标越界的话并不会引发任何错误，比如上面的list中的a，如果访问a[1:10000]，和a[-10000:]会返回[2,3]和[1,2,3]而不会引发任何错误。这是和按下标访问时的一个区别。
更新：
#a=[1,2,3]
a[2] = 4 #修改单个元素,此时a=[1,2,4]
a[1:3] = [8,24] #修改多个元素此时a=[1,8,24]
a[1:3] = [1,2,3,4] #a=[1,1,2,3,4]
a.append(1) #a=[1,1,2,3,4,1]
a.extend([1,2,3]) #在a后面添加一个list,a=[1,1,2,3,4,1,1,2,3]
a.insert(0,1) #在a中0的位置上插入1,a=[1,1,1,2,3,4,1,1,2,3]
删除：
#a=[1,2,3]
#类似更新的操作方法
a = a[:1] + a[2:] #a=[1,3] 相当于删除了a[1]
#其他删除方法
#a=[1,2,3]
del a[1] #删除a[1]
a.remove(1) #删除a[1]
a.pop() #弹出a的最后一个元素，和上面两者不同的是，该方法返回值是弹出的元素
其他操作
#a=[1,1,2,3,4]
a.count(1) #计算a中1的个数，返回2
a.index(1) #返回元素1在a中第一次出现的位置下标
a.index(7) #由于a中没有7，故引发ValueError
a.reverse() #a=[4,3,2,1,1]将a逆转
a.sort(), sorted(a) #返回排序好的a 这个方法list.sort(cmp, key, reverse)三个参数为别为比较方法，比较的键，是否逆序，sort和sorted的区别在于一个是对原list排序，而另一个是将排好序的结果返回
len(a) #返回a的长度，这里是5
a*2 #返回[1,1,2,3,4,1,1,2,3,4]
max(a),min(a) #分别返回a中的最大值和最小值，这里是4和1
列表推导式：
a = [x for x in range(3)] #a=[0,1,2]
b = [x for x in range(10) if x%2==1] #b=[1,3,5,7,9]
filter,map,reduce:
a = [1,2,3,4,5,6,7]
b = filter(lambda x: x>3, a) #b=[4,5,6,7]
c = map(lambda x:x*x, a) #c=[1,4,9,16,25,36,49]
d = filter(lambda x,y:x+y, a) #d=28
list去重:
#方法1：利用set，不保证去重之后的结果顺序
a = list(set(a))
#方法2：利用dict，不保证顺序
a = {}.fromkeys(a).keys()
#方法3：利用set，保持顺序
a = list(set(a)).sort(key=a.index)
#列表推导式
b = []
[b.append(i) for i in a and i not in b]
合并两个有序链表：
#方法一：递归法
def _recursion_merge_sort2(l1, l2, tmp):
if len(l1) == 0 or len(l2) == 0:
tmp.extend(l1)
tmp.extend(l2)
return tmp
else:
if l1[0] < l2[0]:
tmp.append(l1[0])
del l1[0]
elif l1[0] >= l2[0]:
tmp.append(l2[0])
del l2[0]
return _recursion_merge_sort2(l1, l2, tmp)
def recursion_merge_sort2(l1, l2):
return _recursion_merge_sort2(l1, l2, [])
#方法二：迭代法
def loop_merge_sort(l1, l2):
tmp = []
while len(l1) > 0 and len(l2) > 0:
if l1[0] < l2[0]:
tmp.append(l1[0])
del l1[0]
else:
tmp.append(l2[0])
del l2[0]
tmp.extend(l1)
tmp.extend(l2)
return tmp
tuple元组
定义&访问：
a = (1, ) #当元组只含一个元素时，
a = (1, 3.14, 'Hello') #元祖中可以包含不同类型的元素
a[0] #返回a的第一个元素
a[0:2] #返回a的第1,2个元素
a[0:2:-1] #返回a的第1，2个元素，并逆序
a.count(1) #返回1
a.index(1) #返回3.14
min(a),max(a) #返回1,3.14
可以发现，元组的定义，访问和list列表几乎一样（除了单个元组声明时需要加逗号）
那么tuple和list有什么区别呢？
区别在于tuple不支持修改，也就是类似于 a[0] = 1 的操作对于元组而言是非法的。不可变的意义在于使tuple内的数据更安全，不可修改。
Wait!元组真的完全不可修改吗？定义上来讲元组内的所有元素一旦定义就不可修改，但如果针对元组内的某一个元素进行修改的话是否可行呢？
a = (1,2,[1,2])
a[2][0] = 3 #a=(1,2,[3, 2])
注意！！！以上操作仅供演示，在元组中的元素不应该进行修改，如果需要频繁的修改，建议使用列表。
dict字典
定义&访问&修改：
a = {1:1, 2:2} #字典是一个key->value的对应关系，原则上key可以是任何不可变类型的值（数字，字符串，元组）
a[1], a[7],a.get(7) #第一个返回1，第二个引发KeyError，第三个返回None，实际中推荐使用get的安全访问方法
a[1] = 3 #a={1:3, 2:2}
a[7] = 7 #a={1:3,2:2,7:7}
a.pop(1) #a={2:2, 7:7}
dict 的优势在于利用了哈希策略，是的对于dict的元素插入，查找速度快（O(1)），弊端在于有一定的空间浪费和无序性。
而list的的插入和查找速度慢于dict（O(n)）,但空间利用率好于dict。
set集合
类似dict，但只有key而没有value，特点是无序性和互异性。
a = set([1,1,2,3]) #返回set([1,2,3])
a.add(4) #set([1,2,3,4])
a.remove(2) #set([1,3,4])
a = set([1,2,3])
b = set([2,3,4])
c = a&b #c = set([2,3])
d = a|b #d = set([1,2,3,4])
