チェーンテーブルランダムポインタコピー

2650 ワード

//     
#include<iostream>
#include<ctime>
#include<vector>
#include<cstdlib>
using namespace std;
class CNode
{
public:
	int value;
	CNode* next;
	CNode* rand;
	CNode(int v);
	~CNode();
};
CNode::CNode(int v):value(v),next(0),rand(0){}
CNode::~CNode()
{
	cout<<"~CNode()"<<endl;
}
void buildRand(CNode* clink)
{
	int lenOfclink=0;// clink 
	vector<CNode*> vc;// 
	CNode* p=clink;
	while(p)
	{
		vc.push_back(p);
		p=p->next;
		lenOfclink++;
	}
	// 1
	if(lenOfclink==1)
	{
		clink->rand=clink;
		return;
	}
	else
	{
		p=clink;
		while(p)
		{
			p->rand=vc[rand()%lenOfclink];
			p=p->next;
		}
	}
}
void append(CNode* clink,int v)
{
	CNode* p=clink;
	while(1)
	{
		if(p->next==0)
		{
			p->next=new CNode(v);
			break;
		}
		else
		{
			p=p->next;
		}
	}
	
}
void print(CNode* clink)
{
	CNode* p=clink;
	while(p)
	{
		cout<<"p->value:"<<p->value<<"
"; if(p->next) { cout<<"p->next->value:"<<p->next->value<<"\tp->rand->value:"<<p->rand->value<<endl; p=p->next; } else { break; } } } void copyLink(CNode* src,CNode* &des) { CNode* p=src,*temp; // src while(p) { temp=p->next; // p p->next=new CNode(p->value); p->next->next=temp; p=temp; } // rand p=src; while(p) { p->next->rand=p->rand->next; p=p->next->next; } // des=src->next; p=src; while(p) { temp=p->next; p->next=p->next->next; if(temp->next) temp->next=temp->next->next; p=p->next; } } int main(int args,char* argv[]) { // srand(time(0)); CNode* clink=new CNode(1); append(clink,2); append(clink,3); append(clink,4); append(clink,5); buildRand(clink); print(clink); cout<<endl<<endl; CNode* des=0; copyLink(clink,des); print(des); return 0; }