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

郑州网站关键词优化,做网站会什么问题,iis ip访问网站,工业设计在线1. 数组 (Array) 定义 一组连续内存空间存储的相同类型元素的集合。特点#xff1a;通过下标#xff08;索引#xff09;快速访问元素#xff0c;但大小固定#xff08;静态数组#xff09;或可扩展#xff08;动态数组#xff09;。 核心操作 操作时间复杂度说明访…1. 数组 (Array) 定义 一组连续内存空间存储的相同类型元素的集合。特点通过下标索引快速访问元素但大小固定静态数组或可扩展动态数组。 核心操作 操作时间复杂度说明访问元素O(1)通过索引直接访问如arr[3]插入元素O(n)需要移动后续元素删除元素O(n)同上查找元素O(n)遍历查找无序数组 代码示例

创建数组

arr [1, 2, 3, 4]# 访问元素 print(arr[0]) # 输出 1# 插入元素在末尾添加 arr.append(5) # O(1)动态数组均摊时间 arr.insert(2, 10) # O(n)插入到中间# 删除元素 arr.pop() # 删除末尾元素 O(1) arr.pop(0) # 删除第一个元素 O(n)应用场景 需要快速随机访问如矩阵运算数据量已知或变化较小的场景 2. 链表 (Linked List) 定义 由节点组成的数据结构每个节点包含数据和指向下一个节点的指针。特点内存非连续插入/删除高效但访问元素需要遍历。 类型 单链表每个节点指向下一个节点。双链表节点同时指向前驱和后继。循环链表尾节点指向头节点。 核心操作 操作时间复杂度说明访问元素O(n)从头节点开始遍历插入/删除O(1)已知前驱节点时如双链表查找元素O(n)必须遍历 代码示例单链表 class ListNode:def init(self, val0, nextNone):self.val valself.next next# 创建链表1 - 2 - 3 head ListNode(1) head.next ListNode(2) head.next.next ListNode(3)# 插入节点在节点2后插入4 node head.next new_node ListNode(4) new_node.next node.next node.next new_node # 链表变为1 - 2 - 4 - 3# 删除节点删除节点4 node.next node.next.next # 链表恢复为1 - 2 - 3应用场景 频繁插入/删除的场景如LRU缓存实现栈、队列等数据结构 3. 栈 (Stack) 定义 后进先出(LIFO)的线性结构。核心操作push入栈、pop出栈、peek查看栈顶。 代码示例

用列表模拟栈

stack [] stack.append(1) # push 1 stack.append(2) # push 2 top stack[-1] # peek - 2 stack.pop() # pop - 2应用场景 函数调用栈括号匹配、表达式求值如逆波兰表达式 4. 队列 (Queue) 定义 先进先出(FIFO)的线性结构。核心操作enqueue入队、dequeue出队。 代码示例 from collections import deque queue deque() queue.append(1) # 入队 queue.append(2) front queue[0] # 查看队首 queue.popleft() # 出队 - 1变种队列 双端队列 (Deque)两端均可插入/删除。优先队列 (Priority Queue)按优先级出队通常用堆实现。 应用场景 任务调度、消息队列BFS广度优先搜索 5. 哈希表 (Hash Table) 5.1 哈希表 概念 定义 通过键(Key)直接访问值(Value)的数据结构。核心思想哈希函数将键映射到存储位置。 冲突解决 开放寻址法冲突时寻找下一个空槽。链地址法每个槽存储链表如Python的字典。 代码示例

Python字典 即哈希表实现

hash_map {} hash_map[apple] 1 # 插入 hash_map[banana] 2 print(hash_map.get(apple)) # 获取 - 1 del hash_map[banana] # 删除应用场景 快速查找如数据库索引统计频率如字母异位词分组 5.2 链地址法Chaining 核心思想 每个数组的索引位置称为“桶”不再直接存储单个键值对而是存储一个链表或红黑树等其他数据结构。当多个键的哈希值冲突时它们会被添加到同一个桶的链表中。 具体操作 插入键值对 计算键的哈希值找到对应桶。如果桶为空直接存入链表头节点。如果桶不为空遍历链表 如果发现键已存在更新值。如果不存在将新键值对添加到链表末尾或头部。 查找键值对 计算键的哈希值找到对应桶。遍历链表逐个比较键是否匹配。
代码示例Python简化版 class HashTable:def init(self, size10):self.size sizeself.table [[] for _ in range(size)] # 每个桶是一个列表模拟链表def _hash(self, key):return hash(key) % self.size # 哈希函数def put(self, key, value):bucket_idx self._hash(key)bucket self.table[bucket_idx]# 遍历链表检查是否已存在该键for i, (k, v) in enumerate(bucket):if k key:bucketi # 更新键值对returnbucket.append((key, value)) # 添加新键值对def get(self, key):bucket_idx self._hash(key)bucket self.table[bucket_idx]for k, v in bucket:if k key:return vreturn None # 未找到为什么链地址法不会导致效率低下 虽然链表需要遍历但哈希表的设计目标是通过以下两点保证高效性 (1) 哈希函数的均匀性 好的哈希函数会将键均匀分布到各个桶中避免大量冲突。例如Python的哈希函数对字符串、整数等类型有优化冲突概率极低。 (2) 负载因子Load Factor控制 负载因子 哈希表中元素数量 / 桶的数量。当负载因子超过阈值如0.75哈希表会触发扩容Rehashing 创建一个更大的桶数组例如翻倍。将所有键值对重新哈希到新桶中。 扩容后冲突概率显著降低链表长度保持较短通常为0-2个节点。 现代哈希表如Java的HashMap会进一步优化链地址法 链表转红黑树Java当链表长度超过阈值如8将链表转换为红黑树将查找时间从O(n)优化为O(log n)。动态扩容策略根据负载因子智能调整桶的数量平衡时间和空间。 5.3 开放地址法Open Addressing 核心思想 开放地址法的思想是当发生冲突时寻找另一个空的数组位置来存储冲突的元素。常见的解决方法有线性探测法、二次探测法和双重哈希法等。 具体实现 插入当插入新元素时计算哈希值如果该位置已经被占用就按照预定的探测策略如线性探测尝试查找下一个空的位置。查找查找时先计算哈希值如果当前位置的元素就是我们要查找的键就直接返回值。如果当前位置不匹配就根据探测策略继续查找其他位置直到找到目标或确认该键不存在。 代码示例Python简化版 class HashTable:def init(self, size10):self.size sizeself.table [None] * self.size # 每个桶直接存储键值对或标记def _hash(self, key):return hash(key) % self.sizedef _probe(self, start_idx):线性探测下一个可用位置idx start_idxwhile True:if self.table[idx] is None or self.table[idx] DELETED:return idxidx (idx 1) % self.size # 回绕到数组开头if idx start_idx: # 整个表已满raise Exception(Hash table is full)def put(self, key, value):start_idx self._hash(key)idx start_idx# 查找可插入的位置或更新现有键while True:if self.table[idx] is None or self.table[idx] DELETED:# 插入新键值对self.tableidxreturnelif self.table[idx][0] key:# 键已存在更新值self.tableidxreturnidx (idx 1) % self.size # 通过取余方式能够遍历整个数组if idx start_idx:raise Exception(Hash table is full)def get(self, key):start_idx self._hash(key)idx start_idxwhile True:entry self.table[idx]if entry is None:return None # 未找到elif entry ! DELETED and entry[0] key:return entry[1] # 返回找到的值idx (idx 1) % self.sizeif idx start_idx:return None # 遍历完整个表未找到6. 二叉树 (Binary Tree) 定义 每个节点最多有两个子节点左子节点、右子节点。特殊类型 二叉搜索树 (BST)左子树所有节点 根节点 右子树所有节点。平衡二叉树如AVL树、红黑树通过旋转保持高度平衡。
遍历方式 遍历方式顺序前序遍历根 - 左 - 右中序遍历左 - 根 - 右后序遍历左 - 右 - 根层序遍历按层级从上到下、从左到右 代码示例二叉树节点 class TreeNode:def init(self, val0, leftNone, rightNone):self.val valself.left leftself.right right# 创建二叉树 root TreeNode(1) root.left TreeNode(2) root.right TreeNode(3)应用场景 文件系统结构表达式树用于计算 7. 堆 (Heap) 定义 一种完全二叉树满足 最大堆父节点值 ≥ 子节点值。最小堆父节点值 ≤ 子节点值。
:::tip 完全二叉树是指除了最后一层外其他层的节点都是 满的并且最后一层的节点 尽可能靠左排列。 ::: 核心操作 操作时间复杂度说明插入元素O(log n)上浮调整sift up删除堆顶O(log n)下沉调整sift down 代码示例Python的 heapq 模块 import heapq# 最小堆 heap [] heapq.heappush(heap, 3) heapq.heappush(heap, 1) heapq.heappush(heap, 2) print(heapq.heappop(heap)) # 输出1应用场景 优先队列Top K问题如最大的K个元素 8. 图 (Graph) 定义 由 顶点(Vertex) 和 边(Edge) 组成的非线性结构。表示方式 邻接矩阵二维数组表示顶点连接关系。邻接表为每个顶点维护一个链表记录其邻居。
常见算法 遍历DFS深度优先、BFS广度优先最短路径Dijkstra无负权边、Bellman-Ford含负权边最小生成树Prim算法、Kruskal算法 代码示例邻接表表示图

使用字典表示邻接表

graph {A: [B, C],B: [D],C: [E],D: [],E: [] }# DFS遍历 def dfs(graph, node, visited):if node not in visited:print(node)visited.add(node)for neighbor in graph[node]:dfs(graph, neighbor, visited)dfs(graph, A, set()) # 输出A - B - D - C - E应用场景 社交网络顶点为用户边为好友关系路径规划如地图导航