线性表-----链式描述（单链表）

/*
 * 线性表的抽象类
*/
template<class T>
class linearList
{
public:
    virtual ~linearList(){};
    virtual bool empty() const = 0;//线性表为空，返回ture
    virtual int size() const = 0;//返回线性表的元素个数
    virtual T& get(int theIndex) const = 0;//返回索引为theIndex的索引
    virtual int indexOf(const T& theElement) const = 0;//返回元素theElement第一次出现时的索引
    virtual void erase(int theIndex) const = 0;//删除索引为theIndex的元素
    virtual void insert(int theIndex,const T& theElement) const= 0;//插入元素
    virtual void output(ostream& out) const = 0;//把线性表插入输出流out

};

//链表节点定义
template<class T>
struct chainNode
{
    //数据成员
    T element;
    chainNode<T> *next;

    //方法
    chainNode(){}
    chainNode(const T& element)
    {
        this->element = element;
    }
    chainNode(const T& element,chainNode<T>* next)
    {
        this->element = element;
        this->next = next;
    }
};

//链表结构定义
template<class T>
class chain:public linearList<T>
{
public:
    //构造函数，复制构造函数和析构函数
    chain(int initialCapacity = 10);
    chain(const chain<T>&);
    ~chain();

    //抽象类中的函数
    bool empty()const;
    int size() const;
    T& get(int theIndex) const;
    int indexOf(const T &theElement) const;
    void erase(int theIndex) const;
    void insert(int theIndex, const T &theElement) const;
    void output(ostream &out) const;

protected:
    void checkIndex(int theIndex) const;//检查索引是否有效
    chainNode<T>* firstNode;//指向链表第一个节点的指针
    int listSize;//线性表元素个数
};

/*
 * 链表结构中各种函数的具体实现
*/
//构造函数
template<class T>
chain<T>::chain(int initialCapacity)
{
    if(initialCapacity > 0)
    {
        firstNode = NULL;
        listSize = 0;
    }else
    {
        cout<<"初始化的数据量必须大于0"<<endl;
    }
}
//复制构造函数
template<class T>
chain<T>::chain(const chain<T>& theList)
{
    listSize = theList.listSize;
    if(listSize == 0)
    {
        firstNode = NULL;
        return;
    }
    //链表theList为非空
    chainNode<T>* sourceNode = theList.firstNode;
    firstNode = new chainNode<T>(sourceNode->element);//复制线性表theList的首元素
    sourceNode = sourceNode->next;
    chainNode<T>* targetNode = firstNode;//当前链表*this的最后一个节点
    while(sourceNode != NULL)
    {
        //复制剩余元素
        targetNode->next = new  chainNode<T>(sourceNode->element);
        targetNode = targetNode->next;
        sourceNode = sourceNode->next;
    }
    targetNode->next = NULL;//链表结束
}
//析构函数
template<class T>
chain<T>::~chain()
{
    //删除链表所有节点
    while(firstNode != NULL)
    {
        chainNode<T>* nextNode = firstNode->next;
        delete firstNode;
        firstNode = nextNode;
    }
}


//bool empty()const;
//判断链表是否为空
template<class T>
bool chain<T>::empty() const
{
    return listSize == 0;
}

//int size() const;
//记录线性表元素个数
template<class T>
int chain<T>::size() const
{
    return listSize;
}

//T& get(int theIndex) const;
//返回索引为theIndex的元素
template<class T>
T& chain<T>::get(int theIndex) const
{
    checkIndex(theIndex);
    chainNode<T>* currentNode = firstNode;
    for(int i=0;i<theIndex;i++)
        currentNode = currentNode->next;
    return currentNode->element;
}

//int indexOf(const T &theElement) const;
//返回元素theElement的索引
template<class T>
int chain<T>::indexOf(const T &theElemet) const
{
    chainNode<T>* currentNode;
    currentNode = firstNode;int index=0;
    while(currentNode != NULL && currentNode->element != theElemet)
    {
        currentNode = currentNode->next;
        index++;
    }

    if(currentNode == NULL)
        return -1;
    else
        return index;
}

//void erase(int theIndex) const;
//删除索引为theIndex的元素
//感觉书上写的代码比我的更加简洁一些
template<class T>
void chain<T>::erase(int theIndex) const
{
    checkIndex(theIndex);
    chainNode<T>* currentNode = firstNode;int index = 0;
    //如果删除的元素是首元素,索引为0，单独处理
    if(theIndex == 0)
    {
            currentNode = firstNode;
            firstNode = firstNode->next;
    }else
    {
        while((index) != (theIndex-1))
        {
            currentNode = currentNode->next;
            index++;
        }
        currentNode->next = currentNode->next->next;
    }
}

//void insert(int theIndex, const T &theElement) const;
//在索引为theIndex的位置插入元素
//书上的写法更加简洁
template<class T>
void chain<T>::insert(int theIndex,const T& theElement) const
{
    checkIndex(theIndex);
    if(theIndex == 0)
    {
        theElement->next = firstNode->next;
        theElement = firstNode;
    }
    else
    {
        chainNode<T>* currentNode = firstNode;
        for(int i = 0;i<(theIndex-1);i++)
            currentNode = currentNode->next;
        theElement->next = currentNode->next->next;
        currentNode->next = theElement;
    }
}

//void output(ostream &out) const;
//把线性表插入输出流out
template<class T>
void chain<T>::output(ostream &out) const
{
    //把链表放入输出流
    for(chainNode<T>* currentNode = firstNode;
                        currentNode != NULL;
                        currentNode = currentNode->next)
        out<<currentNode->element<<" ";
}
//重载<<
template<class T>
ostream& operator<<(ostream& out,const chain<T>& x)
{
    x.output(out);
    return out;
}

//void checkIndex(int theIndex) const;
//检查索引是否有效
template<class T>
void chain<T>::checkIndex(int theIndex) const
{
    if(theIndex < 0 || theIndex > listSize)
        cout<<"输入的索引不合法！"<<endl;
    return;
}

/*
 * 删除索引为theIndex的元素
*/
template<class T>
void chain<T>::erase(int theIndex)
{
    //检查索引是否合法
    checkIndex(theIndex);

    //索引有效，删除索引theIndex的元素
    chainNode<T>* deleteNode;
    //待删除元素为首元素
    if(theIndex == 0)
    {
        deleteNode = firstNode;
        firstNode = firstNode->next;
    }
    else
    {
        chainNode<T>* p =firstNode;
        for(int i = 0;i<theIndex-1;i++)
            p = p->next;

        deleteNode = p->next;
        p->next = p->next->next;
    }
listSize++;
    delete deleteNode;
}

/*
 * 插入元素theElement并使其索引为theIndex
*/
template<class T>
void chain<T>::insert(int theIndex,const T& theElement)
{
    if(theIndex < 0 || theIndex > listSize)
    {
        ostringstream s;
        s<<"index = "<<theIndex<<" size"<<listSize;
        throw illegalIndex(s.str());
    }
    if(theIndex == 0)
        firstNode = new chainNode<T>(theElement,firstNode);
    else
    {
        //寻找新元素的前驱
        chainNode<T>* p = firstNode；
        for(int i = 0;i < theIndex -1;i++)
                p = p->next;
        //在p之后插入
        p->next = new chainNode<T>(theElement,p->next);
    }
    listSize++;
}