数据结构"/>
2. Python 数据结构
文章目录
- Python 数据结构
- 1.2.1 列表
- 1.2.1.1 查找元素
- 1.2.1.2 修改元素
- 1.2.1.3 增加元素
- 1.2.1.4 删除元素
- 1.2.1.5 小例子
- 1.2.2 元组
- 1.2.3 字典
- 1.2.3.1 增加元素
- 1.2.3.2 删除元素
- 1.2.3.3 查找元素
- 1.2.3.4 修改元素
- 1.2.3.5 小例子
- 1.2.4 集合
- 1.2.4.1 增加元素
- 1.2.4.2 删除元素
- 1.2.4.3 查找元素
- 1.2.4.4 数学操作
- 1.2.5 练习
- 1.2.5.1 列表练习
- 1.2.5.2 字典练习
Python 数据结构
顾名思义，数据结构是能够将数据组合在一起的一种结构。
在数据科学领域，很多情况下需要将数据进行有序排列。例如我们统计了大学某班 50 人的数学成绩，那么创建 50 个变量例如 XiaoMing = 99, XiaoHu = 86 … 无疑是非常繁琐的。这时我们可以通过数据结构整合这些数据，例如在上一节中以方括号标识的列表 [ 99, 86, 77 .... ]，这将会使我们的程序大大简化。
Python 中常用的数据结构有：
- 列表 List: 用于保存有序项集合的变量，以方括号标识。
- 元组 Tuple: 用于保存有序项集合的常量，以圆括号标识。
- 字典 Dict: 用于保存无序（键，值）项集合的变量，以花括号标识。
- 集合 Set: 用于保存无序项集合的变量，以花括号标识。
瑞士计算机科学家 Niklaus Wirth 曾说过 “程序 = 数据结构 + 算法”，这个公式在 40 年后的今天仍然成立。掌握 Python 中常用的数据结构是我们设计程序的一大基石。
在本节中我们将尝试设计一个学生成绩管理系统，实现对学生成绩的增、删、查、改功能。
1.2.1 列表
列表是用于保存有序项集合的变量，通过方括号创建。列表是最容易理解的数据结构，它就像一个任务清单，任务清单的每一项都是一个单独的任务。
下面我们创建一个含有四个整数的列表。
l = [1, 2, 3, 4]
列表支持以下操作：
- 增：通过函数
append可以向列表内增加元素 - 删：通过关键字
del可以删除列表内元素 - 查：通过关键字
[ ]可以查找列表某个位置元素 - 改：通过赋值符号
=可以修改某个位置的元素
列表的优点是：
- 快速向尾部添加元素
- 快速遍历所有元素
- 节省占用计算机内容空间
1.2.1.1 查找元素
我们通过 [ ] 关键字查找列表中某个位置的元素。
例如 l[0] 可以获取列表中首个元素，l[1] 可以获取列表中第 2 个元素。同时它还支持倒序查找，例如 l[-1] 表示倒数第一个元素（末尾的元素）。
## 查找 首个 元素
print(l[0])
## 查找第 2 个元素
print(l[1])
## 查找第 最后 元素
print(l[-1])
## 查找倒数第 2 个元素
print(l[-2])
1
2
4
3
[ ] 关键字也可以通过 “切片” 的形式获取含有多个元素的子列表。
例如 l[0:2] 代表列表从中第 0 个元素 到 第 2 个元素（左闭右开 [ ) ，不包括第 2 个元素）
## 查找第 0 到 第 2 的元素子列表
print(l[0:2])
## 查找第 1 到 最后 的元素子列表
print(l[1:-1])
[1, 2]
[2, 3]
1.2.1.2 修改元素
通过 [ ] 关键字同样可以修改列表中某个位置的元素，类似的它也支持倒序以及切片的形式。
## 修改 首个 元素的值为 -1
l[0] = -1
print(l)
[-1, 2, 3, 4]
## 修改从第 0 到第 2 的元素子列表的值为 [-1, -2]
l[0:2] = [-1, -2]
print(l)
[-1, -2, 3, 4]
1.2.1.3 增加元素
通过 append 函数可以实现向列表尾部添加新的元素。
## 向集合尾部添加元素 5
l.append(5)
print(l)
## 向集合尾部添加元素 6
l.append(6)
print(l)
[-1, -2, 3, 4, 5]
[-1, -2, 3, 4, 5, 6]
1.2.1.4 删除元素
通过 del 关键字可以删除列表某个位置的元素。
## 删除列表 首个 元素
del l[0]
print(l)
## 删除列表 最后一个 元素
del l[-1]
print(l)
[-2, 3, 4, 5, 6]
[-2, 3, 4, 5]
1.2.1.5 小例子
在熟悉了列表的增删查找功能后，我们就可以尝试以此为基础搭建我们的学生成绩管理系统。
Task 1. 在上一次期末考试中，XiaoHu 考了数学 65 分，语文 55 分；XiaoMing 考了数学 80 分，语文92 分；XiaoWei 考了数学 95 分，语文 98 分，以此建立学生成绩管理系统。
Task 2. 在本次期末考试中，XiaoHu 考了数学 95 分，语文 85 分；XiaoMing 考了数学 75 分，语文 71 分；XiaoWei 考了数学 92 分，语文 93 分，以此对之前的成绩进行更新。
Task 3. 由于 XiaoMing 的成绩出现了大幅度下滑，家长决定要 XiaoMing 转学到另一所高中，以此在系统中删除 XiaoMing 的信息。
Task 4. 学校新转来的学生 Cryin 本次考试成绩为 数学 87 分，语文 88 分，在系统中录入 Cryin 的成绩。
## Task 1 建立学生信息管理系统## 首先建立一个 “名字” 列表记录哪个学生在列表的哪个位置。
names = ['XiaoHu', 'XiaoMing', 'XiaoWei']## 根据名字列表的位置分别建立 “语文成绩” “数学成绩列表” 列表。
Math_scores = [65, 80, 95]
Chinese_scores = [55, 92, 98]
## Task 2 根据本次期末考试的成绩更新系统## 首先找到 "XiaoHu" 在哪个位置，更新该位置的成绩
## 通过 for-in 循环遍历名字元素
position = None
count = 0
for name in names:## 找到 XiaoHu 在列表中的位置if name == "XiaoHu":position = countcount = count + 1
## 根据 XiaoHu 在列表中的位置更新成绩
Math_scores[position] = 95
Chinese_scores[position] = 85## 以同样方法更新 XiaoMing 与 XiaoWei 的成绩
position = None
count = 0
for name in names:if name == "XiaoMing":position = countcount = count + 1
Math_scores[position] = 75
Chinese_scores[position] = 71position = None
count = 0
for name in names:if name == "XiaoWei":position = countcount = count + 1
Math_scores[position] = 92
Chinese_scores[position] = 93
print(names)
print(Math_scores)
print(Chinese_scores)
['XiaoHu', 'XiaoMing', 'XiaoWei']
[95, 75, 92]
[85, 71, 93]
## Task 3 删除 XiaoMing 的信息## 首先找到 "XiaoMing" 在哪个位置
## 通过 for-in 循环遍历名字元素
position = None
count = 0
for name in names:## 找到 XiaoMing 在列表中的位置if name == "XiaoMing":position = countcount = count + 1
## 根据 XiaoMing 在列表中的位置删除
del names[position]
del Math_scores[position]
del Chinese_scores[position]
print(names)
print(Math_scores)
print(Chinese_scores)
['XiaoHu', 'XiaoWei']
[95, 92]
[85, 93]
## Task 4 录入 Cryin 的信息names.append('Cryin')
Math_scores.append(87)
Chinese_scores.append(88)
print(names)
print(Math_scores)
print(Chinese_scores)
['XiaoHu', 'XiaoWei', 'Cryin']
[95, 92, 87]
[85, 93, 88]
以上我们就初步实现了学生成绩管理系统，并实现了用户的一些简单需求。可以发现列表的增删改操作相对轻松，但最困难的部分是需要遍历整个列表寻找元素在列表中的位置，这种困难是由列表在计算机中的存储形式决定的。后面我们介绍的数据结构 “字典” 可以用来解决这个问题。
1.2.2 元组
元组与列表具有近乎一样的特性，他们唯一的区别在于元组无法被修改。由于不可修改的特性，元组一般用来保证存放数据的可靠性，例如用元组保存八大行星的名称，因为它们的名称不会被改变，也不会轻易减少：
planets = [ Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, Neptune]
下面我们创建一个含有四个元素的元组。
t = (1, 2, 3, 4)
## 尝试修改元组，提示元素无法被赋值
t[0] = -1
TypeError: 'tuple' object does not support item assignment
## 尝试增加元素，系统提示不支持 append 操作
t.append(5)
AttributeError: 'tuple' object has no attribute 'append'
## 尝试删除元素，系统提示元素无法被删除
del t[0]
TypeError: 'tuple' object doesn't support item deletion
1.2.3 字典
顾名思义，字典就像现实世界中的字典，只要知道一个单词的读音，就能找到它在书中具体的位置！即我们将一个 “键(key)” 与 “值(value)” 相关联，通过键迅速检索到对应的值。要注意键必须是唯一的，这就好比两个单词如果读音一样就会出现歧义一样。
字典通过花括号 { } 创建，通过 : 符号区分键与值，通过逗号分隔。下面我们创建一个字典存储联系人的邮箱。
ab = {"XiaoHu": "xiaohu@RNG","XiaoWei": "xiaowei@RNG","XiaoMing": "xiaoming@RNG"
}
print(ab)
{'XiaoHu': 'xiaohu@RNG', 'XiaoWei': 'xiaowei@RNG', 'XiaoMing': 'xiaoming@RNG'}
字典支持以下操作：
- 增：通过关键字
[ ]可以向列表内增加元素 - 删：通过关键字
del可以删除列表内元素 - 查：通过关键字
[ ]可以查找列表某个位置元素 - 改：通过赋值符号
=可以修改某个位置的元素
字典的优点是：
- 快速检索到键对应的值
- 字典内的键值不存在顺序关系
1.2.3.1 增加元素
## 通过 [ ] 关键字 与赋值符号 = 向字典添加新的元素ab['Cryin'] = "cryin@RNG"
print(ab)
{'XiaoHu': 'xiaohu@RNG', 'XiaoWei': 'xiaowei@RNG', 'XiaoMing': 'xiaoming@RNG', 'Cryin': 'cryin@RNG'}
1.2.3.2 删除元素
## 通过 del 关键字 删除字典中的元素del ab['XiaoMing']
print(ab)
{'XiaoHu': 'xiaohu@RNG', 'XiaoWei': 'xiaowei@RNG', 'Cryin': 'cryin@RNG'}
1.2.3.3 查找元素
## 通过 [ ] 关键字根据键查找值print(ab['XiaoHu'])
xiaohu@RNG
## 通过 in 关键字可以查找某个键是否在字典中
print('XiaoHu' in ab)
print('UZI' in ab)
True
False
1.2.3.4 修改元素
## 通过 [ ] 关键字 与赋值符号 = 修改字典内的元素ab['XiaoHu'] = "xiaohu@EDG"
print(ab)
{'XiaoHu': 'xiaohu@EDG', 'XiaoWei': 'xiaowei@RNG', 'Cryin': 'cryin@RNG'}
1.2.3.5 小例子
下面我们以字典为基础重新构建学生成绩管理系统：
## Task 1 建立学生信息管理系统Math_scores = {}
Math_scores['XiaoHu'] = 65
Math_scores['XiaoMing'] = 80
Math_scores['XiaoWei'] = 95Chinese_scores = {}
Chinese_scores['XiaoHu'] = 55
Chinese_scores['XiaoMing'] = 92
Chinese_scores['XiaoWei'] = 98print(Math_scores)
print(Chinese_scores)
{'XiaoHu': 65, 'XiaoMing': 80, 'XiaoWei': 95}
{'XiaoHu': 55, 'XiaoMing': 92, 'XiaoWei': 98}
## Task 2 根据本次期末考试的成绩更新系统Math_scores['XiaoHu'] = 95
Math_scores['XiaoMing'] = 75
Math_scores['XiaoWei'] = 92Chinese_scores = {}
Chinese_scores['XiaoHu'] = 85
Chinese_scores['XiaoMing'] = 71
Chinese_scores['XiaoWei'] = 93print(Math_scores)
print(Chinese_scores)
{'XiaoHu': 95, 'XiaoMing': 75, 'XiaoWei': 92}
{'XiaoHu': 85, 'XiaoMing': 71, 'XiaoWei': 93}
## Task 3 删除 XiaoMing 的信息del Math_scores['XiaoMing']
del Chinese_scores['XiaoMing']print(Math_scores)
print(Chinese_scores)
{'XiaoHu': 95, 'XiaoWei': 92}
{'XiaoHu': 85, 'XiaoWei': 93}
## Task 4 录入 Cryin 的信息Math_scores['Cryin'] = 87
Chinese_scores['Cryin'] = 88print(Math_scores)
print(Chinese_scores)
{'XiaoHu': 95, 'XiaoWei': 92, 'Cryin': 87}
{'XiaoHu': 85, 'XiaoWei': 93, 'Cryin': 88}
在我们的小例子中可以观察到，字典构建的学生管理系统避免了查找元素所在位置的操作，这是字典根据“键”可以迅速找到“值”的特性决定的。
1.2.4 集合
集合是用来存储无序的元素集合。通常我们只考虑元素的存在，而不考虑元素的顺序或出现次数时使用集合。
集合与字典一样也通过花括号创建，但不存在 : 分隔符号。例如用集合表示中国的四个直辖市，它们无需考虑顺序与出现次数。
municipalities = { "Beijing", "Shanghai", "Tianjin", "Chongqing" }
注意集合中不能存在重复元素。
## 创建一个集合s = {1,2,3,4,5}
集合支持以下操作：
- 增：通过函数
add可以向集合内增加元素 - 删：通过函数
remove可以删除集合内元素 - 查：通过关键字
in可以查找某个元素是否在集合内
集合的优点是：
- 支持数学集合操作
- 快速检索某个元素是否在集合内
- 集合内的键值不存在顺序关系
1.2.4.1 增加元素
## 增加新的元素到集合中s.add(6)
print(s)
{1, 2, 3, 4, 5, 6}
1.2.4.2 删除元素
## 删除集合中某个元素s.remove(6)
print(s)
{1, 2, 3, 4, 5}
1.2.4.3 查找元素
## 查找某个元素是否在集合中
print(5 in s)
print(6 in s)
True
False
1.2.4.4 数学操作
集合的一大特点是支持数学操作，其中包括求集合的 并集、交集 以及 亦或 操作。
## 创建另一个集合
s2 = {3,4,5,6,7}
## 集合并集
print(s | s2)
{1, 2, 3, 4, 5, 6, 7}
## 集合交集
print(s & s2)
{3, 4, 5}
## 集合异或，即不属于交集的部分
print(s ^ s2)
{1, 2, 6, 7}
1.2.5 练习
1.2.5.1 列表练习
给定两个大小分别为 m 和 n 的升序（从小到大）列表 nums1 和 nums2。请你找出并返回这两个升序列表的 中位数 。
例子：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
找到两个列表的中位数的思路分两步，首先合并两个升序列表为一个升序列表，然后找到升序列表中中间的数即为中位数。
合并两个升序列表的思路很简单，因为两个列表都是升序，所以只需要判断两个列表首个元素的大小，将最小的依次放入一个新的数组中。如果其中一个数组空了，说明另一个数组中的所有元素都比之前的大，将它们合并到新数组的尾部即可。
## 定义合并两个升序列表的函数
def merge(nums1, nums2):result = []## 如果两个列表都不是空的，依次比较首个元素大小while len(nums1) > 0 and len(nums2) > 0:## 如果第一个列表首个元素更小if nums1[0] < nums2[0]:## 将 nums1 列表的首个元素放入 result 列表result.append(nums1[0])nums1 = nums1[1:]## 如果第 nums2 列表首个元素更小else:## 将 nums2 列表的首个元素放入 result 列表result.append(nums2[0])nums2 = nums2[1:]## 如果某个列表空了，将非空的数组合并到 result 尾部result = result + nums1result = result + nums2return result
## 在合并后的列表中寻找中位数
def find_medium(nums):half = len(nums) // 2## 如果列表长度为偶数，则取中间两个数的平均值if len(nums) % 2 == 0:return (nums[half - 1] + nums[half]) / 2## 如果列表长度为奇数，则取最中间数else:return nums[half]
nums1 = [1,2]
nums2 = [3,4]
find_medium(merge(nums1, nums2))
2.5
1.2.5.2 字典练习
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数。 例子：输入：nums = [2,7,11,15], target = 9 输出：[2,7] 解释：因为 nums[0] + nums[1] == 9 ，返回 [2, 7] 。
本练习在上一节中我们已经实现过，思路是通过两重 for-in 循环寻找两个和为 target 的整数：
def check_sum(num1, num2, target):a = num1b = num2return a + b == targetdef twosum(nums, target):finded = Falsefor a in nums:for b in nums:if check_sum(a,b,target):return [a,b]
nums = [2,7,11,15]
twosum(nums, 9)
[2, 7]
在这里我们简要引入时间复杂度的概念，它在计算机科学与数据科学领域发挥着不可替代的作用。我们经常会看到 O ( n ) , O ( l o g ( n ) ) , O ( n k ) O(n),O(log(n)),O(n^k) O(n),O(log(n)),O(nk) 等符号，它们表示程序运行时间与程序输入大小的关系。
其中 O ( n ) O(n) O(n) 表示程序运行时间跟随程序输入大小线性增长。就好比我们在赛百味买一个 6 英寸三明治是 18 块钱，买一个 12 英寸的三明治是 36 块钱……
O ( n 2 ) O(n^2) O(n2) 表示程序运行时间跟随程序输入大小平方增长。就像我们在必胜客买一个 12 英寸的披萨的价格大概是 6 英寸披萨价格的四倍……
## 本段代码绘图使用无需理解
! pip3 install numpy matplotlib
import numpy as np
import matplotlib.pyplot as plt
x = np.arange(0,5,0.1)
y = x
plt.plot(x,y)
y = x**2
plt.plot(x,y)
plt.xlabel('Imput size')
plt.ylabel('Running time')
Text(0, 0.5, 'Running time')
在上面的图中可以直观看到 平方复杂度 随着时间增长 运行时间急剧增加，因此能够把复杂度从 O ( n 2 ) O(n^2) O(n2) 降低到 O ( n ) O(n) O(n) 甚至 O ( l o g ( n ) ) O(log(n)) O(log(n)) 带来的增益是巨大的。尤其是在数据科学领域，程序往往需要处理上千万条数据，不同复杂度的代码运行时间差距非常显著。
那么在上述程序中，输入列表的大小为 4，在最坏情况下 twosum 函数中的两个 for-in 循环一共执行 16 次 check_sum 操作，因此该算法的复杂度是 O ( n 2 ) O(n^2) O(n2)。下面我们用 字典 优化代码复杂度为 O ( n ) O(n) O(n)，思路是遍历一次列表并将遍历过的元素值存储到字典中，若有字典中的元素值与列表中的元素值求和为target，则返回这两个值。
def twosum(nums, target):hashtable = {}for num in nums:if num in hashtable:return [hashtable[num], num]hashtable[target - num] = num
twosum(nums,9)
[2, 7]
更多推荐
2. Python 数据结构
发布评论