数据结构基本概念

💡 低优先级
不会直接考察类型,这里作为一个总览,帮助大家理清考题中会涉及到哪些数据结构。

数据结构

数据结构(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
      哈希函数
      快速查找
      应用
        字典
        缓存

考试中涉及的数据结构可以分为以下几种:

  1. 线性结构(元素之间有顺序关系)
    • 数组(Array):连续内存,随机访问快,插入删除慢
    • 链表(Linked List):节点通过指针连接,插入删除快,访问慢
    • 栈(Stack):后进先出(LIFO),用于函数调用、表达式求值
    • 队列(Queue):先进先出(FIFO),用于任务调度
    • 双端队列(Deque):两端都可以操作
  2. 树形结构(元素之间有层级关系)
    • 二叉树(Binary Tree)
    • 二叉搜索树(BST)
    • 堆(Heap):优先队列实现
    • 平衡树(AVL、红黑树)
  3. 图结构(元素之间有网络关系)
    • 有向图 / 无向图
    • 邻接矩阵 / 邻接表存储
    • 常用于路径搜索、社交网络建模
  4. 散列表(Hash Table)
    • 通过哈希函数实现快速查找
    • 常用于字典、缓存

算法

算法(Algorithm)是 解决问题的一系列步骤或方法,用来操作数据结构,实现具体功能。

数据结构和算法的关系

  • 数据结构提供“容器”
  • 算法提供“操作方法”
  • 好的数据结构可以让算法更高效
  • 算法的设计也依赖数据结构特性

💡 举例:

  • 用数组实现栈 → 可以快速访问栈顶
  • 用链表实现队列 → 插入删除都很快
  • 用堆实现优先队列 → 可以快速找最大/最小值
  • 用图 + BFS → 可以找最短路径