0001 template <typename T> class List { //列表模板类
0002 protected:
0003    Rank _size;  LNP<T> head, tail; //规模、头哨兵、尾哨兵
0004    void init(); //列表创建时的初始化
0005    void copy(LNP<T>, Rank); //复制列表中自位置p起的n项
0006    void mergeSort(LNP<T>, LNP<T>); //归并排序
0007    void selectionSort(LNP<T>, LNP<T>); //选择排序
0008    void insertionSort(LNP<T>, LNP<T>); //插入排序
0009    void radixSort(LNP<T>, LNP<T>); //基数排序
0010 public:
0011    List() { init(); } //默认
0012    List(const List<T>& L, Rank r, Rank n) { copy(L[r], n); } //复制L中自第r项起的n项
0013    List(const List<T>& L) { copy(L.first(), L._size); } //整体复制列表L
0014    List(LNP<T> p, Rank n) { copy(p, n); } //复制列表中自位置p起的n项
0015    ~List(); //析构
0016 //静态操作
0017    Rank size() const { return _size; } //规模
0018    bool empty() const { return _size <= 0; } //判空
0019    LNP<T> operator[](Rank r) const; //重载，支持循秩访问（效率低）
0020    LNP<T> first() const { return head->succ; } //首节点位置
0021    LNP<T> last() const { return tail->pred; } //末节点位置
0022    LNP<T> find(const T& e) const { return find(head, e, tail); } //无序查找
0023    LNP<T> find(LNP<T>, const T&, LNP<T>) const; //无序区间查找
0024    LNP<T> search(const T& e) const { return search(head, e, tail); } //有序查找
0025    LNP<T> search(LNP<T>, const T&, LNP<T>) const; //有序区间查找
0026    LNP<T> getMax(LNP<T>, LNP<T>); //找出区间中的最大者
0027    LNP<T> getMax() { return getMax(head, tail); } //整体最大者
0028 //动态操作
0029    template <typename VST> void traverse(VST&); //遍历（函数对象）
0030    LNP<T> insertFirst(const T& e); //将e当作首节点插入
0031    LNP<T> insertLast(const T& e); //将e当作末节点插入
0032    LNP<T> insert(LNP<T> p, const T& e); //将e当作p的后继插入
0033    LNP<T> insert(const T& e, LNP<T> p); //将e当作p的前驱插入
0034    T remove(LNP<T>); //删除节点
0035    void sort(LNP<T>, LNP<T>); //区间排序
0036    void sort() { sort(head, tail); } //整体排序
0037    void merge(LNP<T>, LNP<T>, LNP<T>); //区间归并
0038    void merge(LNP<T> y) { merge(head, y, tail); } //整体归并
0039    void dedup(); //无序去重
0040    void uniquify(); //有序去重
0041 }; //List