本次博文是關(guān)于利用C++模板的方式實(shí)現(xiàn)的雙向循環(huán)鏈表以及雙向循環(huán)鏈表的基本操作，在之前的博文C++語言實(shí)現(xiàn)雙向鏈表中，已經(jīng)給大家分析了雙向循環(huán)鏈表的結(jié)構(gòu)，并以圖示的方式給大家解釋了雙向循環(huán)鏈表的基本操作。本篇文章利用C++實(shí)現(xiàn)了雙向循環(huán)鏈表的基本操作，其中包括：

定義雙向鏈表的結(jié)點(diǎn)

雙向循環(huán)鏈表的結(jié)點(diǎn)由三部分構(gòu)成，用于指向當(dāng)前節(jié)點(diǎn)的直接前驅(qū)節(jié)點(diǎn)的指針域用于存儲數(shù)據(jù)元素?cái)?shù)據(jù)域，以及用于指向當(dāng)前節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)的指針域。

在之前的C++語言實(shí)現(xiàn)雙向鏈表時(shí)已經(jīng)給大家解釋了封裝的結(jié)點(diǎn)的特點(diǎn)，不需要作太大的改變，我們需要封裝一個(gè)結(jié)點(diǎn)類,定義了結(jié)點(diǎn)的三個(gè)要素，并利用構(gòu)造函數(shù)實(shí)現(xiàn)初始化，另外，考慮到在雙向循環(huán)鏈表中要用到結(jié)點(diǎn)類，所以將雙向鏈表類定義為結(jié)點(diǎn)的友元類。

template<class T> 
class doubleCircularLinkedList;//聲明一下雙向循環(huán)鏈表，以免定義友元時(shí)報(bào)錯(cuò)
template <class T>
class doubleCircularLinkedListNode
{
    private:
        doubleCircularLinkedListNode<T> *prior;//雙向結(jié)點(diǎn)前驅(qū)指針指向該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
        T data;//儲存結(jié)點(diǎn)數(shù)據(jù)
        doubleCircularLinkedListNode<T> *next;//雙向結(jié)點(diǎn)的后驅(qū)指針指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)
        //將雙向循環(huán)鏈表類定義為結(jié)點(diǎn)的友元類
        friend  class doubleCircularLinkedList<T>;
    public:
        //結(jié)點(diǎn)的無參構(gòu)造函數(shù),將結(jié)點(diǎn)指針域初始化為NULL
        doubleCircularLinkedListNode()
        {
            prior = NULL;
            next = NULL;
        }
        //結(jié)點(diǎn)的有參構(gòu)造函數(shù)，初始化指針域和數(shù)據(jù)域
        doubleCircularLinkedListNode(T _data,doubleCircularLinkedListNode<T> *_prior = NULL,doubleCircularLinkedListNode<T> *_next = NULL)
        {
            prior = _prior;//初始化前驅(qū)指針
            data = _data;//初始化數(shù)據(jù)域
            next = _next;//初始化后繼指針
        }
        ~doubleCircularLinkedListNode()
        {
            prior = NULL;
            next = NULL;
        }
};

雙向鏈表的基本操作

本次實(shí)現(xiàn)的操作跟雙向鏈表實(shí)現(xiàn)的操作基本一樣，實(shí)現(xiàn)了雙向循環(huán)鏈表頭部插入結(jié)點(diǎn)， 尾部插入結(jié)點(diǎn)，指定位置插入結(jié)點(diǎn)建立鏈表， 查找給定數(shù)值的指定位置，刪除指定位置的結(jié)點(diǎn)，修改指定位置的結(jié)點(diǎn)，雙向循環(huán)鏈表的長度，打印雙向循環(huán)鏈表，接下來逐一進(jìn)行講解實(shí)現(xiàn)：

頭部插入結(jié)點(diǎn)建立鏈表

實(shí)現(xiàn)雙向循環(huán)鏈表的頭部插入結(jié)點(diǎn)，之前的雙向鏈表因?yàn)樵陬^部和尾部的指針都是指向NULL的,所以需要分情況來處理，然而雙向循環(huán)鏈表沒有元素時(shí)這兩個(gè)指針都是指向自身的，因此并不需要分情況處理，都需要修改四個(gè)指針。
因此，頭部插入結(jié)點(diǎn)實(shí)現(xiàn)如下：

template<class T>
bool doubleCircularLinkedList<T>::insertNodeByhead(T item)
{
    //創(chuàng)建一個(gè)新的結(jié)點(diǎn)
    doubleCircularLinkedListNode<T>* newNode = new doubleCircularLinkedListNode<T>(item);
    if (newNode == NULL){
        cout << "內(nèi)存分配失敗，新結(jié)點(diǎn)無法創(chuàng)建" << endl;
        return false;
    }
    else{
        newNode->prior = headNode;
        newNode->next = headNode->next;
        headNode->next->prior=newNode;
        headNode->next = newNode;
        return true;
    }
}

尾部插入結(jié)點(diǎn)建立鏈表

在尾部插入結(jié)點(diǎn)，當(dāng)然第一步需要找到最后一個(gè)結(jié)點(diǎn)，然后在其后進(jìn)行插入，調(diào)整四個(gè)指針即可。

template<class T>
bool doubleCircularLinkedList<T>::insertNodeBytail(T item)
{
    //創(chuàng)建一個(gè)新的結(jié)點(diǎn)
    doubleCircularLinkedListNode<T>* newNode = new doubleCircularLinkedListNode<T>(item);
    if (newNode == NULL){
        cout << "內(nèi)存分配失敗，新結(jié)點(diǎn)無法創(chuàng)建" << endl;
        return false;
    }
    //首先找到最后一個(gè)結(jié)點(diǎn)
    doubleCircularLinkedListNode<T>* lastNode = headNode;
    while(lastNode->next != headNode)
    {
        lastNode = lastNode->next;//沒找到就一直循環(huán)
    }
    //找到之后調(diào)整四個(gè)指針
    headNode->prior = newNode;
    newNode->next = headNode;
    lastNode->next = newNode;
    newNode->prior = lastNode;
    return true;
}

實(shí)現(xiàn)指定位置插入結(jié)點(diǎn)

在指定位置插入只需要兩步走，首先也是找到指定的位置，然后就是插入新結(jié)點(diǎn)的指針的調(diào)整，中間插入是最復(fù)雜的，都需要調(diào)整四個(gè)指針，最后讓新結(jié)點(diǎn)與前繼結(jié)點(diǎn)建立關(guān)系，實(shí)現(xiàn)新結(jié)點(diǎn)的插入。

template<class T>
bool doubleCircularLinkedList<T>::insertNode(T item,int n)
{
    if(n<1){
        cout<<"輸入的非有效位置！"<<endl;
        return false;
    }
    doubleCircularLinkedListNode<T>* pMove = headNode;//創(chuàng)建一個(gè)新的指針，設(shè)置為游標(biāo)指針
    //首先找到插入位置
    for(int i=1;i<n;i++)
    {
        pMove = pMove->next;
        if(pMove == NULL&& i<=n)
        {
            cout<<"插入位置無效！"<<endl;
            return false;
        }
    }
    //創(chuàng)建一個(gè)新的結(jié)點(diǎn)
    doubleCircularLinkedListNode<T>* newNode = new doubleCircularLinkedListNode<T>(item);
    if (newNode == NULL){
        cout << "內(nèi)存分配失敗，新結(jié)點(diǎn)無法創(chuàng)建" << endl;
        return false;
    }
    //插入新的結(jié)點(diǎn)
    newNode->next = pMove->next;   
    if (pMove->next != headNode)
    {
        pMove->next->prior = newNode;
    }
    newNode->prior = pMove;
    pMove->next = newNode;
    return true;
}

查找給定數(shù)值是否存在

查找給定元素，也就是一個(gè)遍歷雙向循環(huán)鏈表的過程，從頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開始遍歷，畢竟第一個(gè)頭結(jié)點(diǎn)是沒有儲存數(shù)據(jù)項(xiàng)的。

template<class T>
bool doubleCircularLinkedList<T>::findData(T item)
{
    doubleCircularLinkedListNode<T> *pMove = headNode->next; //設(shè)置游標(biāo)指針
    doubleCircularLinkedListNode<T> *pMoveprior = headNode;//指定結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)的指針
    //找到指定位置
    while(pMove->data != item)
    {
        pMoveprior = pMove;
        pMove = pMoveprior->next;
        //如果沒有找到特殊處理
        if(pMove == headNode)
        {
            return false;
        }
    }
    return true;
}

刪除指定位置的結(jié)點(diǎn)

刪除指定的結(jié)點(diǎn)，第一步查找到刪除的結(jié)點(diǎn)，需要定義一個(gè)刪除指針臨時(shí)指向?qū)⒁獎(jiǎng)h除的結(jié)點(diǎn)，最后指針處理刪除之后別忘了釋放該結(jié)點(diǎn)空間。

template<class T>
bool doubleCircularLinkedList<T>::deleteData(int n)
{
    if (n<1||n>getLength())
    {
        cout << "輸入非有效位置" << endl;
        return false;
    }
    doubleCircularLinkedListNode<T> * pMove = headNode;//設(shè)置游標(biāo)指針
    doubleCircularLinkedListNode<T> * pDelete;             
    //查找刪除結(jié)點(diǎn)的位置
    for (int i = 1; i <= n; i++)
    {
        pMove = pMove->next;                                         //游標(biāo)指針后移
    }
    //刪除結(jié)點(diǎn)
    pDelete = pMove;      
    pMove->prior->next = pDelete->next;
    pMove->next->prior = pDelete->prior;
    delete pDelete;//釋放空間
    return true;
}

修改指定位置的結(jié)點(diǎn)

修改指定位置的結(jié)點(diǎn)數(shù)據(jù)，當(dāng)然還是得找到指定位置，然后對其進(jìn)行修改，修改之后將原來的數(shù)據(jù)以引用的形式返回。

template<class T>
bool doubleCircularLinkedList<T>::changeListElements(int n,T item,T &x)
{
    if (n<1||n>getLength())
    {
        cout << "輸入非有效位置" << endl;
        return false;
    }
    doubleCircularLinkedListNode<T> *pMove = headNode->next;  //設(shè)置游標(biāo)指針
    for(int i=1;i<n;i++)//找到指定位置1
    {
        pMove = pMove->next;
    }
    x = pMove->data;
    pMove->data = item;
    return true;
}

雙向循環(huán)鏈表的長度

計(jì)算雙向鏈表的長度的函數(shù)，在雙向鏈表的私有成員封裝了一個(gè)變量<font color=green>length</font>,以此來記錄雙向鏈表的長度，遍歷雙向鏈表，逐一進(jìn)行計(jì)算結(jié)點(diǎn)數(shù)就是雙向鏈表的長度。

template<class T>
int doubleCircularLinkedList<T>::getLength()
{
    doubleCircularLinkedListNode<T> *pMove = headNode->next;  //設(shè)置游標(biāo)指針
    int length=0;
    //遍歷鏈表，計(jì)算結(jié)點(diǎn)數(shù)
    while(pMove != headNode)
    {
        pMove = pMove->next;  //游標(biāo)指針后移
        length++;       //計(jì)算length
    }
    return length;
}

打印雙向循環(huán)鏈表

template<class T>
void doubleCircularLinkedList<T>::printLinkedlist()
{
    //從第二個(gè)結(jié)點(diǎn)開始打印，表頭不含數(shù)據(jù)
    doubleCircularLinkedListNode<T>* pMove = headNode->next;
    while(pMove !=headNode)//如果pMove->next != headNode這樣寫，最后一個(gè)結(jié)點(diǎn)是不會(huì)打印的
    {
        cout<<pMove->data<<" ";
        pMove = pMove->next;//移動(dòng)指針
    }
    cout<<endl;
}

以上就是我簡要的給大家分享的C++實(shí)現(xiàn)雙向循環(huán)鏈表，因?yàn)閷?shí)現(xiàn)了雙向鏈表，所以基本上實(shí)現(xiàn)思路差不多，唯一的不同就是在循環(huán)一詞不同，這一不同就是頭結(jié)點(diǎn)的前驅(qū)指針和尾結(jié)點(diǎn)的后驅(qū)指針指向不同，要是還是不太清楚的可以去那篇博客看看。本次的完整代碼已經(jīng)全部上傳到github! (C++實(shí)現(xiàn)雙向循環(huán)鏈表),還想了解其他的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的可以去我的博客，我們一起討論啊，一起進(jìn)步！