這篇文章主要介紹“c++復(fù)雜鏈表拷貝的方法是什么”，在日常操作中，相信很多人在c++復(fù)雜鏈表拷貝的方法是什么問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”c++復(fù)雜鏈表拷貝的方法是什么”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

成都一家集口碑和實力的網(wǎng)站建設(shè)服務(wù)商，擁有專業(yè)的企業(yè)建站團(tuán)隊和靠譜的建站技術(shù)，十年企業(yè)及個人網(wǎng)站建設(shè)經(jīng)驗 ,為成都數(shù)千家客戶提供網(wǎng)頁設(shè)計制作,網(wǎng)站開發(fā),企業(yè)網(wǎng)站制作建設(shè)等服務(wù),包括成都營銷型網(wǎng)站建設(shè)，品牌網(wǎng)站建設(shè)，同時也為不同行業(yè)的客戶提供成都網(wǎng)站制作、網(wǎng)站設(shè)計的服務(wù),包括成都電商型網(wǎng)站制作建設(shè),裝修行業(yè)網(wǎng)站制作建設(shè)，傳統(tǒng)機(jī)械行業(yè)網(wǎng)站建設(shè),傳統(tǒng)農(nóng)業(yè)行業(yè)網(wǎng)站制作建設(shè)。在成都做網(wǎng)站,選網(wǎng)站制作建設(shè)服務(wù)商就選創(chuàng)新互聯(lián)建站。

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

結(jié)點的C++定義如下：

template<class T>

struct ComplexListNode

{

    T value;

    ComplexListNode* pNext;

    ComplexListNode* pSibling;

};

如圖 實箭頭表示pNext   虛箭頭表示pSibling

（問題 主要是要解決pSibling）

方案一：1、根據(jù)pNext先復(fù)制一個A' ->B'->C'->D'->E'新鏈表

            2、 設(shè)置新鏈表的每個結(jié)點的pSibling 

                每次都從原鏈表的頭開始向后掃描 從對應(yīng)點開始 找到pSlibing后記下次數(shù) 再在新鏈表根據(jù)此數(shù)找到新鏈表的pSlibling

                比如B->E 則設(shè)置一個count從頭A開始掃，找出B 和 E之間的間隔結(jié)點數(shù)3 根據(jù)這個count

設(shè)置B'的pSibling

方案一缺點：

        1、每個結(jié)點pSlibling的解決都是從頭找 時間復(fù)雜度為O(n^2) 有點大

方案二：（優(yōu)化方案一 ，解決pSlibling時間復(fù)雜度大的問題 ）

        1、 設(shè)置一個索引（哈希表） 將新表和舊表的 每個結(jié)點的地址對應(yīng)起來 這樣就能在O(1)的時間復(fù)雜度根據(jù)舊表的結(jié)點指針 找到新表結(jié)點指針 所以總時間復(fù)雜度為O(n)

        2、 方案二多用了一張表 ，空間復(fù)雜度為O(n) 相當(dāng)于 用空間換時間 將時間復(fù)雜度從O(n^2)降到O(n)

方案三:（相對最優(yōu)的  優(yōu)化方案二 不用輔助空間 實現(xiàn)時間復(fù)雜度O(n)）：

        1、 先復(fù)制每個結(jié)點 不過把新結(jié)點 鏈接到原鏈表對應(yīng) 結(jié)點的后面

                如： A->A'->B->B'->C->C'->D->D'->E->E'

        2、這個新舊一體鏈有一個特點 那就是 【新結(jié)點的pSlibling 是 對應(yīng)舊結(jié)點的pNext】

            如 A->C  則 A'->C'   C'是C的pNext

        3、 設(shè)置完后 奇偶節(jié)點拆鏈 分開新舊鏈表

方案三代碼：

//----------ComplexListNode.hpp-----------

#pragma once

// 復(fù)雜鏈表的 拷貝 （復(fù)雜鏈表：鏈表中還有一個指針pSibling指向別的節(jié)點） 

template<class T>

struct ComplexListNode

{

ComplexListNode()

:pNext(NULL)

,pSibling(NULL)

{}

ComplexListNode(const T& v)

:pNext(NULL)

,pSibling(NULL)

,value(v)

{}

T value;

ComplexListNode* pNext;

ComplexListNode* pSibling;// 隨機(jī)指向 兄弟節(jié)點

};

/* 創(chuàng)建每個新節(jié)點pCloned 分別鏈接到對應(yīng)的 原節(jié)點 pNode后面 */

template<class T>

void CloneNode(ComplexListNode<T>* pHead)

{

ComplexListNode<T>* pNode = pHead;

while(pNode != NULL)

{

ComplexListNode<T>* pCloned = new ComplexListNode<T>(pNode->value);

pCloned->pNext = pNode->pNext;

pNode->pNext = pCloned;

pNode = pCloned->pNext;

}

}

/* 設(shè)置復(fù)制出來的節(jié)點 的 pSlibling值*/

template<class T>

void ConnectSiblingNodes(ComplexListNode<T>* pHead)

{

ComplexListNode<T>* pNode = pHead;

while (pNode != NULL)

{

ComplexListNode<T>* pCloned = pNode->pNext;

if (pNode->pSibling != NULL)

{

// 因為pCloned在對應(yīng)的pNode后面

// 所以pCloned的pSlibling也在 對應(yīng)的pNode的pSlibling后面

// 包含pNode指向自己的情況

pCloned->pSibling = pNode->pSibling->pNext; 

}

pNode = pCloned->pNext;

}

}

/* 拆分合并的鏈表 （從1開始）奇數(shù)位置上組成原鏈表 偶數(shù)位置上是復(fù)制出來的新鏈表*/

template<class T>

ComplexListNode<T>* ReconnectNodes(ComplexListNode<T>* pHead)

{

ComplexListNode<T>* pNode = pHead;

ComplexListNode<T>* pClonedHead = NULL;

ComplexListNode<T>* pClonedNode = NULL;

if (pNode != NULL)

{

pClonedHead = pClonedNode = pNode->pNext;

pNode->pNext = pClonedNode->pNext;

pNode = pNode->pNext;

}

while (pNode != NULL)// pNode 比 pClonedNode多走一步 ，pNode不為空 說明后面還有至少一個 pClonedNode

{

pClonedNode->pNext = pNode->pNext;

pClonedNode = pClonedNode->pNext;

pNode->pNext = pClonedNode->pNext;

pNode = pNode->pNext;

}

return pClonedHead;

}

// 復(fù)制復(fù)雜鏈表函數(shù)

template<class T>

ComplexListNode<T>* Clone(ComplexListNode<T>* pHead)

{

CloneNode<T>(pHead);

ConnectSiblingNodes<T>(pHead);

return ReconnectNodes<T>(pHead);

}

//---------------test.cpp --------------

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

#include "ComplexListNode.hpp"

using namespace std;

void testComplexListNode()

{

ComplexListNode<int> L1(1);

ComplexListNode<int> L2(2);

ComplexListNode<int> L3(3);

ComplexListNode<int> L4(4);

ComplexListNode<int> L5(5);

L1.pNext = &L2;

L2.pNext = &L3;

L3.pNext = &L4;

L4.pNext = &L5;

// 1 ->2 ->3 ->4 ->5

// pSibling

// 2->2 

L2.pSibling = &L2;

// L3->L1

L3.pSibling = &L1;

// L5->L1

L5.pSibling = &L1;

ComplexListNode<int>* Head2 = Clone(&L1);

}

int main()

{

testComplexListNode();

return 0;

}

到此，關(guān)于“c++復(fù)雜鏈表拷貝的方法是什么”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>

新聞標(biāo)題：c++復(fù)雜鏈表拷貝的方法是什么
分享網(wǎng)址：http://www.rwnh.cn/article40/gsppeo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供、虛擬主機(jī)、靜態(tài)網(wǎng)站、用戶體驗、搜索引擎優(yōu)化、網(wǎng)站營銷

廣告

聲明：本網(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)