一、实验内容

链表操作
⭐ ⭐ ⭐

二、实验目的

熟悉用C/C++语言进行程序设计的方法。
掌握链表的基本操作：插入、删除、查找等运算

三、实验内容

1用单链表表示集合（集合中无相同元素）
2求两个集合的并、交、差运算

四、实验步骤

1输入第一个集合，建立链表并输出
2输入第二个集合，建立链表并输出
3选择对集合的运算，输出结果

五、注意

1如果输入了重复值，可以自动跳过
2运算做成重复的菜单形式，以便于重复选择

六、解答

求集合（用单链表表示）的并、交和差运算
目的：掌握单链表的应用和有序单链表的二路归并算法。
内容：采用单链表表示集合（假设同一个集合中不存在重复的元素），将其按递增方式排序，构成有序单链表，并求这样的两个集合的并、交和差。

graph TD
A(L) --> B(apple)
A(L) --> C(pear)
C(pear) --> D(banana)
A(L) --> E(orange)

F[分离banana]
B --> F
F --> G(apple)
F --> H(pear)
H(pear) --> I(orange)

思路（并）：同时扫描两个链表，将不相同的元素放在第三个链表中。

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
bool Union(LinkNode* L1, LinkNode* L2, LinkNode*& L3)	//L1、L2、L3为三个单链表的头结点
{
	//如果L1和L2中均没有数据
	if (L1->next == NULL && L2->next == NULL) {
		return false;
	}
	//直到L3申请成功
	while (!L3) {
		L3 = (LinkNode*)malloc(sizeof(LNode));
	}
	LinkNode* p, * q, * r, * s = NULL;
	p = L1->next;		//p为L1的工作指针
	q = L2->next;		//q为L2的工作指针
	r = L3;				//r为L3的尾指针
	//当L1和L2均不为空时
	while (p && q) {
		s = (LinkNode*)malloc(sizeof(LNode));
		//如果申请失败继续申请，直到申请成功，因为malloc可能申请失败
		while (!s) {
			s = (LinkNode*)malloc(sizeof(LNode));
		}
		if (p->data < q->data) {
			s->data = p->data;	//如果此时p指向的data的值小，复制该结点的值
			r->next = s;		//将s接到尾指针后面
			r = r->next;		//尾指针后移
			p = p->next;		//p继续向后扫描L1
		}
		else if (q->data < p->data) {
			s->data =q->data;	//如果此时q指向的data的值小，复制该结点的值
			r->next = s;		//将s接到尾指针后面
			r = r->next;		//尾指针后移
			q = q->next;		//q继续向后扫描L2
		}
		else {
			s->data = p->data;	//如果两个值相等，复制其中一个结点的值
			r->next = s;		//将s接到尾指针后面
			r = r->next;		//尾指针后移
			p = p->next;		//p继续向后扫描L1
			q = q->next;		//q继续向后扫描L2
		}
	}
	//当p不为空时，将剩余结点接到尾指针后面
	while (p) {
		s = (LinkNode*)malloc(sizeof(LNode));
		//如果申请失败继续申请，直到申请成功，因为malloc可能申请失败
		while (!s) {
			s = (LinkNode*)malloc(sizeof(LNode));
		}
		s->data = p->data;	//复制结点的值
		r->next = s;		//将s接到尾指针后面
		r = r->next;		//尾指针后移
		p = p->next;		//p继续向后扫描L1
	}
	//当q不为空时，将剩余结点接到尾指针后面
	while (q) {
		s = (LinkNode*)malloc(sizeof(LNode));
		//如果申请失败继续申请，直到申请成功，因为malloc可能申请失败
		while (!s) {
			s = (LinkNode*)malloc(sizeof(LNode));
		}
		s->data = q->data;	//复制结点的值
		r->next = s;		//将s接到尾指针后面
		r = r->next;		//尾指针后移
		q = q->next;		//q继续向后扫描L2
	}
	r->next = NULL;		//此时将尾指针后面置空，单链表L3建成
	return true;
}

思路（交）：同时扫描两个链表，将相同的元素放在第三个链表中。

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
bool Intersection(LinkNode* L1, LinkNode* L2, LinkNode*& L3)	//L1、L2、L3为三个单链表的头结点
{
	//如果L1和L2中均没有数据
	if (L1->next == NULL && L2->next == NULL) {
		return false;
	}
	//直到L3申请成功
	while (!L3) {
		L3 = (LinkNode*)malloc(sizeof(LNode));
	}
	LinkNode* p, * q, * r, * s = NULL;
	p = L1->next;		//p为L1的工作指针
	q = L2->next;		//q为L2的工作指针
	r = L3;				//r为L3的尾指针
	//当L1和L2均不为空时,只要有一个为空就不会再有交集了
	while (p && q) {
		s = (LinkNode*)malloc(sizeof(LNode));
		//如果申请失败继续申请，直到申请成功，因为malloc可能申请失败
		while (!s) {
			s = (LinkNode*)malloc(sizeof(LNode));
		}
		if (p->data < q->data) {
			p = p->next;		//如果p偏小，继续向后扫描L1
		}
		else if (q->data < p->data) {
			q = q->next;		//如果q偏小，继续向后扫描L2
		}
		else {
			s->data = p->data;	//如果两个值相等，复制其中一个结点的值
			r->next = s;		//将s接到尾指针后面
			r = r->next;		//尾指针后移
			p = p->next;		//p继续向后扫描L1
			q = q->next;		//q继续向后扫描L2
		}
	}
	r->next = NULL;		//此时将尾指针后面置空，单链表L3建成
	return true;
}

思路（差）：同时扫描两个链表，将在表1不在表2的元素放在第三个链表中。

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
bool Difference(LinkNode* L1, LinkNode* L2, LinkNode*& L3)	//L1、L2、L3为三个单链表的头结点
//将L1所指链表与L2所指链表求差，将在L1中不在L2中的数据复制到L3中
{
	//如果L1和L2中均没有数据
	if (L1->next == NULL && L2->next == NULL) {
		return false;
	}
	//直到L3申请成功
	while (!L3) {
		L3 = (LinkNode*)malloc(sizeof(LNode));
	}
	LinkNode* p, * q, * r, * s = NULL;
	p = L1->next;		//p为L1的工作指针
	q = L2->next;		//q为L2的工作指针
	r = L3;				//r为L3的尾指针
	//当L1和L2均不为空时
	while (p&&q) {
		s = (LinkNode*)malloc(sizeof(LNode));
		//如果申请失败继续申请，直到申请成功，因为malloc可能申请失败
		while (!s) {
			s = (LinkNode*)malloc(sizeof(LNode));
		}
		if (p->data < q->data) {
			s->data = p->data;	//如果此时p指向的data的值小，复制该结点的值
			r->next = s;		//将s接到尾指针后面
			r = r->next;		//尾指针后移
			p = p->next;		//p继续向后扫描L1
		}
		else if (q->data < p->data) {
			q = q->next;		//q继续向后扫描L2
		}
		//如果两个值相等，跳过该结点
		else {
			p = p->next;		//p继续向后扫描L1
			q = q->next;		//q继续向后扫描L2
		}
	}
	//当p不为空时，将L1剩余结点接到尾指针后面
	while (p) {
		s = (LinkNode*)malloc(sizeof(LNode));
		//如果申请失败继续申请，直到申请成功，因为malloc可能申请失败
		while (!s) {
			s = (LinkNode*)malloc(sizeof(LNode));
		}
		s->data = p->data;	//复制结点的值
		r->next = s;		//将s接到尾指针后面
		r = r->next;		//尾指针后移
		p = p->next;		//p继续向后扫描L1
	}
	r->next = NULL;		//此时将尾指针后面置空，单链表L3建成
	return true;
}

与主函数相结合

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
224
225
226
227
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LinkNode;

bool Union(LinkNode* L1, LinkNode* L2, LinkNode*& L3);			//L1、L2、L3为三个单链表的头结点
bool Intersection(LinkNode* L1, LinkNode* L2, LinkNode*& L3);	//L1、L2、L3为三个单链表的头结点
bool Difference(LinkNode* L1, LinkNode* L2, LinkNode*& L3);		//L1、L2、L3为三个单链表的头结点
bool InitList(LinkNode*& L);		//链表产生
bool DispList(LinkNode* L);			//链表输出

int main(int argc, const char* argv[])
{
	LinkNode* L1 = NULL, * L2 = NULL, * L3 = NULL, * L4 = NULL, * L5 = NULL;
	bool flag = false;
	InitList(L1);
	InitList(L2);
	flag = Union(L1, L2, L3);
	cout << "求并集：\n";
	flag = DispList(L3);
	flag = Intersection(L1, L2, L4);
	cout << "求交集：\n";
	flag = DispList(L4);
	flag = Difference(L1, L2, L5);
	cout << "求差集：\n";
	flag = DispList(L5);
	return 0;
}

bool InitList(LinkNode*& L)		//建立单链表
{
	while (!L) {
		L = (LinkNode*)malloc(sizeof(LNode));
	}
	L->next = NULL;
	int i, n;
	LinkNode* p = NULL, * q = NULL;
	q = L;
	printf("请输入数据规模：\n");
	scanf("%d", &n);
	printf("请输入数据：\n");
	for (i = 0; i < n; i++) {
		while (!p) {
			p = (LinkNode*)malloc(sizeof(LNode));
		}
		scanf("%d", &p->data);
		q->next = p;
		q = p;
		p = q->next = NULL;
	}
	return true;
}
bool DispList(LinkNode* L)		//输出单链表
{
	LinkNode* p = L->next;
	while (p) {
		printf("\t%d", p->data);
		p = p->next;
	}
	cout << "\n";
	return true;
}
bool Union(LinkNode* L1, LinkNode* L2, LinkNode*& L3)	//L1、L2、L3为三个单链表的头结点
{
	//如果L1和L2中均没有数据
	if (L1->next == NULL && L2->next == NULL) {
		return false;
	}
	//直到L3申请成功
	while (!L3) {
		L3 = (LinkNode*)malloc(sizeof(LNode));
	}
	LinkNode* p, * q, * r, * s = NULL;
	p = L1->next;		//p为L1的工作指针
	q = L2->next;		//q为L2的工作指针
	r = L3;				//r为L3的尾指针
	//当L1和L2均不为空时
	while (p && q) {
		s = (LinkNode*)malloc(sizeof(LNode));
		//如果申请失败继续申请，直到申请成功，因为malloc可能申请失败
		while (!s) {
			s = (LinkNode*)malloc(sizeof(LNode));
		}
		if (p->data < q->data) {
			s->data = p->data;	//如果此时p指向的data的值小，复制该结点的值
			r->next = s;		//将s接到尾指针后面
			r = r->next;		//尾指针后移
			p = p->next;		//p继续向后扫描L1
		}
		else if (q->data < p->data) {
			s->data =q->data;	//如果此时q指向的data的值小，复制该结点的值
			r->next = s;		//将s接到尾指针后面
			r = r->next;		//尾指针后移
			q = q->next;		//q继续向后扫描L2
		}
		else {
			s->data = p->data;	//如果两个值相等，复制其中一个结点的值
			r->next = s;		//将s接到尾指针后面
			r = r->next;		//尾指针后移
			p = p->next;		//p继续向后扫描L1
			q = q->next;		//q继续向后扫描L2
		}
	}
	//当p不为空时，将剩余结点接到尾指针后面
	while (p) {
		s = (LinkNode*)malloc(sizeof(LNode));
		//如果申请失败继续申请，直到申请成功，因为malloc可能申请失败
		while (!s) {
			s = (LinkNode*)malloc(sizeof(LNode));
		}
		s->data = p->data;	//复制结点的值
		r->next = s;		//将s接到尾指针后面
		r = r->next;		//尾指针后移
		p = p->next;		//p继续向后扫描L1
	}
	//当q不为空时，将剩余结点接到尾指针后面
	while (q) {
		s = (LinkNode*)malloc(sizeof(LNode));
		//如果申请失败继续申请，直到申请成功，因为malloc可能申请失败
		while (!s) {
			s = (LinkNode*)malloc(sizeof(LNode));
		}
		s->data = q->data;	//复制结点的值
		r->next = s;		//将s接到尾指针后面
		r = r->next;		//尾指针后移
		q = q->next;		//q继续向后扫描L2
	}
	r->next = NULL;		//此时将尾指针后面置空，单链表L3建成
	return true;
}
bool Intersection(LinkNode* L1, LinkNode* L2, LinkNode*& L3)	//L1、L2、L3为三个单链表的头结点
{
	//如果L1和L2中均没有数据
	if (L1->next == NULL && L2->next == NULL) {
		return false;
	}
	//直到L3申请成功
	while (!L3) {
		L3 = (LinkNode*)malloc(sizeof(LNode));
	}
	LinkNode* p, * q, * r, * s = NULL;
	p = L1->next;		//p为L1的工作指针
	q = L2->next;		//q为L2的工作指针
	r = L3;				//r为L3的尾指针
	//当L1和L2均不为空时,只要有一个为空就不会再有交集了
	while (p && q) {
		s = (LinkNode*)malloc(sizeof(LNode));
		//如果申请失败继续申请，直到申请成功，因为malloc可能申请失败
		while (!s) {
			s = (LinkNode*)malloc(sizeof(LNode));
		}
		if (p->data < q->data) {
			p = p->next;		//如果p偏小，继续向后扫描L1
		}
		else if (q->data < p->data) {
			q = q->next;		//如果q偏小，继续向后扫描L2
		}
		else {
			s->data = p->data;	//如果两个值相等，复制其中一个结点的值
			r->next = s;		//将s接到尾指针后面
			r = r->next;		//尾指针后移
			p = p->next;		//p继续向后扫描L1
			q = q->next;		//q继续向后扫描L2
		}
	}
	r->next = NULL;		//此时将尾指针后面置空，单链表L3建成
	return true;
}
bool Difference(LinkNode* L1, LinkNode* L2, LinkNode*& L3)	//L1、L2、L3为三个单链表的头结点
//将L1所指链表与L2所指链表求差，将在L1中不在L2中的数据复制到L3中
{
	//如果L1和L2中均没有数据
	if (L1->next == NULL && L2->next == NULL) {
		return false;
	}
	//直到L3申请成功
	while (!L3) {
		L3 = (LinkNode*)malloc(sizeof(LNode));
	}
	LinkNode* p, * q, * r, * s = NULL;
	p = L1->next;		//p为L1的工作指针
	q = L2->next;		//q为L2的工作指针
	r = L3;				//r为L3的尾指针
	//当L1和L2均不为空时
	while (p&&q) {
		s = (LinkNode*)malloc(sizeof(LNode));
		//如果申请失败继续申请，直到申请成功，因为malloc可能申请失败
		while (!s) {
			s = (LinkNode*)malloc(sizeof(LNode));
		}
		if (p->data < q->data) {
			s->data = p->data;	//如果此时p指向的data的值小，复制该结点的值
			r->next = s;		//将s接到尾指针后面
			r = r->next;		//尾指针后移
			p = p->next;		//p继续向后扫描L1
		}
		else if (q->data < p->data) {
			q = q->next;		//q继续向后扫描L2
		}
		//如果两个值相等，跳过该结点
		else {
			p = p->next;		//p继续向后扫描L1
			q = q->next;		//q继续向后扫描L2
		}
	}
	//当p不为空时，将L1剩余结点接到尾指针后面
	while (p) {
		s = (LinkNode*)malloc(sizeof(LNode));
		//如果申请失败继续申请，直到申请成功，因为malloc可能申请失败
		while (!s) {
			s = (LinkNode*)malloc(sizeof(LNode));
		}
		s->data = p->data;	//复制结点的值
		r->next = s;		//将s接到尾指针后面
		r = r->next;		//尾指针后移
		p = p->next;		//p继续向后扫描L1
	}
	r->next = NULL;		//此时将尾指针后面置空，单链表L3建成
	return true;
}