Python 数据结构

数据结构是计算机科学中组织和存储数据的方式，它决定了如何访问和修改数据。Python 提供了多种内置的数据结构，本章节将详细介绍这些数据结构的特点和使用方法。

内置数据结构

Python 提供了以下内置数据结构：

1. 列表（List）：有序、可变的元素集合
2. 元组（Tuple）：有序、不可变的元素集合
3. 字典（Dictionary）：无序、可变的键值对集合
4. 集合（Set）：无序、不可重复的元素集合
5. 字符串（String）：有序、不可变的字符序列

列表（List）

列表是 Python 中最常用的数据结构之一，用于存储有序、可变的元素集合。

特点：

• 有序：元素的顺序是固定的
• 可变：可以修改、添加、删除元素
• 可重复：可以包含重复的元素
• 异构：可以包含不同类型的元素

示例：

# 列表示例

# 创建列表
fruits = ["apple", "banana", "cherry"]
print(f"原始列表：{fruits}")

# 访问元素
print(f"第一个元素：{fruits[0]}")
print(f"最后一个元素：{fruits[-1]}")

# 修改元素
fruits[1] = "orange"
print(f"修改后的列表：{fruits}")

# 添加元素
fruits.append("grape")
print(f"添加元素后的列表：{fruits}")

# 插入元素
fruits.insert(1, "pear")
print(f"插入元素后的列表：{fruits}")

# 删除元素
fruits.remove("apple")
print(f"删除元素后的列表：{fruits}")

# 弹出元素
popped = fruits.pop()
print(f"弹出的元素：{popped}")
print(f"弹出元素后的列表：{fruits}")

# 列表长度
print(f"列表长度：{len(fruits)}")

# 列表切片
print(f"列表切片：{fruits[1:3]}")

# 列表排序
default_numbers = [3, 1, 4, 1, 5, 9, 2, 6]
default_numbers.sort()
print(f"排序后的列表：{default_numbers}")

# 列表反转
fruits.reverse()
print(f"反转后的列表：{fruits}")

元组（Tuple）

元组是 Python 中另一种有序的数据结构，但它是不可变的。

特点：

• 有序：元素的顺序是固定的
• 不可变：不能修改、添加、删除元素
• 可重复：可以包含重复的元素
• 异构：可以包含不同类型的元素

示例：

# 元组示例

# 创建元组
tuple1 = (1, 2, 3, 4, 5)
print(f"原始元组：{tuple1}")

# 创建单元素元组
tuple2 = (42,)
print(f"单元素元组：{tuple2}")
print(f"类型：{type(tuple2)}")

# 访问元素
print(f"第一个元素：{tuple1[0]}")
print(f"最后一个元素：{tuple1[-1]}")

# 元组切片
print(f"元组切片：{tuple1[1:4]}")

# 元组长度
print(f"元组长度：{len(tuple1)}")

# 元组解包
a, b, c, d, e = tuple1
print(f"解包结果：a={a}, b={b}, c={c}, d={d}, e={e}")

# 元组连接
tuple3 = (6, 7, 8)
tuple4 = tuple1 + tuple3
print(f"连接后的元组：{tuple4}")

# 元组重复
tuple5 = (1, 2) * 3
print(f"重复后的元组：{tuple5}")

# 元组方法
print(f"元素 3 出现的次数：{tuple1.count(3)}")
print(f"元素 3 的索引：{tuple1.index(3)}")

# 注意：元组是不可变的，以下操作会引发错误
# tuple1[0] = 10  # TypeError: 'tuple' object does not support item assignment
# tuple1.append(6)  # AttributeError: 'tuple' object has no attribute 'append'

字典（Dictionary）

字典是 Python 中用于存储键值对的数据结构，它是无序的。

特点：

• 无序：元素的顺序不是固定的（Python 3.7+ 中会保持插入顺序）
• 可变：可以修改、添加、删除键值对
• 键唯一：键不能重复
• 键不可变：键必须是不可变类型（如字符串、数字、元组）

示例：

# 字典示例

# 创建字典
person = {
    "name": "Alice",
    "age": 30,
    "city": "New York"
}
print(f"原始字典：{person}")

# 访问元素
print(f"姓名：{person['name']}")
print(f"年龄：{person.get('age')}")
print(f"不存在的键：{person.get('country', 'USA')}")

# 修改元素
person['age'] = 31
print(f"修改后的字典：{person}")

# 添加元素
person['country'] = 'USA'
print(f"添加元素后的字典：{person}")

# 删除元素
person.pop('city')
print(f"删除元素后的字典：{person}")

# 字典长度
print(f"字典长度：{len(person)}")

# 字典键
print(f"字典键：{list(person.keys())}")

# 字典值
print(f"字典值：{list(person.values())}")

# 字典键值对
print(f"字典键值对：{list(person.items())}")

# 遍历字典
print("遍历字典：")
for key, value in person.items():
    print(f"{key}: {value}")

# 字典更新
person.update({"job": "Engineer", "age": 32})
print(f"更新后的字典：{person}")

# 清空字典
person.clear()
print(f"清空后的字典：{person}")

集合（Set）

集合是 Python 中用于存储无序、不可重复元素的数据结构。

特点：

• 无序：元素的顺序不是固定的
• 可变：可以添加、删除元素
• 不可重复：不能包含重复的元素
• 元素不可变：元素必须是不可变类型

示例：

# 集合示例

# 创建集合
fruits = {"apple", "banana", "cherry"}
print(f"原始集合：{fruits}")

# 创建空集合
empty_set = set()
print(f"空集合：{empty_set}")

# 从列表创建集合
numbers = [1, 2, 3, 3, 4, 5, 5]
unique_numbers = set(numbers)
print(f"去重后的集合：{unique_numbers}")

# 添加元素
fruits.add("orange")
print(f"添加元素后的集合：{fruits}")

# 移除元素
fruits.remove("banana")
print(f"移除元素后的集合：{fruits}")

# 集合长度
print(f"集合长度：{len(fruits)}")

# 检查元素
print(f"'apple' 在集合中：{'apple' in fruits}")
print(f"'banana' 在集合中：{'banana' in fruits}")

# 集合运算
set1 = {1, 2, 3, 4}
set2 = {3, 4, 5, 6}

print(f"集合 1：{set1}")
print(f"集合 2：{set2}")
print(f"并集：{set1.union(set2)}")
print(f"交集：{set1.intersection(set2)}")
print(f"差集：{set1.difference(set2)}")
print(f"对称差集：{set1.symmetric_difference(set2)}")

# 集合方法
set1.update({5, 6, 7})
print(f"更新后的集合 1：{set1}")

set1.intersection_update({4, 5, 6})
print(f"交集更新后的集合 1：{set1}")

set1.difference_update({5})
print(f"差集更新后的集合 1：{set1}")

字符串（String）

字符串是 Python 中用于存储字符序列的数据结构，它是不可变的。

特点：

• 有序：字符的顺序是固定的
• 不可变：不能修改字符
• 可索引：可以通过索引访问字符
• 可切片：可以通过切片获取子字符串

示例：

# 字符串示例

# 创建字符串
text = "Hello, World!"
print(f"原始字符串：{text}")

# 访问字符
print(f"第一个字符：{text[0]}")
print(f"最后一个字符：{text[-1]}")

# 字符串长度
print(f"字符串长度：{len(text)}")

# 字符串切片
print(f"切片：{text[7:12]}")
print(f"步长切片：{text[::2]}")
print(f"反转字符串：{text[::-1]}")

# 字符串方法
print(f"大写：{text.upper()}")
print(f"小写：{text.lower()}")
print(f"首字母大写：{text.capitalize()}")
print(f"标题格式：{text.title()}")
print(f"查找子串：{text.find('World')}")
print(f"替换子串：{text.replace('World', 'Python')}")
print(f"分割字符串：{text.split(', ')}")
print(f"连接字符串：'-'.join(['Hello', 'World', '!'])")
print(f"去除空白：'  Hello  '.strip()")
print(f"是否以 'Hello' 开头：{text.startswith('Hello')}")
print(f"是否以 '!' 结尾：{text.endswith('!')}")
print(f"是否全为字母：{'Hello'.isalpha()}")
print(f"是否全为数字：{'123'.isdigit()}")
print(f"是否全为空格：{'   '.isspace()}")

高级数据结构

除了内置数据结构外，Python 的标准库中还提供了一些高级数据结构，这些数据结构位于 collections 模块中。

计数器（Counter）

Counter 是一个用于计数的字典子类，它可以统计元素出现的次数。

示例：

# 计数器示例

from collections import Counter

# 创建计数器
text = "hello world"
counter = Counter(text)
print(f"字符计数：{counter}")

# 统计列表元素
fruits = ["apple", "banana", "cherry", "apple", "banana", "apple"]
fruit_counter = Counter(fruits)
print(f"水果计数：{fruit_counter}")

# 获取最常见的元素
print(f"最常见的 2 个元素：{fruit_counter.most_common(2)}")

# 计数器运算
counter1 = Counter([1, 2, 3, 1, 2])
counter2 = Counter([2, 3, 4, 2, 4])
print(f"计数器 1：{counter1}")
print(f"计数器 2：{counter2}")
print(f"并集：{counter1 + counter2}")
print(f"差集：{counter1 - counter2}")
print(f"交集：{counter1 & counter2}")
print(f"对称差集：{counter1 | counter2}")

有序字典（OrderedDict）

OrderedDict 是一个保持插入顺序的字典子类。在 Python 3.7+ 中，普通字典也会保持插入顺序，所以 OrderedDict 的使用场景减少了。

示例：

# 有序字典示例

from collections import OrderedDict

# 创建有序字典
ordered_dict = OrderedDict()
ordered_dict['a'] = 1
ordered_dict['b'] = 2
ordered_dict['c'] = 3
print(f"有序字典：{ordered_dict}")

# 遍历有序字典
print("遍历有序字典：")
for key, value in ordered_dict.items():
    print(f"{key}: {value}")

# 移动到末尾
ordered_dict.move_to_end('a')
print(f"移动 'a' 到末尾：{ordered_dict}")

# 移动到开头
ordered_dict.move_to_end('c', last=False)
print(f"移动 'c' 到开头：{ordered_dict}")

默认字典（defaultdict）

defaultdict 是一个在访问不存在的键时会返回默认值的字典子类。

示例：

# 默认字典示例

from collections import defaultdict

# 创建默认字典（默认值为 0）
counts = defaultdict(int)
fruits = ["apple", "banana", "cherry", "apple", "banana", "apple"]

# 统计水果出现次数
for fruit in fruits:
    counts[fruit] += 1

print(f"水果计数：{dict(counts)}")

# 创建默认字典（默认值为列表）
grouped = defaultdict(list)

# 分组
for i, fruit in enumerate(fruits):
    grouped[fruit].append(i)

print(f"水果分组：{dict(grouped)}")

# 创建默认字典（默认值为集合）
unique_grouped = defaultdict(set)

# 分组（去重）
for i, fruit in enumerate(fruits):
    unique_grouped[fruit].add(i)

print(f"水果分组（去重）：{dict(unique_grouped)}")

双向队列（deque）

deque 是一个双向队列，支持从两端快速添加和删除元素。

特点：

• 两端操作：可以从两端添加和删除元素
• 高效：两端操作的时间复杂度为 O(1)
• 可迭代：可以像列表一样遍历

示例：

# 双向队列示例

from collections import deque

# 创建双向队列
dq = deque([1, 2, 3])
print(f"原始双向队列：{dq}")

# 添加元素到右侧
dq.append(4)
print(f"右侧添加元素：{dq}")

# 添加元素到左侧
dq.appendleft(0)
print(f"左侧添加元素：{dq}")

# 删除元素从右侧
popped_right = dq.pop()
print(f"右侧弹出元素：{popped_right}")
print(f"右侧弹出元素后的双向队列：{dq}")

# 删除元素从左侧
popped_left = dq.popleft()
print(f"左侧弹出元素：{popped_left}")
print(f"左侧弹出元素后的双向队列：{dq}")

# 双向队列长度
print(f"双向队列长度：{len(dq)}")

# 双向队列旋转
dq.rotate(1)  # 向右旋转 1 位
print(f"向右旋转 1 位：{dq}")

rotate(-1)  # 向左旋转 1 位
print(f"向左旋转 1 位：{dq}")

# 双向队列扩展
dq.extend([4, 5])
print(f"右侧扩展元素：{dq}")

# 左侧扩展
dq.extendleft([-1, 0])
print(f"左侧扩展元素：{dq}")

# 清空双向队列
dq.clear()
print(f"清空后的双向队列：{dq}")

命名元组（namedtuple）

namedtuple 是一个创建具有命名字段的元组子类的工厂函数。

特点：

• 不可变：与元组一样，是不可变的
• 命名字段：可以通过字段名访问元素
• 轻量：比类更轻量

示例：

# 命名元组示例

from collections import namedtuple

# 创建命名元组类
Person = namedtuple('Person', ['name', 'age', 'city'])

# 创建命名元组实例
person = Person('Alice', 30, 'New York')
print(f"命名元组：{person}")

# 通过索引访问
print(f"通过索引访问：{person[0]}")

# 通过字段名访问
print(f"通过字段名访问：{person.name}")
print(f"年龄：{person.age}")
print(f"城市：{person.city}")

# 转换为字典
print(f"转换为字典：{person._asdict()}")

# 替换字段值（返回新实例）
new_person = person._replace(age=31, city='Boston')
print(f"替换后的命名元组：{new_person}")
print(f"原始命名元组：{person}")

# 解包
name, age, city = person
print(f"解包：{name}, {age}, {city}")

# 命名元组的字段名
print(f"字段名：{person._fields}")

数据结构的选择

在选择数据结构时，需要考虑以下因素：

1. 有序性：是否需要保持元素的顺序
2. 可变性：是否需要修改元素
3. 唯一性：元素是否可以重复
4. 访问方式：如何访问元素（通过索引、键等）
5. 性能：时间复杂度和空间复杂度

数据结构对比

数据结构	有序性	可变性	元素唯一性	访问方式	适用场景
列表	是	是	否	索引	存储有序、可修改的元素集合
元组	是	否	否	索引	存储有序、不可修改的元素集合
字典	是（Python 3.7+）	是	键唯一	键	存储键值对，通过键快速访问
集合	否	是	是	成员检查	存储唯一元素，进行集合运算
字符串	是	否	否	索引	存储字符序列

性能对比

操作	列表	字典	集合
访问元素	O(1)	O(1)	O(1)
插入元素	O(1)（末尾）/ O(n)（开头）	O(1)	O(1)
删除元素	O(1)（末尾）/ O(n)（其他）	O(1)	O(1)
成员检查	O(n)	O(1)	O(1)
排序	O(n log n)	-	-

自定义数据结构

除了使用内置和标准库中的数据结构外，我们还可以自定义数据结构。

栈（Stack）

栈是一种后进先出（LIFO）的数据结构。

示例：

# 自定义栈

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        """添加元素到栈顶"""
        self.items.append(item)
    
    def pop(self):
        """移除并返回栈顶元素"""
        if not self.is_empty():
            return self.items.pop()
        return None
    
    def peek(self):
        """返回栈顶元素，不移除"""
        if not self.is_empty():
            return self.items[-1]
        return None
    
    def is_empty(self):
        """检查栈是否为空"""
        return len(self.items) == 0
    
    def size(self):
        """返回栈的大小"""
        return len(self.items)

# 使用栈
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(f"栈大小：{stack.size()}")
print(f"栈顶元素：{stack.peek()}")
print(f"弹出元素：{stack.pop()}")
print(f"栈大小：{stack.size()}")
print(f"弹出元素：{stack.pop()}")
print(f"弹出元素：{stack.pop()}")
print(f"栈是否为空：{stack.is_empty()}")

队列（Queue）

队列是一种先进先出（FIFO）的数据结构。

示例：

# 自定义队列

class Queue:
    def __init__(self):
        self.items = []
    
    def enqueue(self, item):
        """添加元素到队列尾部"""
        self.items.append(item)
    
    def dequeue(self):
        """移除并返回队列头部元素"""
        if not self.is_empty():
            return self.items.pop(0)
        return None
    
    def front(self):
        """返回队列头部元素，不移除"""
        if not self.is_empty():
            return self.items[0]
        return None
    
    def is_empty(self):
        """检查队列是否为空"""
        return len(self.items) == 0
    
    def size(self):
        """返回队列的大小"""
        return len(self.items)

# 使用队列
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(f"队列大小：{queue.size()}")
print(f"队列头部元素：{queue.front()}")
print(f"出队元素：{queue.dequeue()}")
print(f"队列大小：{queue.size()}")
print(f"出队元素：{queue.dequeue()}")
print(f"出队元素：{queue.dequeue()}")
print(f"队列是否为空：{queue.is_empty()}")

总结

Python 提供了丰富的数据结构，包括内置的数据结构（列表、元组、字典、集合、字符串）和标准库中的高级数据结构（计数器、有序字典、默认字典、双向队列、命名元组）。

选择合适的数据结构对于编写高效、清晰的代码非常重要。在选择数据结构时，需要考虑数据的特性、操作的频率以及性能要求。

本章节介绍了各种数据结构的特点、使用方法和应用场景，希望对你有所帮助。