Python和C++数据结构学习笔记

Python和C++数据结构学习笔记

引言

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

第一部分：数据结构的逻辑分类

逻辑结构的本质

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

线性结构

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

非线性结构

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

第二部分：核心数据结构详解

Python的四大内置结构

list：动态数组

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

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

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

dict：哈希表

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

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

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

set：集合

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

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

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

tuple：不可变序列

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

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

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

C++的核心容器体系

vector：动态数组

std::vector是C++中最常用的容器，它是动态数组的标准实现。vector在连续内存空间中存储元素，提供O(1)的随机访问和O(1)均摊的末尾插入。vector采用容量翻倍的扩容策略以减少重新分配的频率。

#include <vector>
#include <iostream>// 基本操作
std::vector<int> 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 << x << " ";
}// 使用迭代器
for (auto it = vec.begin(); it != vec.end(); ++it) {std::cout << *it << " ";
}// 算法配合
#include <algorithm>
std::sort(vec.begin(), vec.end());
auto it = std::find(vec.begin(), vec.end(), 3);

vector相比原生数组的优势包括自动内存管理、边界检查（通过at方法）、迭代器接口等。在实际开发中，除非有明确的性能需求或需要栈上分配的固定大小数组，否则应当优先使用vector而非原生数组。

unordered_map：哈希表

std::unordered_map基于哈希表实现，提供O(1)的平均查找时间。unordered_map使用哈希函数将键映射到桶中，采用链地址法或开放地址法解决冲突。

#include <unordered_map>
#include <string>// 基本操作
std::unordered_map<int, std::string> map;
map[1] = "one";                    // O(1) 插入/更新
map.insert({2, "two"});            // O(1) 插入
std::string val = map[1];          // O(1) 访问// 安全访问
if (map.find(3) != map.end()) {std::cout << map[3];
}// 检查键存在
if (map.count(1) > 0) {// 键存在
}// 删除
map.erase(1);                      // O(1) 删除// 遍历
for (const auto& [key, value] : map) {std::cout << key << ": " << value << "\n";
}// 预分配
map.reserve(1000);// 自定义类型需要提供哈希函数
struct Point {int x, y;
};struct PointHash {size_t operator()(const Point& p) const {return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);}
};struct PointEqual {bool operator()(const Point& a, const Point& b) const {return a.x == b.x && a.y == b.y;}
};std::unordered_map<Point, std::string, PointHash, PointEqual> point_map;

unordered_map的性能高度依赖于哈希函数的质量。标准库为内置类型提供了优化的哈希函数，但对于自定义类型，开发者需要提供合适的哈希函数和相等性判断。在绝大多数需要快速查找的场景中，unordered_map是首选。

map：有序映射

std::map基于红黑树实现，提供O(log n)的查找时间但保证元素按键有序。map的迭代器遍历时元素按键的顺序排列，这在需要有序输出、范围查询的场景中不可或缺。

#include <map>// 基本操作
std::map<int, std::string> map;
map[1] = "one";
map[2] = "two";
map[3] = "three";// 有序遍历
for (const auto& [key, value] : map) {std::cout << key << ": " << value << "\n";// 输出顺序: 1, 2, 3
}// 范围查询
auto lower = map.lower_bound(2);  // 第一个 >= 2 的元素
auto upper = map.upper_bound(2);  // 第一个 > 2 的元素// 区间遍历
for (auto it = lower; it != upper; ++it) {std::cout << it->first << ": " << it->second << "\n";
}// 查找
auto it = map.find(2);
if (it != map.end()) {std::cout << "Found: " << it->second;
}

选择unordered_map还是map的判断标准明确：如果不需要维护键的顺序且追求最快的查找速度，使用unordered_map；如果需要有序遍历或范围查询，使用map。

unordered_set与set

unordered_set基于哈希表实现，提供O(1)的成员检查。set基于红黑树实现，提供O(log n)的成员检查但保证元素有序。

#include <unordered_set>
#include <set>// unordered_set 基本操作
std::unordered_set<int> uset = {1, 2, 3};
uset.insert(4);              // O(1) 插入
uset.erase(2);               // O(1) 删除
bool exists = uset.count(3); // O(1) 检查存在// set 基本操作
std::set<int> oset = {3, 1, 4, 2};
oset.insert(5);// 有序遍历
for (int x : oset) {std::cout << x << " ";  // 输出: 1 2 3 4 5
}// 范围查询
auto lower = oset.lower_bound(2);
auto upper = oset.upper_bound(4);// 集合运算
std::set<int> s1 = {1, 2, 3, 4};
std::set<int> s2 = {3, 4, 5, 6};
std::set<int> result;std::set_intersection(s1.begin(), s1.end(),s2.begin(), s2.end(),std::inserter(result, result.begin()));
// result = {3, 4}

unordered_set在需要快速判断元素存在性、去重、集合运算的场景中表现出色。set的有序性使其在需要维护元素顺序、进行范围查询的场景下不可替代。

array：固定大小数组

std::array是C++11引入的固定大小数组容器，在栈上分配内存，提供编译时大小检查。array结合了原生数组的性能和STL容器的安全性与便利性。

#include <array>// 创建固定大小数组
std::array<int, 5> arr = {1, 2, 3, 4, 5};// 访问元素
int first = arr[0];
int safe = arr.at(0);// 大小
size_t sz = arr.size();  // 编译时常量// 遍历
for (int x : arr) {std::cout << x << " ";
}// 与STL算法配合
std::sort(arr.begin(), arr.end());// 多维数组
std::array<std::array<int, 3>, 3> matrix = {{{1, 2, 3},{4, 5, 6},{7, 8, 9}
}};

array适合表示固定维度的数学向量、小型查找表、配置常量数组等。需要注意的是，array的大小是类型的一部分，array<int, 5>和array<int, 10>是完全不同的类型。

第三部分：次要结构速览

栈与队列

栈遵循后进先出（LIFO）原则，队列遵循先进先出（FIFO）原则。这两种结构在算法实现中广泛应用，但通常不需要专门的栈或队列类型。

# Python - 栈操作
stack = []
stack.append(10)      # 入栈
stack.append(20)
top = stack[-1]       # 查看栈顶
stack.pop()           # 出栈# Python - 队列操作
from collections import deque
queue = deque()
queue.append(10)      # 入队
queue.append(20)
front = queue[0]      # 查看队首
queue.popleft()       # 出队

// C++ - 栈
#include <stack>
std::stack<int> s;
s.push(10);           // 入栈
s.push(20);
int top = s.top();    // 查看栈顶
s.pop();              // 出栈// C++ - 队列
#include <queue>
std::queue<int> q;
q.push(10);           // 入队
q.push(20);
int front = q.front();// 查看队首
q.pop();              // 出队

栈的典型应用包括函数调用栈模拟、括号匹配、表达式求值、深度优先搜索的迭代实现。队列的主要应用在广度优先搜索、任务调度、消息传递、缓冲区管理等场景。

deque：双端队列

deque支持在两端高效插入和删除。Python的collections.deque和C++的std::deque都提供O(1)的两端操作。

# Python deque
from collections import deque
dq = deque([1, 2, 3])
dq.append(4)          # 右端添加
dq.appendleft(0)      # 左端添加
dq.pop()              # 右端删除
dq.popleft()          # 左端删除
dq.rotate(1)          # 循环右移

// C++ deque
#include <deque>
std::deque<int> dq = {1, 2, 3};
dq.push_back(4);      // 右端添加
dq.push_front(0);     // 左端添加
dq.pop_back();        // 右端删除
dq.pop_front();       // 左端删除
int elem = dq[1];     // O(1) 随机访问

deque的典型应用包括实现固定大小的滑动窗口、维护最近访问记录、实现双端队列算法等。deque作为std::stack和std::queue的默认底层容器，因为它比vector在头部操作更高效，比list的随机访问更快。

堆：优先级队列

堆是特殊的完全二叉树结构，满足堆性质。堆能够在O(log n)时间内插入元素和取出最大或最小元素，这使得它成为实现优先级队列的标准数据结构。

# Python heapq (最小堆)
import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
min_elem = heapq.heappop(heap)  # 1# 将列表转换为堆
lst = [3, 1, 4, 1, 5]
heapq.heapify(lst)# Top K问题
numbers = [5, 2, 8, 1, 9, 3]
top3 = heapq.nlargest(3, numbers)  # [9, 8, 5]

// C++ priority_queue (最大堆)
#include <queue>
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(2);
int max_elem = pq.top();  // 3
pq.pop();// 最小堆
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(3);
min_pq.push(1);
int min_elem = min_pq.top();  // 1

堆的应用场景包括Top-K问题、任务调度、Dijkstra最短路径算法、合并K个有序数组等。

树与图

树和图是表达层次关系和网络关系的非线性数据结构，在Python和C++中都没有内置的标准实现，需要根据具体问题自行设计。

# Python - 树节点定义
class TreeNode:def __init__(self, val):self.val = valself.left = Noneself.right = None# 二叉树遍历
def inorder(root):if root:inorder(root.left)print(root.val)inorder(root.right)# Python - 图的邻接表表示
graph = {'A': ['B', 'C'],'B': ['A', 'D', 'E'],'C': ['A', 'F'],'D': ['B'],'E': ['B', 'F'],'F': ['C', 'E']
}# BFS遍历
from collections import deque
def bfs(graph, start):visited = set()queue = deque([start])visited.add(start)while queue:node = queue.popleft()print(node)for neighbor in graph[node]:if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)

// C++ - 树节点定义
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// C++ - 图的邻接表表示
#include <unordered_map>
#include <vector>
std::unordered_map<int, std::vector<int>> graph;
graph[1] = {2, 3};
graph[2] = {1, 4};
graph[3] = {1, 4};
graph[4] = {2, 3};// DFS遍历
void dfs(int node, std::unordered_set<int>& visited) {visited.insert(node);std::cout << node << " ";for (int neighbor : graph[node]) {if (visited.find(neighbor) == visited.end()) {dfs(neighbor, visited);}}
}

树结构应用于文件系统、语法分析树、决策树、B树索引等。C++的std::map和std::set底层就是红黑树实现。图结构用于表达任意的多对多关系，应用于网络路由、社交网络分析、依赖关系解析等领域。

第四部分：选型实战指南

核心三件套的应用场景

在实际开发中，大约90%的数据结构需求可以由数组、字典和集合满足。这三种结构分别对应三种最基本的数据组织需求：有序集合、键值映射、无重复集合。

# Python实战示例：推荐系统中的数据结构选择# 1. 用户历史行为 - 使用list
user_history = [101, 205, 303, 410]  # 按时间顺序的物品ID# 2. 物品特征映射 - 使用dict
item_features = {101: {'category': 'electronics', 'price': 999},205: {'category': 'books', 'price': 29}
}# 3. 已推荐物品 - 使用set
recommended = {101, 205, 303}# 过滤已推荐物品
candidates = [101, 205, 401, 502]
new_candidates = [item for item in candidates if item not in recommended]# 计算用户共同兴趣
user1_items = {101, 205, 303}
user2_items = {205, 303, 401}
common_interests = user1_items & user2_items  # {205, 303}

// C++实战示例：高性能计算中的数据结构选择#include <vector>
#include <unordered_map>
#include <unordered_set>// 1. 大规模数值计算 - 使用vector
std::vector<double> data(1000000);
for (size_t i = 0; i < data.size(); ++i) {data[i] = compute(i);
}// 2. 特征索引 - 使用unordered_map
std::unordered_map<std::string, int> feature_index;
feature_index["age"] = 0;
feature_index["income"] = 1;// 3. 去重与快速查找 - 使用unordered_set
std::unordered_set<int> seen;
for (int value : data) {if (seen.count(value) == 0) {process(value);seen.insert(value);}
}

特定场景的选型决策

// 场景1：需要维护有序数据并进行范围查询 - 使用map
std::map<int, std::string> timestamp_events;
timestamp_events[1000] = "event1";
timestamp_events[2000] = "event2";
timestamp_events[3000] = "event3";// 查询时间区间[1500, 2500]内的所有事件
auto start = timestamp_events.lower_bound(1500);
auto end = timestamp_events.upper_bound(2500);
for (auto it = start; it != end; ++it) {std::cout << it->second << "\n";
}

# 场景2：频繁在序列两端操作 - 使用deque
from collections import deque# 实现固定大小的滑动窗口
window = deque(maxlen=5)
for value in data_stream:window.append(value)if len(window) == 5:avg = sum(window) / 5print(f"Moving average: {avg}")

# 场景3：优先级调度 - 使用堆
import heapq# 任务调度系统
tasks = []
heapq.heappush(tasks, (1, "high priority task"))
heapq.heappush(tasks, (5, "low priority task"))
heapq.heappush(tasks, (3, "medium priority task"))# 按优先级处理任务
while tasks:priority, task = heapq.heappop(tasks)process(task)

性能优化要点

// 优化1：预分配空间避免频繁扩容
std::vector<int> vec;
vec.reserve(1000000);  // 预分配容量
for (int i = 0; i < 1000000; ++i) {vec.push_back(i);  // 不会触发扩容
}// 优化2：使用emplace避免不必要的拷贝
std::vector<std::string> strings;
strings.emplace_back("hello");  // 就地构造，无拷贝// 优化3：使用const引用传递容器
void process(const std::vector<int>& data) {// 避免拷贝整个容器
}

# 优化1：使用生成器减少内存占用
def process_large_file(filename):with open(filename) as f:for line in f:  # 逐行处理，不加载整个文件yield process(line)# 优化2：使用集合判断成员资格而非列表
# 错误方式 - O(n)
if item in large_list:pass# 正确方式 - O(1)
large_set = set(large_list)
if item in large_set:pass