外观
1.3 关系加操作:抽象数据类型
本节问题知道了数据之间的关系,就知道怎么组织它了吗?还缺什么?
回到1.2的四个例子,这次看要对它们做什么。
编辑器里的一行文字,用户要在中间插入字符、删除字符、读出来显示。文件夹要新增、删除、读取、修改,还要一层层打开。地图要查"从家到公司怎么走"、"附近有哪些加油站"、某条路封了要改道。拦截名单要加入号码、移除号码、来电时判断这个号码在不在。
每个例子都是"一种关系"加"一组要做的事"。文件管理的问题可以描述为树形模型加一组操作,导航问题是图模型加一组操作,拦截名单是集合模型加一组操作。这一组要做的事叫操作集,逻辑关系加上操作集,就是描述一个数据模型所需的全部——这样一份描述叫抽象数据类型(Abstract Data Type,ADT):
抽象数据类型 = 逻辑关系 + 操作集
它只说数据是什么关系、能做什么,不说怎么存、怎么做。"抽象"就是这个意思。
同一种关系,不同的操作集,就是不同的抽象数据类型。 光有关系不够,看线性关系:编辑器要在任意位置插入删除;浏览器的"后退"只需记住最近打开的页面、最后打开的最先退回,只在一端进出;打印机处理任务是先提交的先打印,一端进、另一端出。三者的元素之间都是一对一的前后关系,要做的事却不同,于是是三个不同的ADT:任意位置插入删除的叫线性表,只在一端进出的叫栈,一端进另一端出的叫队列。很多教材把栈和队列叫作"操作受限的线性表",这里的"线性表"指的是线性的逻辑关系,说的是同一件事:关系和线性表相同,操作只是线性表操作的一部分,而且限定在端点进行,所以是不同的ADT。集合关系也一样:拦截名单只要增、删、判断是否存在,是集合;通讯录要按姓名查号码,元素是"姓名→号码"的对子,是字典;社交软件判断两个人是否在同一个朋友圈、把两个圈子合并,是并查集。树形关系同样如此:文件夹管理关注遍历和增删结点,而按学号快速查找学生所用的二叉搜索树,关注的是按键查找。
有人可能会问:既然关系只有四种,为什么不在每种关系上把可能用到的操作全放进一个操作集,一种关系只定义一个ADT,岂不是更省事?
逻辑上这样定义并没有错,但有两个问题。
第一,从使用的角度,操作集越精简,含义越清楚。栈只允许在一端进出,不是因为做不到别的,而是这个约束本身在传递信息:看到"栈",使用者立刻知道它处理的是"后进先出"的问题,也不会在中间随意插入元素而破坏这个性质。把所有操作都开放出来,这层含义就没有了。
第二,从实现的角度,回到这门课要解决的问题——"让管理和操作数据的效率更高",关键词是效率。ADT最终要映射到计算机的存储上去实现,而几乎不存在一种存储方式能让所有操作都高效:让一部分操作快,往往要以另一部分操作慢为代价。操作集小而明确,才能针对它挑选最合适的存储方式。
那么,ADT是怎么映射到存储上的?效率又怎么量?这是接下来两节的事。
到这里你有了抽象数据类型的定义,以及"操作集决定ADT"这个判断。练一练(1)撤销功能(Ctrl+Z)需要的操作集是什么?它和线性表、栈、队列哪个最接近?(2)"待办清单"通常需要哪些操作?如果加一条"按截止时间取最紧急的一项",操作集变了,它还是同一个ADT吗?(3)给1.2练一练里你自己举的四个例子各列一个操作集。