跳转至

列表、栈、队列

Abstract

数据结构基础第 2 周课程内容

  • 数据类型(Data Type)= { 对象 } ∪ { 操作 }
  • 抽象数据类型(Abstract Data Type),指定的对象和操作和实际的表示以及实现是分离的

列表 ADT

  • 对象:(元素 0, 元素 1, ..., 元素 n-1)
  • 操作:
    • 寻找长度:n
    • 打印列表
    • 构造空列表
    • 找到第 k 个元素
    • 在第 k 个元素后插入新元素
    • 删除某一个元素
    • 找到当前元素的下一个/上一个元素
  • 有多种实现:简单数组、各种链表……
  • 简单数组
    • 优点:
      • 找第 k 个元素的复杂度为 \(O(1)\)
    • 缺点:
      • 需要预先估计最大长度(分配空间)
      • 插入和删除复杂度为 \(O(N)\),且会造成大量内存移动
  • 链表
    • 插入和删除复杂度都为 \(O(1)\)
    • 动态分配空间
    • 寻找第 k 个元素复杂度 \(O(N)\)
    • 会涉及删除第一个节点的话添加虚拟表头(dummy head)更方便

最后更新: 2022年9月21日 01:16:49
创建日期: 2022年9月21日 01:16:49
回到页面顶部