算法与数据结构

算法与数据结构：定义、范畴与抽象数据类型

01-基础与复杂度分析入门预计 15 分钟基础概念ADT定义总览
学习状态：

一句话定义

算法（Algorithm）是求解特定问题的有限、明确、可终止的步骤序列；数据结构（Data Structure）是组织、存储数据以支持一组操作的方式；抽象数据类型（Abstract Data Type, ADT）只规定「有哪些操作、满足什么语义约定」，把「怎么实现」留给具体数据结构。

为什么重要

这一对概念是整个计算机软件的地基：所有系统的性能上限由算法决定，所有系统的可维护性由数据抽象决定。建立「接口与实现分离」的心智后，你会发现哈希表、红黑树、跳表只是同一个「映射 ADT」的不同实现，选型从「背哪个好」变成「按访问模式推理哪个好」。它也是本库一切讨论的语言：后文所有知识点都默认你能区分 ADT、数据结构、实现这三个层次。

前置知识

本节不适用额外前置：掌握任一语言的变量、循环、函数写法即可开始，数学上只需要能理解「步骤数」这个概念。

核心概念

  • 算法五特性：输入（零个或多个）、输出（至少一个）、确定性（每步含义唯一）、有限性（有限步内终止）、可行性（每步可由基本操作完成）。死循环、依赖随机猜测的「步骤」都不构成算法。
  • 数据结构三要素：逻辑结构（数据元素间的关系，如线性、树形、图状）、存储结构（顺序、链式、索引、散列）、运算集合（增删改查遍历等）。
  • ADT 与实现的分层：例如「栈 ADT」= {push, pop, peek, isEmpty} + LIFO 语义；它的实现可以是数组也可以是链表。调用方只依赖前者，实现可以自由替换。
  • 不变量（Invariant）：每个操作执行前后必须保持的性质（如 BST 的有序性质）。它是结构正确性证明与调试的锚点，本库会反复使用。

直观类比

把 ADT 想象成餐厅菜单上的一道菜：「咖喱饭」规定了内容与口味（操作与语义），后厨用哪个锅做（数组还是链表实现）你并不关心；换后厨不影响你点单——这就是接口与实现分离带来的可替换性。

原理与机制

抽象分层的价值来自两个机制。其一是信息隐藏：实现细节被封在模块内部，调用方只依赖操作契约，因此实现可以优化、替换而调用代码不动。其二是可组合性：复杂结构由简单 ADT 组合而成——LRU 缓存 = 哈希表（定位）+ 双向链表（顺序），图的邻接表 = 顶点数组 + 每顶点的邻居链表。理解了这一点，「学数据结构」就不是背容器 API，而是学每种实现为每种操作付出的代价，以及它维护了什么不变量。

图示

        ┌──────────── ADT：栈 Stack ────────────┐
        │  操作：push / pop / peek / isEmpty    │
        │  语义：后进先出（LIFO）                │
        └───────┬───────────────────┬──────────┘
        实现 A  │                   │  实现 B
     ┌──────────▼────────┐ ┌────────▼─────────┐
     │ 数组实现           │ │ 链表实现          │
     │ 顶部=末尾，O(1)    │ │ 顶部=头节点，O(1) │
     └───────────────────┘ └──────────────────┘

上层只依赖 ADT，两个实现可互换；这正是「数据结构选型」问题的一般形态。

实例或案例

  • 浏览器「后退」按钮是栈：访问新页 push，点后退 pop，回到上一个状态。
  • 打印队列是队列：先提交的先打印，插入在尾、取出在头。
  • 同一个「列表 ADT」，Python 的 list 用动态数组实现（尾插快、中间插慢），而教学用链表实现则相反——同一个接口，代价分布完全不同，这正是后续复杂度分析要量化的事。

常见误区

  • 把「数据结构」等同于「容器类库」：结构的核心是代价分布与不变量，不是 API 名字。
  • 把算法等同于代码：算法先于语言与代码存在，伪代码、流程图都是算法的载体。
  • 只谈效率不谈正确性：一个不满足确定性与终止性的「算法」谈复杂度没有意义，正确性证明（哪怕口头论证不变量）永远优先。

自测题

  1. 「队列」ADT 的操作集与语义约定是什么？用数组实现时头出队为什么不能直接移动数组？

答案要点：enqueue/dequeue/front/isEmpty，先进先出；若每次出队都搬移剩余元素则出队退化为 O(n)，应改用头指针（见 kp-008 循环队列）。

  1. 判断这段伪代码是否算法：while true: x ← x + 1。

答案要点：不终止，违反有限性，故不是算法。

  1. 「映射 Map」ADT 规定了哪些操作？说出两种满足该 ADT 的实现并各给一个最典型操作代价。

答案要点：put/get/delete/contains；哈希表期望 O(1) 查找，平衡树 O(log n) 查找且有序遍历（分别见 kp-009、kp-013）。

与其他知识点的关系

kp-002 把本节的「代价」量化成渐进记号；kp-005 说明这对概念如何演化成一门学科；后续每个具体结构（kp-006 起）都遵循「ADT → 不变量 → 操作代价」的同一分析框架。

延伸阅读

  • 《算法导论》第 1 章「算法在计算中的作用」。
  • 《算法（第 4 版）》第 1.2 节关于抽象数据类型的论述。

前置知识点

本知识点没有前置要求。

相关知识点