0001 #include "listNode.h" //引入列表节点类
0002 
0003 template <typename T> class List { //列表模板类
0004 
0005 private:
0006    Rank _size; ListNodePosi<T> head, tail; //规模、头哨兵、尾哨兵
0007 
0008 protected:
0009    void init(); //列表创建时的初始化
0010    Rank clear(); //清除所有节点
0011    void copyNodes( ListNodePosi<T>, Rank ); //复制列表中自位置p起的n项
0012    ListNodePosi<T> merge( ListNodePosi<T>, Rank, List<T>&, ListNodePosi<T>, Rank ); //归并
0013    void mergeSort( ListNodePosi<T>&, Rank ); //对从p开始连续的n个节点归并排序
0014    void selectionSort( ListNodePosi<T>, Rank ); //对从p开始连续的n个节点选择排序
0015    void insertionSort( ListNodePosi<T>, Rank ); //对从p开始连续的n个节点插入排序
0016    void radixSort( ListNodePosi<T>, Rank ); //对从p开始连续的n个节点基数排序
0017 
0018 public:
0019 // 构造方法
0020    List() { init(); } //默认
0021    List( List<T> const& L ); //整体复制列表L
0022    List( List<T> const& L, Rank r, Rank n ); //复制列表L中自第r项起的n项
0023    List( ListNodePosi<T> p, Rank n ); //复制列表中自位置p起的n项
0024    // 析构方法
0025    ~List(); //释放（包含头、尾哨兵在内的）所有节点
0026 // 只读访问接口
0027    Rank size() const { return _size; } //规模
0028    bool empty() const { return _size <= 0; } //判空
0029    ListNodePosi<T> operator[]( Rank r ) const; //重载，支持循秩访问（效率低）
0030    ListNodePosi<T> first() const { return head->succ; } //首节点位置
0031    ListNodePosi<T> last() const { return tail->pred; } //末节点位置
0032    bool valid( ListNodePosi<T> p ) //判断位置p是否对外合法
0033    { return p && ( tail != p ) && ( head != p ); } //将头、尾节点等同于NULL
0034    ListNodePosi<T> find( T const& e ) const //无序列表查找
0035    { return find( e, _size, tail ); }
0036    ListNodePosi<T> find( T const& e, Rank n, ListNodePosi<T> p ) const; //无序区间查找
0037    ListNodePosi<T> search( T const& e ) const //有序列表查找
0038    { return search( e, _size, tail ); }
0039    ListNodePosi<T> search( T const& e, Rank n, ListNodePosi<T> p ) const; //有序区间查找
0040    ListNodePosi<T> selectMax( ListNodePosi<T> p, Rank n ); //在p及其n-1个后继中选出最大者
0041    ListNodePosi<T> selectMax() { return selectMax( head->succ, _size ); } //整体最大者
0042 // 可写访问接口
0043    ListNodePosi<T> insertFirst( T const& e ); //将e当作首节点插入
0044    ListNodePosi<T> insertLast( T const& e ); //将e当作末节点插入
0045    ListNodePosi<T> insert( ListNodePosi<T> p, T const& e ); //将e当作p的后继插入
0046    ListNodePosi<T> insert( T const& e, ListNodePosi<T> p ); //将e当作p的前驱插入
0047    T remove( ListNodePosi<T> p ); //删除合法位置p处的节点,返回被删除节点
0048    void merge( List<T>& L ) { merge( head->succ, _size, L, L.head->succ, L._size ); } //全列表归并
0049    void sort( ListNodePosi<T>, Rank ); //列表区间排序
0050    void sort() { sort( first(), _size ); } //列表整体排序
0051    Rank dedup(); //无序去重
0052    Rank uniquify(); //有序去重
0053    void reverse(); //前后倒置（习题）
0054 // 遍历
0055    void traverse( void ( * )( T& ) ); //依次实施visit操作（函数指针）
0056    template <typename VST> void traverse( VST& ); //依次实施visit操作（函数对象）
0057 }; //List