ListNode.h
typedef int Rank;
#define ListNodePosi(T) 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); //在紧靠当前节点之后插入新节点
};
List.h
#include "ListNode.h" //引入列表节点类
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项
void 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个节点插入排序
public:
//构造函数
List(); //默认
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 ;//规模
bool empty()const ; //判空
ListNodePosi(T)& operator[](Rank r)const; //重载,支持循秩访问(效率低)
ListNodePosi(T) first(); //首节点位置
ListNodePosi(T) last(); //末节点位置
bool valid(ListNodePosi(T) p); //判断p对外位置是否合法
int disordered()const; //判断列表是否已经排序
ListNodePosi(T) find(T const&e )const;//无序列表查找
ListNodePosi(T) find(T const& e,int n,ListNodePosi(T)p)const; //无序区间查找
ListNodePosi(T) search(T const& e);
ListNodePosi(T) search(T const& e,int n,ListNodePosi(T) p)const; //有序区间查找
ListNodePosi(T) search2(T const& e,int n,ListNodePosi(T) p)const; //有序区间查找2(供插入算法使用)
ListNodePosi(T) selectMax(ListNodePosi(T) p,int n); //在p及其n-1个后继中选出最大者
ListNodePosi(T) selectMin(ListNodePosi(T) p,int n); //在p及其n-1个后继中选出最小者
ListNodePosi(T) selectMax(); //整体最大者
ListNodePosi(T) selectMin(); //整体最小者
bool lt(T a,T b); //比较大小
//可写访问接口
ListNodePosi(T) insertAsFirst(T const& e); //将e当作首节点插入
ListNodePosi(T) insertAsLast(T const& e); //将e当作末节点插入
ListNodePosi(T) insertA(ListNodePosi(T) p,T const& e); //将e当作p的后继插入
ListNodePosi(T) insertB(ListNodePosi(T) p,T const& e); //将e当作p的前端插入
T remove(ListNodePosi(T) p); //删除合法位置p处的节点,返回被删除节点
void merge(List<T>& L); //全列表归并
void sort(ListNodePosi(T) p,int n); //列表区间排序
void sort(); //列表整体排序
int deduplicate(); //无序去重
int uniquify(); //有序去重
void reverse(); //前后倒置（习题）
//遍历
void traverse(void(* )(T& )); //遍历，依次实施visit操作（函数指针，只读或局部性修改）
template <typename VST> //操作器
void traverse(VST& ); //遍历，依次实施visit操作（函数对象，可全局性修改）
void traverse();
};//List
List.hpp
#include "List.h"
template <typename T>
void List<T>::init() //列表创建时的初始化
{
header=new ListNode<T>; //创建头哨兵节点
trailer=new ListNode<T>; //创建尾哨兵节点
header->pred=NULL;header->succ=trailer;
trailer->pred=header;trailer->succ=NULL;
_size=0; //规模置空
}
template <typename T>
int List<T>::clear() //清除所有节点
{
int old_size=_size;
while (0<_size) //不停删除哨头节点，直至规模为0
{
remove(header->succ);
}
return old_size; //返回原先规模
}
template <typename T>
void List<T>::copyNodes(ListNodePosi(T) p,int n) //复制列表中自位置p起的n项
{
init(); //创造头尾哨兵节点并初始化
while (n--)
{
insertAsLast(p->data);p=p->succ;
}
}
template <typename T>
void List<T>::merge(ListNodePosi(T)& p, int n, List<T>& L, ListNodePosi(T) q,int m) //归并
{
ListNodePosi(T) pp=p->pred;
while (0<m)
{
if((0<n)&&(p->data<=q->data))
{
if(q==(p=p->succ))break;
n--;
}
else
{
insertB(p,L.remove((q=q->succ)->pred));
m--;
}
}
pp->succ=p;p->pred=pp;
}
template <typename T>
void List<T>::mergeSort(ListNodePosi(T)& p,int n) //对从p开始的连续的n个节点归并排序
{
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); //划分列表
merge(p,m,*this,q,n-m); //归并
}//注意:排序后，p依然指向归并后区间的新起点
template <typename T>
void List<T>::selectionSort(ListNodePosi(T) p,int n) //对从p开始的连续n个节点选择排序
{
//第一种:用尾插法将最大值放在末尾
/*ListNodePosi(T) q=p;
ListNodePosi(T) head=p->pred;
for(int i=0;i<n;i++)q=q->succ; //设置待排序区间为(head,q);
for(int i=1;i<n;i++)
{
ListNodePosi(T) Max=selectMax(head->succ,n-i);
insertB(q,Max->data);
q=q->pred;
remove(Max);
}*/
//第二种:用头插法将最大值移动到末尾
/*ListNodePosi(T) head=p->pred;
ListNodePosi(T) q;
for(int i=0;i<n;i++)
{
q=head->succ;
for(int j=0;j<i;j++)q=q->succ;
ListNodePosi(T) Max=selectMax(q,n-i);
insertA(head,Max->data);
remove(Max);
}*/
//第三种:头插法，插入一个元素移动一次header
ListNodePosi(T) header=p->pred;
ListNodePosi(T) q=header->succ;
for(int i=1;i<n;i++)
{
insertA(header,remove(selectMin(q,n-i)));
header=header->succ;
q=header->succ;
}
}
template <typename T>
void List<T>::insertionSort(ListNodePosi(T) p,int n) //对从p开始的连续n个节点插入排序
{
for(int i=0;i<n;i++)
{
insertA(search2(p->data,i,p),p->data);
p=p->succ;
remove(p->pred);
}
}
//构造函数
template <typename T>
List<T>::List()//默认
{
init();
}
template <typename T>
List<T>::List(List<T>const& L) //整体复制列表L
{
copyNodes(L.first(),l._size);
}
template <typename T>
List<T>::List(List<T>const& L,Rank r,int n) //复制列表L中自第r项起的n项
{
copyNodes(L[r],n);
}
template <typename T>
List<T>::List(ListNodePosi(T)p,int n) //复制列表中自位置p起的n项
{
copyNodes(p,n);
}
template <typename T>
//析构函数
List<T>::~List() //释放(包头，尾哨兵在内的)所有节点
{
clear();
delete header;delete trailer;
}
template <typename T>
//只读访问接口
Rank List<T>::size()const //规模
{
return _size;
}
template <typename T>
bool List<T>::empty()const //判空
{
return _size<=0;
}
template <typename T>
ListNodePosi(T)& List<T>::operator[](Rank r)const //重载,支持循秩访问(效率低)
{
ListNode(T) p=L.first();
for(int i=0;i<r;i++)p=p->succ;
return p;
}
template <typename T>
ListNodePosi(T) List<T>::first() //首节点位置
{
return header->succ;
}
template <typename T>
ListNodePosi(T) List<T>::last() //末节点位置
{
return trailer->pred;
}
template <typename T>
bool List<T>::valid(ListNodePosi(T) p) //判断p对外位置是否合法
{
return p&&(trailer!=p)&&(header!=p); //将头尾节点等同于NULL
}
template <typename T>
int List<T>::disordered()const //判断列表是否已经排序
{
if(_size<2) return ;//平凡序列自然有序
int n=0;ListNodePosi(T) p=header->succ;
while(p->succ!=trailer)
{
if((p->data)>(p->succ->data))n++;
p=p->succ;
}
return n; //当且仅当n==0时列表已排序
}
template <typename T>
ListNodePosi(T) List<T>::find(T const&e )const//无序列表查找
{
return find(e,_size,trailer);
}
template <typename T>
ListNodePosi(T) List<T>::find(T const& e,int n,ListNodePosi(T)p)const //无序区间查找
{
while(0<n--)
{
if(e==(p=p->pred)->data)return p; //从后往前找
}
return NULL; //查找失败
}
template <typename T>
ListNodePosi(T) List<T>::search(T const& e)
{
return search(e,_size,trailer);
}
template <typename T>
ListNodePosi(T) List<T>::search(T const& e,int n,ListNodePosi(T) p)const //有序区间查找
{
while (0<n--)
{
if((p=p->pred)->data<=e)break;
}
(p->data==e)?return p:return NULL;//返回header时为查找失败
}
template <typename T>
ListNodePosi(T) List<T>::search2(T const& e,int n,ListNodePosi(T) p)const//有序区间查找(为插入算法服务)
{
while (0<=n--) //p有可能为header,后再header后插入新的元素
{
if((p=p->pred)->data<=e)break;
}
return p;
}
/*template <typename T>
void List<T>::selectionSort(ListNodePosi(T) p,int n) //对从p开始的连续n个节点选择排序
{
//第一种
ListNodePosi(T) q=p;
for(int i=0;i<=n;i++)q=q->succ;
for(int i=1;i<n;i++)
{
ListNodePosi(T) Max=selectMax(p,n-i);
insertB(q,Max->data);q=q->pred;
remove(Max);
}
//第二种
ListNodePosi(T)q=p;
for(int i=1;i<n;i++)
{
ListNodePosi(T) Min=selectMin(p,n-i);
insertA(q,Min->data);q=q->succ;
remove(Min);
}
}*/
template <typename T>
ListNodePosi(T) List<T>::selectMax(ListNodePosi(T) p,int n) //在p及其n个后继中选出最大者
{
ListNodePosi(T) Max=p;
for(ListNodePosi(T) q=p->succ;0<n--;q=q->succ)
{
if(!lt(q->data,Max->data))Max=q;
}
return Max;
}
template <typename T>
ListNodePosi(T) List<T>::selectMin(ListNodePosi(T) p,int n) //在p及其n个后继中选出最小者
{
ListNodePosi(T) Min=p;
for(ListNodePosi(T) q=p->succ;0<n--;q=q->succ)
{
if(lt(q->data,Min->data))Min=q; //lt(a,b)表示a<b
}
return Min;
}
template <typename T>
ListNodePosi(T) List<T>::selectMin() //整体最小者
{
return selectMin(header->succ,_size-1);
}
template <typename T>
ListNodePosi(T) List<T>::selectMax() //整体最大者
{
return selectMax(header->succ,_size-1);
}
//可写访问接口
template <typename T>
ListNodePosi(T) List<T>::insertAsFirst(T const& e) //将e当作首节点插入
{
return insertA(header,e);
}
template <typename T>
ListNodePosi(T) List<T>::insertAsLast(T const& e) //将e当作末节点插入
{
return insertB(trailer,e);
}
template <typename T>
ListNodePosi(T) List<T>::insertA(ListNodePosi(T) p,T const& e) //将e当作p的后继插入
{
_size++;//更新规模
return p->insertAsSucc(e);
}
template <typename T>
ListNodePosi(T) List<T>::insertB(ListNodePosi(T) p,T const& e) //将e当作p的前端插入
{
_size++; //更新规模
return p->insertAsPred(e);
}
template <typename T>
ListNodePosi(T) ListNode<T>::insertAsPred(T const& e) //在紧靠当前节点之前插入新节点
{
ListNodePosi(T) p=new ListNode<T>(e,pred,this);
p->data=e;
this->pred->succ=p;this->pred=p;
return p;
}
template <typename T>
ListNodePosi(T) ListNode<T>::insertAsSucc(T const& e) //在紧靠当前节点之后插入新节点
{
ListNodePosi(T) p=new ListNode<T>(e,this,succ);
p->data=e;
this->succ->pred=p;this->succ=p;
return p;
}
template <typename T>
T List<T>::remove(ListNodePosi(T) p) //删除合法位置p处的节点,返回被删除节点
{
T e;
e=p->data; //备份数据
p->succ->pred=p->pred;
p->pred->succ=p->succ;
_size--; //更新规模
delete p;p=NULL;
return e; //返回被删除数据
}
template <typename T>
void List<T>::merge(List<T>& L) //全列表归并
{
merge(first(),_size,L,L.first(),L._size);
}
template <typename T>
void List<T>::sort(ListNodePosi(T) p,int n) //列表区间排序
{
/*switch(rand()%3) //随机选择排序法
{
case 1:insertionSort(p,n);break;
case 2:selectionSort(p,n);break;
default:mergeSort(p,n);break;
}*/
mergeSort(p,n);
}
template <typename T>
void List<T>::sort() //列表整体排序
{
sort(first(),_size);
}
template <typename T>
int List<T>::deduplicate() //无序去重(类似冒泡排序)
{
if(_size<0) return 0;//自然序列有序
int old_size=_size; //记录原规模
ListNodePosi(T) p=header;
Rank r=0;
while (trailer!=(p=p->succ))
{
ListNodePosi(T) q=find(p->data,r,p); //从p开始的r个前驱里查找相同元素
q?remove(q):r++;
}
return old_size-_size; //返回删除元素总数
}
template <typename T>
int List<T>::uniquify() //有序去重(类似冒泡排序,俩个俩个比较)
{
if(_size<2)return 0; //平凡序列自然有序
ListNodePosi(T) p=first();ListNodePosi(T) q;
int old_size=_size; //记录原规模
while (trailer!=(q=p->succ)) //不断比较p和q
{
if(p->data!=q->data)p=q;
else remove(q); //删除后者
}
return old_size-_size; //返回删除元素个数
}
template <typename T>
void List<T>::reverse() //前后倒置（习题）
{
ListNodePosi(T) p=head;
ListNodePosi(T) q=trailer;
for(int i=1;i<_size;i+=2)
{
swap((p=p->succ)->data,(q=q->pred)->data);
}
}
//遍历
template <typename T>
void List<T>::traverse(void(*visit)(T&)) //遍历，依次实施visit操作（函数指针，只读或局部性修改）
{
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) //遍历，依次实施visit操作（函数对象，可全局性修改）
{
for(ListNodePosi(T)p=header->succ;p!=trailer;p=p->succ)visit(p->data);
}
template <typename T>
void List<T>::traverse()
{
for(ListNodePosi(T)p=header->succ;p!=trailer;p=p->succ)cout<<p->data<<" ";
cout<<endl;
}
template <typename T>
bool List<T>::lt(T a,T b)
{
return (a<b)?true:false;
}
