数据结构·绪论

什么是数据与数据结构

  • 数据（Data）：能被计算机识别、处理的符号集合（数值、字符、图像、音频等）。
  • 数据元素（Data Element）：数据的基本单位，可由若干数据项组成。
  • 数据结构（Data Structure）：带有“关系”的数据元素集合，通常描述为（数据的逻辑结构 + 存储结构 + 运算）。
  • 抽象数据类型（ADT）：对数据对象及其运算的数学抽象，仅关心“能做什么”，不关心“如何实现”。

逻辑结构与存储结构

  • 逻辑结构：线性结构、集合、树形结构、图结构。
  • 存储结构：顺序存储、链式存储、索引存储、散列（哈希）存储。
flowchart LR A[数据结构] --> B[逻辑结构] A --> C[存储结构] B --> B1[线性表/栈/队列] B --> B2[树/二叉树/堆] B --> B3[图/网] C --> C1[顺序] C --> C2[链式] C --> C3[索引] C --> C4[散列]

常见运算

  • 线性表：查找、插入、删除、遍历
  • 栈/队列：入/出、判空/判满
  • 树/图：遍历（DFS/BFS）、查找、插入/删除、最短路径、最小生成树

算法与复杂度

  • 正确性、可读性、健壮性、效率与代价。
  • 时间复杂度：用大 O 记号表示随输入规模 (n) 增长的执行次数上界，如 (O(1)), (O(log n)), (O(n)), (O(nlog n)), (O(n^2))。
  • 空间复杂度：算法运行所需额外存储的数量级。

顺序与链式的权衡

  • 顺序存储：支持随机访问，定位快；插入/删除（中间位置）代价高；需要连续内存。
  • 链式存储：插入/删除灵活，不需连续内存；随机访问慢（需遍历）。

备考建议：理解“逻辑结构-存储结构-运算”三元关系；掌握各结构的时间/空间权衡与典型用法，为后续各章（线性表、栈队列、树、图）打基础。