open-courses
Search…
Sequence and Set Interface

Interface (API/ADT) vs. Data structure

二者的主要区别如下:
Interface (API/ADT)
Data Structure
规范 (Specification)
表现形式 (Representation)
需要维护什么数据
如何维护数据
指定支持的操作及其语义
实现所支持操作的算法
提出问题
解决方案

Sequence Interface

Static Sequence Interface

维护一个数据序列(sequence),
x0,x1,x2,...,xn1x_0, x_1, x_2, ..., x_{n-1}
,同时支持以下操作:
  • len():返回数据序列的长度 n
  • seq-iter():遍历
    x0,x1,x2,...,xn1x_0, x_1, x_2, ..., x_{n-1}
  • at(i):返回序号为 i 的数据
    xix_i
    • left() => at(0)
    • right() => at(n-1)
  • set-at(i, x):将序号为 i 的元素替换为 x
我们有哪些数据结构可以实现 static sequence interface?如静态数组 A[0...n]

Dynamic Sequence Interface

维护一个数据序列,
x0,x1,x2,...,xn1x_0, x_1, x_2, ..., x_{n-1}
,除了支持 Static Sequence Interface 之外,还支持以下操作:
  • insert-at(i, x):将 x 插入到序号为 i 的位置上,同时将所有原来序号 ≥ i 的元素向右移动一个位置
  • delete-at(i): 将所有序号 ≥ i+1 的元素向左移动一个位置
  • set-at(i, x):语义上等同于连续执行 delete-at(i) 和 insert-at(i, x)

特殊案例:

  • Stack
    • right() - top
    • insert/delete-right() - push/pop
  • queue
    • insert-right() - enqueue
    • delete-left() - dequeue
  • deque
    • insert/delete left/right

Set Interface

Static Set Interface

维护一个键值对集合,支持以下操作:
  • find-key(k):如果可以,找到对应 k 的值
  • iter():按任意顺序遍历所有键值对/键/值

Dynamic Set Interface

维护一个键值对集合,在支持 static set interface 所有操作的基础上,支持以下操作:
  • insert(k, x):将键值对 k, v 存入键值对中,若键已存在,则覆盖值
  • delete-key(k):将键为 k 的键值对从集合中删除

Ordered Set Interface

维护一个键值对集合,所有键按顺序排列。在支持 static set interface 所有操作的基础上,支持以下操作:
  • find-next(k):找到键大于 k 的最小键对应的值
  • find-prev(k):找到键小于 k 的最大键对应的值
  • find-min():找到最小键对应的值
  • find-max():找到最大键对应的值
  • order-iter():按键的顺序依次遍历所有键值对/键/值

Dynamic Ordered Set Interface

在 Ordered Set Interface 的基础上,支持以下操作:
  • delete-min():删除最小键对应的键值对
  • delete-max():删除最大键对应的键值对

Priority Queue Interface

priority queue 是 dynamic ordered set 的一个特殊例子,支持:
  • insert(x)
  • find/delete-min() 或者 find/delete-max()