Python数据结构

1 列表（List）

1.1 创建列表

在 Python 中，列表是由一系元素按特定顺序构成的数据序列，这就意味着如果我们定义一个列表类型的变量，可以用它来保存多个数据。在 Python 中，可以使用[ ]字面量语法来定义列表，列表中的多个元素用逗号进行分隔，代码如下所示：

items1 = [35, 12, 99, 68, 55, 35, 87]
items2 = ['Python', 'Java', 'Go', 'Kotlin']
items3 = [100, 12.3, 'Python', True]
print(items1)  # 结果为[35, 12, 99, 68, 55, 35, 87]
print(items2)  # 结果为['Python', 'Java', 'Go', 'Kotlin']
print(items3)  # 结果为[100, 12.3, 'Python', True]

注意：列表中可以有重复元素，例如items1中的35；列表中可以有不同类型的元素，例如items3中有int类型、float类型、str类型和bool类型的元素，但是我们通常并不建议将不同类型的元素放在同一个列表中，主要是操作起来极为不便。

除此以外，还可以通过 Python 内置的list函数将其他序列变成列表:

items4 = list(range(1, 10))
items5 = list('hello')
print(items4)  # [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(items5)  # ['h', 'e', 'l', 'l', 'o']

1.2 列表运算

可以使用+运算符实现两个列表的拼接，拼接运算会将两个列表中的元素连接起来放到一个列表中，代码如下所示：

list_1 = ['apple','banana','peal','watermelon','peach']
list_2 = [1,2,3]
list_merge = list_1 +list_2
print(list_merge)
#结果为：['apple', 'banana', 'peal', 'watermelon', 'peach', 1, 2, 3]

使用运算符实现列表的重复运算，运算符会将列表元素重复指定的次数

list_1 = [1,2,3]
#重复两次
list_repeat_2 = list_1 *2
#重复三次
list_repeat_3 = list_1 *3

print(list_repeat_2) #[1, 2, 3, 1, 2, 3]
print(list_repeat_3) #[1, 2, 3, 1, 2, 3, 1, 2, 3]

可以使用in或not in运算符判断一个元素在不在列表中

list_1 = ['apple','banana','peal','watermelon','peach']
if 'apple' in list_1:
    print('apple在列表中')
else:
     print('apple不在列表中')
#结果为：apple在列表中

 #还可以直接判断
print('apple' in list_1). #True
print('apple' not in list_1) #False
print('orange' in list_1) #False
print('orange' not in list_1) #True

1.3索引运算

列表中有多个元素，而且元素是按照特定顺序放在列表中的，当我们想操作列表中的某个元素时，可以使用[]运算符，通过在[]中指定元素的位置来访问该元素，这种运算称为索引运算。 需要说明的是，[]的元素位置可以是0到N - 1的整数，也可以是-1到-N的整数，分别称为正向索引和反向索引，其中N代表列表元素的个数。对于正向索引，[0]可以访问列表中的第一个元素，[N - 1]可以访问最后一个元素；对于反向索引，[-1]可以访问列表中的最后一个元素，[-N]可以访问第一个元素，代码如下所示：

#位置索引
list_fruit = ['apple','peach','watermelon','strawberry']
print(list_fruit[0]) #apple
print(list_fruit[1]) #peach
print(list_fruit[-1]) #strawberry
print(list_fruit[-2]) #watermelon
print(list_fruit[-4]) #apple

print('---------------------分割线----------------------')

#在某个位置处替换元素
list_fruit = ['apple','peach','watermelon','strawberry']
list_fruit[1] = 'banana'
print(list_fruit)
#['apple', 'banana', 'watermelon', 'strawberry']

1.4 切片运算

如果希望一次性访问列表中的多个元素，我们可以使用切片运算。切片运算是形如[startstride]的运算符，其中start代表访问列表元素的起始位置，end代表访问列表元素的终止位置（终止位置的元素无法访问），而stride则代表了跨度，简单的说就是位置的增量，比如访问的第一个元素在start位置，那么第二个元素就在start + stride位置，start + stride要小于end，代码实例如下：

list_fruit = ['apple','peach','watermelon','strawberry','banana','durian']
print(list_fruit[0:5:1])#['apple', 'peach', 'watermelon', 'strawberry', 'banana']
print(list_fruit[0:5:2])#['apple', 'watermelon', 'banana']
print(list_fruit[2:3:1])#['watermelon']
print(list_fruit[2:5:1])#['watermelon', 'strawberry', 'banana']
print(list_fruit[2:6:1])#['watermelon', 'strawberry', 'banana', 'durian']
print(list_fruit[-2:-4:-1])#['banana', 'strawberry']

print('---------------------分割线----------------------')
#遍历元素
for fruit in list_fruit:
    print(fruit,end='\t')

1.5 添加和删除

列表是一种可变容器，可变容器指的是我们可以向容器中添加元素、可以从容器移除元素，也可以修改现有容器中的元素。可以使用列表的append方法向列表中追加元素，使用insert方法向列表中插入元素。追加指的是将元素添加到列表的末尾，而插入则是在指定的位置添加新元素，此外可以用列表的remove方法从列表中删除指定元素，需要注意的是，如果要删除的元素并不在列表中，会引发ValueError错误导致程序崩溃，具体代码如下：

list_fruit_1 = ['apple','peach','watermelon','strawberry']
list_fruit_1.append('durian')
print(list_fruit_1)
# ['apple', 'peach', 'watermelon', 'strawberry', 'durian']

list_fruit_2 = ['apple','peach','watermelon','strawberry']
list_fruit_2.insert(1,'durian')
print(list_fruit_2)
#['apple', 'durian', 'peach', 'watermelon', 'strawberry']

list_fruit_3 = ['apple','peach','watermelon','strawberry']
list_fruit_3.remove('apple')
print(list_fruit_3)
#['peach', 'watermelon', 'strawberry']

2 元组（Tuple）

在 Python 语言中，元组也是多个元素按照一定顺序构成的序列。元组和列表的不同之处在于，元组是不可变类型，这就意味着元组类型的变量一旦定义，其中的元素不能再添加或删除，而且元素的值也不能修改。如果试图修改元组中的元素，将引发TypeError错误，导致程序崩溃。

2.1 元组的定义及运算

定义元组通常使用形如(x, y, z)的字面量语法，代码如下：

#定义三元组
cell_1 = (1,2,45)
#定义五元组
cell_2 = ('小明','哈士奇','成都人','宠物')
# 查看变量的类型
print(type(cell_1))  # <class 'tuple'>
print(type(cell_2))  # <class 'tuple'>
# 查看元组中元素的数量
print(len(cell_1)) # 3
print(len(cell_2)) # 4

print('---------------------分割线----------------------')
#元组运算
#拼接运算
print(cell_1 + cell_2) #(1, 2, 45, '小明', '哈士奇', '成都人', '宠物')
#重复运算
print(cell_1 *2) #(1, 2, 45, 1, 2, 45)
print(cell_1 * 1.5) #报错

#索引运算
print(cell_1[0]) # 1
print(cell_1[1]) # 2
print(cell_2[0]) # 小明
print(cell_2[-1]) #宠物
print(cell_2[-4]) #小明


#切片运算
print(cell_2[2:4])#('成都人', '宠物')
print(cell_2[:2])#('小明', '哈士奇')

#从索引0开始，每隔 2 个元素选取一个（即步长为 2），直到序列末尾。
print(cell_2[::2])#('小明', '成都人')


#循环遍历元组中的元素
for item in cell_2:
    print(item,end='\t')
#结果为：小明        哈士奇        成都人        宠物        

2.2 打包和解包操作

把多个用逗号分隔的值赋给一个变量时，多个值会打包成一个元组类型；把一个元组赋值给多个变量时，元组会解包成多个值然后分别赋给对应的变量，如下面的代码所示：

#打包
cell = 1,12,34
print(type(cell)) # <class 'tuple'>
print(cell)       #(1,12,34)

#解包操作
i, j, k = cell
print(i,j,k) #1 12 34

在解包时，如果解包出来的元素个数和变量个数不对应，会引发ValueError异常，错误信息为：too many values to unpack（解包的值太多）或not enough values to unpack（解包的值不足）：

a = 1, 10, 100, 1000 
i, j, k = a             # ValueError: too many values to unpack (expected 3)
i, j, k, l, m, n = a    # ValueError: not enough values to unpack (expected 6, got 4)

2.3 元组和列表的转换

Python 中的元组和列表类型是可以相互转换的，可以通过下面的代码来完成该操作：

list_fruit = ['apple','peach','watermelon','strawberry']
cell = ('apple','peach','watermelon','小明')
# 将元组转换成列表
print(list(cell))
#['apple', 'peach', 'watermelon', '小明']

#将列表转换成元组
print(tuple(list_fruit))
#('apple', 'peach', 'watermelon', 'strawberry')

3 集合

我们把一定范围的、确定的、可以区别的事物当作一个整体来看待，那么这个整体就是集合，集合中的各个事物称为集合的元素。通常，集合需要满足以下要求： 1. 无序性：一个集合中，每个元素的地位都是相同的，元素之间是无序的。 2. 互异性：一个集合中，任何两个元素都是不相同的，即元素在集合中只能出现一次。 3. 确定性：给定一个集合和一个任意元素，该元素要么属这个集合，要么不属于这个集合，二者必居其一，不允许有模棱两可的情况出现。 Python 程序中的集合跟数学上的集合没有什么本质区别，需要强调的是上面所说的无序性和互异性。无序性说明集合中的元素并不像列中的元素那样存在某种次序，可以通过索引运算就能访问任意元素，集合并不支持索引运算。另外，集合的互异性决定了集合中不能有重复元素，这一点也是集合区别于列表的地方，我们无法将重复的元素添加到一个集合中。

3.1 创建集合

在 Python 中，创建集合可以使用{}语法，{}中需要至少需要有一个元素，因为没有元素的{}并不是空集合而是一个空字典，此外，我们还可以使用 Python 内置函数set来创建一个集合，而set并不是一个函数，而是创建集合对象的构造器，创建字典的代码实例如下所示：

set_1 = {1,2,2,3,3,4,5,6,2,2,3,5}
print(set_1)
#{1, 2, 3, 4, 5, 6}

set_2 = {'banana', 'pitaya', 'apple', 'apple', 'banana', 'grape'}
print(set_2)
#{'pitaya', 'grape', 'apple', 'banana'}

set_3 = {num for num in range(1,30) if num %3 ==0 or num % 4 ==0}
#{3, 4, 6, 8, 9, 12, 15, 16, 18, 20, 21, 24, 27, 28}

set_4 = set('hello')
print(set_4)
#{'h', 'e', 'o', 'l'}

set_5 = set([1, 2, 2, 3, 3, 3, 2, 1])
print(set_5)
#{1, 2, 3}

3.2 集合运算

Python 为集合类型提供了非常丰富的运算，主要包括：成员运算、交集运算、并集运算、差集运算、比较运算（相等性、子集、超集）等。

3.2.1 成员运算

可以通过成员运算in和not in 检查元素是否在集合中，代码如下：

set_1 = {'banana', 'pitaya', 'apple', 'apple', 'banana', 'grape'}
print('banana' in set_1) #True
print('banana' not in set_1) #False
print('peach' in set_1) #False
print('peach' not in set_1) #True

3.2.2 二元运算

集合的二元运算主要指集合的交集、并集、差集、对称差等运算，这些运算可以通过运算符来实现，也可以通过集合类型的方法来实现，代码如下所示：

set1 = {1, 2, 3, 4, 5, 6, 7}
set2 = {2, 4, 6, 8, 10}

# 交集
print(set1 & set2)                      # {2, 4, 6}
print(set1.intersection(set2))          # {2, 4, 6}

# 并集
print(set1 | set2)                      # {1, 2, 3, 4, 5, 6, 7, 8, 10}
print(set1.union(set2))                 # {1, 2, 3, 4, 5, 6, 7, 8, 10}

# 差集
print(set1 - set2)                      # {1, 3, 5, 7}
print(set1.difference(set2))            # {1, 3, 5, 7}

# 对称差，指集合的并集减去集合的交集
print(set1 ^ set2)                      # {1, 3, 5, 7, 8, 10}
print(set1.symmetric_difference(set2))  # {1, 3, 5, 7, 8, 10}

3.2.3 比较运算

两个集合可以用==和!=进行相等性判断，如果两个集合中的元素完全相同，那么==比较的结果就是True，否则就是False。如果集合A的任意一个元素都是集合B的元素，那么集合A称为集合B的子集，Python 为集合类型提供了判断子集和超集的运算符，即的<、<=、>、>=这些运算符，代码如下所示：

set1 = {1, 3, 5}
set2 = {1, 2, 3, 4, 5}
set3 = {5, 4, 3, 2, 1}

print(set1 < set2)   # True
print(set1 <= set2)  # True
print(set2 < set3)   # False
print(set2 <= set3)  # True
print(set2 > set1)   # True
print(set2 == set3)  # True

3.3 集合的方法

可以通过.add()、.discard()、clear()等方法实现向集合添加元素或从集合中删除元素，代码如下：

set_1 = {3,4,56,89}

#增加元素
set_1.add(999)
set_1.add(888)
print(set_1)  #{3, 4, 999, 888, 56, 89}

#删掉元素
set_1.discard(999)
print(set_1) #{3, 4, 888, 56, 89}

#清空元素
set_1.clear()
print(set_1) #set()

4 字典（Dictionary）

4.1 创建和使用字典

Python 中创建字典可以使用{}语法，与集合创建方法相似，但是字典的{}中的元素是以键值对的形式存在的，每个元素由:分隔的两个值构成，:前面是键，:后面是值，代码如下所示：

# 创建字典
person = {'name':'小明',
          'age':'17岁',
          'height':'185cm',
          'weight':'150斤',
          'phone_number':123456}
print(person)

#结果为：{'name': '小明', 'age': '17岁', 'height': '185cm', 'weight': '150斤', 'phone_number': 123456}

4.2 字典的运算

对于字典类型来说，成员运算和索引运算肯定是很重要的，前者可以判定指定的键在不在字典中，后者可以通过键访问对应的值或者向字典中添加新的键值对，值得注意的是，字典的索引不同于列表的索引，列表中的元素因为有属于自己有序号，所以列表的索引是一个整数；字典中因为保存的是键值对，所以字典需要用键去索引对应的值，例如：

person = {'name':'小明',
          'age':'17岁',
          'height':'185cm',
          'weight':'150斤',
          'phone_number':123456}

#成员运算 in、not in
print('name' in person) #True
print('name' not in person) #False
print('address' not in person) #True
print('address' in person) #Fasle

#索引运算
print(person['name']) #小明
print(person['age'])  #17岁

person['age'] = '25岁'
print(person['age']) #25岁


#遍历字典
for key in person:
    print(key, person[key])
'''
输出结果为：name 小明
age 25岁
height 185cm
weight 150斤
phone_number 123456
'''

for key, value in person.items():
    print(key, value)
 '''
输出结果为：name 小明
age 25岁
height 185cm
weight 150斤
phone_number 123456
'''

4.3 字典的方法

字典类型的方法基本上都跟字典的键值对操作相关，其中get方法可以通过键来获取对应的值。跟索引运算不同的是，get方法在字典中没有指定的键时不会产生异常，而是返回None或指定的默认值，代码如下所示：

person = {'name':'小明',
          'age':'17岁',
          'height':'185cm',
          'weight':'150斤',
          'phone_number':123456}
 print(person.get('name')) #小明
 print(person.get('sex'))  #None

字典的update方法实现两个字典的合并操作。例如，有两个字典x和y，当执行x.update(y)操作时，x跟y相同的键对应的值会被y中的值更新，而y中有但x中没有的键值对会直接添加到x中，代码如下所示：

person1 = {'name': '小明', 'age': 55, 'height': 178}
person2 = {'age': 25, 'addr': '成都市武侯区天府三街地铁1号线'}
person1.update(person2)
print(person1)  # {'name': '小明', 'age': 25, 'height': 178, 'addr': '成都市武侯区天府三街地铁1号线'}

需要获取字典中所有的键，可以使用keys方法；如果需要获取字典中所有的值，可以使用values方法；字典还有一个名为items的方法，它会将键和值组装成二元组，通过该方法来遍历字典中的元素也是非常方便的，代码如下：

person = {'name':'小明',
          'age':'17岁',
          'height':'185cm',
          'weight':'150斤',
          'phone_number':123456}
print(person.keys()) #dict_keys(['name', 'age', 'height', 'weight', 'phone_number'])
print(person.values()) #dict_values(['小明', '17岁', '185cm', '150斤', 123456])
print(person.items()) #dict_items([('name', '小明'), ('age', '17岁'), ('height', '185cm'), ('weight', '150斤'), ('phone_number', 123456)])

实践应用

数据结构的选择

1. 列表：当需要有序、可修改的序列时
2. 元组：当数据不应被修改时
3. 字典：当需要键值对映射时
4. 集合：当需要去重或集合运算时

性能考虑

• 列表的查找时间复杂度为O(n)
• 字典和集合的查找时间复杂度为O(1)
• 元组比列表占用更少的内存

练习题

1. 实现一个简单的通讯录系统，使用字典存储联系人信息
2. 编写程序去除列表中的重复元素（使用集合）
3. 实现一个函数，统计文本中各个单词的出现频率（使用字典）

小结

• 掌握Python主要数据结构的特点和用法
• 理解不同数据结构的适用场景
• 能够根据需求选择合适的数据结构
• 掌握各种数据结构的常用操作方法