学习数据结构的框架思维

线性数据结构

  • 数组/向量 vector
    优点内存局部性好
    下标直接访问
  • 链表(基本操作)list
    查找、插入、删除 带有哑结点的链表
  • 栈 stack
    深度优先算法
  • 队列 queue
    控制流程图算法 广度优先算法

集合和字典(set和map) 基于基本的线性结构

  • 7大功能
    查找、插入、删除 最小元 最大元 上一元素 下一元素
  • 底层实现
    可以使用无序数组、有序数组
    使用二叉查找树来实现 保持平衡(红黑树) h=O(logn)
    treap 树堆

堆结构(priority_queue)

  • 优先级队列 下沉操作 上浮操作

散列(unordered_set) 优点快速查找

  • 散列函数的设计
  • 装填因子的选择 a = total/m格
  • 底层实现 使用结链法
  • 性能分析 最长链、平均链长
  • 可用于字符串子串匹配 rabin-karp算法