数据结构-C++实现（三）循环链表

偷懒很久不发数据结构了，其实代码都写好了，但是书上的应用迟迟吃不透搞不定，所以也就没有及时发出来。

我看的是《数据结构、算法与应用 C++语言描述》这本书，配合着网易云课堂上面的一个入门级别的数据结构公开课一起学习。老实说，了解一个数据结构不是很难，但是搞清楚她们的应用场合，与适当的算法结合起来处理问题真么难上加难，比如什么约瑟夫环，汉诺塔，不得不佩服开拓这门学科的科学家们。

好了，废话说太多了，我们来看这回的数据结构，循环链表。循环链表的最后一个元素的next指针指向头指针，这样就可以构成一个循环链路，值得注意，循环链表也可以分成单向循环与双向循环。循环链表的优势在于灵活方便并且没有增加多余的空间要求。

整体结构和之前并无二致，抽象类Linear.h与之前相同，这里就不贴出。

然后是单向循环链表：

//
// Created by djf on 2016/12/21 0021.
//

#ifndef INC_03_SINGLELINKEDCIRCULARLIST_DOUBLELINKEDLIST_SINGLELINKEDCIRCULARLIST_H
#define INC_03_SINGLELINKEDCIRCULARLIST_DOUBLELINKEDLIST_SINGLELINKEDCIRCULARLIST_H
#include "LinearList.h"
using namespace std;
template
struct chainNode{
    //data
    T element;
    chainNode *next;
    //method
    chainNode() {}
    chainNode(const T& e) { this->element=e;}
    chainNode(const T& e, chainNode* n) { this->element=e;this->next=n;}
};

template
class SingleLinkedCircularList: public LinearList {
public:
    class iterator{
    public:
        //
        typedef forward_iterator_tag iterator_category;
        typedef T value_type;
        typedef ptrdiff_t difference_type;
        typedef T* pointer;
        typedef T& reference;
        //construct
        iterator(chainNode* theNode = nullptr) { node = theNode;}
        //operator
        T& operator*() const { return node->element;}
        T* operator&() const { return &node->element;}
        iterator& operator++() { node = node->next;return *this;}
        iterator operator++(int) { iterator old = *this; node = node->next; return old;}
        bool operator==(const iterator rhl) const { return node == rhl.node;}
        bool operator!=(const iterator rhl) const { return node != rhl.node;}
    protected:
        chainNode* node;
    };
    iterator begin(){ return iterator(headerNode->next->element);}
    iterator end(){ return iterator(headerNode->element);}
public:
    //construct copy destroy
    SingleLinkedCircularList(): listSize(0) { headerNode = new chainNode(); headerNode->next = headerNode;}
    SingleLinkedCircularList(const SingleLinkedCircularList& );
    ~SingleLinkedCircularList();
    //ADT
    bool empty() const override;
    int size() const override ;
    T& get(int index) const override ;
    int indexof(const T& theElement) const override ;
    void erase(int index) override ;
    void insert(int index,const T& theElement) override ;
    void output(ostream& out) const override ;
    //extend
    void clear() override ;
    void push_back(const T& theElement) override ;
protected:
    void checkIndex(int index) const;
    chainNode* headerNode;
    int listSize;
};

template
SingleLinkedCircularList::SingleLinkedCircularList(const SingleLinkedCircularList &S)
{
    chainNode* currNode = headerNode;
    chainNode* currS = S.headerNode;
    while(currS->next!=S.headerNode)
    {
        currNode->next = new chainNode(currS->next->element);
        currNode = currNode->next;
        currS = currS->next;
    }
    currNode->next = headerNode;
    listSize = S.listSize;
}

template
SingleLinkedCircularList::~SingleLinkedCircularList()
{
    chainNode* currNode = headerNode->next;
    while(headerNode->next != headerNode)
    {
        headerNode->next = currNode->next;
        delete currNode;
        currNode = headerNode->next;
    }
}
template
bool SingleLinkedCircularList::empty() const
{
    return headerNode->next==headerNode;
}

template
int SingleLinkedCircularList::size() const
{
    return listSize;
}

template
void SingleLinkedCircularList::checkIndex(int index) const
{
    if(index<0 || index>listSize)
    {
        cerr << "----! index outrange!----" << endl;
    }
}

template
T &SingleLinkedCircularList::get(int index) const
{
    checkIndex(index);
    chainNode* currNode = headerNode->next;
    for(int i = 0;inext;
    }
    return currNode->element;
}

template
int SingleLinkedCircularList::indexof(const T &theElement) const
{
    chainNode* currNode = headerNode->next;
    int i = 0;
    while(currNode->next != headerNode)
    {
        currNode = currNode->next;
        if(currNode->element==theElement)
            return i;
        ++i;
    }
    return -1;
}

template
void SingleLinkedCircularList::erase(int index)
{
    checkIndex(index);
    chainNode* currNode = headerNode->next;
    for(int i = 0;inext;
    chainNode* tmp = currNode->next;
    currNode->next = currNode->next->next;
    delete tmp;
    --listSize;
}

template
void SingleLinkedCircularList::insert(int index, const T &theElement)
{
    checkIndex(index);
    chainNode* currNode = headerNode->next;
    for(int i=0;inext;
    currNode->next = new chainNode(theElement,currNode->next->next);
    ++listSize;
}

template
void SingleLinkedCircularList::output(ostream &out) const
{
    chainNode* currNode = headerNode->next;
    while(currNode!=headerNode)
    {
        out << currNode->element << " ";
        currNode = currNode->next;
    }
}

template
void SingleLinkedCircularList::clear()
{
    chainNode* currNode = headerNode->next;
    while(currNode!=headerNode)
    {
        headerNode->next = headerNode->next->next;
        delete currNode;
        currNode = headerNode->next;
    }
    listSize = 0;
}

template
void SingleLinkedCircularList::push_back(const T &theElement)
{
    headerNode->next = new chainNode(theElement,headerNode->next);
    ++listSize;
}


#endif //INC_03_SINGLELINKEDCIRCULARLIST_DOUBLELINKEDLIST_SINGLELINKEDCIRCULARLIST_H

双向：

//
// Created by djf on 2016/12/21 0021.
//

#ifndef INC_03_SINGLELINKEDCIRCULARLIST_DOUBLELINKEDLIST_DOUBLELINKEDLIST_H
#define INC_03_SINGLELINKEDCIRCULARLIST_DOUBLELINKEDLIST_DOUBLELINKEDLIST_H

#include "LinearList.h"

using namespace std;

template 
struct doubleChainNode{
    T element;
    doubleChainNode* next;
    doubleChainNode* previous;
    doubleChainNode() {}
    doubleChainNode(const T& e) { this->element = e;}
    doubleChainNode(const T& e, doubleChainNode* p,doubleChainNode* n)
        { this->element=e;this->previous=p;this->next=n;}
};

template
class DoubleLinkedList: public LinearList {
public:
    class iterator{
    };
public:
    //construct copy destroy
    DoubleLinkedList():listSize()
    { headerNode = new doubleChainNode();headerNode->next=headerNode;headerNode->previous=headerNode;}
    DoubleLinkedList(const DoubleLinkedList& D);
    ~DoubleLinkedList();
    //ADT
    bool empty() const override ;
    int size() const override ;
    T& get(int index) const override ;
    int indexof(const T& theElement) const override ;
    void erase(int index) override ;
    void insert(int index,const T& theElement) override ;
    void output(ostream& out) const override ;
    //extend
    void clear() override ;
    void push_back(const T& theElement) override ;
protected:
    void checkIndex(int index);
    int listSize;
    doubleChainNode* headerNode;
};

template
void DoubleLinkedList::checkIndex(int index)
{
    if(index<0 || index>listSize)
        cerr << "----! index outrange !----" << endl;
}

#endif //INC_03_SINGLELINKEDCIRCULARLIST_DOUBLELINKEDLIST_DOUBLELINKEDLIST_H

单双向的区别在于迭代器的定义上，双向的循环链表，迭代器具有递增和递减的操作，而单向循环链表则只能递增，递减则违法。