当前位置： 首页 > news >正文

常用数据结构及复杂度

news 2026/7/26 18:55:38

常用数据结构及复杂度

在软件开发中，数据结构是组织和存储数据的方式，它直接影响程序的性能。理解常见数据结构及其时间复杂度（Big O 表示法）是每个工程师的必备技能。本文将从实战角度出发，通过大量代码示例，深入剖析数组、链表、栈、队列、哈希表、树和图等核心数据结构，并分析它们在插入、删除、查找等操作下的复杂度。### 一、数组（Array）数组是最基础的数据结构，它使用连续的内存空间存储一组相同类型的元素。其核心优势在于通过索引访问元素时，时间复杂度为 O(1)，但插入和删除操作（特别是中间位置）会导致元素移动，复杂度为 O(n)。#### 实战示例：Python 数组操作python# 示例：数组的插入、删除和访问def array_operations(): arr = [10, 20, 30, 40, 50] print("原始数组:", arr) # 访问第三个元素 (索引2) - O(1) element = arr[2] print(f"访问索引2的元素: {element}") # 输出: 30 # 在索引1插入元素25 - O(n) arr.insert(1, 25) print("插入25后:", arr) # 输出: [10, 25, 20, 30, 40, 50] # 删除索引3的元素 - O(n) arr.pop(3) print("删除索引3后:", arr) # 输出: [10, 25, 20, 40, 50] # 查找元素20 - O(n) index = arr.index(20) print(f"元素20的索引: {index}") # 输出: 2array_operations()复杂度总结：- 访问：O(1)- 查找：O(n)- 插入（末尾）：O(1)- 插入（中间）：O(n)- 删除（末尾）：O(1)- 删除（中间）：O(n)### 二、链表（Linked List）链表通过节点（Node）之间的指针连接数据，不要求连续内存。单链表的插入和删除操作在已知位置时效率高（O(1)），但查找元素需要遍历（O(n)）。#### 实战示例：Python 单链表实现pythonclass Node: def __init__(self, data): self.data = data self.next = Noneclass LinkedList: def __init__(self): self.head = None # 在链表末尾插入元素 - O(n) def append(self, data): new_node = Node(data) if not self.head: self.head = new_node return current = self.head while current.next: current = current.next current.next = new_node # 在链表头部插入元素 - O(1) def prepend(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node # 删除指定元素 - O(n) def delete(self, data): if not self.head: return if self.head.data == data: self.head = self.head.next return current = self.head while current.next and current.next.data != data: current = current.next if current.next: current.next = current.next.next def display(self): elements = [] current = self.head while current: elements.append(current.data) current = current.next print("链表内容:", elements)# 测试链表操作ll = LinkedList()ll.append(10)ll.append(20)ll.prepend(5) # 头部插入ll.display() # 输出: [5, 10, 20]ll.delete(10)ll.display() # 输出: [5, 20]复杂度总结：- 访问：O(n)- 查找：O(n)- 插入（头部/已知位置）：O(1)- 插入（末尾）：O(n)- 删除（已知位置）：O(1)- 删除（查找后删除）：O(n)### 三、栈（Stack）和队列（Queue）栈是后进先出（LIFO）结构，常用于函数调用和撤销操作；队列是先进先出（FIFO）结构，常用于任务调度和缓冲区。#### 实战示例：Python 实现栈和队列pythonfrom collections import deque# 栈实现class Stack: def __init__(self): self.items = [] def push(self, item): # O(1) self.items.append(item) def pop(self): # O(1) if not self.is_empty(): return self.items.pop() return None def peek(self): # O(1) if not self.is_empty(): return self.items[-1] return None def is_empty(self): return len(self.items) == 0# 队列实现（使用deque保证效率）class Queue: def __init__(self): self.items = deque() def enqueue(self, item): # O(1) self.items.append(item) def dequeue(self): # O(1) if not self.is_empty(): return self.items.popleft() return None def front(self): # O(1) if not self.is_empty(): return self.items[0] return None def is_empty(self): return len(self.items) == 0# 测试栈stack = Stack()stack.push(1)stack.push(2)stack.push(3)print("栈弹出:", stack.pop()) # 输出: 3# 测试队列queue = Queue()queue.enqueue(1)queue.enqueue(2)queue.enqueue(3)print("队列出队:", queue.dequeue()) # 输出: 1复杂度总结：- 栈：push O(1), pop O(1), peek O(1)- 队列：enqueue O(1), dequeue O(1), front O(1)### 四、哈希表（Hash Table）哈希表通过哈希函数将键映射到存储位置，以实现平均 O(1) 的查找、插入和删除操作。但在处理哈希冲突时（如链地址法），最坏情况可能退化为 O(n)。#### 实战示例：Python 字典操作python# Python 内置字典就是哈希表实现def hash_table_demo(): user_scores = { "Alice": 95, "Bob": 87, "Charlie": 92 } # 插入 - O(1) 平均 user_scores["David"] = 88 print("插入David后:", user_scores) # 访问 - O(1) 平均 alice_score = user_scores["Alice"] print(f"Alice的分数: {alice_score}") # 输出: 95 # 删除 - O(1) 平均 del user_scores["Bob"] print("删除Bob后:", user_scores) # 查找 - O(1) 平均 if "Charlie" in user_scores: print("Charlie在字典中") # 冲突处理（演示链地址法） # 当两个键哈希值相同时，Python使用开放寻址法处理冲突 # 这里仅展示概念 custom_table = {} custom_table["key1"] = 1 custom_table["key2"] = 2 # 可能发生冲突，但Python自动处理 print("自定义哈希表:", custom_table)hash_table_demo()复杂度总结：- 插入：平均 O(1)，最坏 O(n)- 删除：平均 O(1)，最坏 O(n)- 查找：平均 O(1)，最坏 O(n)### 五、树（Tree）树是一种非线性结构，二叉搜索树（BST）在平衡状态下，查找、插入和删除的时间复杂度为 O(log n)。但若不平衡，可能退化为 O(n)。#### 实战示例：Python 二叉搜索树pythonclass TreeNode: def __init__(self, val): self.val = val self.left = None self.right = Noneclass BinarySearchTree: def __init__(self): self.root = None # 插入 - O(log n) 平均，O(n) 最坏 def insert(self, val): if not self.root: self.root = TreeNode(val) return self._insert_recursive(self.root, val) def _insert_recursive(self, node, val): if val < node.val: if node.left: self._insert_recursive(node.left, val) else: node.left = TreeNode(val) else: if node.right: self._insert_recursive(node.right, val) else: node.right = TreeNode(val) # 查找 - O(log n) 平均，O(n) 最坏 def search(self, val): return self._search_recursive(self.root, val) def _search_recursive(self, node, val): if not node or node.val == val: return node if val < node.val: return self._search_recursive(node.left, val) return self._search_recursive(node.right, val) # 中序遍历 - O(n) def inorder_traversal(self): result = [] self._inorder(self.root, result) return result def _inorder(self, node, result): if node: self._inorder(node.left, result) result.append(node.val) self._inorder(node.right, result)# 测试BSTbst = BinarySearchTree()values = [50, 30, 70, 20, 40, 60, 80]for v in values: bst.insert(v)print("中序遍历:", bst.inorder_traversal()) # 输出: [20, 30, 40, 50, 60, 70, 80]found = bst.search(40)print("查找40:", found.val if found else "未找到") # 输出: 40复杂度总结：- 插入（平衡树）：O(log n)- 删除（平衡树）：O(log n)- 查找（平衡树）：O(log n)- 遍历：O(n)### 六、图（Graph）图由顶点和边组成，常用邻接矩阵或邻接表表示。深度优先搜索（DFS）和广度优先搜索（BFS）的时间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数。#### 实战示例：Python 图实现与遍历pythonfrom collections import defaultdict, dequeclass Graph: def __init__(self): self.graph = defaultdict(list) # 邻接表 # 添加边 - O(1) def add_edge(self, u, v): self.graph[u].append(v) self.graph[v].append(u) # 无向图 # 广度优先搜索 - O(V + E) def bfs(self, start): visited = set() queue = deque([start]) visited.add(start) result = [] while queue: vertex = queue.popleft() result.append(vertex) for neighbor in self.graph[vertex]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return result # 深度优先搜索 - O(V + E) def dfs(self, start): visited = set() result = [] self._dfs_recursive(start, visited, result) return result def _dfs_recursive(self, vertex, visited, result): visited.add(vertex) result.append(vertex) for neighbor in self.graph[vertex]: if neighbor not in visited: self._dfs_recursive(neighbor, visited, result)# 测试图g = Graph()g.add_edge(0, 1)g.add_edge(0, 2)g.add_edge(1, 2)g.add_edge(1, 3)g.add_edge(2, 4)print("BFS从0开始:", g.bfs(0)) # 输出: [0, 1, 2, 3, 4]print("DFS从0开始:", g.dfs(0)) # 输出: [0, 1, 2, 3, 4]复杂度总结：- 添加边：O(1)- BFS：O(V + E)- DFS：O(V + E)### 总结本文从实战角度出发，通过 Python 代码示例详细介绍了数组、链表、栈、队列、哈希表、树和图这七种常用数据结构。每种数据结构都有其独特的适用场景和时空复杂度：-数组适合快速随机访问，但插入和删除慢，适用于静态数据。-链表适合频繁插入和删除，但查找慢，适用于动态场景。-栈和队列是线性结构的特例，适用于特定顺序的数据处理。-哈希表提供近乎常数时间的操作，是键值对存储的首选。-树在平衡时提供对数级操作，适用于需要有序数据的场景。-图适用于复杂关系建模，遍历算法是核心操作。理解这些数据结构的复杂度，是编写高效代码的基础。在实际开发中，应根据具体需求（如数据量、操作频率、内存限制）选择合适的数据结构，甚至组合使用以达到最佳性能。

http://www.jsqmd.com/news/1269187/

相关文章：

  • 01:A+B问题
  • 探索风扇智能控制：构建个人PC散热系统的完整指南
  • GPU加速实时图像处理引擎：5大技术优势深度解析
  • 编写程序，接受结果不完美，程序保存半成品创意，后续不定期迭代，慢慢打磨成完整作品。
  • 5分钟掌握Illustrator智能脚本：提升设计效率10倍的终极指南
  • BililiveRecorder终极指南：高效实现B站直播自动录制与智能管理
  • ALVR无线串流：如何彻底摆脱线缆束缚，享受自由VR游戏体验
  • 2026年巴度食品固体饮料贴牌代工双认证解读 - 万相科技
  • 从理论到落地：数据库范式（1NF-4NF）的准确定义与工程取舍
  • 2026年云南电大中专怎么报名？在哪报名？招生办联系电话是多少？ - 最新资讯
  • Havenlon | 杂谈：总有刁民想害朕：一句玩笑话里的安全工程学
  • 图片转文字识别软件免费版有哪些：乱码表格繁体坑怎么排
  • 终极指南：5分钟快速上手CFR Java反编译神器
  • RedReader开发者终极指南：3步快速配置Reddit API密钥
  • GetQzonehistory：终极QQ空间回忆备份工具完整指南
  • 深度解析AhMyth：跨平台Android远程管理工具的终极实战指南
  • Ministral-3-8B-Base-2512-8bit核心特性大揭秘：8位量化技术如何实现高效边缘计算
  • 【Python课程设计/毕业设计】基于 Python 的多媒体音乐资源管理与社交分享系统 在线音乐社区互动与资源推送平台【附源码、数据库、万字文档】
  • 2026年上海120长途跨市救护车选择指南 不同需求对应转运服务全解析 - 榜单测评
  • [具身智能-664]：TogetheROS.Bot的出现的背景、发展历史、深度定制化解决什么问题以及与原始ROS2的对比。
  • 最新卖家精灵插件支持listing速览，可用最新的卖家精灵优惠折扣码开通！ - 跨境电商卖家出海
  • 武汉合院别墅设计行业深度评测：四面围合的那方天地，谁在让院落精神真正重生？ - 品牌红黑榜
  • NeteaseCloudMusicApi：在C中构建网易云音乐客户端与服务的完整指南
  • 2026中科大软件学院夏令营、推免指南
  • 昆明宝妈看过来！2026电大中专报名启动，不耽误带娃，拿证后正好赶上明年二建报考 - 最新资讯
  • 漯河食品厂员工：2026电大中专药剂/中药专业，转岗质检/药房的必备学历 - 最新资讯
  • 如何构建支持百万字符对话的智能助手：LWM完全指南
  • 告别复杂UI开发：用Vizia构建响应式Rust桌面应用的全新范式
  • 免费开源字体Montserrat终极指南：现代设计的几何美学解决方案
  • 02:计算(a+b)*c的值