什么是复杂链表?
复杂链表指的是一个链表有若干个结点,每个结点有一个数据域用于存放数据,还有两个指针域,其中一个指向下一个节点,还有一个随机指向当前复杂链表中的任意一个节点或者是一个空结点。今天我们要实现的就是对这样一个复杂链表复制产生一个新的复杂链表。
复杂链表的数据结构如下:
1 typedef int DataType; //数据域的类型
2
3 //复杂链表的数据结构
4
5 typedef struct ComplexNode
6
7 {
8
9 DataType _data ; // 数据
10
11 struct ComplexNode * _next; // 指向下个节点的指针
12
13 struct ComplexNode * _random; // 指向随机节点(可以是链表中的任意节点 or 空)
14
15 }ComplexNode;
上图就是一个复杂链表的例子,那么我们应该如何实现复杂链表的复制呢?
1、首先我们应该根据已有的复杂链表创建一条新的复杂链表,但是这个新的复杂链表的所有的结点的random指针都指向空,这样是很好实现的,相当于我们创建了一条简单的单链表(newlist),我们要复制的链表不妨称之为oldlist。
2、接下来我们应该把新创建的这条复杂链表(newlist)与已有的复杂链表(oldlist)合并成如下的形式:
在这种情况下我们已经把两条复杂链表合并成了一条链表(称之为linklist),通过对这条链表(linklist)的观察,我们可以发现合并的链表(linklist)中属于newlist的结点pnew的上一个结点pold(属于oldlist的结点)的random指针所指向的结点的next指针就应该是pnew结点的randow指针所指向的结点。
这样我们让pold和pnew指针一直往后走最后就可以实现对所有属于新创建的复杂链表(newlist)的random指针指向相应的结点的操作。构成的复杂链表如下图
在完成以上的步骤之后我们所要做的工作就很简单了,我们只要把这一条链表linklist分开成我们的newlist链表和oldlist链表就可以了。
这样我们就完美的完成了复杂链表的复制工作下面就是具体实现的代码:
头文件complexnode.h:
1 #ifndef __COMPLEX__NODE__H__
2
3 #define __COMPLEX__NODE__H__
4
5
6
7 //包含头文件
8
9 #include <stdio.h>
10
11 #include<stdlib.h>
12
13 #include <assert.h>
14
15
16
17
18
19 typedef int DataType; //数据域的类型
20
21
22
23 //复杂链表的数据结构
24
25 typedef struct ComplexNode
26
27 {
28
29 DataType _data ; // 数据
30
31 struct ComplexNode * _next; // 指向下个节点的指针
32
33 struct ComplexNode * _random; // 指向随机节点(可以是链表中的任意节点 or 空)
34
35 }ComplexNode;
36
37
38
39 //创建一个复杂链表的结点
40
41 ComplexNode * BuyComplexNode(DataType x);
42
43
44
45 //打印复杂的单链表
46
47 void Display(const ComplexNode * cplist);
48
49
50
51 //复杂链表的复制
52
53 ComplexNode * CopyComplexNode(ComplexNode * cplist);
54
55
56
57 #endif//__COMPLEX__NODE__H__
具体功能实现complexnode.c
1 #include "complexnode.h"
2
3
4
5 //创建一个复杂链表的结点
6
7 ComplexNode * BuyComplexNode(DataType x)
8
9 {
10
11 ComplexNode *cnode = (ComplexNode *)malloc(sizeof(ComplexNode));
12
13 if(cnode == NULL)//创建失败
14
15 {
16
17 perror("BuyComplexNode()::malloc");
18
19 return NULL;
20
21 }
22
23 //创建成功
24
25 cnode->_data = x;
26
27 cnode->_next = NULL;
28
29 cnode->_random = NULL;
30
31 return cnode;
32
33 }
34
35
36
37 //打印复杂的单链表
38
39 void Display(const ComplexNode * cplist)
40
41 {
42
43 ComplexNode *pnode = cplist;
44
45 while (pnode)
46
47 {
48
49 printf("%d::%d -->",pnode->_data,pnode->_random->_data);
50
51 pnode = pnode->_next;
52
53 }
54
55 printf("over\n");
56
57
58
59 }
60
61
62
63 //复杂链表的复制
64
65 ComplexNode * CopyComplexNode(ComplexNode * cplist)
66
67 {
68
69
70
71 ComplexNode * pold = NULL;
72
73 ComplexNode * pnew = NULL;
74
75 ComplexNode * newlist = NULL;//指向新的复杂链表的头结点的指针
76
77 pold = cplist;
78
79 //创建一条新的复杂链表
80
81 while(pold != NULL)
82
83 {
84
85 ComplexNode * new_node = BuyComplexNode(pold->_data);
86
87 if(newlist == NULL)//当新的复杂链表中没有结点时
88
89 {
90
91 newlist = new_node;
92
93 }
94
95 else//当新的复杂链表有结点时
96
97 {
98
99 ComplexNode * node = newlist;
100
101 while(node->_next != NULL)//找到最后一个结点
102
103 {
104
105 node = node->_next;
106
107 }
108
109 node->_next = new_node;//插入新的结点
110
111 }
112
113 pold = pold-&g