复杂链表的复制

发表于

标题：复杂链表的复制

复杂链表：在复杂链表中，每个节点除了有一个next指向下一节点外，还有一个random指向任意节点或者NULL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 #ifndef __LINKLIST_H__
 #define __LINKLIST_H__
 #include <stdio.h>
 #include <stdlib.h>
 #include <assert.h>
//定义元素类型
typedef int DataType;
//复杂链表的定义
typedef struct ComplexNode
{
	DataType data;
	struct ComplexNode* next;     //存放下一个节点
	struct ComplexNode* random;  //存放任意节点
}ComplexNode;
//申请节点
ComplexNode *BuyComplexNode(DataType x);
//复杂链表的复制
ComplexNode *CopyComplexList(ComplexNode* plist);
//复杂链表的打印
void PrintComplexList(ComplexNode* plist);
 #endif __LINKLIST_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
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
 #include "Linklist.h"
//申请节点
ComplexNode* BuyComplexNode(DataType d)
{
	ComplexNode* node = (ComplexNode *)malloc(sizeof(ComplexNode));
	if (node == NULL){
		perror("Buy Node");
		exit(FILENAME_MAX);
	}
	node->data = d;
	node->next = NULL;
	node->random = NULL;
	return node;
}
//复杂链表的打印
void PrintComplexList(ComplexNode* plist)
{
	assert(plist);
	while (plist)
	{
		printf("%d : ", plist->data);
		if (plist->random != NULL){
			printf("(%d)-->", plist->random->data);
		}
		else{
			printf("(NULL)-->");
		}
		plist = plist->next;
	}
	printf("Over !\n");
}
//复杂链表的复制
ComplexNode* CopyComplexList(ComplexNode* plist)
{
	ComplexNode* cur = NULL;
	ComplexNode* tmp = NULL;
	ComplexNode* head = NULL;
	assert(plist);
	cur = plist;
	//将链表中每个节点复制，并将复制的节点挂在该节点后边
	while (cur != NULL){
		tmp = BuyComplexNode(cur->data);
		tmp->next = cur->next;
		cur->next = tmp;
		cur = tmp->next;
	}
	cur = plist;
	tmp = cur->next;
	//将复制节点的random指针指向它被复制节点random的next节点
	while (cur != NULL){
		if (cur->random != NULL){
			tmp->random = cur->random->next;
		}
		cur = tmp->next;
        //若cur为空循环结束
		if (cur == NULL){
			break;
		}
		tmp=cur->next;
	}
	cur = plist;
	tmp = cur->next;
	head = tmp;
	//将复制的节点从链表中分离出来
	while (cur != NULL)
	{
		cur->next = tmp->next;
		cur = cur->next;
		//当cur为空,链表分离结束，跳出循环
		if (cur == NULL){
			break;
		}
		tmp->next = cur->next;
		tmp = tmp->next;
	}
	//返回新复杂链表的头结点
	return head;
}

test.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
 #include "Linklist.h"
void testCopyComplexList()
{
	ComplexNode * cur;
	ComplexNode * plist;
	ComplexNode * p1 = BuyComplexNode(5);
	ComplexNode * p2 = BuyComplexNode(4);
	ComplexNode * p3 = BuyComplexNode(3);
	ComplexNode * p4 = BuyComplexNode(2);
	ComplexNode * p5 = BuyComplexNode(1);
	plist = p1;
	p1->next = p2;
	p2->next = p3;
	p3->next = p4;
	p4->next = p5;
	p1->random = p3;
	p2->random = p5;
	p3->random = NULL;
	p4->random = p1;
	p5->random = p2;
	PrintComplexList(plist);
	cur = CopyComplexList(plist);
	PrintComplexList(plist);
}
int main()
{
 testCopyComplexList();
 system("pause");
 return 0;
}

感谢观赏，欢迎留言！