3.1 列表

根据是否修改数据结构，所有操作分两类：
(1) 静态，仅读取，数据结构的内容及组成一般不变：get、search
(2) 动态，需写入，数据结构的局部或整体发生改变：insert、remove
数据元素的存储与组织方式分两种：
(1) 静态，数据空间整体创建或销毁，数据元素的物理存储次序与其逻辑次序严格一致，可支持高效的静态操作
(2) 动态，为各数据元素动态分配与回收物理空间，逻辑上相邻的元素记录彼此的物理地址，在逻辑上形成一个整体，可支持高效的动态操作

列表(list)是采用动态存储策略的典型结构，其中的元素称作节点(node)，各节点通过指针或引用彼此联接，在逻辑上构成一个线性序列
L = {a₀, a₁, ... , a_n-1}
相邻节点彼此称为前驱(predecessor)或后继(successor)，若前驱或后继存在，则必然唯一，无前驱的唯一节点称作首(first/front)节点，无后继的唯一节点称作末(last/rear)节点
循位置访问(call-by-position)，利用节点之间的相互引用，找到特定的节点

作为列表的基本元素，列表节点需要封装实现，可设置并约定若干基本操作接口
列表节点ADT接口
pred() 当前节点前驱节点位置
succ() 当前节点后继节点位置
data() 当前节点所存数据对象
insertAsPred(e) 插入前驱节点，存入被引用对象e，返回新节点位置
insertAsSucc(e) 插入后继节点，存入被引用对象e，返回新节点位置
列表节点ListNode模板类

#define Posi(T) ListNode<T>* // 列表节点位置
template <typename T> struct ListNode { // 列表节点模板类（以双向链表形式实现）
    T data; // 数值
    Posi(T) pred; // 前驱
    Posi(T) succ; // 后继
    ListNode() {} // 针对header与trailer的构造
    ListNode(T e, Posi(T) p = NULL, Posi(T) s = NULL): data(e), pred(p), succ(s) {} // 默认构造器
    Posi(T) insertAsPred(T const& e); // 前插入
    Posi(T) insertAsSucc(T const& e); // 后插入
}

列表ADT接口
size() 报告列表当前规模（节点数）
first() last() 返回首末节点位置
insertAsFirst(e) insertAsLast(e) 将e当作首/末节点插入
insertBefore(p, e) insertAfter(p, e) 将e当作节点p前驱/后继插入
remove(p) 删除位置p的节点，返回其引用
disordered() 判断所有节点是否已按非降序排列
sort() 按非降序排列各节点
find(e) 查找目标元素e，失败时返回NULL
search(e) 在有序列表中查找目标元素e，返回不大于e且秩最大的元素
deduplicate() 删除重复节点
uniquify() 删除有序列表重复节点
traverse() 遍历列表
列表List模板类

#include "listNode.h" // 引入列表节点类
template <typename T> class List { // 列表模板类
    private:
        int _size; // 规模
        Posi(T) header; // 头哨兵
        Post(T) trailer; // 尾哨兵
    protected:
        /* ... 内部函数 */
    public:
        /* ... 构造函数 */
        /* ... 析构函数 */
        /* ... 只读接口 */
        /* ... 可写接口 */
        /* ... 遍历接口 */
}

构造

template <typename T> void List<T>::init() { // 初始化，创建列表对象时统一调用
    header = new ListNode<T>; // 创建头哨兵节点
    trailer = new ListNode<T>; // 创建尾哨兵节点
    header -> succ = trailer;
    header -> pred = NULL;
    trailer -> pred = header;
    trailer -> succ = NULL; // 互联
    _size = 0; // 记录规模
}