8  基本数据结构：进阶

前面介绍了常用数据结构的构建，读写数据和遍历等等，这里介绍一些关于数据结构的进阶用法。

8.1 嵌套数据结构

数据结构可以相互嵌套。比如List嵌套List，后面我们会知道这是表示矩阵的一种方式。

a = [[1,2,3],[3,5,1],[6,4,2]] # List of List
a[0] 
[1, 2, 3]

List嵌套Tuple：

b = [('A',2),('B',3),('C',1)]
b[2]
('C', 1)

字典嵌套 List和Tuple：

c = {'A':[1,2,3],'B':(3,4,5),'C':[2,3,4]}
c['B']
(3, 4, 5)

当然嵌套可以多层嵌套下去。

嵌套的数据结构，其取值的方法也和原来一样，按照索引或者key逐级排列即可。

a[0][1]
2
b[1][0]
'B'
c['B'][1]
4

8.2 排序专题

8.2.1 列表

列表的排序很简单

  1. sorted()函数返回一个排序后的新列表，原列表不变。
  2. 列表的.sort()方法，对原列表进行“原地排序”，不返回值，但原列表会改变。
a = [3,2,1,5]
print(sorted(a)) #返回排序后的新列表
print(a) # 注意sorted函数不会改变a
[1, 2, 3, 5]
[3, 2, 1, 5]
a.sort() # 原地排序，会改变a
print(a)
[1, 2, 3, 5]

逆序的话，需要加入reverse=True参数。

a = [2,5,1,3]

print(sorted(a,reverse=True)) # 逆序，sorted返回一个排序好的新列表，不改变原值
print(a) # a保持不变
a.sort(reverse=True) # 逆序，原地排序，这个方法不返回值。
print(a) # a已经被改变
[5, 3, 2, 1]
[2, 5, 1, 3]
[5, 3, 2, 1]

8.2.2 任意排序规则

对于嵌套数据结构和字典等等，我们可以构造任意的排序规则。例如，一个嵌套的List：

a = [['C',1,2],['A',3,1],['B',2,6]]
a
[['C', 1, 2], ['A', 3, 1], ['B', 2, 6]]

我们想根据每个子List的第二个元素来排序，需要用到参数key（上面两种排序方法都适用）

  1. key参数接受一个函数
  2. 这个函数接受List的一个元素，返回一个”可以比较大小的值”（比如一个数字）。

换句话说，你给出一个排序的凭据，要构造一个比较不同子List大小办法，这个办法的结果，体现在你要算出一个可比较的值，如一个数字。

落实到本例，如果只是比较第二个元素的大小，则直接返回第二个元素即可。

def get_2nd_item(x):
    return x[1]

sorted(a, key = get_2nd_item)
[['C', 1, 2], ['B', 2, 6], ['A', 3, 1]]

也可以采用匿名函数，见前面的章节。

# 写成匿名函数的版本
sorted(a, key = lambda x:x[1]) 
[['C', 1, 2], ['B', 2, 6], ['A', 3, 1]]

有如，比如你要根据 “第2和第3个元素的和”来排序，你只要构造一个函数，返回这两者的和即可。

def sum_2_3(x):
    return x[1]+x[2]

print(a[0]) # 测试一下是否正常

sorted(a, key = sum_2_3)
['C', 1, 2]
[['C', 1, 2], ['A', 3, 1], ['B', 2, 6]]
# 写成匿名函数的版本
sorted(a, key = lambda x:x[1]+x[2])
[['C', 1, 2], ['A', 3, 1], ['B', 2, 6]]

8.2.3 字典排序

前面说过，字典大约也可以“看成”一个嵌套数据结构，以前面的字典c为例

c.items()
dict_items([('A', [1, 2, 3]), ('B', (3, 4, 5)), ('C', [2, 3, 4])])

注意到value是一个3个元素的List或者Tuple，我们要根据value的第一个元素来排序。

sorted_items = sorted(c.items(), key= lambda x:x[1][0])
sorted_items
[('A', [1, 2, 3]), ('C', [2, 3, 4]), ('B', (3, 4, 5))]

注意，其中x是一个字典中的item，即一个(key,value)对。那么x[0]就是key，x[1]就是value，x[1][0]就是value中的第一个元素了。

注意上面得到的是一个List of Tuple，即单纯的嵌套数据结构。如果需要转为字典，调用dict()函数即可（简单类型转换）

dict(sorted(c.items(), key= lambda x:x[1][0]))
{'A': [1, 2, 3], 'C': [2, 3, 4], 'B': (3, 4, 5)}

8.3 其他

8.3.1 枚举 enumerate函数

enumerate()函数一般用于遍历一个可迭代对象的时候，同时还可以获得对应的索引。

或者说，你遍历一个a_list = [‘a’,‘b’,‘c’]的时候，还想获得当前值是“第几个”，我们用以下循环

for i,value in enumerate(a_list):

a_list = list('apple')

for i,value in enumerate(a_list):
    print(i,value) # 此时，i就表示遍历过程中的索引
0 a
1 p
2 p
3 l
4 e

显然，和字典.items()类似，enumerate(a_list)也是获得可以 [(index, value), (index, value), ...]的序列。

注：enumerate(a_list)返回一个生成器，当你要具体访问里面的值的时候，才会临时生成某个(index,value)，如果要打印出来看，需要转为List。（当然也可以转为字典）

# 把a_list，转为带有索引的list
print(list(enumerate(a_list)))

# 把a_list，转为以index为key的字典
print(dict(enumerate(a_list)))
[(0, 'a'), (1, 'p'), (2, 'p'), (3, 'l'), (4, 'e')]
{0: 'a', 1: 'p', 2: 'p', 3: 'l', 4: 'e'}

进一步，可以获得“某个元素的索引”，比如问’p’是几号元素？

a_list = list('apple')
[i for i,value in enumerate(a_list) if value == 'p']
[1, 2]

8.3.2 zip函数

把几个序列结构，每个元素对位组合，形成一个Tuple，再组成一个List。

注意：zip以最短的元素为主。

list1= ('a', 'b', 'c')
list2 = [1, 2, 3, 4]

print(list(zip(list1,list2)))
print(list(zip(list1,list2,list1))) # 可以组合不止2个序列
[('a', 1), ('b', 2), ('c', 3)]
[('a', 1, 'a'), ('b', 2, 'b'), ('c', 3, 'c')]

稍微发散一下，这不就是一个Dict的结构吗？所以可以直接转为字典。

dict(zip(list1,list2))
{'a': 1, 'b': 2, 'c': 3}

当然也可以多序列循环

for i,j in zip(list1,list2):
    print(i,j)
a 1
b 2
c 3

回忆函数的拆包操作，我把一个List（等）传递给一个函数，前面加一个*，就会自动把List中的元素逐一拆出来，传递给函数。

def add(a,b):
    return a + b

add(*[1,2]) # 对[1,2]进行拆包：按顺序传递给a和b
3

对于zip函数也可以这样做，比如你有一个序列

a_list = [(1, 'one'), (2, 'two'), (3, 'three')]

你希望第一位的元素组成序列，第二位的元素组成一个序列….

a_list = [(1, 'one'), (2, 'two'), (3, 'three')]
list(zip(*a_list))
[(1, 2, 3), ('one', 'two', 'three')]
x,y = list(zip(*a_list)) # 如果要赋值的话，可以这么写

8.3.3 pop函数

pop()函数用于“返回并移除一个元素”，近似理解就是把队尾的一个元素“拿出来”。

对于List，默认是最后一个元素（队尾）。

a = list('apple')

print(a.pop()) # 获取最后个元素，并删除。
print(a) # 最后一个元素已经删除
e
['a', 'p', 'p', 'l']

也可以指定index，比如拿出1号元素。

print(a.pop(1))
print(a)
p
['a', 'p', 'l']

对于Dic，需要指定key，pop()会返回value，并移除这个key。

b = {'a': 1, 'b': 2, 'c': 3}

print(b.pop('b')) # 获取'b'对应的value，并删除'b'。
print(b) # 'b'已经删除
2
{'a': 1, 'c': 3}

8.4 更多练习

以下是同学的姓名，学号和考试分数的数据

names = ["Alice", "Bob", "Clare"]
ids = [101,102,103]
scores = [85, 92, 78]
  1. 构建一个字典data，其中key是名字，value是另一个字典key和value是id和score以及对应的值。

构建出来大概是这样： {'Alice': {'id': 1, 'score': 85}, ...}

  1. 对data按分数排序，高分的在前面。

  2. 找出分数最高的同学，打印“分数最高的同学是: ??? ，学号是???，分数是： ???。”