淺談復(fù)雜鏈表的復(fù)制

鏈表是一種很常見的數(shù)據(jù)結(jié)構(gòu)，單鏈表、雙向鏈表、循環(huán)鏈表和復(fù)雜鏈表都是其衍生物。復(fù)雜鏈表之所以命名為復(fù)雜鏈表，也正是由于其結(jié)構(gòu)的復(fù)雜。它比其他其他種類的鏈表多了一個指針域，這個指針域可以指向鏈表中的任一結(jié)點，也可以為空。

專注于為中小企業(yè)提供網(wǎng)站制作、成都網(wǎng)站制作服務(wù),電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)通化免費做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了上千企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實現(xiàn)規(guī)模擴充和轉(zhuǎn)變。

其結(jié)構(gòu)定義如下：

struct ComplexNode
{
	DataType _data;
	struct ComplexNode * _next;
	struct ComplexNode * _random;//隨機域
};

結(jié)構(gòu)示例：

ps：藍色指針為next域，紅色為random域。

接下來就要思考如何復(fù)制了。復(fù)制一個單鏈表很簡單，所以問題的難點就在于如何復(fù)制它的隨機指針域。

首先想到的就是先將原始鏈表的每一個結(jié)點復(fù)制下來，并用next連接，使其先成為一個單鏈表。接下來，就是考慮如何復(fù)制random域了。由于這個指針可以指向鏈表中的任何一個指針，所以必須從頭遍歷整個鏈表才可以找到這個指針。可以采取這樣一種方式，就是先遍歷原始鏈表，數(shù)出其到random是多少步，然后記下，讓復(fù)制的鏈表也進行相同的步數(shù)找到其random指向的結(jié)點。這樣就可以復(fù)制random指針了。這種方法需要對n個結(jié)點遍歷n次才可以。時間復(fù)雜度為O（n^2）。

嘗試對其進行優(yōu)化。

Step1——>要做的還是將鏈表的每個結(jié)點復(fù)制下來，并將其連在原始鏈表的后面，先將其random域賦為空。

代碼實現(xiàn)：

void CopyNode(ComplexNode *pHead)
{
	ComplexNode *pNode=pHead;
	while(pNode!=NULL)
	{
		ComplexNode *pCopy=new ComplexNode;
		pCopy->_data=pNode->_data;
		pCopy->_next=pNode->_next;
		pCopy->_random=NULL;
		pNode->_next=pCopy;
		pNode=pCopy->_next;
	}
}

Step2——>拷貝random域。由于已經(jīng)將復(fù)制的結(jié)點連接在相應(yīng)的原始結(jié)點的后面。所以復(fù)制的結(jié)點的random域也是原始結(jié)點對應(yīng)的random域的下一個指針。

代碼實現(xiàn);

void ConnectRandom(ComplexNode *pHead)
{
	ComplexNode *pNode=pHead;
	while(pNode!=NULL)
	{
		ComplexNode *pCopy=pNode->_next;
		if(pNode->_random!=NULL)
		{
			pCopy->_random=pNode->_random->_next;
		}
		pNode=pCopy->_next;
	}
}

Step3——>將鏈表拆分為兩個部分，也就是將原始鏈表和復(fù)制鏈表分開。返回的是復(fù)制的鏈表。

ComplexNode* SplitList(ComplexNode *pHead)
{

    ComplexNode *pCloneHead = pHead->_next;
    ComplexNode *tmp;	   
    ComplexNode *cur = pHead;
        while(cur->_next)
		{
            tmp = cur->_next;
            cur->_next =tmp->_next;
            cur = tmp;
        }
        return pCloneHead;
}

名稱欄目：淺談復(fù)雜鏈表的復(fù)制
URL標題：http://bm7419.com/article48/psdcep.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、服務(wù)器托管、網(wǎng)站導(dǎo)航、網(wǎng)站收錄、網(wǎng)站改版、網(wǎng)頁設(shè)計公司

廣告

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