C++實現(xiàn)雙向循環(huán)鏈表

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

雙向循環(huán)鏈表	實現(xiàn)的功能
頭部插入結(jié)點建立鏈表	尾部插入結(jié)點建立鏈表
實現(xiàn)指定位置插入結(jié)點	查找給定數(shù)值是否存在
刪除指定位置的結(jié)點	修改指定位置的結(jié)點
雙向鏈表的長度	打印雙向鏈表

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

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

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

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

雙向鏈表的基本操作

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

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

實現(xiàn)雙向循環(huán)鏈表的頭部插入結(jié)點，之前的雙向鏈表因為在頭部和尾部的指針都是指向NULL的,所以需要分情況來處理假褪，然而雙向循環(huán)鏈表沒有元素時這兩個指針都是指向自身的署咽，因此并不需要分情況處理，都需要修改四個指針嗜价。
因此艇抠，頭部插入結(jié)點實現(xiàn)如下：

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

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

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

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

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

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

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

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

查找給定元素立帖，也就是一個遍歷雙向循環(huán)鏈表的過程眼溶，從頭結(jié)點的下一個結(jié)點開始遍歷，畢竟第一個頭結(jié)點是沒有儲存數(shù)據(jù)項的晓勇。

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

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

刪除指定的結(jié)點堂飞，第一步查找到刪除的結(jié)點，需要定義一個刪除指針臨時指向?qū)⒁獎h除的結(jié)點绑咱，最后指針處理刪除之后別忘了釋放該結(jié)點空間绰筛。

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é)點的位置
    for (int i = 1; i <= n; i++)
    {
        pMove = pMove->next;                                         //游標(biāo)指針后移
    }
    //刪除結(jié)點
    pDelete = pMove;      
    pMove->prior->next = pDelete->next;
    pMove->next->prior = pDelete->prior;
    delete pDelete;//釋放空間
    return true;
}

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

修改指定位置的結(jié)點數(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)鏈表的長度

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

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

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

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

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