/******************* WZ ASUST 2016 1:先int实例 后模板化 2: 复制不能改变原串的数据及结构 3: 随机指针的正确性 思考:除了追加新结点后分离新旧链表; 还有一复杂度高的算法,就是记录下每一个结点,随机指针指向的结点在整个链中的排序(队列实现)建立新链表后,根据队列记录,连接随机指针; 不能记录值,仅能实现一些特殊的,如无重复段的链; *******************/ #include #include #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 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<value<<" "; p=p->pNext; } cout<value<<" "; p=p->next; } cout<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<value<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()"<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:"<pSibling)->value< 下一篇为铁西等地区用户提供了全套网页设计制作服务,及铁西网站建设行业解决方案。主营业务为网站建设、成都做网站、铁西网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远! 分享题目:复杂单链表的实现 本文路径:http://myzitong.com/article/ghossd.html
下一篇
为铁西等地区用户提供了全套网页设计制作服务,及铁西网站建设行业解决方案。主营业务为网站建设、成都做网站、铁西网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!