数据结构"/>
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 数据结构
发布评论