数据结构

数据结构是计算机科学中用于高效组织、存储和管理数据的核心概念。它决定了数据如何被访问、修改和操作，直接影响程序的性能和可维护性。

同时对于学习数据结构，我的笔记本身记得不是很好，所以，我给你推荐两个网站，一个是hello算法，另一个是柏马数据结构。

1 数据结构的本质

• 目的：解决复杂问题时，通过合理设计数据的存储形式，优化时间与空间效率。
• 与算法的关系： 数据结构是算法的载体（如排序算法依赖数组或链表），而算法依赖数据结构实现功能（如搜索算法需哈希表支持）。

2 常见数据结构分类

2.1. 线性结构

数组（Array）

• 特点：连续内存分配，索引直接访问，支持随机读取。

• 缺点：插入/删除效率低（O(n)）。

• 场景：缓存、矩阵运算。

链表（Linked List）

• 单链表/双向链表/循环链表

• 特点：动态扩展，插入/删除快（O(1)），但随机访问慢（O(n)）。

• 场景：实现栈、队列，内存管理。

栈（Stack）

• LIFO（后进先出），仅操作头部。

• 应用：函数调用栈、表达式解析。

队列（Queue）

• FIFO（先进先出），队尾添加，队头删除。
• 应用：任务调度、广度优先搜索（BFS）。

2.2. 树形结构

二叉树（Binary Tree）

• 节点最多两个子节点（左/右）。

• 优化搜索效率（如二叉搜索树，BST）。

平衡树（Balanced Tree）

• 自动调节高度，保持左右子树平衡（如AVL树、红黑树）。

• 应用：数据库索引、语言标准库（C++ STL中的map）。

堆（Heap）

• 完全二叉树，父节点值大于等于（最大堆）或小于等于（最小堆）子节点。

• 应用：优先级队列、Dijkstra算法。

Trie树（字典树）

• 前缀树，高效存储字符串集合（如自动补全）。

2.3 图（Graph）

• **节点（Node）与边（Edge）**构成，分为有向图和无向图。
• 应用：社交网络分析、路径规划（最短路径算法）。

2.4 哈希表（Hash Table）

• 通过哈希函数将键（Key）映射到桶（Bucket），实现O(1)平均时间复杂度的查找。
• 缺点：哈希冲突需额外处理（链表法、开放寻址法）。
• 应用：数据库索引、缓存（Redis）、集合（Set）。

2.5 高级结构

• 并查集（Disjoint Set Union, DSU）：管理元素分组，支持快速合并与查询。
• 线段树（Segment Tree）：区间查询与更新（如Range Sum Query）。
• 跳表（Skip List）：基于有序链表的随机访问优化，常用于数据库索引。