複雜連結清單複制——時間複雜度為O(N)

        今天我們來分享一下關于複雜連結清單複制，時間複雜度為O(N)的算法。

    複雜連結清單是擁有節點值，後繼節點及随機前序節點的連結清單，複雜連結清單複制的難度在于如何找到那個随機的前序節點，一般的算法在找前序節點的效率是非常低的，需要結合被複制的連結清單去周遊查找，時間複雜度一般為O(N)。

   下面我們來舉例說明這個時間複雜度為O(N)的複雜連結清單複制算法，一般用面向過程書寫比較友善。

      首先，将要被複制的複雜連結清單如下：

     步驟一：在被複制的連結清單中對應插入擁有相應值的新節點

    步驟二：通過找到被複制連結清單的前序随機節點，找到新增節點的前序随機節點

    步驟三：拆掉新增結點和被複制節點間的聯系，依次連接配接接新增加節點，并恢複被複制節點之間的連接配接

    即可得到複制後的複雜連結清單。

    雖然不是很喜歡在部落格中粘貼代碼，但還是粘貼一下我的代碼吧！僅供參考！個人覺得面向過程寫的比較好。

面向過程：

Complex.h
//複雜連結清單Y(面向過程)
#pragma once
 
typedef int Type;
//定一結構體
struct Clist
{
Type _data;
Clist* _next;
Clist* _random;
Clist(Type data)
:_data(data)
,_next(NULL)
,_random(NULL)
{
}
};
 
Clist* ComplexCP(Clist*l)
{
if(l ==NULL)return NULL;
//插入連接配接上
Clist* cur = l;
while(cur)
{
Clist* next = cur->_next;
Clist* add = new Clist(cur->_data);
cur->_next = add;
add->_next = next;
 
cur = next;
}
//找到随機連結的結點
cur =l;
while(cur)
{
Clist* next = cur->_next;
Clist* prev = cur->_random;
 
if(prev != NULL)
{
Clist* Pnext = prev->_next;
next->_random = Pnext;
}
else
next->_random = NULL;
 
cur = next->_next;
}
//取出新鍊
cur = l;
Clist* newlist = NULL;
Clist* tail = NULL;
while(cur)
{
Clist* newPoint = cur->_next;
Clist* next = newPoint->_next;
 
cur->_next = next;
if(newlist == NULL)
{
newlist = newPoint;
tail = newPoint;
}
else
{
tail->_next = newPoint;
tail = tail->_next;
}
 
cur = next;
}
return newlist;
}
 
void Printf(Clist*l)
{
Clist* cur = l;
while(cur)
{
cout<<"結點 "<<cur<<" : "<<cur->_data<<" , next-> ";
if(cur->_next != NULL)
cout<<cur->_next->_data<<" , random-> ";
else
    cout<<"NULL , random-> ";
 
if(cur->_random != NULL)
   cout<<cur->_random->_data<<endl;
else
   cout<<" NULL "<<endl;
 
cur = cur->_next;
}
}
 
void TestCLCP()//複雜連結清單的複制面向過程
{
Clist* node1 = new Clist(5);
Clist* node2 = new Clist(4);
Clist* node3 = new Clist(3);
Clist* node4 = new Clist(2);
Clist* node5 = new Clist(1);
 
node1->_next = node2;
node2->_next = node3;
node3->_next = node4;
node4->_next = node5;
node5->_next = NULL;
 
node1->_random = node4;
node2->_random = NULL;
node3->_random = node5;
node4->_random = node2;
node5->_random = node1;
 
cout<<"列印node1: "<<endl;
Printf(node1);
 
Clist* CPlist = ComplexCP(node1);
cout<<endl<<"CPlist= ComplexCP(node1):>"<<endl<<"列印CPlist: "<<endl;
Printf(CPlist);
}
Run.h
#include<iostream>
#include<string>//不加.h
using namespace std;
#include"Complex.h"//複雜連結清單Y(面向過程)
 
int main()
{
cout<<"*******************************"<<endl;
cout<<"複雜連結清單的複制(面向過程)："<<endl<<endl;
TestCLCP();//複雜連結清單的複制面向過程
cout<<"*******************************"<<endl;
system("pause");
return 0;
}
           

面向對象（low）

//複雜連結清單的複制
#pragma once
 
template<class T>
class CListNode
{
public:
	T _data;
	CListNode<T>* _prev;
	CListNode<T>* _next;
	CListNode()
	{}
	CListNode(T data)
		:_data(data)
		,_prev(NULL)
		,_next(NULL)
	{
	}
};
 
template<class T>
class CList
{
public:
	typedef CListNode<T> Node;
	//構造,拷貝構造(*),find,Insert,析構
	CList()
		:_head(NULL)
	{
	}
	CList(CList<T>& l)
		:_head(NULL)
	{
		Node* Lhead = l._head;
		if(Lhead != NULL)
		{
			Node* prev = NULL;
			Node* cur = Lhead;
			while(cur)//鍊上
			{
				Node* next = cur->_next;
				Node* add = new Node(cur->_data);
 
				cur->_next = add;
				add->_next = next;
 
				prev = add;
				cur = next;
			}
			//add加上prev
			cur = Lhead;
			while(cur)
			{
				Node* prev = cur->_prev ;
				Node* next = cur->_next;
 
				if(prev != NULL)
				{
					Node* Pnext = prev->_next;
					next->_prev = Pnext;
				}
				else
					next->_prev = NULL;
 
				cur = next->_next;
			}
			//拆鍊
			cur = Lhead;
			Node* next = cur->_next;
			_head = next;
			while(next->_next)
			{
				Node* Cnext = next->_next;//你有一萬個見他的理由，卻沒有了一個見面的身份
				Node* Nnext = Cnext->_next;
				
				cur->_next = Cnext;
				cur = next->_next;
				next->_next = Nnext;
				next = cur->_next;
			}
			cur->_next = next->_next;
		}
	}
	CList*  operator=(CList<T> l)
	{
		swap(l._head, _head);
		return this;
	}
 
	~CList()
	{
		_Clear(_head);
		_head = NULL;
	}
 
	bool PushBack(T data)
	{
		return _PushBack(_head, data);
	}
	Node* Find(const T& data)
	{
		return _Find(_head, data);
	}
	void Print()
	{
		//cout<<"列印連結清單： ";
		_Print(_head);
		cout<<endl;
	}
protected:
	void _Clear(Node*  cur)
	{
		if(cur == NULL) return;
		Node* pt = cur->_next;
		delete cur;
		_Clear(pt);
	}
	void _Print(Node* cur)
	{
		if(cur == NULL) return;
 
		cout<<"節點 0x"<<cur<<" : "<<cur->_data<<" 前序節點->"<<cur->_prev->_data <<" , 後繼節點： ";
		if(cur->_next == NULL)
			cout<<"無";
		else
			cout<<cur->_next->_data<<endl;
		_Print(cur->_next);
	}
	bool _PushBack(Node* & cur, T& data)
	{
		if(cur == NULL)
		{
			cur=new Node(data);
			return true;
		}
		else
		{
			return _PushBack(cur->_next, data);
		}
 
	}
	Node* _Find(Node*& cur,const T& data)
	{
		if(cur == NULL) return NULL;
 
		if(cur->_data == data) return cur;
		else
		return _Find(cur->_next, data);
	}
protected:
	Node* _head;
};
 
void CLCP()//複雜連結清單的複制
{
	CList<int> LS;
	LS.PushBack(5);
	LS.PushBack(2);
	LS.PushBack(1);
	LS.PushBack(4);
	LS.PushBack(3);
	
	for(int i=1; i<6; i++)
	{
		CListNode<int>* cur = LS.Find(i);
		CListNode<int>* prev = LS.Find((2+i)%5);
		if(prev == NULL)
			prev = LS.Find(1);
		cur->_prev = prev;
 
	}
 
	cout<<"LS連結清單列印： "<<endl;
	LS.Print();
	cout<<endl;
 
	CList<int> LSCP(LS);
	cout<<"LSCP連結清單列印： "<<endl;
	LSCP.Print();
 
	CList<int> LSCP2;
	LSCP2 = LS;
	cout<<"LSCP2連結清單列印： "<<endl;
	LSCP2.Print();
}
Run.c
#include<iostream>
#include<string>
using namespace std;
#include"BST.h"
#include"VK.h"
#include"ComplexCP.h"
 
int main()
{
	cout<<"*******************************"<<endl;
	cout<<"複雜連結清單的複制："<<endl<<endl;
	CLCP();//複雜連結清單的複制
	cout<<"*******************************"<<endl;
	system("pause");
	return 0;
}
           

運作界面

今天的分享到此為止，望共同進步！