C++：list结构算法

List

1.元素在逻辑上具有线性次序物理地址不做限制。
2.哨兵节点header和trailer封装后外部不可见。
3.重载操作符[]实现下标和位置转换。
4.有序查找无序查找
5.前插入算法首先创建新节点
然后使new成为this节点的前驱和this节点前驱节点的后继。
6.后插入算法
7.基于复制的构造方法从源列表中取出n个相邻节点作为末节点插入新列表
8.删除p节点的前驱与p节点的后继相连然后释放p节点。
9.析构删除列表节点直到列表为空然后释放列表头尾哨兵节点。
10.去重算法有序、无序去重
11.排序算法插入、选择、归并

using Rank = int; //秩
template <typename T> struct ListNode;
template <typename T> using ListNodePosi = ListNode<T>*; //列表节点位置
template <typename T> struct ListNode { //列表节点模板类以双向链表形式实现
// 成员
   T data; ListNodePosi<T> pred; ListNodePosi<T> succ; //数值、前驱、后继
// 构造函数
   ListNode() {} //针对header和trailer的构造
   ListNode ( T e, ListNodePosi<T> p = NULL, ListNodePosi<T> s = NULL )
      : data ( e ), pred ( p ), succ ( s ) {} //默认构造器
// 操作接口
   ListNodePosi<T> insertAsPred ( T const& e ); //紧靠当前节点之前插入新节点
   ListNodePosi<T> insertAsSucc ( T const& e ); //紧随当前节点之后插入新节点
};


template <typename T> class List { //列表模板类

private:
   int _size; ListNodePosi<T> header; ListNodePosi<T> trailer; //规模、头哨兵、尾哨兵

protected:
   void init(); //列表创建时的初始化
   int clear(); //清除所有节点
   void copyNodes ( ListNodePosi<T>, int ); //复制列表中自位置p起的n项
   ListNodePosi<T> merge ( ListNodePosi<T>, int, List<T> &, ListNodePosi<T>, int ); //归并
   void mergeSort ( ListNodePosi<T> &, int ); //对从p开始连续的n个节点归并排序
   void selectionSort ( ListNodePosi<T>, int ); //对从p开始连续的n个节点选择排序
   void insertionSort ( ListNodePosi<T>, int ); //对从p开始连续的n个节点插入排序
   void radixSort(ListNodePosi<T>, int); //对从p开始连续的n个节点基数排序

public:
// 构造函数
   List() { init(); } //默认
   List ( List<T> const& L ); //整体复制列表L
   List ( List<T> const& L, Rank r, int n ); //复制列表L中自第r项起的n项
   List ( ListNodePosi<T> p, int n ); //复制列表中自位置p起的n项
// 析构函数
   ~List(); //释放包含头、尾哨兵在内的所有节点
// 只读访问接口
   Rank size() const { return _size; } //规模
   bool empty() const { return _size <= 0; } //判空
   T& operator[] ( Rank r ) const; //重载支持循秩访问效率低
   ListNodePosi<T> first() const { return header->succ; } //首节点位置
   ListNodePosi<T> last() const { return trailer->pred; } //末节点位置
   bool valid ( ListNodePosi<T> p ) //判断位置p是否对外合法
   { return p && ( trailer != p ) && ( header != p ); } //将头、尾节点等同于NULL
   ListNodePosi<T> find ( T const& e ) const //无序列表查找
   { return find ( e, _size, trailer ); }
   ListNodePosi<T> find ( T const& e, int n, ListNodePosi<T> p ) const; //无序区间查找
   ListNodePosi<T> search ( T const& e ) const //有序列表查找
   { return search ( e, _size, trailer ); }
   ListNodePosi<T> search ( T const& e, int n, ListNodePosi<T> p ) const; //有序区间查找
   ListNodePosi<T> selectMax ( ListNodePosi<T> p, int n ); //在p及其n-1个后继中选出最大者
   ListNodePosi<T> selectMax() { return selectMax ( header->succ, _size ); } //整体最大者
// 可写访问接口
   ListNodePosi<T> insertAsFirst ( T const& e ); //将e当作首节点插入
   ListNodePosi<T> insertAsLast ( T const& e ); //将e当作末节点插入
   ListNodePosi<T> insert ( ListNodePosi<T> p, T const& e ); //将e当作p的后继插入
   ListNodePosi<T> insert ( T const& e, ListNodePosi<T> p ); //将e当作p的前驱插入
   T remove ( ListNodePosi<T> p ); //删除合法位置p处的节点,返回被删除节点
   void merge ( List<T> & L ) { merge ( header->succ, _size, L, L.header->succ, L._size ); } //全列表归并
   void sort ( ListNodePosi<T> p, int n ); //列表区间排序
   void sort() { sort ( first(), _size ); } //列表整体排序
   int deduplicate(); //无序去重
   int uniquify(); //有序去重
   void reverse(); //前后倒置习题
// 遍历
   void traverse ( void (* ) ( T& ) ); //遍历依次实施visit操作函数指针只读或局部性修改
   template <typename VST> //操作器
   void traverse ( VST& ); //遍历依次实施visit操作函数对象可全局性修改
}; //List


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; //记录规模
}

template <typename T> //重载下标操作符以通过秩直接访问列表节点虽方便效率低需慎用
T& List<T>::operator[] ( Rank r ) const { //assert: 0 <= r < size
   ListNodePosi<T> p = first(); //从首节点出发
   while ( 0 < r-- ) p = p->succ; //顺数第r个节点即是
   return p->data; //目标节点返回其中所存元素
}

template <typename T> //在无序列表内节点p可能是trailer的n个真前驱中找到等于e的最后者
ListNodePosi<T> List<T>::find ( T const& e, int n, ListNodePosi<T> p ) const {
   while ( 0 < n-- ) //0 <= n <= rank(p) < _size对于p的最近的n个前驱从右向左
      if ( e == ( p = p->pred )->data ) return p; //逐个比对直至命中或范围越界
   return NULL; //p越出左边界意味着区间内不含e查找失败
} //失败时返回NULL

template <typename T> //在有序列表内节点p可能是trailer的n个真前驱中找到不大于e的最后者
ListNodePosi<T> List<T>::search ( T const& e, int n, ListNodePosi<T> p ) const {
// assert: 0 <= n <= rank(p) < _size
   do {
      p = p->pred; n--;  //从右向左
   } while ( ( -1 < n ) && ( e < p->data ) ); //逐个比较直至命中或越界
   return p; //返回查找终止的位置
} //失败时返回区间左边界的前驱可能是header——调用者可通过valid()判断成功与否

template <typename T> ListNodePosi<T> List<T>::insertAsFirst ( T const& e )
{  _size++; return header->insertAsSucc ( e );  } //e当作首节点插入

template <typename T> ListNodePosi<T> List<T>::insertAsLast ( T const& e )
{  _size++; return trailer->insertAsPred ( e );  } //e当作末节点插入

template <typename T> ListNodePosi<T> List<T>::insert ( ListNodePosi<T> p, T const& e )
{  _size++; return p->insertAsSucc ( e );  } //e当作p的后继插入

template <typename T> ListNodePosi<T> List<T>::insert ( T const& e, ListNodePosi<T> p )
{  _size++; return p->insertAsPred ( e );  } //e当作p的前驱插入

template <typename T> //将e紧随当前节点之后插入于当前节点所属列表设有哨兵尾节点trailer
ListNodePosi<T> ListNode<T>::insertAsSucc ( T const& e ) {
   ListNodePosi<T> x = new ListNode ( e, this, succ ); //创建新节点
   succ->pred = x; succ = x; //设置逆向链接
   return x; //返回新节点的位置
}
template <typename T> //将e紧靠当前节点之前插入于当前节点所属列表设有哨兵头节点header
ListNodePosi<T> ListNode<T>::insertAsPred ( T const& e ) {
   ListNodePosi<T> x = new ListNode ( e, pred, this ); //创建新节点
   pred->succ = x; pred = x; //设置正向链接
   return x; //返回新节点的位置
}

template <typename T> //列表内部方法复制列表中自位置p起的n项
void List<T>::copyNodes ( ListNodePosi<T> p, int n ) { //p合法且至少有n-1个真后继节点
   init(); //创建头、尾哨兵节点并做初始化
   while ( n-- ) { insertAsLast ( p->data ); p = p->succ; } //将起自p的n项依次作为末节点插入
}
template <typename T> //复制列表中自位置p起的n项assert: p为合法位置且至少有n-1个后继节点
List<T>::List ( ListNodePosi<T> p, int n ) { copyNodes ( p, n ); }

template <typename T> //整体复制列表L
List<T>::List ( List<T> const& L ) { copyNodes ( L.first(), L._size ); }

template <typename T> //复制L中自第r项起的n项assert: r+n <= L._size
List<T>::List ( List<T> const& L, Rank r, int n ) {
   ListNodePosi<T> p = L.first();
   while ( 0 < r-- ) p = p->succ;
   copyNodes ( p, n );
}

template <typename T> T List<T>::remove ( ListNodePosi<T> p ) { //删除合法节点p返回其数值
   T e = p->data; //备份待删除节点的数值假定T类型可直接赋值
   p->pred->succ = p->succ; p->succ->pred = p->pred; //后继、前驱
   delete p; _size--; //释放节点更新规模
   return e; //返回备份的数值
}

template <typename T> List<T>::~List() //列表析构器
{ clear(); delete header; delete trailer; } //清空列表释放头、尾哨兵节点
template <typename T> int List<T>::clear() { //清空列表
   int oldSize = _size;
   while ( 0 < _size ) remove ( header->succ ); //反复删除首节点直至列表变空
   return oldSize;
}

template <typename T> int List<T>::deduplicate() {
   int oldSize = _size; ListNodePosi<T> p = first();
   for ( Rank r = 0; p != trailer; p = p->succ ) //O(n)
      if ( ListNodePosi<T> q = find(p->data, r, p) )
         remove(q); //此时q与p雷同但删除前者更为简明
      else r++; //r为无重前缀的长度
   return oldSize - _size; //删除元素总数
}
template <typename T> int List<T>::uniquify() { //成批剔除重复元素效率更高
   if ( _size < 2 ) return 0; //平凡列表自然无重复
   int oldSize = _size; //记录原规模
   ListNodePosi<T> p = first(); ListNodePosi<T> q; //p为各区段起点q为其后继
   while ( trailer != ( q = p->succ ) ) //反复考查紧邻的节点对(p, q)
      if ( p->data != q->data ) p = q; //若互异则转向下一区段
      else remove ( q ); //否则雷同删除后者
   return oldSize - _size; //列表规模变化量即被删除元素总数
}

template <typename T> void List<T>::traverse ( void ( *visit ) ( T& ) ) //借助函数指针机制遍历
{  for ( ListNodePosi<T> p = header->succ; p != trailer; p = p->succ ) visit ( p->data );  }

template <typename T> template <typename VST> //元素类型、操作器
void List<T>::traverse ( VST& visit ) //借助函数对象机制遍历
{  for ( ListNodePosi<T> p = header->succ; p != trailer; p = p->succ ) visit ( p->data );  }

template <typename T> void List<T>::sort ( ListNodePosi<T> p, int n ) { //列表区间排序
   
   switch ( rand() % 4 ) { //随机选取排序算法。可根据具体问题的特点灵活选取或扩充
      case 1:  insertionSort ( p, n ); break; //插入排序
      case 2:  selectionSort ( p, n ); break; //选择排序
      case 3:  mergeSort ( p, n ); break; //归并排序
      default: radixSort ( p, n ); break; //基数排序
   }
}
template <typename T> //对列表中起始于位置p、宽度为n的区间做插入排序
void List<T>::insertionSort ( ListNodePosi<T> p, int n ) { //valid(p) && rank(p) + n <= size
   for ( int r = 0; r < n; r++ ) { //逐一为各节点
      insert ( search ( p->data, r, p ), p->data ); //查找适当的位置并插入
      p = p->succ; remove ( p->pred ); //转向下一节点
   }
}
template <typename T> //对列表中起始于位置p、宽度为n的区间做选择排序
void List<T>::selectionSort ( ListNodePosi<T> p, int n ) { //valid(p) && rank(p) + n <= size
   ListNodePosi<T> head = p->pred, tail = p;
   for ( int i = 0; i < n; i++ ) tail = tail->succ; //待排序区间为(head, tail)
   while ( 1 < n ) { //在至少还剩两个节点之前在待排序区间内
      ListNodePosi<T> max = selectMax ( head->succ, n ); //找出最大者歧义时后者优先
      insert ( remove ( max ), tail ); //将其移至无序区间末尾作为有序区间新的首元素
      tail = tail->pred; n--;
   }
}
template <typename T> //列表的归并排序算法对起始于位置p的n个元素排序
void List<T>::mergeSort ( ListNodePosi<T> & p, int n ) { //valid(p) && rank(p) + n <= size
   if ( n < 2 ) return; //若待排序范围已足够小则直接返回否则...
   int m = n >> 1; //以中点为界
   ListNodePosi<T> q = p; for (int i = 0; i < m; i++) q = q->succ; //找到后子列表起点
   mergeSort(p, m); mergeSort(q, n - m); //前、后子列表各分别排序
   p = merge ( p, m, *this, q, n - m ); //归并
} //注意排序后p依然指向归并后区间的新起点

typedef unsigned int U; //约定类型T或就是U或可转换为U并依此定序

template <typename T> //对列表中起始于位置p、宽度为n的区间做基数排序
void List<T>::radixSort ( ListNodePosi<T> p, int n ) { //valid(p) && rank(p) + n <= size
   ListNodePosi<T> head = p->pred; ListNodePosi<T> tail = p;
   for ( int i = 0; i < n; i++ ) tail = tail->succ; //待排序区间为(head, tail)
   for ( U radixBit = 0x1; radixBit && (p = head); radixBit <<= 1 ) //以下反复地
      for ( int i = 0; i < n; i++ ) //根据当前基数位将所有节点
         radixBit & U (p->succ->data) ? //分拣为后缀1与前缀0
            insert( remove( p->succ ), tail ) : p = p->succ;
}