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,...,xn−1x_0, x_1, x_2, ..., x_{n-1}x0​,x1​,x2​,...,xn−1​
 ，同时支持以下操作：
len()：返回数据序列的长度 n
seq-iter()：遍历  x0,x1,x2,...,xn−1x_0, x_1, x_2, ..., x_{n-1}x0​,x1​,x2​,...,xn−1​
 
at(i)：返回序号为 i 的数据 xix_ixi​
 
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,...,xn−1x_0, x_1, x_2, ..., x_{n-1}x0​,x1​,x2​,...,xn−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()
​

UCB - CS162 - Previous

Topic: Ensuring Data Reaches Disk

Next - MIT - 6.006

Data Structure for Dynamic Sequence Interface

Last modified 3yr ago

Copy link

Outline

Interface (API/ADT) vs. Data structure

Sequence Interface

Static Sequence Interface

Dynamic Sequence Interface

Set Interface

Static Set Interface

Dynamic Set Interface

Ordered Set Interface

Dynamic Ordered Set Interface