复杂链表节点结构:
让客户满意是我们工作的目标,不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户,将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴,公司提供的服务项目有:申请域名、虚拟空间、营销软件、网站建设、丰满网站维护、网站推广。struct ComplexNode { ComplexNode(const int& d) :_data(d) ,_next(NULL) ,random(NULL) {} int _data; //数据域 ComplexNode* _next; //指向下一节点 ComplexNode* _random; //指向随机节点 };
复制复杂链表可以分为三步来完成:
第一步:将新复制的节点插入到原来链表当中(插入到原节点后面)
图示:
代码实现:
void CloneNodes(ComplexNode* pHead) { ComplexNode* cur = pHead; while(cur) { ComplexNode* NewHead = new ComplexNode(); //开辟新节点 NewHead->_data = cur->_data; NewHead->_next = cur->_next; NewHead->_random = NULL; cur->_next = NewHead; //连接新节点 cur = NewHead->_next; //跳转到下一个要复制的节点 } }
第二步:修改新开辟的节点的_random,新的_random其实就是旧的_random的_next(新开辟的节点链在原来节点的后面,所以就是旧的_random->_next)
代码实现:
void UpdateNewNodeRandom(ComplexNode* pHead) { ComplexNode* cur = pHead; while(cur) { ComplexNode* next = cur->_next; //指向新节点 if(cur->_random != NULL) //优化:随机指针不为空时,复制 { next->_random = cur->_random->_next; //复制随机指针 } cur = next->_next; //下一个要复制的节点 } }
第三步:将复制出来的链表拆分出来
代码实现:
ComplexNode* DisconnectNewNode(ComplexNode* pHead) { ComplexNode* cur = pHead; //指向原来的节点 ComplexNode* next = NULL; //指向复制出来的节点 ComplexNode* pNewHead = NULL; //新链表的头节点 if(cur != NULL) { pNewHead = next = cur->_next; //指向新链表的头 cur->_next = next->_next; //将新节点分离 cur = next->_next; } while(cur) { next->_next = cur->_next; //往复制出的链表上面连接新节点 next = next->_next; //分离新节点 cur->_next = next->_next; cur = next->_next; } return pNewHead; //返回新链表的头结点 }
最后复制复杂链表就转化下面代码:
ComplexNode* CopyComplexLinkList(ComplexNode * pHead) { if(pHead != NULL) //判空 { CloneNodes (pHead); //复制节点并连接在其后面 UpdateNewNodeRandom(pHead); //更新新节点的随机指针 return DisconnectNewNode (pHead);/ /拆分链表并返回新链表的头结点 } return NULL; }
创建复杂链表:
ComplexNode* CreatList() { ComplexNode* Node1 = new ComplexNode(1); //创建节点 ComplexNode* Node2 = new ComplexNode(2); ComplexNode* Node3 = new ComplexNode(3); ComplexNode* Node4 = new ComplexNode(4); ComplexNode* Node5 = new ComplexNode(5); Node1->_next = Node2; //连接节点 Node2->_next = Node3; Node3->_next = Node4; Node4->_next = Node5; Node1->_random = Node3; //置_random Node2->_random = Node4; Node3->_random = Node1; Node4->_random = Node5; Node5->_random = Node2; return Node1; //返回头 }
打印链表:
void Print(ComplexNode* _head) { ComplexNode* cur = _head; while(cur) { cout<<"("<_data<<","< _random->_data<<")"<<"->"; cur = cur->_next; } cout<<"Nvl."< 测试代码:
void Test() { ComplexNode* head = CreatList(); Print(head); cout<<"---------------------------------------"<测试结果:
总结:复杂链表的复制分为三步:第一步就是把新复制出来的节点插入源链表中,第二步修改新插入节点的随机指针,第三步就是将新节点从源中拆分出来,并合并成一个新链表。
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
文章题目:C++复杂链表的复制-创新互联
文章URL:http://bjjierui.cn/article/csijpd.html