3.3 有序列表

唯一化

template <typename T> int List<T>::uniquify() { // 成批剔除重复元素
    if (_size < 2)
        return 0; // 平凡列表自然无重复
    int oldSize = _size; // 记录原规模
    ListNodePosi(T) p = first(); // p为区段起点
    ListNodePosi(T) q; // q为后继
    while (trailer != (q = p -> succ)) { // 反复考查相邻节点对(p, q)
        if (p -> data != q -> data)
            p = q; // 若互异，则转向下一区段
        else
            remove(q); // 若相同，删除后者
    }
    return oldSize - _size; // 列表规模变化量，即被删除元素总数
}

查找

template <typename T> // 在有序列表内节点p的n个（真）前驱中，找到不大于e的最后者
Posi(T) List<T>::search(T const & e, int n, Posi(T) p) const {
    while (0 <= n--) // 对于p的最近的n个前驱，从右向左
        if(((p = p -> pred) -> data) <= e)
            break; // 逐个比较
    return p; // 直至命中或数值越界或范围越界后，返回查找终止位置
}