Python和C++数据结构整理

Python和C++数据结构整理

引言

数据结构是软件开发的基石，但许多开发者对数据结构的分类和选型仍存在认知盲区。本文将系统梳理数据结构的逻辑分类，深入剖析C++和Python中常用数据结构的底层实现与应用场景，通过实际代码示例帮助开发者建立完整的知识体系。
第一部分：数据结构的逻辑分类

逻辑结构的本质

数据结构的分类应当从逻辑结构角度理解，而非物理存储方式。逻辑结构描述数据元素之间的关系，这种关系独立于具体编程语言和底层实现。从逻辑层面看，数据结构分为线性结构和非线性结构两大类。
线性结构

线性结构指数据元素之间存在一对一的顺序关系。除首尾元素外，每个元素都有唯一的前驱和后继。典型的线性结构包括数组、链表、栈、队列和哈希表。哈希表虽然在物理存储上通过散列函数分散存储元素，但从逻辑关系看，每个键值对是独立的一一对应关系，因此属于线性结构。
非线性结构

非线性结构表现为数据元素之间存在一对多或多对多的关系。树结构是典型的一对多关系，每个父节点可以拥有多个子节点，形成层次化结构。图结构代表多对多关系，图中节点可以与任意数量的其他节点建立连接，这种灵活性使得图成为表达复杂关系网络的理想选择。
第二部分：核心数据结构详解

Python的四大内置结构

list：动态数组

Python的list是动态数组实现，使用连续内存空间存储元素引用。list支持O(1)时间复杂度的索引访问和O(1)均摊时间复杂度的末尾追加操作。当容量不足时，Python自动分配更大内存空间并复制现有元素，采用过度分配机制减少频繁的内存重新分配。

1. # 基本操作
2. lst = [1, 2, 3]
3. lst.append(4)           # O(1) 末尾添加
4. lst.insert(0, 0)        # O(n) 头部插入
5. element = lst[2]        # O(1) 索引访问
6. lst.pop()               # O(1) 末尾删除
7. lst.pop(0)              # O(n) 头部删除
9. # 切片操作
10. sub_list = lst[1:3]     # 创建新列表
11. lst[1:3] = [10, 20]     # 替换子序列
13. # 列表推导式
14. squares = [x**2 for x in range(10)]
16. # 遍历
17. for item in lst:
18.     print(item)

复制代码

list在实际开发中应用极为广泛，几乎任何需要存储序列数据的场景都会用到。然而需要注意，list在非末尾位置的插入删除操作时间复杂度为O(n)，因为需要移动后续所有元素。如果频繁需要在序列中间进行插入删除，应当考虑使用collections.deque。
dict：哈希表

Python的dict基于哈希表实现，提供近乎O(1)的查找、插入和删除操作。dict采用开放地址法解决哈希冲突，在空间利用率和性能之间取得良好平衡。自Python 3.7起，dict保证维护插入顺序。

1. # 基本操作
2. d = {'name': 'Alice', 'age': 30}
3. d['city'] = 'Beijing'           # O(1) 插入/更新
4. value = d.get('name')           # O(1) 安全访问
5. value = d.get('gender', 'N/A')  # 提供默认值
6. del d['age']                    # O(1) 删除
8. # 检查键存在
9. if 'name' in d:
10.     print(d['name'])
12. # 遍历
13. for key, value in d.items():
14.     print(f"{key}: {value}")
16. # 字典推导式
17. squared = {x: x**2 for x in range(5)}
19. # 合并字典 (Python 3.9+)
20. d1 = {'a': 1, 'b': 2}
21. d2 = {'b': 3, 'c': 4}
22. merged = d1 | d2  # {'a': 1, 'b': 3, 'c': 4}

复制代码

dict的键必须是可哈希的不可变对象，常见的不可变类型如字符串、数字、元组都可以作为键。dict在配置管理、缓存系统、数据索引等场景中地位举足轻重，其查找速度远超线性搜索。
set：集合

Python的set基于哈希表实现，用于存储唯一元素。set提供O(1)的成员检查、添加和删除操作，这使得它在需要快速判断元素是否存在的场景中表现出色。

1. # 基本操作
2. s = {1, 2, 3}
3. s.add(4)              # O(1) 添加元素
4. s.remove(2)           # O(1) 删除元素，不存在会报错
5. s.discard(2)          # O(1) 删除元素，不存在不报错
6. exists = 3 in s       # O(1) 成员检查
8. # 集合运算
9. s1 = {1, 2, 3, 4}
10. s2 = {3, 4, 5, 6}
11. union = s1 | s2           # {1, 2, 3, 4, 5, 6} 并集
12. intersection = s1 & s2    # {3, 4} 交集
13. difference = s1 - s2      # {1, 2} 差集
14. sym_diff = s1 ^ s2        # {1, 2, 5, 6} 对称差
16. # 去重
17. lst = [1, 2, 2, 3, 3, 3]
18. unique = list(set(lst))   # [1, 2, 3]
20. # frozenset (不可变集合)
21. fs = frozenset([1, 2, 3])
22. # fs可以作为dict的键或另一个set的元素

复制代码

set的典型应用场景包括数据去重、成员资格测试和集合运算。set与frozenset的区别在于可变性，frozenset是不可变的，可以作为dict的键或另一个set的元素。
tuple：不可变序列

tuple是Python的不可变序列类型，创建后无法修改。tuple的不可变性带来两个重要优势：可以作为dict的键，在多线程环境中天然线程安全。tuple在底层内存布局比list更紧凑，创建速度也更快。

1. # 创建tuple
2. t = (1, 2, 3)
3. t = 1, 2, 3           # 括号可省略
4. single = (1,)         # 单元素tuple需要逗号
5. empty = ()
7. # 访问元素
8. first = t[0]          # O(1) 索引访问
9. sub = t[1:3]          # 切片返回新tuple
11. # 解包
12. a, b, c = t
13. x, *rest = (1, 2, 3, 4)  # x=1, rest=[2,3,4]
15. # 作为字典的键
16. point_data = {(0, 0): 'origin', (1, 1): 'diagonal'}
18. # 函数返回多值
19. def get_coordinates():
20.     return 10, 20
22. x, y = get_coordinates()
24. # 命名元组 (更好的可读性)
25. from collections import namedtuple
26. Point = namedtuple('Point', ['x', 'y'])
27. p = Point(10, 20)
28. print(p.x, p.y)

复制代码

tuple常用于表示固定的数据组合，例如函数返回多个值、表示坐标点、作为字典的复合键等。虽然tuple不能修改元素，但如果tuple中包含可变对象（如list），那些可变对象本身的内容仍然可以修改。
C++的核心容器体系

vector：动态数组

std::vector是C++中最常用的容器，它是动态数组的标准实现。vector在连续内存空间中存储元素，提供O(1)的随机访问和O(1)均摊的末尾插入。vector采用容量翻倍的扩容策略以减少重新分配的频率。
[code]#include #include // 基本操作std::vector vec = {1, 2, 3};vec.push_back(4);           // O(1) 末尾添加vec.pop_back();             // O(1) 末尾删除int elem = vec[0];          // O(1) 访问，无边界检查int safe = vec.at(0);       // O(1) 访问，有边界检查// 插入删除vec.insert(vec.begin(), 0); // O(n) 头部插入vec.erase(vec.begin());     // O(n) 头部删除// 容量管理vec.reserve(1000);          // 预分配容量vec.shrink_to_fit();        // 释放多余容量size_t sz = vec.size();     // 当前元素数量size_t cap = vec.capacity();// 当前容量// 遍历for (int x : vec) {    std::cout

很好很强大  我过来先占个楼 待编辑