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