/*******************WZASUST20161：先int实例后模板化2：复制不能改变原串的数据及结构3：随机指针的正确性思考：除了追加新结点后分离新旧链表；还有一复杂度高的算法，就是记录下每一个结点，随机指针指向的结点在整个链中的排序（队列实现）建立新链表后，根据队列记录，连接随机指针；不能记录值，仅能实现一些特殊的，如无重复段的链；*******************/#include<map>#include<queue>#include"wz.h"structComplexNode{intvalue;ComplexNode*pNext;ComplexNode*pSibling;};structmyNode{intvalue;int*ptr;myNode*next;};ComplexNode*Clone(ComplexNode*pHead){if(pHead==NULL)returnNULL;map<ComplexNode*,ComplexNode*>pointMap;ComplexNode*newHead,*tail;newHead=newComplexNode;newHead->value=pHead->value;newHead->pNext=NULL;newHead->pSibling=NULL;pointMap[pHead]=newHead;tail=newHead;ComplexNode*p=pHead->pNext;while(p!=NULL){ComplexNode*newNode=newComplexNode;newNode->value=p->value;newNode->pNext=NULL;newNode->pSibling=NULL;tail->pNext=newNode;tail=newNode;pointMap[p]=newNode;p=p->pNext;}p=pHead;tail=newHead;while(p!=NULL){if(p->pSibling!=NULL){tail->pSibling=pointMap.find(p->pSibling)->second;}p=p->pNext;tail=tail->pNext;}returnnewHead;}voiddeleteList(ComplexNode*pHead){while(pHead!=NULL){ComplexNode*pNext=pHead->pNext;deletepHead;pHead=pNext;}}voidprint(ComplexNode*pHead){ComplexNode*p=pHead;while(p){cout<<p->value<<"";p=p->pNext;}cout<<endl;}voidprint(myNode*pHead){myNode*p=pHead;while(p){cout<<p->value<<"";p=p->next;}cout<<endl;}ComplexNode*myClone2(ComplexNode*pHead){//intk=4;ComplexNode*p=newComplexNode;ComplexNode*q=NULL;ComplexNode*newhead=NULL;if(pHead){p=pHead;while(p->pNext){ComplexNode*add=newComplexNode;add->value=p->value;add->pSibling=NULL;add->pNext=p->pNext;p->pNext=add;p=p->pNext->pNext;}ComplexNode*add=newComplexNode;add->value=p->value;add->pSibling=NULL;add->pNext=p->pNext;p->pNext=add;p=pHead;q=p->pNext;newhead=q;cout<<q->value<<endl;//bugrandpointor:pSibling//while(p->pNext)while(k--){q->pSibling=p->pSibling->pNext;//p->pNext=q->pNext;//q->pNext=p->pNext;//p=p->pNext;//q=q->pNext;}//while(p->pNext)//{//q->pSibling=p->pSibling->pNext;//p->pNext=p->pNext->pNext;//q->pNext=q->pNext->pNext;//p=p->pNext->pNext;//q=q->pNext->pNext;//}/**madenewlink:q***///newhead=q;//while(q->pNext)//{//q->pNext=q->pNext->pNext;//q=q->pNext;//}/*****newlinkout*****///p=pHead;q=newhead;while(q->pNext){p->pNext=q->pNext;p=p->pNext;q->pNext=p->pNext;q=q->pNext;}//deletep->pNext;//canontdothisp->pNext=NULL;//mustdothisoradd4tooldlink//newlinkout//p=pHead;}returnnewhead;}voidt2(){cout<<"t2()"<<endl;ComplexNode*p1=newComplexNode;ComplexNode*p2=newComplexNode;ComplexNode*p3=newComplexNode;ComplexNode*p4=newComplexNode;p1->pNext=p2;p2->pNext=p3;p3->pNext=p4;p4->pNext=NULL;p1->value=1;p2->value=2;p3->value=3;p4->value=4;p1->pSibling=p3;p2->pSibling=p4;p3->pSibling=NULL;p4->pSibling=NULL;print(p1);ComplexNode*newHead=myClone2(p1);cout<<"oldlink:"<<endl;print(p1);cout<<"newlink:"<<endl;print(newHead);//cout<<(newHead->pSibling)->value<<endl;//3deleteList(newHead);deleteList(p1);}intmain(){t2();return0;}//随机处的bug没处理

下一篇