您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
/******************* WZ ASUST 2016 1:先int实例 后模板化 2: 复制不能改变原串的数据及结构 3: 随机指针的正确性 思考:除了追加新结点后分离新旧链表; 还有一复杂度高的算法,就是记录下每一个结点,随机指针指向的结点在整个链中的排序(队列实现)建立新链表后,根据队列记录,连接随机指针; 不能记录值,仅能实现一些特殊的,如无重复段的链; *******************/ #include <map> #include<queue> #include"wz.h" struct ComplexNode { int value; ComplexNode* pNext; ComplexNode* pSibling; }; struct myNode { int value; int* ptr; myNode *next; }; ComplexNode* Clone(ComplexNode* pHead) { if(pHead == NULL) return NULL; map<ComplexNode*, ComplexNode*> pointMap; ComplexNode* newHead,*tail; newHead = new ComplexNode; newHead->value = pHead->value; newHead->pNext = NULL; newHead->pSibling = NULL; pointMap[pHead] = newHead; tail = newHead; ComplexNode *p = pHead->pNext; while(p != NULL) { ComplexNode* newNode = new ComplexNode; 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; } return newHead; } void deleteList(ComplexNode* pHead) { while(pHead!=NULL) { ComplexNode* pNext = pHead->pNext; delete pHead; pHead = pNext; } } void print(ComplexNode* pHead) { ComplexNode* p=pHead; while(p) { cout<<p->value<<" "; p=p->pNext; } cout<<endl; } void print( myNode* pHead) { myNode* p=pHead; while(p) { cout<<p->value<<" "; p=p->next; } cout<<endl; } ComplexNode* myClone2(ComplexNode* pHead) { //int k=4; ComplexNode*p= new ComplexNode; ComplexNode*q= NULL; ComplexNode*newhead= NULL; if(pHead) { p=pHead; while(p->pNext) { ComplexNode*add= new ComplexNode; add->value=p->value; add->pSibling=NULL;add->pNext=p->pNext; p->pNext=add; p=p->pNext->pNext; } ComplexNode*add= new ComplexNode; 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; // bug rand pointor: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; // } /** made new link:q***/ // newhead=q; // while(q->pNext) //{ // q->pNext=q->pNext->pNext; // q=q->pNext; // } /*****new link out*****/ // p=pHead; q=newhead; while(q->pNext) { p->pNext=q->pNext;p=p->pNext; q->pNext=p->pNext;q=q->pNext; } // delete p->pNext; //can ont do this p->pNext=NULL; // must do this or add 4 to old link // new link out // p=pHead; } return newhead; } void t2() { cout<<"t2()"<<endl; ComplexNode* p1 = new ComplexNode; ComplexNode* p2 = new ComplexNode; ComplexNode* p3 = new ComplexNode; ComplexNode* p4 = new ComplexNode; 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<<"old link:"<<endl; print(p1); cout<<"new link:"<<endl; print(newHead); // cout<<(newHead->pSibling)->value<<endl; //3 deleteList(newHead); deleteList(p1); } int main() { t2(); return 0; } // 随机处的bug 没处理
下一篇
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。