#include <stdlib.h> #include <stdio.h> #include <iostream> using namespace std; int lengthlist;
struct randlist
{
int data;
randlist * randnode;
randlist * next;
};
randlist * setlist(int & length)//形成一个随机跳跃链
{
length=1;//计算链的长度
char order;
randlist * list;
randlist * listhead;
list = listhead = new randlist;
while (length<100)
{
cout<<"第"<<length<<"节点数据是：";
cin>>list->data;
cout<<"此节点是否是最后一个(y/n):";
cin>>order;
while(order!='y'&&order!='Y'&&order!='n'&&order!='N')
{
cout<<"输入错误,请输入y或n";
cin>>order;
}
if(order=='y'||order=='Y')
{
list->next =0;
break;
}
if(order=='n'||order=='N')
{
list->next = new randlist;
list = list->next;
length++;
}
}
list = listhead;
randlist * listfind=listhead;
for(int i=0;i<length;i++ )//产生随机跳跃点
{
int ranknum;//随机跳到第几个节点
ranknum = rand()%length+1;
for(int k=0;k<ranknum-1;k++)
{
listfind = listfind->next;
}
list->randnode =listfind;
listfind =listhead;
list =list->next;
}
return listhead;
}
int printlist(randlist* randhead)
{
randlist * rand;
rand = randhead;
cout<< randhead<<endl;
for(int i =0;i<lengthlist;i++)
{
cout<<rand->data<<";"<<rand->randnode<<";"<<rand->next<<endl;
rand = rand->next;
}
getchar();
return 0;
}
randlist * copylist(randlist* randAhead)
{
int serial =0;
randlist * randB,*randB2,*randBhead,*randA;
randA = randAhead;
randB = randB2 = randBhead = new randlist;
while(1)//把A的数据存到B，数据区用作记录是第几个节点
{
randB->data = randA->data;
randA->data = serial;
if(randA->next!=0)
{
randB->next = new randlist;
randB = randB->next;
randA =randA->next;
serial++;
}
else
{
randB->next=0;
break;
}
}
randA = randAhead;
randB = randBhead;//新链表随机数的地址对应起来
do
{
int num = randA->randnode->data;
for ( int k=0 ;k<num;k++)
{
randB2 =randB2->next;
}
randB -> randnode = randB2;
randB2 = randBhead;
if(randA->next !=0)
{
randA = randA->next;
randB = randB->next;
}
else
break;
}while(1);
randA=randAhead;
randB= randBhead;//把listA还原 for (int i=0;i<lengthlist;i++)
{
randA->data = randB->data;
randA = randA->next;
randB = randB ->next;
}
return randBhead;
}
int main(void)
{
randlist * oldlist,*newlist; oldlist = setlist(lengthlist);//传出链长度
cout<<"the size is "<<lengthlist;
newlist = copylist(oldlist);
printlist(oldlist);
printlist(newlist);
return 0;
} |
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 算法理论与分析 』 → 随机跳跃表如何复制？
(订阅本版)
2006/10/13 22:54:00
新浪微博
