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 void 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 0017 public: 0018 // 构造函数 0019 List() { init(); } //默认 0020 List ( List<T> const& L ); //整体复制列表L 0021 List ( List<T> const& L, Rank r, int n ); //复制列表L中自第r项起的n项 0022 List ( ListNodePosi(T) p, int n ); //复制列表中自位置p起的n项 0023 // 析构函数 0024 ~List(); //释放(包含头、尾哨兵在内的)所有节点 0025 // 只读访问接口 0026 Rank size() const { return _size; } //规模 0027 bool empty() const { return _size <= 0; } //判空 0028 T& operator[] ( Rank r ) const; //重载,支持循秩访问(效率低) 0029 ListNodePosi(T) first() const { return header->succ; } //首节点位置 0030 ListNodePosi(T) last() const { return trailer->pred; } //末节点位置 0031 bool valid ( ListNodePosi(T) p ) //判断位置p是否对外合法 0032 { return p && ( trailer != p ) && ( header != p ); } //将头、尾节点等同于NULL 0033 int disordered() const; //判断列表是否已排序 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) insertA ( ListNodePosi(T) p, T const& e ); //将e当作p的后继插入(After) 0046 ListNodePosi(T) insertB ( ListNodePosi(T) p, T const& e ); //将e当作p的前驱插入(Before) 0047 T remove ( ListNodePosi(T) p ); //删除合法位置p处的节点,返回被删除节点 0048 void merge ( List<T>& L ) { merge ( first(), size, L, L.first(), 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