C語言之複雜鏈表的複製

什麼是複雜鏈表？

複雜鏈表指的是一個鏈表有若干個結點，每個結點有一個數據域用於存放數據，還有兩個指針域，其中一個指向下一個節點，還有一個隨機指向當前複雜鏈表中的任意一個節點或者是一個空結點。今天我們要實現的就是對這樣一個複雜鏈表複製產生一個新的複雜鏈表。

複雜鏈表的數據結構如下：

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
10
11 #include
12
13 #include
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
");
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->_next;
114
115
116
117 }//創建新的複雜鏈表結束
118
119
120
121 //合并兩條複雜鏈表
122
123 pold = cplist;
124
125 pnew = newlist;
126
127 while (pold)
128
129 {
130
131 ComplexNode * curold = NULL;
132
133 ComplexNode * curnew = NULL;
134
135 curold = pold->_next;
136
137 curnew = pnew->_next;
138
139 if(pold->_next == NULL)
140
141 {
142
143 pold->_next = pnew;
144
145 pold = curold;
146
147 pnew = curnew;
148
149 break;
150
151 }
152
153 pold->_next = pnew;
154
155 pnew->_next = curold;
156
157 pold = curold;
158
159 pnew = curnew;
160
161 }//合并兩條複雜鏈表結束
162
163
164
165 //讓新創建的那條複雜鏈表上的所有結點的random指針指向相應的結點
166
167 pold = cplist;
168
169 pnew = newlist;
170
171 while (pnew)
172
173 {
174
175 pnew->_random = pold->_random->_next;
176
177 pold = pnew->_next;
178
179 if(pold == NULL)//這是pnew的_next指針已經指向空
180
181 {
182
183 break;
184
185 }
186
187 pnew = pold->_next;
188
189 }//結束
190
191
192
193 //分離合并後的複雜鏈表
194
195 pold = cplist;
196
197 pnew = newlist;
198
199 while (pold)
200
201 {
202
203 ComplexNode * curold = NULL;
204
205 ComplexNode * curnew = NULL;
206
207 if(pnew->_next == NULL)//已經分離完成
208
209 {
210
211 pold->_next = NULL;
212
213 pnew->_next = NULL;
214
215 break;
216
217
218
219 }
220
221 curold = pold->_next->_next;
222
223 curnew = pnew->_next->_next;
224
225
226
227 pold->_next = curold;
228
229 pnew->_next = curnew;
230
231 pold = curold;
232
233 pnew = curnew;
234
235 }//分離合并的複雜鏈表結束
236
237
238
239 return newlist;
240
241 }

測試代碼test.c：

1 #include "complexnode.h"
2
3 //
4
5 //複雜鏈表的複製。?個鏈表的每個節點，有?個指向next指針指向下?個節
6
7 //點，還有?個random指針指向這個鏈表中的?個隨機節點或者NULL，現在要
8
9 //求實現複製這個鏈表，返回複製後的新鏈表。
10
11 //ps: 複雜鏈表的結構
12
13
14
15
16
17
18
19 void test
20
21 {
22
23 ComplexNode * cplist;
24
25 ComplexNode * copylist;
26
27 ComplexNode * node1;
28
29 ComplexNode * node2;
30
31 ComplexNode * node3;
32
33 ComplexNode * node4;
34
35 cplist = BuyComplexNode(1);
36
37 node1 = BuyComplexNode(2);
38
39 node2 = BuyComplexNode(3);
40
41 node3 = BuyComplexNode(4);
42
43 node4 = BuyComplexNode(5);
44
45 cplist->_next = node1;
46
47 node1->_next = node2;
48
49 node2->_next = node3;
50
51 node3->_next = node4;
52
53 cplist->_random = node3;
54
55 node1->_random = node4;
56
57 node2->_random = cplist;
58
59 node3->_random = node1;
60
61 node4->_random = node2;
62
63 Display(cplist);
64
65 copylist = CopyComplexNode(cplist);
66
67 Display(copylist);
68
69
70
71 }
72
73 int main
74
75 {
76
77 test;
78
79 return 0;
80
81 }

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！