C 模版编程——单链表的实现

C++模版编程——单链表的实现

分类： C++基础 2012-06-04 17:42 257人阅读 评论(0) 收藏 举报

代码的注释还是很清晰的，就不说废话了。

直接上代码:

#pragma once
#include <assert.h>
#include <iostream>
using std::cout;
using std::endl;
//单链表模板类
template<class T>
class CList
{
public:
    //类方法接口
    enum{begin=0,end=-1};
    typedef struct _LIST
    {
        _LIST* pNext;//指向下一个元素
        T data;//数据域
    }LIST,*PLIST;
    explicit CList(const T s[],const int n);
    explicit CList();
    CList<T>& operator=(const CList<T>& l);//默认赋值操作符
    bool operator==(const CList<T>& l);//重载等于操作符
    friend bool operator==(const LIST& l1,const LIST& l2)
    {
        if((l1.data==l2.data))
            return true;
        return false;
    }
    virtual~ CList();
    //打印链表元素
    void Show()const;
    //获取元素数目
    void GetLength()const;
    //获取第index 个元素
    T GetAt(const int& index)const;
    T operator[](int index)const;
    //在第index个元素前插入元素t,插入末尾时约定index=-1
    void Insert(const T& t,const int& index=end);//默认情况下，在链表末尾插入
    void Insert(const T s[],const int count,const int& index=end);//在第index个元素前插入count个元素
    //删除索引为index 的元素
    void Delete(const int& index);
    //删除从index开始的n个元素,当n大于index开始的元素数目之和时，删除后面所有的
    void Delete(const int& index,const int& n);
    //删除索引为index1和index2之间的所有元素
    void DeleteBetween(const int& index1,const int& index2);//index1和index2之间大小不用限定
    //删除链表中所有元素
    void DeleteAll();
    //获取链表所有元素，存在数组中
    void GetData(T s[])const;
    //获取链表中最大元素
    T GetMaxData()const;
    //获取链表中最小元素
    T GetMinData()const;
    //对链表进行排序
    void SortList();
    //链表逆置
    void InverseList();
    //链表是否为空
    bool IsEmpty()const;
    //替换索引为index处的元素值
    void Replace(const T& t,const int& index);
    //用数组s[]中的count个元素替换index开始的count个节点的值
    void Replace(const T s[],const int& index,const int& count);
    //从pos开始查找,默认从第一个位置,按先后顺序查找元素值，返回索引值，没有找到返回-1,找到即停止
    int Find(const T& t,const int pos=begin);
    //从末尾开始查找，没找到返回-1
    int FindLastOf(const T& t,const int pos=end);
    //获取两个变量中大的一个
    inline int GetMax(const int& a,const int& b)const;
    //获取两个变量中小的那个
    inline int GetMin(const int& a,const int& b)const;
protected:
    void Release();//释放所有内存空间
    //释放index开始的所有内存空间
    void Release(const int& index);
    //释放index1到index2之间元素的内存空间
    void Release(const int& index1,const int& index2);
    //创建一个链表链接S[]内所有元素，返回首地址
    LIST* CreateList(const T s[],const int& count)const
    {
        assert(count>0);
        PLIST p1=new LIST;//第一个节点
        p1->data=s[0];
        PLIST temp=p1;
        for(int i=1;i<count-1;++i)
        {
            PLIST p=new LIST;
            p->data=s[i];
            temp->pNext=p;
            temp=p;
        }
        PLIST tail=new LIST;
        tail->data=s[count-1];
        temp->pNext=tail;
        tail->pNext=NULL;
        return p1;
    }
    //返回第index(从0开始索引)个元素的地址,默认值-1,返回头指针地址
    LIST* GetAddr(const int& index=-1)
    {
        assert(index>=-1&&index<m_iLength);
        if(index==-1)
            return pHeader;
        PLIST p=pHeader->pNext;
        for(int i=0;i<index;++i)
            p=p->pNext;
        return p;
    }
    //交换元素值
    inline void Swap(LIST* p1,LIST* p2)const;
    //快速排序算法
    int Partition(int low,int high);
    void QSort(int low,int high);
    void QuickSort();
private:
    //类属性
    PLIST pHeader;//指向数据域缓冲区首地址,data存放链表长度
    int m_iLength;//元素数目
};
//实现类方法
template<class T>
CList<T>::CList():pHeader(NULL),m_iLength(0)
{
    pHeader=new LIST;
    pHeader->pNext=NULL;
    pHeader->data=(T)0;
}
template<class T>
CList<T>::CList(const T s[], const int n):pHeader(NULL),m_iLength(n)
{
    assert(n>=0);
    pHeader=new LIST;
    pHeader->data=(T)0;
    pHeader->pNext=CreateList(s,n);
}
template<class T>
void CList<T>::Release()
{
    PLIST p=pHeader;
    while(p)
    {
        PLIST temp=p->pNext;
        delete p;
        p=temp;
    }
    pHeader=NULL;
    m_iLength=0;
}
template<class T>
CList<T>::~CList()
{
    Release();
}
template<class T>
void CList<T>::Show()const
{
    PLIST p=pHeader->pNext;
    for(int i=0;i<m_iLength-1;++i)
    {
        cout<<p->data<<"--->";
        p=p->pNext;
    }
    cout<<p->data<<endl;
    cout<<endl;
}
template<class T>
void CList<T>::GetLength() const
{
    return m_iLength;
}
template<class T>
T CList<T>::GetAt(const int& index) const
{
    assert(index>=0&&index<m_iLength);
    PLIST p=pHeader->pNext;
    for(int i=0;i<index;++i)
        p=p->pNext;
    return p->data;
}
template<class T>
T CList<T>::operator [](int index) const
{
    return GetAt(index);
}
template<class T>
CList<T>& CList<T>::operator =(const CList<T> &l)
{
    if(*this==l)
        return *this;
    Release();
    pHeader=new LIST;
    pHeader->data=(T)0;
    m_iLength=l.m_iLength;
    PLIST lp=pHeader;
    for(int i=0;i<m_iLength-1;++i)
    {
        PLIST p=new LIST;
        p->data=l[i];
        lp->pNext=p;
        lp=p;
    }
    PLIST tail=new LIST;
    tail->data=l[m_iLength-1];
    tail->pNext=NULL;
    lp->pNext=tail;
    return *this;
}
template<class T>
bool CList<T>::operator ==(const CList<T> &l)
{
    if(pHeader==l.pHeader)
        return true;
    return false;
}
template<class T>
void CList<T>::Insert(const T &t, const int& index = -1)
{
    assert(index>=-1&&index<m_iLength);//确保插入位置有效
    LIST* p=new LIST;
    p->data=t;
    if(index==-1)// 末尾插入
    {
        GetAddr(m_iLength-1)->pNext=p;
        p->pNext=NULL;
    }
    else
    {
        PLIST pl=NULL;
        if(index==0)
            pl=GetAddr();
        else
            pl=GetAddr(index-1);
        p->pNext=pl->pNext;
        pl->pNext=p;
    }
    m_iLength++;
}
template<class T>
void CList<T>::Insert(const T s[], const int count, const int& index = -1)
{
    assert(count>1);
    assert(index>=-1&&index<m_iLength);
    PLIST p=CreateList(s,count);
    if(index==-1)//末尾插入
        GetAddr(m_iLength-1)->pNext=p;
    else
    {
        PLIST p1=NULL;
        if(index==0)//头结点后插入
            p1=GetAddr();
        else
            p1=GetAddr(index-1);
        PLIST tail=p->pNext;
        while(true)//循环获取插入短链的尾指针
        {
            if(tail->pNext==NULL)
                break;
            tail=tail->pNext;
        }
        tail->pNext=p1->pNext;
        p1->pNext=p;
    }
    m_iLength+=count;
}
template<class T>
void CList<T>::Delete(const int& index)
{
    assert(index>=0&&index<m_iLength);
    PLIST p=NULL;
    if(index==0)//删除第一个节点
    {
        p=pHeader->pNext;
        pHeader->pNext=p->pNext;
        delete p;
        p=NULL;
    }
    else if(index==m_iLength-1)//删除最后一个节点
    {
        p=GetAddr(m_iLength-2);
        PLIST temp=p->pNext;
        p->pNext=NULL;
        delete temp;
        temp=NULL;
    }
    else//其他情况
    {
        p=GetAddr(index-1);
        PLIST temp=p->pNext;
        p->pNext=temp->pNext;
        delete temp;
        temp=NULL;
    }
    m_iLength--;
}
template<class T>
void CList<T>::GetData(T s[]) const
{
    PLIST p=pHeader->pNext;
    int i=0;
    while(p)
    {
        s[i]=p->data;
        p=p->pNext;
        ++i;
    }
}
template<class T>
void CList<T>::DeleteAll()
{
    Release();
    pHeader=new LIST;
    pHeader->data=(T)0;
    pHeader->pNext=NULL;
}
template<class T>
void CList<T>::Delete(const int &index, const int &n)
{
    assert(index>=0&&index<m_iLength);
    assert(n>0);
    if(m_iLength-index<n)//删除index开始的所有元素
        Release(index);
    else//删除index开始的n个元素
        Release(index,n+index-1);
}
template<class T>
void CList<T>::DeleteBetween(const int& index1, const int& index2)
{
    assert(index1>=0&&index1<m_iLength);
    assert(index2>=0&&index2<m_iLength);
    Release(index1,index2);
}
template<class T>
void CList<T>::Release(const int &index)
{
    PLIST p=GetAddr(index-1);
    PLIST temp=p->pNext;//保存下一个节点
    p->pNext=NULL;
    while(temp)
    {
        PLIST lp=temp->pNext;
        delete temp;
        temp=lp;
    }
    m_iLength=index;
}
template<class T>
void CList<T>::Release(const int &index1, const int &index2)
{
    if(index1==index2)//不释放
        return;
    int max=GetMax(index1,index2);
    int min=GetMin(index1,index2);
    if(max==m_iLength-1)
    {
        Release(min);
        return;
    }
    PLIST p1=GetAddr(min-1);
    PLIST p2=p1->pNext;//保存需要删除内存首地址
    PLIST p3=GetAddr(max+1);
    p1->pNext=p3;//连接
    while(p2!=p3)
    {
        PLIST temp=p2->pNext;//保存下一个节点的地址
        delete p2;
        p2=temp;
    }
    m_iLength-=(max-min+1);
}
template <class T>
T CList<T>::GetMaxData() const
{
    assert(m_iLength>0);
    T max=GetAt(0);
    for(int i=1;i<m_iLength;++i)
    {
        T temp=GetAt(i);
        if(temp>max)
            max=temp;
    }
    return max;
}
template <class T>
T CList<T>::GetMinData() const
{
    assert(m_iLength>0);
    T min=GetAt(0);
    for(int i=1;i<m_iLength;++i)
    {
        T temp=GetAt(i);
        if(temp<min)
            min=temp;
    }
    return min;
}
template<class T>
void CList<T>::SortList()
{
    if(m_iLength<2)
        return;
    QuickSort();
}
template<class T>
inline void CList<T>::Swap(LIST* p1,LIST* p2)const
{
    T temp=p1->data;
    p1->data=p2->data;
    p2->data=temp;
}
template<class T>
void CList<T>::InverseList()
{
    if(m_iLength<2)
        return;
    int low=0,high=m_iLength-1;
    while(low<high)
    {
        Swap(GetAddr(low),GetAddr(high));
        low++;
        high--;
    }
}
template<class T>
int CList<T>::Partition(int low, int high)
{
    T key=GetAddr(low)->data;
    while(low<high)
    {
        while(low<high&&GetAddr(high)->data>=key)
            --high;
        GetAddr(low)->data=GetAddr(high)->data;
        while(low<high&&GetAddr(low)->data<=key)
            ++low;
        GetAddr(high)->data=GetAddr(low)->data;
    }
    GetAddr(low)->data=key;
    return low;
}
template<class T>
void CList<T>::QSort(int low, int high)
{
    if(low<high)
    {
        int ret=Partition(low,high);
        QSort(low,ret-1);
        QSort(ret+1,high);
    }
}
template<class T>
void CList<T>::QuickSort()
{
    QSort(0,m_iLength-1);
}
template<class T>
bool CList<T>::IsEmpty() const
{
    if(m_iLength)
        return false;
    return true;
}
template<class T>
void CList<T>::Replace(const T &t, const int &index)
{
    assert(index>=0&&index<m_iLength);
    GetAddr(index)->data=t;
}
template<class T>
void CList<T>::Replace(const T s[], const int &index, const int &count)
{
    assert(index>=0&&index<m_iLength);
    assert(count>=0);
    if(count==0)
        return;
    if(m_iLength-index>count)//替换count个元素
    {
        for(int i=0;i<count;++i)
            GetAddr(index+i)->data=s[i];
    }
    else//替换m_iLength-index个
    {
        for(int i=0;i<m_iLength-index;++i)
            GetAddr(index+i)->data=s[i];
    }
}
template<class T>
inline int CList<T>::GetMax(const int& a,const int& b)const
{
    if(a>b)
        return a;
    return b;
}
template<class T>
inline int CList<T>::GetMin(const int& a,const int& b)const
{
    if(a<b)
        return a;
    return b;
}
template<class T>
int CList<T>::Find(const T &t,const int pos)
{
    assert(pos>=0&&pos<m_iLength);
    int index=pos;
    PLIST p=GetAddr(pos);
    while(true)
    {
        if(p->data==t)
            return index;
        if(p->pNext==NULL)
            return -1;
        p=p->pNext;
        ++index;
    }
}
template<class T>
int CList<T>::FindLastOf(const T &t,const int pos)
{
    assert(pos>=-1&&pos<m_iLength);
    PLIST p=NULL;
    int index=pos;
    if(pos==end)
    {
        p=GetAddr(m_iLength-1);
        index=m_iLength-1;
    }
    else
        p=GetAddr(pos);
    while(true)
    {
        if(p->data==t)
            return index;
        if(index==0)
            return -1;
        --index;
        p=GetAddr(index);
    }
}