列表

列表(list)是采用动态储存策略的典型结构,其中的元素称作节点(node),各节点通过指针或引用彼此联接,在逻辑上构成一个线性序列。如L = {a0, a1, a2, …, an-1}。相邻节点彼此互成前驱(predecessor)或后继(successor),前驱或后继若存在,则必然唯一,这也是线性结构的重要特征,没有前驱/后继的唯一节点称作(first/front)/(last/rear)节点。向量支持循秩访问(call-by-rank)的方式,根据数据元素的秩,可在O(1)时间内直接确定其物理地址,既然同属线性序列,列表固然也可通过秩来定位节点,即从头/尾端出发,沿后继/前驱引用,然而,此时的循秩访问成本过高,已不合时宜,因此,应改为循位置访问(call-by-position)的方式,亦即,转而利用节点之间的相互引用,找到特定的节点。

作为列表的基本元素,列表节点首先需要独立的“封装”实现,为此,我们来看一下列表节点ADT操作接口:

操作 功能
pred() 当前节点前驱节点的位置
succ() 当前节点后继节点的位置
data() 当前节点所存数据对象
insertAsPred(e) 插入前驱节点,存入被引用对象e,返回新节点位置
insertAsSucc(e) 插入后继节点,存入被引用对象e,返回新节点位置

接下来是列表ADT操作接口:

操作接口 功能 适用对象
size() 报告列表当前的规模(节点总数) 列表
first(), last() 返回首、末节点的位置 列表
insertAsFirst(e), insertAsLast(e) 将e当做首、末节点插入 列表
insertA(p, e), insertB(p, e) 将e当做节点p的直接后继、前驱插入 列表
remove(p) 删除位置p处的节点,返回其引用 列表
disordered() 判断所有节点是否已按非降序排列 列表
sort() 调整各节点的位置,使之按非降序排列 列表
find(e) 查找目标元素e,失败时返回NULL 列表
search(e) 查找e,返回不大于e且秩最大的节点 有序列表
deduplicate(), uniquify() 剔除重复节点 列表/有序列表
traverse() 遍历列表 列表

无序列表

其实我们可以模仿向量的循秩访问方式,比如,通过重载下标操作符:

只不过,这样做,时间复杂度为O(r),线性正比于待访问节点的秩,以均匀分布为例,单次访问的期望复杂度为:(1 + 2 + 3 + … + n)/n = (n + 1)/2 = O(n)。

定义无序列表的查找操作为:在节点p(可能是trailer)的n个(真)前驱中,找到等于e的最后者。代码如下:

 



发表评论

电子邮件地址不会被公开。 必填项已用*标注