linearList.h 和之前章节的相同

1、chain.h文件 所包含的部分算法

#ifndef CHAIN_H
#define CHAIN_H

#include "linearList.h"
#include "arrayList.h"
#include <algorithm>
#include <iostream>
#include <sstream>

template <class T>
struct chainNode
{
    // data member
    T element;
    chainNode<T>* next;

    // function
    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>
{
    template <class U>
    friend std::ostream& operator<<(std::ostream& out, const chain<U>& x);
public:
    chain(int initialCapacity = 10);
    chain(const chain<T>& theChain);
    ~chain();

    bool empty() const {return listSize == 0;} // 调用STL库的方法
    int size() const {return listSize;}  // STL
    T& get(int theIndex) const override;
    int indexOf(const T& theElement) const;
    void erase(int theIndex);
    void insert(int theIndex, const T& theElement);
    void output(std::ostream &out) const;
    // Q18
    void meld(chain<T>& leftChain, chain<T>& rightChain);
    // Q20
    void merge(chain<T>& leftChain, chain<T>& rightChain);
    // Q22
    void split(chain<T>& leftChain, chain<T>& rightChain);
    // Q26
    void insertSort();
    // Q27
    void bubbleSort();
    void selectSort();
    void countSort(){}

    class myIterator
    {
    public:
        // 构造函数
        myIterator(chainNode<T>* theNode = NULL) {node = theNode;}

        // 解引用操作符
        T& operator*() const {return node->element;}
        T* operator->() const {return &node->element;}

        // 单向列表，只能递加操作，无递减操作
        myIterator& operator++() {node = node->next; return *this;} // 先改变自身，然后返回一个指针
        myIterator operator++(int) {myIterator p=*this; node = node->next;return p;} // 这里关于指针类型的问题很重要

        // 相等检验
        bool operator==(const myIterator& right) const {return node == right.node;}
        bool operator!=(const myIterator& right) const {return node != right.node;}

    protected:
        chainNode<T>* node;
    };

    // 这里指针的值要进行显示转换，因为要支持迭代器的各种操作
    myIterator begin() const {return myIterator(firstNode);}
    myIterator end() const {return myIterator(NULL);}

protected:
    void checkIndex(int theIndex) const;
    chainNode<T>* firstNode; // 指向链表第一个节点的指针
    int listSize; // 当前链表的长度
};

template <class T>
chain<T>::chain(int initialCapacity)
{
    if(initialCapacity < 1)
    {
        std::ostringstream s;
        s << "Initial capacity = " << initialCapacity << " Must be > 0";
        // throw s.str();
    }
    firstNode = NULL;
    listSize = 0;
}

template <class T>
chain<T>::chain(const chain<T>& theList)
{
    listSize = theList.listSize;
    if(listSize == 0)
    {
        firstNode=NULL;
        return;
    }

    // if the theChain is not empty
    chainNode<T>* sourceNode = theList.firstNode;
    firstNode = new chainNode<T>(sourceNode->element); // 复制一个源链表的数据，并生成他的指针赋给头指针

    sourceNode = sourceNode->next;
    chainNode<T>* targetNode = firstNode;
    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;
    }    
}

template <class T>
void chain<T>::checkIndex(int theIndex) const
{
    if(theIndex >= listSize)
        throw "theIndex is bigger than listSize!";
}

template <class T>
T& chain<T>::get(const int theIndex) const
{
    checkIndex(theIndex);

    // 根据索引向前移动
    chainNode<T>* currentNode = firstNode;
    for(int i=0;i<theIndex;i++)
        currentNode = currentNode->next;
    return currentNode->element;
}

template <class T>
int chain<T>::indexOf(const T& theElement) const
{
    chainNode<T>* currentNode = firstNode;
    int index=0; // the index of current nodes
    for(;currentNode != NULL; currentNode = currentNode->next)
    {
        if(theElement == currentNode->element) break;
        index++;
    }
    if(currentNode == NULL)
        return -1;
    return index;
}

template <class T>
void chain<T>::erase(const int theIndex)
{
    checkIndex(theIndex);
    chainNode<T>* deleteNode, *currentNode = firstNode;
    if(theIndex == 0)
    {
        deleteNode = firstNode;
        firstNode = firstNode->next;
    }
    else
    {
        for(int i=0;i<theIndex-1;i++)
            currentNode = currentNode->next;
        deleteNode = currentNode->next;
        // here the next is the core problem
        // currentNode is a point, so it can change its member "next" from the address
        currentNode->next = currentNode->next->next; 
    }
    listSize--;
    delete deleteNode;    
}

template <class T>
void chain<T>::insert(int theIndex, const T& theElement)
{
    // 因为可以在尾后插入，且计数从0开始，所以要减一
    checkIndex(theIndex - 1);
    if(theIndex==0)
        firstNode = new chainNode<T>(theElement, firstNode);
    else
    {
        chainNode<T>* currentNode = firstNode;
        for(int i=0;i<theIndex-1;i++)
            currentNode = currentNode->next;
        // here the next is the core problem
        // currentNode is a point, so it can change its member "next" from the address
        currentNode->next = new chainNode<T>(theElement, currentNode->next);
    }
    listSize++;
}

template <class T>
void chain<T>::output(std::ostream& out) const
{
    for(chainNode<T>* currentNode=firstNode; currentNode != NULL; currentNode=currentNode->next)
        out << currentNode->element << " ";
    
}

template <class T>
std::ostream& operator<<(std::ostream& out, chain<T>& theList)
{
    theList.output(out);
    return out;
}

template <class T>
void chain<T>::meld(chain<T>& leftChain, chain<T>& rightChain)
{
    // 先释放原来的内存
    for(int i=0; i<listSize; i++)
        erase(0);
    chainNode<T>* currentNode = NULL, *leftNode = leftChain.firstNode, *rightNode = rightChain.firstNode;

    int shareSize = std::min(leftChain.size(), rightChain.size());
    // 下边这一段要好好揣摩，画图
    // 尝试有没有更好的实现方法
    for(int i=0; i<shareSize; i++)
    {
        if(i==0)
            currentNode=leftNode;
        else
        {
            currentNode->next=leftNode;
            currentNode=currentNode->next;
        }
        leftNode=leftNode->next;
        
        currentNode->next = rightNode;
        rightNode=rightNode->next;
        currentNode = currentNode->next;
    }
    if(leftChain.size() > rightChain.size())
        currentNode->next=leftNode;
    listSize = leftChain.size() + rightChain.size();
    firstNode = leftChain.firstNode;
    // 将输入链表设为空
    leftChain.firstNode=NULL;
    leftChain.listSize=0;
    rightChain.firstNode=NULL;
    rightChain.listSize=0;
}

template <class T>
void chain<T>::merge(chain<T>& leftChain, chain<T>& rightChain)
{
    // 先释放原来的内存
    for(int i=0; i<listSize; i++)
        erase(0);
    chainNode<T>* leftNode = leftChain.firstNode, *rightNode = rightChain.firstNode, *currentNode = NULL;
    // 首先确定第一个
    if(leftNode->element < rightNode->element)
    {
        currentNode = leftNode;
        leftNode = leftNode->next;
    }
    else
    {
        currentNode = rightNode;
        rightNode = rightNode->next;
    }
    firstNode = currentNode; // 更新当前对象的头指针
    while(leftNode != NULL && rightNode != NULL)
    {
        if(leftNode->element < rightNode->element)
        {
            currentNode->next = leftNode;
            currentNode = currentNode->next;
            leftNode = leftNode->next;
        }
        else
        {
            currentNode->next = rightNode;
            currentNode = currentNode->next;
            rightNode = rightNode->next;
        }
    }
    chainNode<T>* extraNode = (leftNode == NULL) ? rightNode : leftNode;
    currentNode->next=extraNode;
    listSize = leftChain.size() + rightChain.size();
    leftChain.listSize = 0, rightChain.listSize = 0;
    leftChain.firstNode = NULL, rightChain.firstNode = NULL;
}

template <class T>
void chain<T>::split(chain<T>& leftChain, chain<T>& rightChain)
{
    for(int i=0; i<leftChain.size(); i++)
        leftChain.erase(0);
    for(int i=0; i<rightChain.size(); i++)
        rightChain.erase(0);

    typename chain<T>::myIterator fromIter = begin(), endIter = end();
    while (fromIter != NULL)
    {
        leftChain.insert(leftChain.size(), *fromIter++);
        if(fromIter == NULL)   
            break;
        rightChain.insert(rightChain.size(), *fromIter++);
    }
}

// 链表排序
// 也可以不利用指针操作，而是直接对指针内的元素进行元素替换
template <class T>
void chain<T>::insertSort()
{
    // 第一个不用排序
    chainNode<T>* preNode = firstNode, *currentNode = firstNode->next, *nextNode = currentNode->next;
    for(int i=1; i<listSize; i++)
    {
        preNode->next = nextNode;
        
        int j=0; // 用j记录firstnode是否被替换
        chainNode<T>* searchLeftNode = NULL, * searchRightNode = firstNode;
        for(j=0; j<i && currentNode->element > searchRightNode->element;j++)
        {
            searchLeftNode = searchRightNode;
            searchRightNode = searchRightNode->next;
        }
        if(j == 0)
            firstNode = currentNode;
        else
            searchLeftNode->next = currentNode;
        currentNode->next = searchRightNode;
        if(j == i)
            preNode = currentNode; // 只有当currentNode放回原位时preNode才用迭代
        currentNode = nextNode;
        if(nextNode != NULL)
            nextNode = nextNode->next;
    }
}

// 冒泡排序
template <class T>
void chain<T>::bubbleSort()
{
    
    for(int j=listSize; j>1; j--)
    {
        chainNode<T>* currentNode = firstNode, *nextNode = firstNode->next;
        for(int i=0; i<j-1; i++)
        {
            if(currentNode->element > nextNode->element)
            {
                T tmp = currentNode->element;
                currentNode->element = nextNode->element;
                nextNode->element = tmp;
            }
            currentNode=nextNode;
            nextNode=nextNode->next;
        }
    }
}

template <class T>
void chain<T>::selectSort()
{
    // 找最大，方法类似
}



#endif

2、extendChain.h 部分习题

#ifndef EXTENDEDCHAIN_H
#define EXTENDEDCHAIN_H

#include "chain.h"


template <class T>
class extendedChain : public chain<T>  // 这里一定要加模板类型T
{
    template <class U>
    friend std::ostream& operator<<(std::ostream& out, const extendedChain<U>& x);
public:                                                               // 这里访问基类成员一定要在前边加this指针
    extendedChain(int initialCapacity = 10):chain<T>(initialCapacity) {lastNode = this->firstNode;}
    extendedChain(const extendedChain<T>& theList) : chain<T>(theList)
    {
        chainNode<T>* currentNode = this->firstNode;
        lastNode = this->firstNode;
        while (currentNode != NULL)
        {
            lastNode=currentNode;
            currentNode = currentNode->next;
        }
    }

    void erase(int theIndex) override;
    void insert(int theIndex, const T& theElement) override;
    void clear();
    void push_back(const T& theElement);

    // Q2
    void setSize(int theSize);
    // Q3
    void set(int theIndex, const T& theElement);
    // Q4
    void removeRange(int fromIndex, int ToIndex);
    // Q5
    int lastIndexOf(const T& theElement);
    // Q6
    T& operator[](const int& theIndex);
    // Q7
    bool operator==(const extendedChain<T>& theRight);
    // Q8
    bool operator!=(const extendedChain<T>& theRight);
    // Q9
    bool operator<(const extendedChain<T>& theright);
    bool operator>(const extendedChain<T>& theright);
    void operator=(const extendedChain<T>& theright);
    // Q10
    void swap(extendedChain<T>& theright);
    // Q13
    void fromList(const arrayList<T>& theList);
    arrayList<T> toList();
    // Q14
    void leftShift(const int& i);
    // Q15
    void reverse();
    // Q23
    void circularShift(const int shiftLength);

protected:
    chainNode<T>* lastNode;
};

template <class T>
void extendedChain<T>::erase(int theIndex)
{
    chain<T>::erase(theIndex);
    // erase之后listsize已经减一了，所以这里不用再减了
    if(theIndex == this->listSize)
    {
        chainNode<T>* currentNode = this->firstNode;
        while(currentNode != NULL)
        {
            lastNode=currentNode;
            currentNode = currentNode->next;
        }
    }
}

template <class T>
void extendedChain<T>::insert(int theIndex, const T& theElement)
{
    chain<T>::insert(theIndex, theElement);
    // 插入第一个值的时候firstNode的值被改变了，所以需要重新赋值
    if(this->listSize==1)  lastNode=this->firstNode;
    // 这里listsize又加了1
    // 这里的条件需要注意，很容易忽略第二个条件
    if((theIndex == this->listSize-1)&&(this->listSize-1>0))
        lastNode = lastNode->next;
}

template <class T>
void extendedChain<T>::clear()
{
    chainNode<T>* nextNode, *currentNode=this->firstNode;
    while(currentNode != NULL)
    {
        nextNode = currentNode->next;
        delete currentNode;
        currentNode = nextNode;
    }
    this->listSize=0; // 清空保存个数
    lastNode=this->firstNode;
}

template <class T>
void extendedChain<T>::push_back(const T& theElement)
{
    // 利用lastNode指针来加快速度

    if(this->listSize==0)
    {
        this->firstNode = new chainNode<T>(theElement, NULL);
        lastNode = this->firstNode;
    }
    else
    {
        lastNode->next=new chainNode<T>(theElement, NULL);
        lastNode = lastNode->next;
    }
    this->listSize++;
}

template <class T>
std::ostream& operator<<(std::ostream& out, extendedChain<T>& theList)
{
    theList.output(out);
    return out;
}

template <class T>
void extendedChain<T>::setSize(int theSize)
{
    if(theSize < this->listSize)
    {
        while(this->listSize>theSize)
            erase(this->listSize-1);        
    }
}

template <class T>
void extendedChain<T>::set(int theIndex, const T& theElement)
{
    chainNode<T>* currentNode = this->firstNode;
    for(int i=0;i<theIndex;i++)
        currentNode=currentNode->next;
    currentNode->element=theElement;
}

// 不删除索引为toIndex的元素
template <class T>
void extendedChain<T>::removeRange(int fromIndex, int toIndex)
{
    // 直接调用erase函数会使得程序时间复杂度过高
    this->checkIndex(fromIndex);
    // 因为不删除最后一个元素， 所以可以和listSize相等，但检查时要减一
    this->checkIndex(toIndex-1);
    bool ifLastChange = false;
    if(toIndex == this->listSize) ifLastChange=true;
    chainNode<T>* fromNode = this->firstNode, *currentNode=NULL, *deleteNode=this->firstNode;
    // 这里i=1是为了能够获得第一个被删除指针的前一个对象
    if(fromIndex != 0)
    {
        for(int i=1; i<fromIndex;i++)
            fromNode=fromNode->next;
        deleteNode=fromNode->next;
    }
    currentNode=deleteNode;
    for(int i=fromIndex;i<toIndex;i++)
    {
        currentNode=deleteNode->next;
        delete deleteNode;
        deleteNode = currentNode;
        this->listSize--;
    }
    if(fromIndex==0)
        this->firstNode=currentNode;
    else
        fromNode->next=currentNode; 
    // 看最后一个元素是否被删除
    if(ifLastChange==true)
        lastNode=fromNode;
}

template <class T>
int extendedChain<T>::lastIndexOf(const T& theElement)
{
    int i=0, index = -1;
    for(chainNode<T>* currentNode = this->firstNode; currentNode != NULL; currentNode=currentNode->next)
    {
        if(currentNode->element == theElement)
            index=i;
        i++;
    }
    return index;
}

template <class T>
T& extendedChain<T>::operator[](const int& theIndex)
{
    return this->get(theIndex);
}

template <class T>
bool extendedChain<T>::operator==(const extendedChain<T>& theRight)
{
    bool value = false;
    if(this->listSize == theRight.listSize)
    {
        chainNode<T>* currentNodeR = theRight.firstNode;
        for(chainNode<T>* currentNodeL = this->firstNode; currentNodeL != NULL; currentNodeL=currentNodeL->next)
        {
            if(currentNodeL->element != currentNodeR->element)
                break;
            currentNodeR=currentNodeR->next;
        }
        if(currentNodeR == NULL)
            value=true;
    }
    return value;
}

template <class T>
bool extendedChain<T>::operator!=(const extendedChain<T>& theRight)
{
    return !(*this == theRight);
}

template <class T>
bool extendedChain<T>::operator<(const extendedChain<T>& theRight)
{
    chainNode<T>* currentNodeL = this->firstNode, *currentNodeR = theRight.firstNode;
    int bothSize = std::min(this->listSize, theRight.listSize);
    for(int i=0; i<bothSize;i++)
    {
        if(currentNodeL->element < currentNodeR->element)
            return true;
        else if(currentNodeL->element > currentNodeR->element)
            return false;
    }
    // 如果共同长度的元素全部相等，比较长度
    if(this->listSize < theRight.listSize)
        return true;
    else
        return false;    
}

template <class T>
bool extendedChain<T>::operator>(const extendedChain<T>& theRight)
{
    chainNode<T>* currentNodeL = this->firstNode, *currentNodeR = theRight.firstNode;
    int bothSize = std::min(this->listSize, theRight.listSize);
    for(int i=0; i<bothSize;i++)
    {
        if(currentNodeL->element > currentNodeR->element)
            return true;
        else if(currentNodeL->element < currentNodeR->element)
            return false;
        currentNodeR=currentNodeR->next;
        currentNodeL=currentNodeL->next;
    }
    // 如果共同长度的元素全部相等，比较长度
    if(this->listSize > theRight.listSize)
        return true;
    else
        return false;    
}

template <class T>
void extendedChain<T>::operator=(const extendedChain<T>& theright)
{
    this->clear();


    this->listSize = theright.listSize;
    if(this->listSize == 0)
    {
        this->firstNode=NULL;
        return;
    }

    // if the theChain is not empty
    chainNode<T>* sourceNode = theright.firstNode;
    this->firstNode = new chainNode<T>(sourceNode->element); // 复制一个源链表的数据，并生成他的指针赋给头指针

    sourceNode = sourceNode->next;
    chainNode<T>* targetNode = this->firstNode;
    while(sourceNode != NULL)
    {
        targetNode->next = new chainNode<T>(sourceNode->element);
        targetNode = targetNode->next;
        sourceNode = sourceNode->next;
    }
    targetNode->next = NULL;
    chainNode<T>* currentNode = this->firstNode;
    lastNode = this->firstNode;
    while (currentNode != NULL)
    {
        lastNode=currentNode;
        currentNode = currentNode->next;
    }
}

template <class T>
void extendedChain<T>::swap(extendedChain<T>& theright)
{
    int tmpSize = this->listSize;
    chainNode<T>* tmpFirst = this->firstNode, *tmpLast = this->lastNode;
    this->listSize=theright.listSize;
    this->lastNode=theright.lastNode;
    this->firstNode=theright.firstNode;
    theright.listSize=tmpSize;
    theright.firstNode=tmpFirst;
    theright.lastNode=tmpLast;
}

// Q11
// 这里这种赋值方法需要重载=运算符
template <class T>
extendedChain<T> array2chain(const arrayList<T>& fromArray)
{
    extendedChain<T> tmpExtendChain;
    for(int i=0;i<fromArray.size();i++)
    {
        T& tmp = fromArray.get(i);
        tmpExtendChain.insert(i, tmp);
    }
    return tmpExtendChain;
}

// Q12
template <class T>
arrayList<T> chain2array(const extendedChain<T>& fromList)
{
    arrayList<T> tmpArray;
    // chainNode<T>* currentNode = fromList.firstNode; // 是保护成员，不能使用，使用迭代器指针
    typename chain<T>::myIterator chainStart = fromList.begin(), chainEnd = fromList.end();
    for(int i=0; i<fromList.size(); i++)
    {
        tmpArray.insert(i, *chainStart);
        chainStart++;
    }
    return tmpArray;
}

template <class T>
void extendedChain<T>::fromList(const arrayList<T>& theList)
{
    this->clear();
    for(int i=0;i<theList.size();i++)
    {
        T& tmp = theList.get(i);
        push_back(tmp);
    }
}

template <class T>
arrayList<T> extendedChain<T>::toList()
{
    arrayList<T> tmpArray;
    typename chain<T>::myIterator chainStart = this->begin(), chainEnd = this->end();
    for(int i=0; i<this->size(); i++)
    {
        tmpArray.insert(i, *chainStart);
        chainStart++;
    }
    return tmpArray;
}

template <class T>
void extendedChain<T>::leftShift(const int& length)
{
    this->checkIndex(length-1);
    for(int i=0; i<length; i++)
        erase(0);
}

// 原地翻转，两个指针循环迭代
template <class T>
void extendedChain<T>::reverse()
{
    chainNode<T>* aNode = this->firstNode, *bNode = aNode->next, *cNode = NULL;
    aNode->next=NULL; // 首节点变为末节点，下一个为空
    while(bNode != NULL)
    {
        cNode=bNode->next;
        bNode->next=aNode;
        aNode=bNode;
        bNode=cNode;
    }
    lastNode = this->firstNode;
    this->firstNode=aNode;
}

// Q17
template <class T>
extendedChain<T> meld(const extendedChain<T>& leftChain, const extendedChain<T>& rightChain)
{
    extendedChain<T> tmp;
    typename chain<T>::myIterator leftIterator = leftChain.begin(), rightIterator = rightChain.begin();
    int shareSize = std::min(leftChain.size(), rightChain.size());
    for(int i=0; i<shareSize; i++)
    {
        tmp.push_back(*leftIterator++);
        tmp.push_back(*rightIterator++);
        // leftIterator++;
        // rightIterator++;
    }
    if(leftChain.size() < rightChain.size())
        while(rightIterator != NULL)
            tmp.push_back(*rightIterator++);
    else
        while(leftIterator != NULL)
            tmp.push_back(*leftIterator++);
    return tmp;
}

template <class T>
extendedChain<T> merge(const extendedChain<T>& leftChain, const extendedChain<T>& rightChain)
{
    extendedChain<T> tmp;
    typename extendedChain<T>::myIterator leftIter = leftChain.begin(), rightIter = rightChain.begin();
    while(leftIter!=NULL && rightIter!=NULL)
    {
        if(*leftIter<*rightIter)
            tmp.push_back(*leftIter++);
        else
            tmp.push_back(*rightIter++);

    }
    typename extendedChain<T>::myIterator extraIter = (leftIter==NULL) ? rightIter : leftIter;
    while(extraIter!=NULL)
        tmp.push_back(*extraIter++);
    return tmp;
}

// Q21
template <class T>
void split(extendedChain<T>& fromChain, extendedChain<T>& leftChain, extendedChain<T>& rightChain)
{
    leftChain.clear();
    rightChain.clear();
    typename chain<T>::myIterator fromIter = fromChain.begin(), endIter = fromChain.end();
    while (fromIter != NULL)
    {
        leftChain.push_back(*fromIter++);
        if(fromIter == NULL)   
            break;
        rightChain.push_back(*fromIter++);
    }
}

template <class T>
void extendedChain<T>::circularShift(const int shiftLength)
{
    for(int i=0;i<shiftLength;i++)
    {
        lastNode->next = this->firstNode;
        lastNode=lastNode->next;
        this->firstNode = this->firstNode->next;
        lastNode->next = NULL;
    }
}

#endif

3、doubleLinkedList.h

#ifndef DOUBLELINKEDLIST_HPP
#define DOUBLELINKEDLIST_HPP

#include "linearList.h"
#include <iostream>
#include <algorithm>
#include <sstream>


template <class T>
struct doubleChainNode
{
    // data member
    T element;
    doubleChainNode<T>* next, * previous;

    // function
    doubleChainNode() {}
    doubleChainNode(const T& element) {this->element=element;}
    doubleChainNode(const T& element, doubleChainNode<T>* previous, doubleChainNode<T>* next) {this->element=element;this->previous = previous;this->next=next;}
};


template <class T>
class doubleLinkedList : public linearList<T>
{
    template <class U>
    friend std::ostream& operator<<(std::ostream& out, const doubleLinkedList<U>& x);
public:
    doubleLinkedList(int initialCapacity = 10);
    doubleLinkedList(const doubleLinkedList<T>& theChain);
    ~doubleLinkedList();


    bool empty() const {return listSize == 0;} // 调用STL库的方法
    int size() const {return listSize;}  // STL
    T& get(int theIndex) const override;
    int indexOf(const T& theElement) const;
    void erase(int theIndex);
    void insert(int theIndex, const T& theElement);
    void output(std::ostream &out) const;
    void clear();

    // Q39
    void reverse();
    // Q40
    void meld(doubleLinkedList<T>& leftChain, doubleLinkedList<T>& rightChain);
    // Q41
    void merge(doubleLinkedList<T>& leftChain, doubleLinkedList<T>& rightChain);
    // Q45
    void appendChain(doubleLinkedList<T>& rightChain);
    // Q48
    void split(doubleLinkedList<T>& leftChain, doubleLinkedList<T>& rightChain);

protected:
    void checkIndex(int theIndex) const;
    doubleChainNode<T>* firstNode, * lastNode; // 指向链表第一个节点的指针
    int listSize; // 当前链表的长度
};

template <class T>
doubleLinkedList<T>::doubleLinkedList(int initialCapacity)
{
    if(initialCapacity < 1)
    {
        std::ostringstream s;
        s << "Initial capacity = " << initialCapacity << " Must be > 0";
    }
    firstNode = NULL;
    lastNode = NULL;
    listSize = 0;
}

template <class T>
doubleLinkedList<T>::doubleLinkedList(const doubleLinkedList<T>& theChain)
{
    listSize = theChain.listSize;
    if(listSize == 0)
    {
        firstNode = NULL;
        lastNode = NULL;
        return;
    }
    doubleChainNode<T>* sourceNode = theChain.firstNode;
    firstNode = new doubleChainNode<T>(sourceNode->element, NULL, NULL);
    lastNode = firstNode;
    doubleChainNode<T>* targetNode = firstNode, * preNode = NULL;
    sourceNode = sourceNode->next;
    while(sourceNode != NULL)
    {
        targetNode->previous = preNode;
        targetNode->next = new doubleChainNode<T>(sourceNode->element);
        preNode = targetNode;
        targetNode = targetNode->next;
        sourceNode = sourceNode->next;
    }
    targetNode->previous = preNode;
    targetNode->next = NULL;
    lastNode = targetNode;
}

template <class T>
doubleLinkedList<T>::~doubleLinkedList()
{
    doubleChainNode<T>* nextNode;
    while((listSize--)>0)
    {
        nextNode = firstNode->next;
        delete firstNode;
        firstNode = nextNode;
    }
}

template <class T>
void doubleLinkedList<T>::checkIndex(int theIndex) const
{
    if(theIndex >= listSize)
        throw "theIndex is bigger than listSize!";
}

template <class T>
T& doubleLinkedList<T>::get(int theIndex) const
{
    checkIndex(theIndex);
    if(theIndex < listSize/2)
    {
        doubleChainNode<T>* currentNode = firstNode;
        for(int i=0; i<theIndex; i++)
            currentNode = currentNode->next;
        return currentNode->element;
    }
    else
    {
        doubleChainNode<T>* currentNode = lastNode;
        for(int i=0; i<listSize-1-theIndex; i++)
            currentNode = currentNode->previous;
        return currentNode->element;
    }
}

template <class T>
int doubleLinkedList<T>::indexOf(const T& theElement) const
{
    doubleChainNode<T>* currentNode = firstNode;
    int theIndex = 0;
    while(currentNode->element != theElement && currentNode != NULL)
    {
        currentNode = currentNode->next;
        theIndex++;
    }
    if(currentNode == NULL)
        return -1;
    else
        return theIndex;
}

template <class T>
void doubleLinkedList<T>::erase(int theIndex)
{
    checkIndex(theIndex);
    doubleChainNode<T>* currentNode = firstNode, *deleteNode = NULL, * preNode = NULL;
    if(listSize == 1)
    {
        deleteNode = firstNode;
        firstNode=NULL;
        lastNode=NULL;
    }
    else if(theIndex == 0)
    {
        deleteNode = firstNode;
        firstNode = firstNode->next;
        firstNode->previous = NULL; // firsrNode的位置已经变过了
    }
    else
    {
        for(int i=0;i<theIndex;i++)
        {
            preNode = currentNode;
            currentNode = currentNode->next;
        }
        deleteNode = currentNode;
        if(theIndex == listSize-1)
        {
            preNode->next=NULL;
            lastNode=preNode;
        }
        else
        {
            currentNode->next->previous = preNode;
            preNode->next = currentNode->next;
        }
    }
    delete deleteNode;
    listSize--;
}

template <class T>
void doubleLinkedList<T>::insert(int theIndex, const T& theElement)
{
    checkIndex(theIndex-1);
    doubleChainNode<T>* currentNode = firstNode, * preNode = NULL;
    if(listSize == 0)
    {
        firstNode = new doubleChainNode<T>(theElement, NULL, NULL);
        lastNode = firstNode;
    }
    else if(theIndex == 0)
    {
        firstNode = new doubleChainNode<T>(theElement, NULL, firstNode);
        firstNode->next->previous = firstNode;
    }
    else if(theIndex == listSize)
    {
        lastNode->next = new doubleChainNode<T>(theElement, lastNode, NULL);
        lastNode = lastNode->next;
    }
    else
    {
        for(int i=0;i<theIndex;i++)
        {
            preNode = currentNode;
            currentNode = currentNode->next;
        }
        preNode->next = new doubleChainNode<T>(theElement, preNode, currentNode);
        currentNode->previous = preNode->next;
    }
    listSize++;
}

template <class T>
void doubleLinkedList<T>::clear()
{
    for(int i = 0; i< listSize; i++)
        erase(0);
    firstNode = NULL;
    lastNode = NULL;
    listSize = 0;
}

template <class T>
void doubleLinkedList<T>::output(std::ostream &out) const
{
    for(doubleChainNode<T>* currentNode=firstNode; currentNode != NULL; currentNode=currentNode->next)
        out << currentNode->element << " ";
}

template <class U>
std::ostream& operator<<(std::ostream& out, const doubleLinkedList<U>& theList)
{
    theList.output(out);
    return out;
}

template <class T>
void doubleLinkedList<T>::appendChain(doubleLinkedList<T>& rightChain)
{
    lastNode->next = rightChain.firstNode;
    rightChain.firstNode->previous = lastNode;
    lastNode = rightChain.lastNode;
    listSize += rightChain.listSize;
    rightChain.lastNode = NULL;
    rightChain.firstNode = NULL;
    rightChain.listSize = 0;
}

template <class T>
void doubleLinkedList<T>::reverse()
{
    doubleChainNode<T>* currentNode = firstNode, * tmpNode;
    while(currentNode!=NULL)
    {
        tmpNode = currentNode->next;
        currentNode->next = currentNode->previous;
        currentNode->previous = tmpNode;
        currentNode = tmpNode;
    }
    tmpNode = firstNode;
    firstNode = lastNode;
    lastNode = tmpNode;
}

template <class T>
void doubleLinkedList<T>::meld(doubleLinkedList<T>& leftChain, doubleLinkedList<T>& rightChain)
{
    clear();
    doubleChainNode<T>* currentNode = NULL, *leftNode = leftChain.firstNode, *rightNode = rightChain.firstNode;
    int shareSize = std::min(leftChain.size(), rightChain.size());
    for(int i=0; i<shareSize; i++)
    {
        if(i==0)
            currentNode = leftNode;
        else
        {
            leftNode->previous = currentNode;
            currentNode->next = leftNode;
            currentNode = currentNode->next;
        }
        leftNode = leftNode->next;

        rightNode->previous = currentNode;
        currentNode->next = rightNode;
        currentNode = currentNode->next;
        rightNode = rightNode->next;
    }
    if(leftChain.size() > rightChain.size())
    {
        leftNode->previous = currentNode;
        currentNode->next = leftNode;
        lastNode = leftChain.lastNode;
    }
    else
        // 因为上边的for循环最后就是链接到rightchain的
        // 所以省略了一些步骤
        lastNode = rightChain.lastNode;
    if(leftChain.size() != 0)
        firstNode = leftChain.firstNode;
    else
        firstNode = rightChain.firstNode;

    listSize = leftChain.size() + rightChain.size();
    rightChain.lastNode = NULL; rightChain.firstNode = NULL; rightChain.listSize = 0;
    leftChain.lastNode = NULL;  leftChain.firstNode = NULL; leftChain.listSize = 0;    
}

template <class T>
void doubleLinkedList<T>::merge(doubleLinkedList<T>& leftChain, doubleLinkedList<T>& rightChain)
{
    clear();
    doubleChainNode<T>* leftNode = leftChain.firstNode, *rightNode = rightChain.firstNode, *currentNode = NULL;
    if(leftNode->element < rightNode->element)
    {
        currentNode = leftNode;
        leftNode = leftNode->next;
    }
    else
    {
        currentNode = rightNode;
        rightNode = rightNode->next;
    }
    firstNode = currentNode; // 更新当前对象的头指针
    while(leftNode != NULL && rightNode != NULL)
    {
        if(leftNode->element < rightNode->element)
        {
            currentNode->next = leftNode;
            leftNode->previous = currentNode;
            currentNode = currentNode->next;
            leftNode = leftNode->next;
        }
        else
        {
            currentNode->next = rightNode;
            rightNode->previous = currentNode;
            currentNode = currentNode->next;
            rightNode = rightNode->next;
        }
    }
    doubleChainNode<T>* extraNode = (leftNode == NULL) ? rightNode : leftNode;
    currentNode->next = extraNode;
    extraNode->previous = currentNode;
    lastNode = (leftNode == NULL) ? rightChain.lastNode : leftChain.lastNode;
    listSize = leftChain.size() + rightChain.size();
    rightChain.lastNode = NULL; rightChain.firstNode = NULL; rightChain.listSize = 0;
    leftChain.lastNode = NULL;  leftChain.firstNode = NULL; leftChain.listSize = 0; 
}

template <class T>
void doubleLinkedList<T>::split(doubleLinkedList<T>& leftChain, doubleLinkedList<T>& rightChain)
{
    leftChain.clear();
    rightChain.clear();
    doubleChainNode<T>* currentNode = firstNode;
    while (currentNode != NULL)
    {
        leftChain.insert(leftChain.size(), currentNode->element);
        currentNode = currentNode->next;
        if(currentNode == NULL)
            break;
        rightChain.insert(rightChain.size(), currentNode->element);
        currentNode = currentNode->next;
    }    
}

#endif

4、doubleCircleList.h

#ifndef DOUBLECIRCULARLIST_HPP
#define DOUBLECIRCULARLIST_HPP

#include "doubleLinkedList.hpp"
#include "linearList.h"
#include <iostream>
#include <algorithm>
#include <sstream>

template <class T>
class doubleCircularList : public linearList<T>
{
    template <class U>
    friend std::ostream& operator<<(std::ostream& out, const doubleLinkedList<U>& x);
public:
    doubleCircularList(int initialCapacity = 10);
    doubleCircularList(const doubleCircularList<T>& theChain);
    ~doubleCircularList();

    bool empty() const {return listSize == 0;} // 调用STL库的方法
    int size() const {return listSize;}  // STL
    T& get(int theIndex) const override;
    int indexOf(const T& theElement) const;
    void erase(int theIndex);
    void insert(int theIndex, const T& theElement);
    void output(std::ostream &out) const;
    void clear();

    // Q39
    void reverse();
    // Q40
    void meld(doubleCircularList<T>& leftChain, doubleCircularList<T>& rightChain);
    // Q41
    void merge(doubleCircularList<T>& leftChain, doubleCircularList<T>& rightChain);
    // Q48
    void split(doubleCircularList<T>& leftChain, doubleCircularList<T>& rightChain);

protected:
    void checkIndex(int theIndex) const;
    doubleChainNode<T>* firstNode; // 指向链表第一个节点的指针
    int listSize; // 当前链表的长度
};

template <class T>
doubleCircularList<T>::doubleCircularList(int initialCapacity)
{
    if(initialCapacity < 1)
    {
        std::ostringstream s;
        s << "Initial capacity = " << initialCapacity << " Must be > 0";
    }
    firstNode = NULL;
    listSize = 0;
}

template <class T>
doubleCircularList<T>::doubleCircularList(const doubleCircularList<T>& theChain)
{
    listSize = theChain.listSize;
    if(listSize == 0)
    {
        firstNode = NULL;
        return;
    }
    doubleChainNode<T>* sourceNode = theChain.firstNode;
    firstNode = new doubleChainNode<T>(sourceNode->element, NULL, NULL);
    firstNode->next = firstNode;
    firstNode->previous = firstNode;
    doubleChainNode<T>* targetNode = firstNode;
    sourceNode = sourceNode->next;
    while(sourceNode != theChain.firstNode)
    {
        targetNode->next = new doubleChainNode<T>(sourceNode->element, targetNode, firstNode);
        targetNode = targetNode->next;
        sourceNode = sourceNode->next;
        firstNode->previous = targetNode;
    }
}

template <class T>
doubleCircularList<T>::~doubleCircularList()
{
    doubleChainNode<T>* nextNode;
    while((listSize--)>0)
    {
        nextNode = firstNode->next;
        delete firstNode;
        firstNode = nextNode;
    }
}

template <class T>
void doubleCircularList<T>::checkIndex(int theIndex) const
{
    if(theIndex >= listSize)
        throw "theIndex is bigger than listSize!";
}

template <class T>
T& doubleCircularList<T>::get(int theIndex) const
{
    checkIndex(theIndex);
    if(theIndex < listSize/2)
    {
        doubleChainNode<T>* currentNode = firstNode;
        for(int i=0; i<theIndex; i++)
            currentNode = currentNode->next;
        return currentNode->element;
    }
    else
    {
        doubleChainNode<T>* currentNode = firstNode->previous;
        for(int i=0; i<listSize-1-theIndex; i++)
            currentNode = currentNode->previous;
        return currentNode->element;
    }
}

template <class T>
int doubleCircularList<T>::indexOf(const T& theElement) const
{
    doubleChainNode<T>* currentNode = firstNode;
    int theIndex = 0;
    while(currentNode->element != theElement && theIndex < listSize)
    {
        currentNode = currentNode->next;
        theIndex++;
    }
    if(theIndex == listSize)
        return -1;
    else
        return theIndex;
}

template <class T>
void doubleCircularList<T>::erase(int theIndex)
{
    checkIndex(theIndex);
    doubleChainNode<T>* currentNode = firstNode, *deleteNode = NULL, * preNode = NULL;
    // if(listSize == 1)
    // {
    //     deleteNode = firstNode;
    //     firstNode=NULL;
    // }
    if(theIndex == 0)
    {
        deleteNode = firstNode;
        firstNode->next->previous = firstNode->previous;
        firstNode->previous->next = firstNode->next;
        firstNode = firstNode->next;
    }
    else
    {
        for(int i=0;i<theIndex;i++)
            currentNode = currentNode->next;
        deleteNode = currentNode;
        currentNode->previous->next = currentNode->next;
        currentNode->next->previous = currentNode->previous;
    }
    delete deleteNode;
    listSize--;   
}

template <class T>
void doubleCircularList<T>::insert(int theIndex, const T& theElement)
{
    checkIndex(theIndex-1);
    if(listSize == 0)
    {
        firstNode = new doubleChainNode<T>(theElement, NULL, NULL);
        firstNode->next = firstNode; 
        firstNode->previous = firstNode;
    }
    else if(theIndex == 0)
    {
        firstNode = new doubleChainNode<T>(theElement, firstNode->previous, firstNode);
        firstNode->next->previous = firstNode;
        firstNode->previous->next = firstNode;
    }
    else
    {
        doubleChainNode<T>* currentNode = firstNode;
        for(int i=0;i<theIndex;i++)
            currentNode = currentNode->next;
        currentNode->previous->next = new doubleChainNode<T>(theElement, currentNode->previous, currentNode);
        currentNode->previous = currentNode->previous->next;        
    }
    listSize++;    
}

template <class T>
void doubleCircularList<T>::clear()
{
    for(int i = 0; i< listSize; i++)
        erase(0);
    firstNode = NULL;
    listSize = 0;
}

template <class T>
void doubleCircularList<T>::output(std::ostream &out) const
{
    int i=0;
    for(doubleChainNode<T>* currentNode=firstNode; i<listSize; currentNode=currentNode->next, i++)
        out << currentNode->element << " ";
}

template <class U>
std::ostream& operator<<(std::ostream& out, const doubleCircularList<U>& theList)
{
    theList.output(out);
    return out;
}

template <class T>
void doubleCircularList<T>::reverse()
{
    doubleChainNode<T>* currentNode = firstNode, * tmpNode;
    for(int i=0; i<listSize; i++)
    {
        tmpNode = currentNode->next;
        currentNode->next = currentNode->previous;
        currentNode->previous = tmpNode;
        currentNode = tmpNode;
    }
}

// 两个输入都必须至少有一个元素
template <class T>
void doubleCircularList<T>::meld(doubleCircularList<T>& leftChain, doubleCircularList<T>& rightChain)
{
    clear();
    doubleChainNode<T>* currentNode = NULL, *leftNode = leftChain.firstNode, *rightNode = rightChain.firstNode;
    doubleChainNode<T>* leftLastNode = leftNode->previous, * rightLastNode = rightNode->previous;
    int shareSize = std::min(leftChain.size(), rightChain.size());
    for(int i=0; i<shareSize; i++)
    {
        if(i==0)
        {
            currentNode = leftNode;
            leftNode = leftNode->next;
            firstNode = currentNode;
            currentNode->previous = currentNode;
            currentNode->next = currentNode;
        }
        else
        {
            leftNode->previous = currentNode;
            currentNode->next = leftNode;
            leftNode = leftNode->next;
            currentNode = currentNode->next;
            currentNode->next = firstNode;
            firstNode->previous = currentNode;
        }

        rightNode->previous = currentNode;
        currentNode->next = rightNode;
        currentNode = currentNode->next;
        rightNode = rightNode->next;
        currentNode->next = firstNode;
        firstNode->previous = currentNode;
    }

    if(leftChain.size() > rightChain.size())
    {
        leftNode->previous = currentNode;
        currentNode->next = leftNode;
        leftLastNode->next = firstNode;
        firstNode->previous = leftLastNode;
    }
    else
    {
        // 因为上边的for循环最后就是链接到rightchain的
        // 所以省略了一些步骤
        rightLastNode->next = firstNode;
        firstNode->previous = rightLastNode;
    }

    listSize = leftChain.size() + rightChain.size();
    leftChain.firstNode = NULL; leftChain.listSize = 0; 
    rightChain.firstNode = NULL; rightChain.listSize = 0;
}

template <class T>
void doubleCircularList<T>::merge(doubleCircularList<T>& leftChain, doubleCircularList<T>& rightChain)
{
    clear();
    doubleChainNode<T>* currentNode = NULL, *leftNode = leftChain.firstNode, *rightNode = rightChain.firstNode;
    doubleChainNode<T>* leftLastNode = leftNode->previous, * rightLastNode = rightNode->previous;
    int leftCount = leftChain.size(), rightCount = rightChain.size();
    if(leftNode->element < rightNode->element)
    {
        currentNode = leftNode;
        leftNode = leftNode->next;
        leftCount--;
    }
    else
    {
        currentNode = rightNode;
        rightNode = rightNode->next;
        rightCount--;
    }
    firstNode = currentNode; // 更新当前对象的头指针
    firstNode->next = firstNode;
    firstNode->previous = firstNode;
    while(leftCount != 0 && rightCount != 0)
    {
        if(leftNode->element < rightNode->element)
        {
            leftNode->previous = currentNode;
            currentNode->next = leftNode;
            leftNode = leftNode->next;
            currentNode = currentNode->next;
            currentNode->next = firstNode;
            firstNode->previous = currentNode;
            leftCount--;
        }
        else
        {
            rightNode->previous = currentNode;
            currentNode->next = rightNode;
            currentNode = currentNode->next;
            rightNode = rightNode->next;
            currentNode->next = firstNode;
            firstNode->previous = currentNode;
            rightCount--;
        }
    }
    doubleChainNode<T>* extraNode = (leftCount == 0) ? rightNode : leftNode;
    doubleChainNode<T>* extraLast = (leftCount == 0) ? rightLastNode : leftLastNode;
    currentNode->next = extraNode;
    extraNode->previous = currentNode;
    firstNode->previous = extraLast;
    extraLast->next = firstNode;
    listSize = leftChain.size() + rightChain.size();
    rightChain.firstNode = NULL; rightChain.listSize = 0;
    leftChain.firstNode = NULL; leftChain.listSize = 0; 
}

template <class T>
void doubleCircularList<T>::split(doubleCircularList<T>& leftChain, doubleCircularList<T>& rightChain)
{
    leftChain.clear();
    rightChain.clear();
    doubleChainNode<T>* currentNode = firstNode;
    for(int i=0; i<listSize;)
    {
        leftChain.insert(leftChain.size(), currentNode->element);
        currentNode = currentNode->next;
        i++;
        if(i == listSize)
            break;
        rightChain.insert(rightChain.size(), currentNode->element);
        currentNode = currentNode->next;
        i++;
    }    
}

#endif

5、circleListWithHeader.h

#ifndef CIRCULARLISTWITHHEADER
#define CIRCULARLISTWITHHEADER

#include "chain.h"
#include "linearList.h"
#include <iostream>
#include <algorithm>
#include <sstream>



template <class T>
class circularListWithHeader : public linearList<T>
{
    template <class U>
    friend std::ostream& operator<<(std::ostream& out, const circularListWithHeader<U>& x);
public:
    circularListWithHeader(int initialCapacity = 10);
    circularListWithHeader(const circularListWithHeader<T>& theChain);
    ~circularListWithHeader();


    bool empty() const {return listSize == 0;} // 调用STL库的方法
    int size() const {return listSize;}  // STL
    T& get(int theIndex) const override;
    int indexOf(const T& theElement) const;
    void erase(int theIndex);
    void insert(int theIndex, const T& theElement);
    void output(std::ostream &out) const;

    // Q39
    void reverse();
    // Q40
    void meld(circularListWithHeader<T>& leftChain, circularListWithHeader<T>& rightChain);
    // Q41
    void merge(circularListWithHeader<T>& leftChain, circularListWithHeader<T>& rightChain);

protected:
    void checkIndex(int theIndex) const;
    chainNode<T>* headerNode; // 指向链表第一个节点的指针
    int listSize; // 当前链表的长度
};

template <class T>
circularListWithHeader<T>::circularListWithHeader(int initialCapacity)
{
    if(initialCapacity < 1)
    {
        std::ostringstream s;
        s << "Initial capacity = " << initialCapacity << " Must be > 0";
    }
    headerNode = new chainNode<T>();
    headerNode->next = headerNode;
    listSize = 0;
}

template <class T>
circularListWithHeader<T>::circularListWithHeader(const circularListWithHeader<T>& theChain)
{
    listSize = theChain.listSize;
    headerNode = new chainNode<T>();
    if(listSize == 0)
    {    
        headerNode->next = headerNode;
        return;
    }
    chainNode<T>* sourceNode = theChain.headerNode;
    chainNode<T>* targetNode = headerNode;
    while(sourceNode != NULL)
    {
        targetNode->next = new chainNode<T>(sourceNode->element);
        targetNode = targetNode->next;
        sourceNode = sourceNode->next;
    }
    targetNode->next = headerNode;
}

template <class T>
circularListWithHeader<T>::~circularListWithHeader()
{
    chainNode<T>* nextNode;
    while((listSize--)>=0)
    {
        nextNode = headerNode->next;
        delete headerNode;
        headerNode = nextNode;
    }
}

template <class T>
void circularListWithHeader<T>::checkIndex(int theIndex) const
{
    if(theIndex >= listSize)
        throw "theIndex is bigger than listSize!";
}

template <class T>
T& circularListWithHeader<T>::get(int theIndex) const
{
    checkIndex(theIndex);
    chainNode<T>* currentNode = headerNode->next;
    for(int i=0; i<theIndex; i++)
        currentNode = currentNode->next;
    return currentNode->element;
}

template <class T>
int circularListWithHeader<T>::indexOf(const T& theElement) const
{
    chainNode<T>* currentNode = headerNode->next;
    int theIndex = 0;
    while(currentNode->element != theElement && currentNode != headerNode)
    {
        currentNode = currentNode->next;
        theIndex++;
    }
    if(currentNode == headerNode)
        return -1;
    else
        return theIndex;
}

template <class T>
void circularListWithHeader<T>::erase(int theIndex)
{
    checkIndex(theIndex);
    chainNode<T>* currentNode = headerNode->next, *preNode = headerNode;
    for(int i=0; i<theIndex; i++)
    {
        preNode = currentNode;
        currentNode = currentNode->next;
    }
    chainNode<T>* deleteNode = currentNode;
    preNode->next = currentNode->next;
    delete deleteNode;
    listSize--;
}

template <class T>
void circularListWithHeader<T>::insert(int theIndex, const T& theElement)
{
    checkIndex(theIndex-1);
    chainNode<T>* currentNode = headerNode->next, *preNode = headerNode;
    for(int i=0; i<theIndex; i++)
    {
        preNode = currentNode;
        currentNode = currentNode->next;
    }
    preNode->next = new chainNode<T>(theElement, currentNode);
    listSize++;
}

template <class T>
void circularListWithHeader<T>::output(std::ostream &out) const
{
    for(chainNode<T>* currentNode=headerNode->next; currentNode != headerNode; currentNode=currentNode->next)
        out << currentNode->element << " ";
}

template <class U>
std::ostream& operator<<(std::ostream& out, const circularListWithHeader<U>& theList)
{
    theList.output(out);
    return out;
}

template <class T>
void circularListWithHeader<T>::reverse()
{
    chainNode<T>* preNode = headerNode, *currentNode = headerNode->next, *nextNode = currentNode->next;
    // 因为还有头节点，所以需要加1
    for(int i=0;i<listSize+1;i++)
    {
        currentNode->next = preNode;
        preNode = currentNode;
        currentNode = nextNode;
        nextNode = currentNode->next;
    }
}

template <class T>
void circularListWithHeader<T>::meld(circularListWithHeader<T>& leftChain, circularListWithHeader<T>& rightChain)
{
    for(int i=0; i<listSize; i++)
        erase(0);
    chainNode<T>* currentNode = headerNode, *leftNode = leftChain.headerNode->next, *rightNode = rightChain.headerNode->next;

    int shareSize = std::min(leftChain.size(), rightChain.size());
    for(int i=0; i<shareSize; i++)
    {
        currentNode->next=leftNode;
        currentNode=currentNode->next;
        leftNode=leftNode->next;
        
        currentNode->next = rightNode;
        rightNode=rightNode->next;
        currentNode = currentNode->next;
    }
    if(leftChain.size() > rightChain.size())
    {
        while(leftNode != leftChain.headerNode)
        {
            currentNode->next = leftNode;
            leftNode = leftNode->next;
            currentNode = currentNode->next;
        }
    }
    else
    {
        while(rightNode != rightChain.headerNode)
        {
            currentNode->next = rightNode;
            rightNode = rightNode->next;
            currentNode = currentNode->next;
        }
    }
    currentNode->next = headerNode;
    listSize = leftChain.size() + rightChain.size();
    leftChain.headerNode->next=leftChain.headerNode;
    rightChain.headerNode->next=rightChain.headerNode;
    leftChain.listSize=0;
    rightChain.listSize=0;    
}

template <class T>
void circularListWithHeader<T>::merge(circularListWithHeader<T>& leftChain, circularListWithHeader<T>& rightChain)
{
    for(int i=0; i<listSize; i++)
        erase(0);
    chainNode<T>* currentNode = headerNode, *leftNode = leftChain.headerNode->next, *rightNode = rightChain.headerNode->next;
    while(leftNode != leftChain.headerNode && rightNode != rightChain.headerNode)
    {
        if(leftNode->element < rightNode->element)
        {
            currentNode->next = leftNode;
            currentNode = currentNode->next;
            leftNode = leftNode->next;
        }
        else
        {
            currentNode->next = rightNode;
            currentNode = currentNode->next;
            rightNode = rightNode->next;
        }
    }
    chainNode<T>* extraNode = (leftNode == leftChain.headerNode) ? rightNode : leftNode;
    chainNode<T>* theHeader = (leftNode == leftChain.headerNode) ? rightChain.headerNode : leftChain.headerNode;
    while(extraNode != theHeader)
    {
        currentNode->next = extraNode;
        currentNode = currentNode->next;
        extraNode = extraNode->next;
    }
    currentNode->next = headerNode;
    listSize = leftChain.size() + rightChain.size();
    leftChain.headerNode->next=leftChain.headerNode;
    rightChain.headerNode->next=rightChain.headerNode;
    leftChain.listSize=0;
    rightChain.listSize=0;
}

#endif

6、doubleCircularListWithHeader.h

#ifndef DOUBLECIRCULARLISTWITHHEADER_HPP
#define DOUBLECIRCULARLISTWITHHEADER_HPP

#include "doubleLinkedList.hpp"
#include "linearList.h"
#include <iostream>
#include <algorithm>
#include <sstream>

template <class T>
class doubleCircularListWithHeader : public linearList<T>
{
    template <class U>
    friend std::ostream& operator<<(std::ostream& out, const doubleCircularListWithHeader<U>& x);
public:
    doubleCircularListWithHeader(int initialCapacity = 10);
    doubleCircularListWithHeader(const doubleCircularListWithHeader<T>& theChain);
    ~doubleCircularListWithHeader();

    bool empty() const {return listSize == 0;} // 调用STL库的方法
    int size() const {return listSize;}  // STL
    T& get(int theIndex) const override;
    int indexOf(const T& theElement) const;
    void erase(int theIndex);
    void insert(int theIndex, const T& theElement);
    void output(std::ostream &out) const;
    void clear();
    void push_back(const T& theElement);

    // Q39
    void reverse();
    // Q40
    void meld(doubleCircularListWithHeader<T>& leftChain, doubleCircularListWithHeader<T>& rightChain);
    // Q41
    void merge(doubleCircularListWithHeader<T>& leftChain, doubleCircularListWithHeader<T>& rightChain);
    // Q48
    void split(doubleCircularListWithHeader<T>& leftChain, doubleCircularListWithHeader<T>& rightChain);

    class myIterator
    {
        // 构造函数
        myIterator(doubleChainNode<T>* theNode = NULL) {node = theNode;}

        // 解引用操作符
        T& operator*() const {return node->element;}
        T* operator->() const {return &node->element;}

        // 单向列表，只能递加操作，无递减操作
        myIterator& operator++() {node = node->next; return *this;} // 先改变自身，然后返回一个指针
        myIterator operator++(int) {myIterator p=*this; node = node->next;return p;} // 这里关于指针类型的问题很重要
        myIterator& operator--() {node = node->previous; return *this;}
        myIterator operator--(int) {myIterator p=*this; node = node->previous;return p;}

        // 相等检验
        bool operator==(const myIterator& right) const {return node == right.node;}
        bool operator!=(const myIterator& right) const {return node != right.node;}

    protected:
        doubleChainNode<T>* node;
    };

    myIterator begin() const {return myIterator(headerNode->next);}
    myIterator end() const {return myIterator(headerNode);}

protected:
    void checkIndex(int theIndex) const;
    doubleChainNode<T>* headerNode; // 指向链表第一个节点的指针
    int listSize; // 当前链表的长度
};

template <class T>
doubleCircularListWithHeader<T>::doubleCircularListWithHeader(int initialCapacity)
{
    if(initialCapacity < 1)
    {
        std::ostringstream s;
        s << "Initial capacity = " << initialCapacity << " Must be > 0";
    }
    headerNode = new doubleChainNode<T>();
    headerNode->next = headerNode;
    headerNode->previous = headerNode;
    listSize = 0;
}

template <class T>
doubleCircularListWithHeader<T>::doubleCircularListWithHeader(const doubleCircularListWithHeader<T>& theChain)
{
    listSize = theChain.listSize;
    headerNode = new doubleChainNode<T>();
    headerNode->next = headerNode;
    headerNode->previous = headerNode;
    if(listSize == 0)
        return;

    doubleChainNode<T>* sourceNode = theChain.headerNode->next;
    doubleChainNode<T>* targetNode = headerNode;
    while(sourceNode != theChain.headerNode)
    {
        targetNode->next = new doubleChainNode<T>(sourceNode->element, targetNode, headerNode);
        targetNode = targetNode->next;
        sourceNode = sourceNode->next;
        headerNode->previous = targetNode;
    }
}

template <class T>
doubleCircularListWithHeader<T>::~doubleCircularListWithHeader()
{
    doubleChainNode<T>* nextNode;
    while((listSize--)>=0)
    {
        nextNode = headerNode->next;
        delete headerNode;
        headerNode = nextNode;
    }
}

template <class T>
void doubleCircularListWithHeader<T>::checkIndex(int theIndex) const
{
    if(theIndex >= listSize)
        throw "theIndex is bigger than listSize!";
}

template <class T>
T& doubleCircularListWithHeader<T>::get(int theIndex) const
{
    checkIndex(theIndex);
    if(theIndex < listSize/2)
    {
        doubleChainNode<T>* currentNode = headerNode->next;
        for(int i=0; i<theIndex; i++)
            currentNode = currentNode->next;
        return currentNode->element;
    }
    else
    {
        doubleChainNode<T>* currentNode = headerNode->previous;
        for(int i=0; i<listSize-1-theIndex; i++)
            currentNode = currentNode->previous;
        return currentNode->element;
    }
}

template <class T>
int doubleCircularListWithHeader<T>::indexOf(const T& theElement) const
{
    doubleChainNode<T>* currentNode = headerNode->next;
    int theIndex = 0;
    while(currentNode->element != theElement && theIndex < listSize)
    {
        currentNode = currentNode->next;
        theIndex++;
    }
    if(theIndex == listSize)
        return -1;
    else
        return theIndex;
}

template <class T>
void doubleCircularListWithHeader<T>::erase(int theIndex)
{
    checkIndex(theIndex);
    doubleChainNode<T>* currentNode = headerNode->next, *deleteNode = NULL, * preNode = NULL;
    for(int i=0;i<theIndex;i++)
        currentNode = currentNode->next;
    deleteNode = currentNode;
    currentNode->previous->next = currentNode->next;
    currentNode->next->previous = currentNode->previous;
    delete deleteNode;
    listSize--;
}

template <class T>
void doubleCircularListWithHeader<T>::insert(int theIndex, const T& theElement)
{
    checkIndex(theIndex-1);

    doubleChainNode<T>* currentNode = headerNode;
    for(int i=0;i<theIndex;i++)
        currentNode = currentNode->next;
    doubleChainNode<T>* nextNode = currentNode->next;
    currentNode->next = new doubleChainNode<T>(theElement, currentNode, nextNode);
    nextNode->previous = currentNode->next;
    listSize++;
}

template <class T>
void doubleCircularListWithHeader<T>::push_back(const T& theElement)
{
    doubleChainNode<T>* preNode = headerNode->previous;
    headerNode->previous = new doubleChainNode<T>(theElement, preNode, headerNode);
    preNode->next = headerNode->previous;
    listSize++;
}

template <class T>
void doubleCircularListWithHeader<T>::clear()
{
    // headerNode的指针自动复原
    for(int i = 0; i< listSize; i++)
        erase(0);
    listSize = 0;
}

template <class T>
void doubleCircularListWithHeader<T>::output(std::ostream &out) const
{
    int i=0;
    for(doubleChainNode<T>* currentNode=headerNode->next; currentNode != headerNode; currentNode=currentNode->next)
        out << currentNode->element << " ";
}

template <class U>
std::ostream& operator<<(std::ostream& out, const doubleCircularListWithHeader<U>& theList)
{
    theList.output(out);
    return out;
}

template <class T>
void doubleCircularListWithHeader<T>::reverse()
{
    doubleChainNode<T>* currentNode = headerNode, * tmpNode;
    // 多了一个头节点要置换
    for(int i=0; i<listSize+1; i++)
    {
        tmpNode = currentNode->next;
        currentNode->next = currentNode->previous;
        currentNode->previous = tmpNode;
        currentNode = tmpNode;
    }
}

// 两个输入都必须至少有一个元素
template <class T>
void doubleCircularListWithHeader<T>::meld(doubleCircularListWithHeader<T>& leftChain, doubleCircularListWithHeader<T>& rightChain)
{
    clear();
    doubleChainNode<T>* currentNode = headerNode, *leftNode = leftChain.headerNode->next, *rightNode = rightChain.headerNode->next;
    doubleChainNode<T>* leftLastNode = leftChain.headerNode->previous, * rightLastNode = rightChain.headerNode->previous;
    int shareSize = std::min(leftChain.size(), rightChain.size());
    for(int i=0; i<shareSize; i++)
    {
        
        leftNode->previous = currentNode;
        currentNode->next = leftNode;
        leftNode = leftNode->next;
        currentNode = currentNode->next;
        currentNode->next = headerNode;
        headerNode->previous = currentNode;


        rightNode->previous = currentNode;
        currentNode->next = rightNode;
        rightNode = rightNode->next;
        currentNode = currentNode->next;
        currentNode->next = headerNode;
        headerNode->previous = currentNode;
    }

    if(leftChain.size() > rightChain.size())
    {
        leftNode->previous = currentNode;
        currentNode->next = leftNode;
        leftLastNode->next = headerNode;
        headerNode->previous = leftLastNode;
    }
    else if(leftChain.size() < rightChain.size())
    {
        rightNode->previous = currentNode;
        currentNode->next = rightNode;
        rightLastNode->next = headerNode;
        headerNode->previous = rightLastNode;
    }

    listSize = leftChain.size() + rightChain.size();
    leftChain.headerNode->next = leftChain.headerNode; leftChain.headerNode->previous = leftChain.headerNode; leftChain.listSize = 0; 
    rightChain.headerNode->next = rightChain.headerNode; rightChain.headerNode->previous = rightChain.headerNode; rightChain.listSize = 0;
}

template <class T>
void doubleCircularListWithHeader<T>::merge(doubleCircularListWithHeader<T>& leftChain, doubleCircularListWithHeader<T>& rightChain)
{
    clear();
    doubleChainNode<T>* currentNode = headerNode, *leftNode = leftChain.headerNode->next, *rightNode = rightChain.headerNode->next;
    doubleChainNode<T>* leftLastNode = leftChain.headerNode->previous, * rightLastNode = rightChain.headerNode->previous;
    while(leftNode != leftChain.headerNode && rightNode != rightChain.headerNode)
    {
        if(leftNode->element < rightNode->element)
        {
            leftNode->previous = currentNode;
            currentNode->next = leftNode;
            leftNode = leftNode->next;
            currentNode = currentNode->next;
            currentNode->next = headerNode;
            headerNode->previous = currentNode;
        }
        else
        {
            rightNode->previous = currentNode;
            currentNode->next = rightNode;
            currentNode = currentNode->next;
            rightNode = rightNode->next;
            currentNode->next = headerNode;
            headerNode->previous = currentNode;
        }
    }
    doubleChainNode<T>* extraNode = (leftNode == leftChain.headerNode) ? rightNode : leftNode;
    doubleChainNode<T>* extraLast = (leftNode == leftChain.headerNode) ? rightLastNode : leftLastNode;
    currentNode->next = extraNode;
    extraNode->previous = currentNode;
    headerNode->previous = extraLast;
    extraLast->next = headerNode;
    listSize = leftChain.size() + rightChain.size();
    leftChain.headerNode->next = leftChain.headerNode; leftChain.headerNode->previous = leftChain.headerNode; leftChain.listSize = 0; 
    rightChain.headerNode->next = rightChain.headerNode; rightChain.headerNode->previous = rightChain.headerNode; rightChain.listSize = 0;
}

template <class T>
void doubleCircularListWithHeader<T>::split(doubleCircularListWithHeader<T>& leftChain, doubleCircularListWithHeader<T>& rightChain)
{
    leftChain.clear();
    rightChain.clear();
    doubleChainNode<T>* currentNode = headerNode->next;
    while(currentNode != headerNode)
    {
        // 这里可以采用更简单的方法
        leftChain.push_back(currentNode->element);
        currentNode = currentNode->next;
        if(currentNode == headerNode)
            break;
        rightChain.push_back(currentNode->element);
        currentNode = currentNode->next;
    }    
}

#endif