チェーンテーブルランダムポインタコピー
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;
}