数据结构基本概念
低优先级
不会直接考察类型,这里作为一个总览,帮助大家理清考题中会涉及到哪些数据结构。
数据结构
数据结构(Data Structure)是 存储、组织和管理数据的方式,它不仅决定了数据的存储形式,也影响数据访问和操作的效率。
分类
mindmap root((数据结构<br/>Data Structure)) 线性结构 数组 Array 连续内存 随机访问快 插入删除慢 链表 Linked List 节点指针连接 插入删除快 访问慢 栈 Stack 后进先出 LIFO 函数调用 表达式求值 队列 Queue 先进先出 FIFO 任务调度 双端队列 Deque 两端可操作 树形结构 二叉树<br/>Binary Tree 二叉搜索树<br/>BST 堆 Heap 优先队列实现 平衡树 AVL树 红黑树 图结构 有向图 无向图 存储方式 邻接矩阵 邻接表 应用场景 路径搜索 社交网络建模 散列表<br/>Hash Table 哈希函数 快速查找 应用 字典 缓存
考试中涉及的数据结构可以分为以下几种:
- 线性结构(元素之间有顺序关系)
- 数组(Array):连续内存,随机访问快,插入删除慢
- 链表(Linked List):节点通过指针连接,插入删除快,访问慢
- 栈(Stack):后进先出(LIFO),用于函数调用、表达式求值
- 队列(Queue):先进先出(FIFO),用于任务调度
- 双端队列(Deque):两端都可以操作
- 树形结构(元素之间有层级关系)
- 二叉树(Binary Tree)
- 二叉搜索树(BST)
- 堆(Heap):优先队列实现
- 平衡树(AVL、红黑树)
- 图结构(元素之间有网络关系)
- 有向图 / 无向图
- 邻接矩阵 / 邻接表存储
- 常用于路径搜索、社交网络建模
- 散列表(Hash Table)
- 通过哈希函数实现快速查找
- 常用于字典、缓存
算法
算法(Algorithm)是 解决问题的一系列步骤或方法,用来操作数据结构,实现具体功能。
数据结构和算法的关系
- 数据结构提供“容器”
- 算法提供“操作方法”
- 好的数据结构可以让算法更高效
- 算法的设计也依赖数据结构特性
💡 举例:
- 用数组实现栈 → 可以快速访问栈顶
- 用链表实现队列 → 插入删除都很快
- 用堆实现优先队列 → 可以快速找最大/最小值
- 用图 + BFS → 可以找最短路径