c++復雜鏈表拷貝的方法是什么

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

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

結點的C++定義如下：

template<class T>

struct ComplexListNode

{

    T value;

    ComplexListNode* pNext;

    ComplexListNode* pSibling;

};

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

（問題 主要是要解決pSibling）

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

            2、 設置新鏈表的每個結點的pSibling 

                每次都從原鏈表的頭開始向后掃描 從對應點開始 找到pSlibing后記下次數 再在新鏈表根據此數找到新鏈表的pSlibling

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

設置B'的pSibling

方案一缺點：

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

方案二：（優化方案一 ，解決pSlibling時間復雜度大的問題 ）

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

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

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

        1、 先復制每個結點 不過把新結點 鏈接到原鏈表對應 結點的后面

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

        2、這個新舊一體鏈有一個特點 那就是 【新結點的pSlibling 是 對應舊結點的pNext】

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

        3、 設置完后 奇偶節點拆鏈 分開新舊鏈表

方案三代碼：

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

#pragma once

// 復雜鏈表的 拷貝 （復雜鏈表：鏈表中還有一個指針pSibling指向別的節點） 

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;// 隨機指向 兄弟節點

};

/* 創建每個新節點pCloned 分別鏈接到對應的 原節點 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;

}

}

/* 設置復制出來的節點 的 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在對應的pNode后面

// 所以pCloned的pSlibling也在 對應的pNode的pSlibling后面

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

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

}

pNode = pCloned->pNext;

}

}

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

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;

}

// 復制復雜鏈表函數

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;

}

到此，關于“c++復雜鏈表拷貝的方法是什么”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！