C++復(fù)雜鏈表的復(fù)制

復(fù)雜鏈表節(jié)點(diǎn)結(jié)構(gòu)：

創(chuàng)新互聯(lián)堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站、成都外貿(mào)網(wǎng)站建設(shè)公司、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的雞西梨樹網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

struct ComplexNode
{
    ComplexNode(const int& d)
        :_data(d)
        ,_next(NULL)
        ,random(NULL)
    {}
    int _data;            //數(shù)據(jù)域
    ComplexNode* _next;               //指向下一節(jié)點(diǎn)
    ComplexNode* _random;             //指向隨機(jī)節(jié)點(diǎn)
};

復(fù)制復(fù)雜鏈表可以分為三步來完成：

第一步：將新復(fù)制的節(jié)點(diǎn)插入到原來鏈表當(dāng)中（插入到原節(jié)點(diǎn)后面）

圖示：

代碼實(shí)現(xiàn)：

void CloneNodes(ComplexNode* pHead)		
{
	ComplexNode* cur = pHead;
	while(cur)
	{
		ComplexNode* NewHead = new ComplexNode();	//開辟新節(jié)點(diǎn)
		NewHead->_data = cur->_data;
		NewHead->_next = cur->_next;
		NewHead->_random = NULL;

		cur->_next = NewHead;		//連接新節(jié)點(diǎn)

		cur = NewHead->_next;		//跳轉(zhuǎn)到下一個(gè)要復(fù)制的節(jié)點(diǎn)
	}
}

第二步：修改新開辟的節(jié)點(diǎn)的_random，新的_random其實(shí)就是舊的_random的_next（新開辟的節(jié)點(diǎn)鏈在原來節(jié)點(diǎn)的后面，所以就是舊的_random->_next）

代碼實(shí)現(xiàn)：

void UpdateNewNodeRandom(ComplexNode* pHead)
{
	ComplexNode* cur = pHead;
	while(cur)
	{
		ComplexNode* next = cur->_next;			//指向新節(jié)點(diǎn)

		if(cur->_random != NULL)	//優(yōu)化：隨機(jī)指針不為空時(shí)，復(fù)制
		{
			next->_random = cur->_random->_next;	//復(fù)制隨機(jī)指針
		}

		cur = next->_next;			//下一個(gè)要復(fù)制的節(jié)點(diǎn)
	}
}

第三步：將復(fù)制出來的鏈表拆分出來

代碼實(shí)現(xiàn)：

ComplexNode* DisconnectNewNode(ComplexNode* pHead)
{
	ComplexNode* cur = pHead;		//指向原來的節(jié)點(diǎn)
	ComplexNode* next = NULL;		//指向復(fù)制出來的節(jié)點(diǎn)
	ComplexNode* pNewHead = NULL;	//新鏈表的頭節(jié)點(diǎn)

	if(cur != NULL)
	{
		pNewHead = next = cur->_next;	//指向新鏈表的頭
		cur->_next = next->_next;		//將新節(jié)點(diǎn)分離
		cur = next->_next;				
	}

	while(cur)
	{
		next->_next = cur->_next;		//往復(fù)制出的鏈表上面連接新節(jié)點(diǎn)

		next = next->_next;				//分離新節(jié)點(diǎn)
		cur->_next = next->_next;

		cur = next->_next;				
	}

	return pNewHead;					//返回新鏈表的頭結(jié)點(diǎn)

}

最后復(fù)制復(fù)雜鏈表就轉(zhuǎn)化下面代碼：

ComplexNode<T>* CopyComplexLinkList(ComplexNode<T>* pHead)
{
	if(pHead != NULL)					//判空
	{
		CloneNodes<T>(pHead);			//復(fù)制節(jié)點(diǎn)并連接在其后面	
		UpdateNewNodeRandom(pHead);		//更新新節(jié)點(diǎn)的隨機(jī)指針
		return DisconnectNewNode<T>(pHead);/    /拆分鏈表并返回新鏈表的頭結(jié)點(diǎn)
	}
	return NULL;
}

創(chuàng)建復(fù)雜鏈表：

ComplexNode* CreatList()
{
	ComplexNode* Node1 = new ComplexNode(1);    //創(chuàng)建節(jié)點(diǎn)
	ComplexNode* Node2 = new ComplexNode(2);
	ComplexNode* Node3 = new ComplexNode(3);
	ComplexNode* Node4 = new ComplexNode(4);
	ComplexNode* Node5 = new ComplexNode(5);
	
	Node1->_next = Node2;       //連接節(jié)點(diǎn)
	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<<"("<<cur->_data<<","<<cur->_random->_data<<")"<<"->";
		cur = cur->_next;
	}
	cout<<"Nvl."<<endl;
}

測(cè)試代碼：

void Test()
{
	ComplexNode* head = CreatList();
	Print(head);
	cout<<"---------------------------------------"<<endl;
	ComplexNode* NewHead = CopyList(head);
	Print(NewHead);
}

測(cè)試結(jié)果：

總結(jié)：復(fù)雜鏈表的復(fù)制分為三步：第一步就是把新復(fù)制出來的節(jié)點(diǎn)插入源鏈表中，第二步修改新插入節(jié)點(diǎn)的隨機(jī)指針，第三步就是將新節(jié)點(diǎn)從源中拆分出來，并合并成一個(gè)新鏈表。

網(wǎng)站欄目：C++復(fù)雜鏈表的復(fù)制
文章分享：http://bm7419.com/article34/jjspse.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計(jì)公司、建站公司、手機(jī)網(wǎng)站建設(shè)、外貿(mào)建站、搜索引擎優(yōu)化、品牌網(wǎng)站制作

廣告

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