Python 中的数据结构和算法 | 第一部分

2024 年 8 月 29 日 | 阅读 16 分钟

数据结构和算法(DSA)是编程中的一个概念,每个程序员都必须精通,以便通过有效利用可用资源来创建代码。无论使用何种编程语言,DSA 都是一个更普遍的概念。本教程将使用 Python 编程语言介绍 DSA 的基础知识。

数据结构

“数据 + 结构”说明了一切。数据结构就是构建数据的方式。它是一个存储单元,以程序员可以轻松访问的方式组织和存储数据。

在现实世界中,程序员/编码人员的工作涉及大量数据。当数据以正确的方式排列时,程序员可以轻松地分析和使用数据。除了组织数据外,数据结构还使数据的处理和访问变得容易。

本教程涵盖了 Python 的所有数据结构。有内置数据结构,也有用户自定义数据结构。我们先来看看内置的那些。

1. 列表 (Lists)

列表就像一个动态且异构的数组。数组在像 C 这样的语言中使用。与数组不同,列表是动态大小的,可以存储不同类型的数据。它是 Python 中的序列数据类型之一

关于列表的要点

  1. 列表是可变的,这意味着创建后,我们可以修改它们的元素。
  2. 它由方括号-[]内用逗号分隔的数据组成。
  3. 列表允许重复的元素。
  4. 我们使用索引来访问列表元素(0 到 长度 - 1),也允许负索引(-1 到 -长度)。
  5. 我们可以将另一个数据结构作为元素嵌套在列表中。嵌套另一个列表会使其成为一个多维列表
  6. 使用切片,我们可以获取列表的子列表,为此我们需要使用切片操作符 - [:]。
  7. 列表推导式用于从现有列表或其他数据结构创建新列表。它比使用常规 for 循环创建列表更快。
  8. 我们可以使用像 max()、min() 和 sum() 这样的函数来找到列表中的最大值、最小值和元素总和。
  9. 我们可以使用 + 运算符连接列表,使用 * 运算符重复元素。
  10. 要将列表作为输入,我们使用 input(),然后使用 split(separator) 将字符串转换为列表。

最常用的函数和方法

1. len(List)找到列表的长度
2. List.append()在列表末尾添加一个元素。
3. List.insert()在指定索引处添加一个元素。
4. List.remove()从列表中移除指定的元素。
5. List.reverse()返回反向排序的列表。
6. List.index()返回指定元素的首次出现索引。
7. List.extend()将另一个列表的元素作为元素添加到指定列表中。
8. List.pop()移除并返回指定列表的最后一个元素。
9. String.split()将给定的字符串转换为列表

示例

输出

Created lists:
emptylist: []
mylist: [20, 20, 'H', 'Hello']
nestedlist: [[1, 2], [20, 20, 'H', 'Hello']]
Concatenating mylist and nestedlist: [20, 20, 'H', 'Hello', [1, 2], [20, 20, 'H', 'Hello']]
Repeating the elements of a list: [20, 20, 'H', 'Hello', 20, 20, 'H', 'Hello', 20, 20, 'H', 'Hello']

List as an input:
Enter elements(separate by space):8 9 7 8
[8, 9, 7, 8]
In the nested list: 
(Normal)nestedlist[0]: [1, 2]
(Negative)nestedlist[-2]: [1, 2]

Adding elements to the empty list:
emptylist: [1, 3, 4, 5]
Adding an index emptylist[1]: [1, 2, 3, 4, 5]
Extending mylist with emptylist: None

Using Slicing
Slicing mylist[:]: [20, 20, 'H', 'Hello', 1, 2, 3, 4, 5]
Reverse using slicing[::-1]: [5, 4, 3, 2, 1, 'Hello', 'H', 20, 20]
Slicing using indices[1:3]: [20, 'H']

Creating a newlist[] using list comprehension:
newlist with even elements in emptylist: [2, 4]

Using functions:
Length using len(): 9
Removing an element using remove: None
Removing the last element using pop: 5
Using index(): 5
Using reverse on [1, 2, 3, 4, 5] :
[5, 4, 3, 2, 1]

元组 (Tuples)

元组就像一个不可变的列表。它也是 Python 中的一种序列数据类型,可以像列表一样存储不同数据类型的数据,但与列表不同的是,一旦创建元组,我们就不能更改它;如果我们尝试这样做,Python 会引发错误。

示例

输出

nestedtuple.append(1)
AttributeError: 'tuple' object has no attribute 'append.'
  • 上面的元组是一个嵌套元组,其第一个元素是一个列表。我们不能修改元组,但我们可以修改它里面的列表

示例

输出

[1, 2, 1]
([1, 2, 1], (1, 'h', 'Hello'))

关于元组的要点

  1. 元组由圆括号内用逗号分隔的数据组成,尽管圆括号不是强制性的,但为了可读性,在约定中会使用。
  2. 创建没有圆括号的元组称为“元组打包”,而要访问元组,我们也可以使用“元组解包”。
  3. 元组像列表一样允许重复元素。
  4. 我们使用索引来访问元组元素(0 到 长度 - 1),也允许负索引(-1 到 -长度)。
  5. 我们可以将另一个数据结构作为元素嵌套在元组中。嵌套另一个元组会使其成为多维元组。
  6. 使用切片,我们可以获取元组的子元组,为此我们需要使用切片操作符 - [:]。
  7. 我们可以连接两个元组、重复、重新分配或删除整个元组,但一旦创建,我们不能执行像追加、移除、插入元素或删除元素这样的操作,这意味着我们不能干扰创建时的原始元素——元组是不可变的
  8. 要执行我们不能在元组上执行的所有操作,我们通常使用 list() 将元组转换为列表,做我们想做的事,然后使用 tuple() 将其转换回元组。
  9. 由于元组是不可变的,它可以被用作字典中的键
  10. 遍历元组比遍历列表快得多。

最常用的函数和方法

1. len(Tuple)找到元组的长度
2. sorted(Tuple)对指定的元组进行排序
3. max(Tuple)找到元组中的最大值元素。
4. min(Tuple)找到元组中的最小值元素。
5. sum(Tuple)找到元组中元素的总和。
6. Tuple.index()返回指定元素的首次出现索引。
7. all(Tuple)如果元组中的所有元素都为 True,则返回 True。
8. any(Tuple)如果元组中至少有一个元素为 True,则返回 True。
9. Tuple.count(element)返回指定元素在元组中出现的次数。
  • len()、sorted()、max()、min()、sum()、all()、any() 适用于 Python 中的任何可迭代数据类型。
  • 不要将 sort() 与 sorted() 混淆。sort() 仅限于列表。

示例

输出

Emptytuple: ()
mytuple: (1, 'h', 'Hello')
nestedtuple: ([1, 2], (1, 'h', 'Hello'))
By Tuple packing: (1, 'Hi')
Using tuple(): (1, 2, 3)
Tuple with one element: (1,)
Concatenating nestedtuple and mytuple: ([1, 2], (1, 'h', 'Hello'), 1, 'h', 'Hello')
Repeating the elements of a tuple: (1, 'h', 'Hello', 1, 'h', 'Hello', 1, 'h', 'Hello')

Tuple as an input:
Enter elements(separate by space):3 4 5
(3, 4, 5)

Slicing mytuple[:]: (1, 'h', 'Hello')
Reverse using slicing[::-1]: ('Hello', 'h', 1)
Slicing using indices[1:3]: ('h', 'Hello')

Accessing elements:
In nestedtuple[0]: [1, 2]
In nestedtuple[-2]: [1, 2]
By tuple unpacking: 1 h Hello

Using the built-in functions: 
Length of mytuple: 3
Sorting a tuple using sorted(): [0, 1, 2]
Using max(): 23
Using min(): 1
Using sum(): 10
Using all(): False
Using any(): True
Using count(): 2

集合 (Sets)

集合是唯一元素的集合,它不像列表和元组那样支持重复元素。关于集合的另一个重要点是它们是无序的,这使得使用索引访问它们的元素成为不可能。

关于集合的要点

  1. 集合由 {} 括起来。
  2. 它是一种可变数据类型,并且是可迭代的
  3. 尽管集合是可变的,但由于其不允许重复和无序的特性,集合的元素是不可变的
  4. 我们可以向集合中添加或删除元素,但不能对集合执行切片或索引操作。
  5. 还有另一类不可变集合,称为冻结集合 (Frozen sets)
  6. 在内部,集合中的元素是基于哈希和哈希表排列的。
  7. 如果多个元素被放置在一个索引中,这些值会以链表的形式排列到该索引位置。
  8. 每个索引位置都充当一个键,而索引中的成员/值作为值存储在字典中。
  9. 内部工作机制使集合在时间上更优化
  10. 集合不允许像列表这样的可变项作为其元素。

输出

set1 = {[1, 2], 2, 3}	
TypeError: unhashable type: 'list'

集合上最常用的函数和方法

函数/方法等效运算符说明
1. Set.add(value)将指定元素添加到集合中。
2. Set1.union(Set2)Set1 | Set2合并两个给定的集合
3. Set1.intersection(Set2)Set1 & Set2找到两个给定集合的共同元素。
4. Set1.difference(Set2)Set1 - Set2找到 Set1 中不在 Set2 中的元素
5. Set.clear()清空给定的集合。
6. set()创建集合或将其他数据类型转换为集合。
7. Set1.isdisjoint(Set2)检查 Set1 和 Set2 是否没有共同元素。

集合运算符

相等
1. Set1 == Set2
2. Set1 != Set2
检查
1. Set1 是否等于 Set2
2. Set1 是否不等于 Set2
子集
1. Set1 <= Set2
2. Set1 < Set2
检查
1. Set1 是 Set2 的子集
2. Set1 是 Set2 的真子集
超集
1. Set1 >= Set2
2. Set1 > Set2
检查
1. Set1 是 Set2 的超集
2. Set1 是 Set2 的真子集
Set1 ^ Set2返回一个包含在 Set1 或 Set2 中,但不同时在两个集合中的元素的集合。

示例

输出

Creating a set:
Empty set: set()
Myset: {1, 2, 3}
Nestedset: {3, (1, 2), 4}
Removing duplicacy using set(): {1, 2}
Enter elements: 10 11 12
inputset: {10, 11, 12}

Frozen set: ({1, 2, 3, 4, 5})

Adding to emptyset: {'a'}
Union of {1, 2, 3} and {3, (1, 2), 4} :
{1, 2, 3, (1, 2), 4}
Intersection of {1, 2, 3} and {3, (1, 2), 4} :
{3}
Difference of {1, 2, 3} and {3, (1, 2), 4} :
{1, 2}
Clearing emptyset: set()

Membership operator to check if (1, 2) is in nestedset: True
Equivalency on myset and nested set: False
Subset operator to check if {1} is a subset of nestedset: False
proper subset operator to check if {1} is a proper subset of nestedset: False
Superset operator to check if nestedset is a superset of {1}: False
proper superset operator to check if nestedset is a proper superset of {1}: False
Elements in either myset or nestedset but not in both: {1, 2, (1, 2), 4}
  • 如果我们写 emptyset = {},将会创建一个字典来创建一个空集合。因此,我们需要使用 set()。
  • add(element) 会导致错误,因为冻结集合是不可变的。

字典

字典是 {键: 值} 对的集合。键映射值,要访问值,我们需要在索引的位置使用键。它是一个无序的数据集合。

关于字典的要点

  1. 键标识值。因此,键必须是唯一的且不可变的。只有不可变的数据类型才能作为键。
  2. 任何数据类型都可以用作值,因为它是数据。
  3. 不能有重复的键,但允许有重复的值。
  4. 我们也可以使用字典推导式来创建字典,就像列表推导式一样。
  5. 字典的键就像学生的学号,值就是学生的名字。

最常用的 dict 函数和方法

1. keys()返回字典中键的列表
2. values()返回字典中值的列表
3. items()以元组形式返回字典中键值对的列表
4. pop()删除并返回指定键的值
5. dict()创建字典并将键值元组列表转换为字典。
6. get()返回给定键的值
7. update()用给定的键值对扩展字典。

示例

输出

Enter keys: 1 2 3

Enter value for 1: a

Enter value for 2: b

Enter value for 3: c
Created dictionaries:
Emptydict: {}
mydict1: {1: 'A', 2: 'B', 3: 'C'}
mydict2: {4: 'D', 'E': 5}
mydict3: {6: 'F', 7: 'G'}
nesteddict: {1: {1: 'A', 2: 'B', 3: 'C'}, 2: {4: 'D', 'E': 5}}
inputdict: {1: 'a', 2: 'b', 3: 'c'}

Altering mydict2: {4: 'D', 5: 'E'}
Adding elements to mydict3: {6: 'F', 7: 'G', 8: 'H', 9: ('I', 'J', 'K')}

Using get() to access: mydict1.get(1):  A
Using keys() on {1: 'A', 2: 'B', 3: 'C'} : dict_keys([1, 2, 3])
using values() on {1: 'A', 2: 'B', 3: 'C'} : dict_values(['A', 'B', 'C'])
Using items() on {1: 'A', 2: 'B', 3: 'C'} : dict_items([(1, 'A'), (2, 'B'), (3, 'C')])
Updating {1: 'A', 2: 'B', 3: 'C'} with {4: 'D', 5: 'E'} :
{1: 'A', 2: 'B', 3: 'C', 4: 'D', 5: 'E'}
Deleting a value using pop(): B {1: 'A', 3: 'C', 4: 'D', 5: 'E'}

字符串

字符串是字节/字符的数组。在 C 语言中,我们将字符串声明为字符数组。在 Python 中,没有字符数据类型。字符确实存在,但它们被识别为长度为 1 的字符串。字符串是不可变的,这意味着一旦创建就不能修改。

关于字符串的要点

  1. 字符串可以由单引号、双引号甚至三引号括起来。通常,三引号用于创建多行字符串。
  2. 可以使用索引(0 到 长度-1)访问字符串的字节/字符。也允许负索引(-1 到 -长度)。访问超出范围的字符串字符会导致 IndexError。
  3. 只有整数可以用作索引,使用任何其他数据类型都会导致 TypeError。
  4. 使用切片,我们可以从原始字符串中获取子字符串的副本。
  5. 删除或操作字符串的字符会导致错误,因为字符串是不可变的数据类型。使用 del 关键字,我们可以删除整个字符串。我们也可以将新字符串重新赋给旧的现有字符串变量。
  6. 由于引号包围字符串,如果引号是要打印的字符串的一部分,Python 将无法打印它。它会认为已经到达字符串的末尾。因此,我们需要使用“转义序列”。
  7. 使用 {}.format() 方法,我们可以按顺序为格式化和打印变量保留空间。
  8. 如果我们尝试更新/操作字符串的字符

输出

TypeError: 'str' object does not support item assignment

示例

输出

TypeError: 'str' object doesn't support item deletion
  1. 旧式字符串格式化是使用 % 操作符完成的。
  2. 使用格式化,我们甚至可以改变字符串中值的表示形式。

示例:要表示一个浮点数,我们可以使用 %a.bf,其中 a 表示我们希望表示中有多少位数字,b 表示我们希望小数点后有多少位数字。

输出

0.26

示例

输出

Created strings:
Hi
Hi
Hello
            Man

The first character string1[0]: H
The first character string[-2]: H

Substrings of string3:
string3[0:6]: Hello
string3[-6:-1]:    Ma
Reversing using slicing-string3[::-1]: naM            
olleH

Enter a string: What's up
inputstring:: What's up

Reassigning string2 to Hello:
Present: Hi
After reassigning: Hello

Using escape sequences to escape single quotes, double quotes and backslashes
Hi it's my pen
I read a book called "It ends with us" yesterday
The file is stored in the path: C:\Media\Documents\
Printing in a new line: Hi
man
Urging a tab space: Hi	man

The sum of 4 and 5: 9
The difference between 5 and 4: 9
The product of 4 and 5: 20

字符串是 Python 中最常用的数据类型之一。因此,Python 库中有足够多的关于字符串的概念、方法和函数。

一些非常重要的函数和方法

String.split(separator)根据指定的分隔符分割字符串,并返回一个分隔后的子字符串列表。默认分隔符是空格。
String.strip()返回去除所有前导和尾随不必要空格的字符串。
"string".join()用指定的字符串连接可迭代对象的元素,并将其转换为字符串。
String.upper
String.lower
将所有小写字符转换为大写。
将所有大写字符转换为小写。
String.replace(substring1, substring2)在字符串中用 substring2 替换 substring1。
String.find(substring)搜索一个字符或子字符串,并返回首次出现的索引。
String.count(substring)返回子字符串在字符串中出现的次数。

字节数组 (Bytearray)

首先:1 字节 = 8 位(因系统而异)。字节数组,顾名思义,是字节的数组。它是字节的集合。它可以表示范围从 0 到 256 的整数。它是 Python 中的序列数据类型之一。字符串是 Unicode 字符的序列,而字节数组是字节的序列。

关于字节数组的要点

  1. 字节数组是可变的,而 Python 中另一个类似的数据类型——bytes 是不可变的。
  2. 可以使用预定义函数 bytearray() 构建字节数组。该函数也用于将其他数据类型转换为字节数组。
  3. 由于可以直接访问一个数组元素中的 8 位,字节数组的索引比其他序列更快。
  4. 字节数组主要用于代码和内存使用的优化

示例

输出

Created bytearray: bytearray(b'\x01\x02\x03\x04')
Type: <class 'bytearray'>

Elements of bytearray:
1
2
3
4
BA[2]: 3

Modifying BA[2] to 20: bytearray(b'\x01\x02\x06\x04')
Adding elements: bytearray(b'\x01\x02\x06\x04\x07')

bytearray()

该函数可以构造一个字节数组对象,并将其他对象转换为字节数组对象。该函数的语法

  • 它可以有三个可选参数

示例

输出

bytearray(b'')

总结

在本教程中,我们学习了 Python 中的内置数据结构

  1. 列表
  2. 元组 (Tuples)
  3. 集合、冻结集合
  4. 字符串
  5. 字典
  6. 字节数组

在本教程的第二部分,我们将学习 Python 中的用户自定义数据结构,如链表、树和堆。