typedef int DataType;  //數(shù)據(jù)域的類型

//復(fù)雜鏈表的數(shù)據(jù)結(jié)構(gòu)

typedef struct ComplexNode

{

DataType _data ;      // 數(shù)據(jù)

struct ComplexNode * _next;   // 指向下個(gè)節(jié)點(diǎn)的指針

struct ComplexNode * _random;  // 指向隨機(jī)節(jié)點(diǎn)（可以是鏈表中的任意節(jié)點(diǎn) or 空）

}ComplexNode;

#ifndef __COMPLEX__NODE__H__
#define __COMPLEX__NODE__H__
 
//包含頭文件
#include <stdio.h>
#include<stdlib.h>
#include <assert.h>
 
 
typedef int DataType;  //數(shù)據(jù)域的類型
 
//復(fù)雜鏈表的數(shù)據(jù)結(jié)構(gòu)
typedef struct ComplexNode
{
DataType _data ;        // 數(shù)據(jù)
struct ComplexNode * _next;    // 指向下個(gè)節(jié)點(diǎn)的指針
struct ComplexNode * _random;  // 指向隨機(jī)節(jié)點(diǎn)（可以是鏈表中的任意節(jié)點(diǎn) or 空）
}ComplexNode;
 
//創(chuàng)建一個(gè)復(fù)雜鏈表的結(jié)點(diǎn)
ComplexNode * BuyComplexNode(DataType x);
 
//打印復(fù)雜的單鏈表
void Display(const ComplexNode * cplist);
 
//復(fù)雜鏈表的復(fù)制
ComplexNode * CopyComplexNode(ComplexNode * cplist);
 
#endif//__COMPLEX__NODE__H__

#include "complexnode.h"

 

//創(chuàng)建一個(gè)復(fù)雜鏈表的結(jié)點(diǎn)

ComplexNode * BuyComplexNode(DataType x)

{

ComplexNode *cnode = (ComplexNode *)malloc(sizeof(ComplexNode));

if(cnode == NULL)//創(chuàng)建失敗

{

perror("BuyComplexNode()::malloc");

return NULL;

}

//創(chuàng)建成功

cnode->_data = x;

cnode->_next = NULL;

cnode->_random = NULL;

return cnode;

}

 

//打印復(fù)雜的單鏈表

void Display(const ComplexNode * cplist)

{

ComplexNode *pnode = cplist;

while (pnode)

{

printf("%d::%d -->",pnode->_data,pnode->_random->_data);

pnode = pnode->_next;

}

printf("over\n");

 

}

 

//復(fù)雜鏈表的復(fù)制

ComplexNode * CopyComplexNode(ComplexNode * cplist)

{

 

ComplexNode * pold = NULL;

ComplexNode * pnew = NULL;

ComplexNode * newlist = NULL;//指向新的復(fù)雜鏈表的頭結(jié)點(diǎn)的指針

pold = cplist;

//創(chuàng)建一條新的復(fù)雜鏈表

while(pold != NULL)

{

ComplexNode * new_node = BuyComplexNode(pold->_data);

if(newlist == NULL)//當(dāng)新的復(fù)雜鏈表中沒有結(jié)點(diǎn)時(shí)

{

newlist = new_node;

}

else//當(dāng)新的復(fù)雜鏈表有結(jié)點(diǎn)時(shí)

{

ComplexNode * node = newlist;

while(node->_next != NULL)//找到最后一個(gè)結(jié)點(diǎn)

{

node = node->_next;

}

node->_next = new_node;//插入新的結(jié)點(diǎn)

}

pold = pold->_next;

 

}//創(chuàng)建新的復(fù)雜鏈表結(jié)束

 

//合并兩條復(fù)雜鏈表

pold = cplist;

pnew = newlist;

while (pold)

{

ComplexNode * curold = NULL;

ComplexNode * curnew = NULL;

curold = pold->_next;

curnew = pnew->_next;

if(pold->_next == NULL)

{

pold->_next = pnew;

pold = curold;

pnew = curnew;

break;

}

pold->_next = pnew;

pnew->_next = curold;

pold = curold;

pnew = curnew;

}//合并兩條復(fù)雜鏈表結(jié)束

 

//讓新創(chuàng)建的那條復(fù)雜鏈表上的所有結(jié)點(diǎn)的random指針指向相應(yīng)的結(jié)點(diǎn)

pold = cplist;

pnew = newlist;

while (pnew)

{

pnew->_random = pold->_random->_next;

pold = pnew->_next;

if(pold == NULL)//這是pnew的_next指針已經(jīng)指向空

{

break;

}

pnew = pold->_next;

}//結(jié)束

 

//分離合并后的復(fù)雜鏈表

pold = cplist;

pnew = newlist;

while (pold)

{

ComplexNode * curold = NULL;

ComplexNode * curnew = NULL;

if(pnew->_next == NULL)//已經(jīng)分離完成

{

pold->_next = NULL;

pnew->_next = NULL;

break;

 

}

curold = pold->_next->_next;

curnew = pnew->_next->_next;

 

pold->_next = curold;

pnew->_next = curnew;

pold = curold;

pnew = curnew;

}//分離合并的復(fù)雜鏈表結(jié)束

 

return newlist;

}

#include "complexnode.h"

//

//復(fù)雜鏈表的復(fù)制。?個(gè)鏈表的每個(gè)節(jié)點(diǎn)，有?個(gè)指向next指針指向下?個(gè)節(jié)

//點(diǎn)，還有?個(gè)random指針指向這個(gè)鏈表中的?個(gè)隨機(jī)節(jié)點(diǎn)或者NULL，現(xiàn)在要

//求實(shí)現(xiàn)復(fù)制這個(gè)鏈表，返回復(fù)制后的新鏈表。

//ps: 復(fù)雜鏈表的結(jié)構(gòu)

 

 

 

void test()

{

ComplexNode * cplist;

ComplexNode * copylist;

ComplexNode * node1;

ComplexNode * node2;

ComplexNode * node3;

ComplexNode * node4;

cplist = BuyComplexNode(1);

node1 = BuyComplexNode(2);

node2 = BuyComplexNode(3);

node3 = BuyComplexNode(4);

node4 = BuyComplexNode(5);

cplist->_next = node1;

node1->_next = node2;

node2->_next = node3;

node3->_next = node4;

cplist->_random = node3;

node1->_random = node4;

node2->_random = cplist;

node3->_random = node1;

node4->_random = node2;

Display(cplist);

copylist = CopyComplexNode(cplist);

Display(copylist);

 

}

int main()

{

test();

return 0;

}