题目
解决代码及点评
/*复杂链表的拷贝，现在有一个复杂链表，完成一个clone函数拷贝一个链表复杂链表是指struct Node{struct Node* _next;struct Node* _sibling; // sibling指向链表中任意一个节点，或者为NULLint _data;};这道题困难之处在于复制sibling节点，因为按照普通思维，复制好普通链表之后恢复sibling节点指向非常困难解决办法：就地复制，再拆分比如 原始链表是 a->b->c->d 先就地复制 a->a1->b->b1->c->c1->d->d1就地复制后，sibling指针也很好确定，就是原来那个节点的next，放置好sibling之后，再进行拆分即可
*/#include <stdio.h>
#include <stdlib.h>
#include "iostream"
using namespace std;typedef struct link
{char id;struct link *pnext;struct link *pSibling;} *plink,link;// 创建链表
plink creat()
{plink la,lb,lc,ld,le;la = (plink)malloc(sizeof(link));lb = (plink)malloc(sizeof(link));lc = (plink)malloc(sizeof(link));ld = (plink)malloc(sizeof(link));le = (plink)malloc(sizeof(link));la->pnext=lb;la->pSibling=lc;la->id='a';lb->pnext=lc;lb->pSibling=ld;lb->id='b';lc->pnext=ld;lc->pSibling=NULL;lc->id='c';ld->pnext=le;ld->pSibling=la;ld->id='d';le->pnext=NULL;le->pSibling=NULL;le->id='e';return la;}plink copy(plink l)
{plink head2=l;// 就地复制while(head2!=NULL){plink temp;temp = (plink)malloc(sizeof(link));temp->id=head2->id;temp->pnext=head2->pnext;head2->pnext=temp;head2=temp->pnext;}head2=l;plink headt=l->pnext;// 设置siblingwhile(head2->pnext->pnext!=NULL){if (head2->pSibling!=NULL){headt->pSibling=head2->pSibling->pnext;}headt=headt->pnext->pnext;head2=head2->pnext->pnext;}// 拆分链表headt=l->pnext;plink l2=headt;cout<<headt->id<<"->";while(headt->pnext->pnext->pnext!=NULL){headt->pnext=headt->pnext->pnext;headt=headt->pnext;cout<<headt->id<<"->";} cout<<headt->pnext->id<<"->";return l2;}// 主函数
int main()
{plink l;l = creat();plink l2;l2=copy(l);system("pause");return 0;
}
代码下载及其运行
代码下载地址：http://download.csdn.net/detail/yincheng01/6704519
解压密码：c.itcast.cn
下载代码并解压后，用VC2013打开interview.sln，并设置对应的启动项目后，点击运行即可，具体步骤如下：
1）设置启动项目：右键点击解决方案，在弹出菜单中选择“设置启动项目”
2）在下拉框中选择相应项目，项目名和博客编号一致
3）点击“本地Windows调试器”运行
程序运行结果
