符号表

定义：

  • 符号表是一种键值对 (Key-Value Pair) 存储结构。
  • 主要目标是将键 (Key) 与 值 (Value) 关联起来，实现通过键快速查找对应的值。
  • 类似于关联数组或字典，键可以是任意类型。

两种基础实现及性能对比：

  • 1. 顺序查找 (Sequential Search) - 基于无序链表：
    • 原理： 使用链表存储键值对，查找和插入操作均需遍历链表。
    • 优点： 实现简单，适用于小型问题。
    • 缺点： 对于大型符号表，查找和插入效率低 (最坏情况需 N 次比较)。插入 N 个不同键需约 N²/2 次比较。
    • 性能特点： 查找和插入操作的时间复杂度均为 O(N)，其中 N 为符号表大小。
  • 2. 二分查找 (Binary Search) - 基于有序数组：
    • 原理： 使用有序数组存储键，利用二分查找算法进行快速查找。
    • 优点： 查找效率高 (最多 logN + 1 次比较)，有序性相关操作效率高。
    • 缺点： 插入操作慢 (最坏情况需移动约 2N 次数组元素)，插入 N 个元素需约 N² 次数组访问。
    • 性能特点： 查找操作时间复杂度为 O(logN)，插入和删除操作时间复杂度为 O(N)。