c++复杂链表拷贝的方法是什么

这篇文章主要介绍“c++复杂链表拷贝的方法是什么”，在日常操作中，相信很多人在c++复杂链表拷贝的方法是什么问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”c++复杂链表拷贝的方法是什么”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

成都一家集口碑和实力的网站建设服务商，拥有专业的企业建站团队和靠谱的建站技术，十年企业及个人网站建设经验 ,为成都数千家客户提供网页设计制作,网站开发,企业网站制作建设等服务,包括成都营销型网站建设，品牌网站建设，同时也为不同行业的客户提供成都网站制作、网站设计的服务,包括成都电商型网站制作建设,装修行业网站制作建设，传统机械行业网站建设,传统农业行业网站制作建设。在成都做网站,选网站制作建设服务商就选创新互联建站。

题目：请实现函数ComplexListNode* Clone(ComplextListNode* pHead),复制一个复杂链表。在复杂链表中，每个结点除了有一个pNext指针指向下一个结点外，还有一个pSibling指向链表的任意结点或者NULL。

结点的C++定义如下：

template

struct ComplexListNode

{

T value;

ComplexListNode* pNext;

ComplexListNode* pSibling;

};

如图实箭头表示pNext 虚箭头表示pSibling

c++复杂链表拷贝的方法是什么

（问题主要是要解决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

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

void CloneNode(ComplexListNode* pHead)

{

ComplexListNode* pNode = pHead;

while(pNode != NULL)

{

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

pCloned->pNext = pNode->pNext;

pNode->pNext = pCloned;

pNode = pCloned->pNext;

}

/* 设置复制出来的节点的 pSlibling值*/

template

void ConnectSiblingNodes(ComplexListNode* pHead)

{

ComplexListNode* pNode = pHead;

while (pNode != NULL)

{

ComplexListNode* pCloned = pNode->pNext;

if (pNode->pSibling != NULL)

{

// 因为pCloned在对应的pNode后面

// 所以pCloned的pSlibling也在对应的pNode的pSlibling后面

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

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

}

pNode = pCloned->pNext;

}

/* 拆分合并的链表（从1开始）奇数位置上组成原链表偶数位置上是复制出来的新链表*/

template

ComplexListNode* ReconnectNodes(ComplexListNode* pHead)

{

ComplexListNode* pNode = pHead;

ComplexListNode* pClonedHead = NULL;

ComplexListNode* 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

ComplexListNode* Clone(ComplexListNode* pHead)

{

CloneNode(pHead);

ConnectSiblingNodes(pHead);

return ReconnectNodes(pHead);

}

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

#define _CRT_SECURE_NO_WARNINGS 1

#include

#include "ComplexListNode.hpp"

using namespace std;

void testComplexListNode()

{

ComplexListNode L1(1);

ComplexListNode L2(2);

ComplexListNode L3(3);

ComplexListNode L4(4);

ComplexListNode 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* Head2 = Clone(&L1);

}

int main()

{

testComplexListNode();

return 0;

}

到此，关于“c++复杂链表拷贝的方法是什么”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注创新互联网站，小编会继续努力为大家带来更多实用的文章！

分享标题：c++复杂链表拷贝的方法是什么
分享地址：http://6mz.cn/article/gsppeo.html

网站建设知识

c++复杂链表拷贝的方法是什么

其他资讯