什么是复杂链表？
复杂链表指的是一个链表有若干个结点，每个结点有一个数据域用于存放数据，还有两个指针域，其中一个指向下一个节点，还有一个随机指向当前复杂链表中的任意一个节点或者是一个空结点。今天我们要实现的就是对这样一个复杂链表复制产生一个新的复杂链表。
复杂链表的数据结构如下：
|
1
2
3
4
5
6
7
8
9
10
11
|
typedef int DataType; //数据域的类型
//复杂链表的数据结构
typedef struct ComplexNode
{
DataType _data ; // 数据
struct ComplexNode * _next; // 指向下个节点的指针
struct ComplexNode * _random; // 指向随机节点（可以是链表中的任意节点 or 空）
}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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#ifndef __COMPLEX__NODE__H__
#define __COMPLEX__NODE__H__
//包含头文件
#include <stdio.h>
#include<stdlib.h>
#include <assert.h>
typedef int DataType; //数据域的类型
//复杂链表的数据结构
typedef struct ComplexNode
{
DataType _data ; // 数据
struct ComplexNode * _next; // 指向下个节点的指针
struct ComplexNode * _random; // 指向随机节点（可以是链表中的任意节点 or 空）
}ComplexNode;
//创建一个复杂链表的结点
ComplexNode * BuyComplexNode(DataType x);
//打印复杂的单链表
void Display(const ComplexNode * cplist);
//复杂链表的复制
ComplexNode * CopyComplexNode(ComplexNode * cplist);
#endif//__COMPLEX__NODE__H__
|
具体功能实现complexnode.c
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
|
#include "complexnode.h"
//创建一个复杂链表的结点
ComplexNode * BuyComplexNode(DataType x)
{
ComplexNode *cnode = (ComplexNode *)malloc(sizeof(ComplexNode));
if(cnode == NULL)//创建失败
{
perror("BuyComplexNode()::malloc");
return NULL;
}
//创建成功
cnode->_data = x;
cnode->_next = NULL;
cnode->_random = NULL;
return cnode;
}
//打印复杂的单链表
void Display(const ComplexNode * cplist)
{
ComplexNode *pnode = cplist;
while (pnode)
{
printf("%d::%d -->",pnode->_data,pnode->_random->_data);
pnode = pnode->_next;
}
printf("over\n");
}
//复杂链表的复制
ComplexNode * CopyComplexNode(ComplexNode * cplist)
{
ComplexNode * pold = NULL;
ComplexNode * pnew = NULL;
ComplexNode * newlist = NULL;//指向新的复杂链表的头结点的指针
pold = cplist;
//创建一条新的复杂链表
while(pold != NULL)
{
ComplexNode * new_node = BuyComplexNode(pold->_data);
if(newlist == NULL)//当新的复杂链表中没有结点时
{
newlist = new_node;
}
else//当新的复杂链表有结点时
{
ComplexNode * node = newlist;
while(node->_next != NULL)//找到最后一个结点
{
node = node->_next;
}
node->_next = new_node;//插入新的结点
}
pold = pold->_next;
}//创建新的复杂链表结束
//合并两条复杂链表
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;
}//合并两条复杂链表结束
//让新创建的那条复杂链表上的所有结点的random指针指向相应的结点
pold = cplist;
pnew = newlist;
while (pnew)
{
pnew->_random = pold->_random->_next;
pold = pnew->_next;
if(pold == NULL)//这是pnew的_next指针已经指向空
{
break;
}
pnew = pold->_next;
}//结束
//分离合并后的复杂链表
pold = cplist;
pnew = newlist;
while (pold)
{
ComplexNode * curold = NULL;
ComplexNode * curnew = NULL;
if(pnew->_next == NULL)//已经分离完成
{
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;
}//分离合并的复杂链表结束
return newlist;
}
测试代码test.c：
#include "complexnode.h"
//
//复杂链表的复制。?个链表的每个节点，有?个指向next指针指向下?个节
//点，还有?个random指针指向这个链表中的?个随机节点或者NULL，现在要
//求实现复制这个链表，返回复制后的新链表。
//ps: 复杂链表的结构
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;
}
|
程序的运行结果如下图：
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。