實現(xiàn)函數(shù)ComplexListNode* Clone(ComplexListNode* pHead)，復(fù)制一個復(fù)雜鏈表。在復(fù)雜鏈表中，每個結(jié)點除了有一個m_pNext的指針指向下一個結(jié)點外，還有一個m_pSibling的指針指向鏈表中任意結(jié)點或者NULL。

成都創(chuàng)新互聯(lián)專注于涼州企業(yè)網(wǎng)站建設(shè),自適應(yīng)網(wǎng)站建設(shè),購物商城網(wǎng)站建設(shè)。涼州網(wǎng)站建設(shè)公司,為涼州等地區(qū)提供建站服務(wù)。全流程按需求定制制作，專業(yè)設(shè)計，全程項目跟蹤，成都創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務(wù)

如下如所示的一個復(fù)雜鏈表，沒有畫出_sib指針的結(jié)點表示_sib指向NULL：

  對于復(fù)雜鏈表的復(fù)制，首先可以想到的是先遍歷一遍鏈表復(fù)制出各個結(jié)點并設(shè)置好_next指針，復(fù)制好單向的鏈表之后，對于_sib的隨機指針則需要每一次都從頭遍歷找出距當(dāng)前結(jié)點多遠(yuǎn)的結(jié)點才是應(yīng)該指向的隨機結(jié)點，雖然可行，但不難發(fā)現(xiàn)這樣尋找隨機結(jié)點的時間復(fù)雜度是O(N*N)；

  首先，有一種方法，仍然是先遍歷鏈表創(chuàng)建出相應(yīng)的結(jié)點并設(shè)置好每一個的_next指針，之后用一個哈希桶來保存每一個原鏈表結(jié)點的地址和新創(chuàng)建出結(jié)點的地址信息，也就是在每一個原鏈表結(jié)點地址的下面鏈上新創(chuàng)建出對應(yīng)的鏈表結(jié)點的地址，這樣的話一次就能定位新復(fù)制出鏈表中每一個結(jié)點的_sib應(yīng)該指向哪一個對應(yīng)的結(jié)點了；雖然時間復(fù)雜度降為了O(N)，但這是一種以空間換時間的方法；

  另外的一種方法，是在遍歷到原鏈表的一個結(jié)點的時候，就新創(chuàng)建出一個結(jié)點插入當(dāng)前結(jié)點的后面，完成之后原鏈表就變成了兩個連續(xù)重復(fù)的結(jié)點的雙倍長度的鏈表，這樣的話，原來鏈表中結(jié)點的_sib后面的重復(fù)的結(jié)點，也就會是新創(chuàng)建鏈表對應(yīng)結(jié)點的_sib的指向，之后再從頭訪問鏈表，將原鏈表中每個結(jié)點對應(yīng)的_sib指針后面的結(jié)點賦值給當(dāng)前結(jié)點后面新創(chuàng)建結(jié)點的_sib，這樣也就完成了新建鏈表的_sib指向，之后再將兩個鏈表拆開就可以了；

程序設(shè)計如下：

#include <iostream>
#include <assert.h>
using namespace std;

int list_num = 0;

struct ComplexListNode//復(fù)雜鏈表結(jié)點數(shù)據(jù)結(jié)構(gòu)
{
    int _val;
    ComplexListNode* _next;
    ComplexListNode* _sib;

    ComplexListNode(int val)//構(gòu)造函數(shù)
        :_val(val)
         ,_next(NULL)
         ,_sib(NULL)
    {}  
};

ComplexListNode* Buy_Node(int val)//構(gòu)建復(fù)雜鏈表結(jié)點
{
    ComplexListNode* node = new ComplexListNode(val);
    return node;
}

//插入結(jié)點
void Push_Node(ComplexListNode** phead, int val)
{
    if((*phead) == NULL)
        (*phead) = Buy_Node(val);
    else
    {   
        ComplexListNode* tmp = (*phead);
        while(tmp->_next != NULL)
            tmp = tmp->_next;
        tmp->_next = Buy_Node(val);
    }

    ++list_num;
}

//設(shè)置自由結(jié)點的指向
void SetSibPointer(ComplexListNode* head, int* positions)
{
    assert(head && positions);

    ComplexListNode* tmp = head;
    ComplexListNode *p[list_num];
    for(size_t i = 0; i < list_num; ++i)
    {
        p[i] = tmp;
        tmp = tmp->_next;
    }

    tmp = head;
    for(size_t i = 0; i < list_num; ++i)
    {
        if(positions[i] != 0)
            tmp->_sib = p[positions[i]];

        tmp = tmp->_next;
    }
}

//銷毀鏈表
void DestoryList(ComplexListNode* head)
{
    if(head != NULL)
    {
        ComplexListNode* tmp = head;
        while(head != NULL)
        {
            head = head->_next;
            delete tmp;
            tmp = NULL;
            tmp = head;
        }
    }
}

//打印鏈表
void PrintList(ComplexListNode* head)
{
    if(head != NULL)
    {
        ComplexListNode *tmp = head;
        while(tmp != NULL)
        {
            cout<<tmp->_val<<"->";
            tmp = tmp->_next;
        }
        cout<<"NULL"<<endl;

        tmp = head;
        while(tmp != NULL)
        {
            cout<<tmp->_val<<" sibling is ->";
            if(tmp->_sib != NULL)
                cout<<tmp->_sib->_val<<endl;
            else
                cout<<"NULL"<<endl;

            tmp = tmp->_next;
        }
    }
}

//復(fù)制復(fù)雜鏈表
ComplexListNode* Clone(ComplexListNode* head)
{
    if(head != NULL)
    {
        ComplexListNode *tmp = head;
        ComplexListNode *newnode = NULL;

        //復(fù)制每個結(jié)點并插入當(dāng)前結(jié)點的后面
        while(tmp != NULL)
        {
            newnode = Buy_Node(tmp->_val);
            newnode->_next = tmp->_next;
            tmp->_next = newnode;
            tmp = newnode->_next;
        }

        //設(shè)置新創(chuàng)建鏈表結(jié)點的sib指針的指向
        tmp = head;
        newnode = tmp->_next;
        while(tmp != NULL)
        {
            if(tmp->_sib != NULL)
                newnode->_sib = tmp->_sib->_next;
            tmp = newnode->_next;
            if(tmp != NULL)
                newnode = tmp->_next;
        }
        //拆分兩個鏈表
        tmp = head;
        ComplexListNode* NewHead = tmp->_next;
        newnode = tmp->_next;
        while(tmp != NULL)
        {
            tmp->_next = newnode->_next;
            tmp = tmp->_next;
            if(tmp != NULL)
            {
                newnode->_next = tmp->_next;
                newnode = newnode->_next;
            }
        }

        return NewHead;
    }
}

int main()
{
    ComplexListNode* head = NULL;
    Push_Node(&head, 7);
    Push_Node(&head, 5);
    Push_Node(&head, 8);
    Push_Node(&head, 2);
    Push_Node(&head, 6);
    Push_Node(&head, 9);
    Push_Node(&head, 3);

    int positions[7] = {2,5,0,4,0,0,4};
    SetSibPointer(head, positions);
    cout<<"Complex List: ";
    PrintList(head);
     ComplexListNode* NewComplexListHead = Clone(head);
    cout<<"New Complex List: ";
    PrintList(NewComplexListHead);
    cout<<"Complex List: ";
    PrintList(head);

    DestoryList(head);
    DestoryList(NewComplexListHead);
    return 0;
}

運行程序：

《完》

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)站名稱：復(fù)雜鏈表的復(fù)制——26-創(chuàng)新互聯(lián)
當(dāng)前路徑：http://chinadenli.net/article30/dhsdpo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動網(wǎng)站建設(shè)、做網(wǎng)站、網(wǎng)站設(shè)計公司、網(wǎng)站內(nèi)鏈、網(wǎng)站改版、營銷型網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)