本文提到的所有内容均是基于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])