【原创】链表模板类
/*********************************************名称：链表模板类
**作者：吴泔游
**用法：
LinkList<int> list; //创建
list.Create(10); //批量输入10个元素(cin)
list.GetLength(); //返回链表长度
list.ShowAll(); //打印所有元素(cout)
list.RemoveDuplicate(); //去掉重复的元素
list.Delete(2,(int)data); //删除第2个元素，值用data返回,函数返回值代表是否成功
list.Insert(3,(int)data); //插入data，成为第3个元素
list.InsertByOrder((int)data); //按升序插入data
list.Release(); //清空链表元素
list.Reverse(); //逆置链表
list.InsertSort(); //直接插入排序(升序),链表基本升序时较慢，反之较快
list.MergeSort(); //归并排序(升序)
list.GetNodeData(6,int(data)); //用data返回第6个节点，函数返回值代表是否成功
list.GetNodeDataPointer(5,int*(p_data)); //用p_pata返回第5个节点的地址，用于直接修改节点等操作
list.Search((int)key); //遍历查找元素，函数返回值为位置
list.SetSortMethod(SortInt); //指定排序函数
list_1+list_2 //返回两者元素集合，list_1元素在前
list_1=list_2 //赋值
list_1+=list_2 //list_1=list_1+list_2
**最后修改：2015/1/26
1.添加RemoveDuplicate函数
2.添加SetCompareMethod函数
********************************************/
#ifndef _LINK_LIST_H_
#define_LINK_LIST_H_
#include <iostream>
#include <iomanip>
using namespace std;
#define NULL 0
template <class ElemType>
class ListNode
{
public:
ElemType data;
ListNode *next;
ListNode(){next=NULL;}
ListNode(ElemType data)
{
this->data=data;
next=NULL;
}
};
//------------------------------------------------------------
template <class ElemType>
class LinkList
{
private:
ListNode<ElemType> *head;
int length;
bool (*SortMethod)(const ElemType& a,const ElemType& b);
bool (*CompareMethod)(const ElemType& a,const ElemType& b);
ListNode<ElemType>* Merge(ListNode<ElemType>*& a,ListNode<ElemType>*& b);
public:
LinkList();
LinkList(LinkList &b);
~LinkList();
int GetLength();
void ShowAll();
void Create(int n); //创建
void RemoveDuplicate();
bool Delete(int n,ElemType &data); //删除
bool Insert(int n,ElemType data); //插入
bool InsertByOrder(ElemType data);
void Release();
void Reverse(); //转置
void InsertSort(); //升序
void MergeSort();
bool GetNodeData(int n,ElemType &data);
bool GetNodeDataPointer(int n,ElemType*& p_data);
intSearch(ElemType key); //查找
void SetSortMethod(bool (*fun)(const ElemType& a,const ElemType& b)); //设置排序比较方法(<)
void SetCompareMethod(bool (*fun)(const ElemType& a,const ElemType& b)); //设置比较方法(==)
LinkList operator+(const LinkList &b);
LinkList operator=(const LinkList &b);
LinkList& operator+=(const LinkList &b);
};
//-----------------------------------------------------------------------------
template <class ElemType>
LinkList<ElemType>::LinkList():head(new ListNode<ElemType>),length(0),SortMethod(NULL),CompareMethod(NULL)
{
head->next=NULL;
}
template <class ElemType>
LinkList<ElemType>::LinkList(LinkList &b):head(new ListNode<ElemType>),length(b.length),SortMethod(b.SortMethod),CompareMethod(b.CompareMethod)
{
ListNode<ElemType> *p=this->head;
ListNode<ElemType> *q;
ListNode<ElemType> *pb=b.head->next;
while(pb)
{
q=new ListNode<ElemType>();
q->data=pb->data;
p->next=q;
p=q;
pb=pb->next;
}
p->next=NULL;
}
template <class ElemType>
int LinkList<ElemType>::GetLength()
{
return length;
}
template <class ElemType>
void LinkList<ElemType>::ShowAll()
{
cout<<"共"<<length<<"个元素:"<<endl;
ListNode<ElemType> *p=this->head->next;
int i=0;
while(p)
{
cout<<left<<setw(7)<<p->data<<" ";
p=p->next;
i++;
if(i%10==0)
cout<<endl;
}
cout<<endl;
}
//创建
template <class ElemType>
void LinkList<ElemType>::Create(int n)
{
this->length=n;
ListNode<ElemType> *p=this->head;
ListNode<ElemType> *q;
for(int i=0;i!=n;i++)
{
q=new ListNode<ElemType>();
cin>>q->data;
p->next=q;
p=q;
}
p->next=NULL;
}
//插入
template <class ElemType>
bool LinkList<ElemType>::Insert(int n,ElemType data)
{
ListNode<ElemType> *p=this->head;
ListNode<ElemType> *q;
int j=0;
while(p&&j<n-1)
{
p=p->next;
j++;
}
if(!p||j>n-1)return 0;
q=new ListNode<ElemType>(data);
q->next=p->next;
p->next=q;
this->length++;
return 1;
}
template <class ElemType>
bool LinkList<ElemType>::InsertByOrder(ElemType data)
{
ListNode<ElemType> *p=this->head;
ListNode<ElemType> *q;
while(p->next)
{
if(SortMethod==NULL)
{
if(data < p->next->data)
break;
}
else
if(SortMethod(data,p->next->data))
break;
p=p->next;
}
q=new ListNode<ElemType>(data);
q->next = p->next;
p->next = q;
this->length++;
return 1;
}
template <class ElemType>
void LinkList<ElemType>::RemoveDuplicate()
{
if(!this->head->next || !this->head->next->next)
return;
ListNode<ElemType> *p=this->head->next;
ListNode<ElemType> *q,*temp;
if(CompareMethod==NULL)
{
while(p)
{
q=p;
while(q->next)
{
if(p->data == q->next->data)
{
temp=q->next;
q->next=temp->next;
delete temp;
length--;
}
else
q=q->next;
}
p=p->next;
}
}
else
{
while(p)
{
q=p;
while(q->next)
{
if(CompareMethod(p->data , q->next->data))
{
temp=q->next;
q->next=temp->next;
delete temp;
length--;
}
else
q=q->next;
}
p=p->next;
}
}
}
template <class ElemType>
bool LinkList<ElemType>::Delete(int n,ElemType &data)
{
ListNode<ElemType> *p=this->head;
ListNode<ElemType> *q;
int j=0;
while(p->next&&j<n-1)
{
p=p->next;
j++;
}
if(!(p->next)||j>n-1)return 0;
q=p->next;
p->next=q->next;
data=q->data;
delete q;
this->length--;
return 1;
}
template <class ElemType>
void LinkList<ElemType>::Release()
{
length = 0;
ListNode<ElemType> *p=head->next;
while(p)
{
ListNode<ElemType> *q=p->next;
delete p;
p=q;
}
head->next = NULL;
}
//逆置
template <class ElemType>
void LinkList<ElemType>::Reverse()
{
ListNode<ElemType> *p=this->head->next;//p为待处理节点，q为下一个
this->head->next=NULL;
ListNode<ElemType> *q;
while(p)
{
q=p->next;//q保存下一个位置
p->next=this->head->next;
this->head->next=p;
p=q;
}
}
template <class ElemType>
void LinkList<ElemType>::InsertSort()
{
if(!head->next || !head->next->next)
return;
ListNode<ElemType> *p,*q=head->next->next;
ListNode<ElemType> *temp;
head->next->next=NULL;
while(q)
{
p=head;
while(p&&p->next)
{
if(SortMethod==NULL)
{
if(p->next->data < q->data)
break;
}
else
{
if(SortMethod(p->next->data,q->data))
break;
}
p=p->next;
}
temp=q->next;
q->next=p->next;
p->next=q;
q=temp;
}
this->Reverse();
}
template <class ElemType>
ListNode<ElemType>* LinkList<ElemType>::Merge(ListNode<ElemType>*& a,ListNode<ElemType>*& b)
{
if(a==NULL)
return b;
if(b==NULL)
return a;
ListNode<ElemType> *r=new ListNode<ElemType>();
ListNode<ElemType> *c;
ListNode<ElemType> *p;
ListNode<ElemType> *q;
c=r;
q=a->next;
p=b->next;
while(q&&p)
{
if(SortMethod==NULL)
{
if(p->data < q->data)
{
c->next=p;
p=p->next;
}
else
{
c->next=q;
q=q->next;
}
}
else
{
if(SortMethod(p->data,q->data))
{
c->next=p;
p=p->next;
}
else
{
c->next=q;
q=q->next;
}
}
c=c->next;
}
if(q==NULL)
c->next=p;
else if(p==NULL)
c->next=q;
delete a,b;
a=NULL;
b=NULL;
return r;
}
template <class ElemType>
void LinkList<ElemType>::MergeSort()
{
if(length <= 1)
return;
int l=(length+1)/2*2;
ListNode<ElemType>** r=new ListNode<ElemType>*;
ListNode<ElemType> *p=head->next;
for(int i=0;i!=l;i++)
r=new ListNode<ElemType>();
int i=0;
while(p)
{
r->next=p;
if(p->next ==NULL)
break;
p=p->next;
r->next->next=NULL;
i++;
}
for(int d=l;d!=1;d=(d+1)/2)
for(int i=0,j=0;j <=d-1;i++,j+=2)
r=Merge(r,r);
head=r;
}
template <class ElemType>
bool LinkList<ElemType>::GetNodeData(int n,ElemType &data)
{
if(n<=0)
return 0;
ListNode<ElemType> *p=this->head;
int j=0;
while(p&&j<n)
{
p=p->next;
j++;
}
if(!p||j>n)
return 0;
else
{
data=p->data;
return 1;
}
}
template <class ElemType>
bool LinkList<ElemType>::GetNodeDataPointer(int n,ElemType*& p_data)
{
if(n<=0)
return 0;
ListNode<ElemType> *p=this->head;
int j=0;
while(p&&j<n)
{
p=p->next;
j++;
}
if(!p||j>n)
return 0;
else
{
p_data=&p->data;
return 1;
}
}
template <class ElemType>
int LinkList<ElemType>::Search(ElemType key)
{
ListNode<ElemType> *p=this->head->next;
int i=1;
if(CompareMethod==NULL)
{
while(p)
{
if(p->data == key)
return i;
i++;
p=p->next;
}
}
else
{
while(p)
{
if(CompareMethod(p->data,key))
return i;
i++;
p=p->next;
}
}
return 0;
}
//设置排序比较方法(<)
template <class ElemType>
void LinkList<ElemType>::SetSortMethod(bool (*fun)(const ElemType& a,const ElemType& b))
{
SortMethod = fun;
}
//设置排序比较方法(==)
template <class ElemType>
void LinkList<ElemType>::SetCompareMethod(bool (*fun)(const ElemType& a,const ElemType& b))
{
CompareMethod = fun;
}
template <class ElemType>
LinkList<ElemType> LinkList<ElemType>::operator+(const LinkList<ElemType> &b)
{
LinkList<ElemType> c(*this);
ListNode<ElemType> *p=b.head->next;
ListNode<ElemType> *q;
ListNode<ElemType> *pc=c.head;
while(pc->next)
{
pc=pc->next;
}
while(p)
{
q=new ListNode<ElemType>();
q->data=p->data;
pc->next=q;
pc=q;
p=p->next;
}
pc->next=NULL;
c.length+=b.length;
return c;
}
template <class ElemType>
LinkList<ElemType> LinkList<ElemType>::operator=(const LinkList<ElemType> &b)
{
this->Release();
ListNode<ElemType> *p=this->head;
ListNode<ElemType> *q;
ListNode<ElemType> *pb=b.head->next;
while(pb)
{
q=new ListNode<ElemType>();
q->data=pb->data;
p->next=q;
p=q;
pb=pb->next;
}
p->next=NULL;
this->length=b.length;
this->SortMethod=b.SortMethod;
this->CompareMethod=b.CompareMethod;
return *this;
}
template <class ElemType>
LinkList<ElemType>& LinkList<ElemType>::operator+=(const LinkList<ElemType> &b)
{
*this=*this+b;
return *this;
}
template <class ElemType>
LinkList<ElemType>::~LinkList()
{
ListNode<ElemType> *p=head->next;
if(head)
{
delete head;
}
while(p)
{
ListNode<ElemType> *q=p->next;
delete p;
p=q;
}
}
#endif
例子和源码在附件内
页:
[1]