整数集合用单链表实现存储，设集合中元素互不相同，实现如下操作：（30分） （1） 初始化集合 （2） 按指定位置插入一个数到集合 （3） 按值删除集合中的元素 （4） 按值在集合中进行查找 （5） 清空集合 （6） 求两个集合的交集 （7） 求两个集合的并集 （8） 求两个集合的差集 （9） 输出集合

1. 初始化集合

定义一个结构体Node，用于存储每个元素和指向下一个元素的指针。定义一个链表头指针head，初始为NULL，表示链表为空。

struct Node {
int data;
Node* next;
};

Node* head = NULL;

2. 按指定位置插入一个数到集合

先判断要插入的位置是否合法，即是否在链表长度范围内。然后遍历链表，找到要插入位置的前一个节点，将要插入的节点插入到该节点之后。

void insert(int pos, int value) {
if (pos < 1 || pos > size() + 1) {
cout << "Invalid position" << endl;
return;
}
Node* newNode = new Node;
newNode->data = value;
newNode->next = NULL;
if (pos == 1) {
newNode->next = head;
head = newNode;
}
else {
Node* pre = head;
for (int i = 1; i < pos - 1; i++) {
pre = pre->next;
}
newNode->next = pre->next;
pre->next = newNode;
}
}

3. 按值删除集合中的元素

先判断链表是否为空。然后遍历链表，找到要删除的节点的前一个节点，将该节点从链表中删除并释放内存。

void remove(int value) {
if (head == NULL) {
cout << "The set is empty" << endl;
return;
}
Node* pre = NULL;
Node* cur = head;
while (cur != NULL && cur->data != value) {
pre = cur;
cur = cur->next;
}
if (cur == NULL) {
cout << "The value is not in the set" << endl;
return;
}
if (pre == NULL) {
head = cur->next;
}
else {
pre->next = cur->next;
}
delete cur;
}

4. 按值在集合中进行查找

遍历链表，找到第一个值为value的节点，返回该节点的位置。

int find(int value) {
Node* cur = head;
int pos = 1;
while (cur != NULL && cur->data != value) {
cur = cur->next;
pos++;
}
if (cur == NULL) {
return -1;
}
else {
return pos;
}
}

5. 清空集合

遍历链表，释放每个节点的内存，将链表头指针置为NULL。

void clear() {
Node* cur = head;
while (cur != NULL) {
Node* temp = cur;
cur = cur->next;
delete temp;
}
head = NULL;
}

6. 求两个集合的交集

先新建一个空集合，遍历第一个集合，对于每个元素，在第二个集合中查找是否存在，如果存在则插入到新集合中。

Node* intersect(Node* set1, Node* set2) {
Node* newSet = NULL;
Node* cur1 = set1;
while (cur1 != NULL) {
if (findInSet(cur1->data, set2) != -1) {
insertToSet(cur1->data, newSet);
}
cur1 = cur1->next;
}
return newSet;
}

7. 求两个集合的并集

先新建一个空集合，遍历两个集合，将所有元素插入到新集合中。插入时需要判断新集合中是否已经存在该元素。

Node* unionSet(Node* set1, Node* set2) {
Node* newSet = NULL;
Node* cur1 = set1;
while (cur1 != NULL) {
insertToSet(cur1->data, newSet);
cur1 = cur1->next;
}
Node* cur2 = set2;
while (cur2 != NULL) {
if (findInSet(cur2->data, newSet) == -1) {
insertToSet(cur2->data, newSet);
}
cur2 = cur2->next;
}
return newSet;
}

8. 求两个集合的差集

先新建一个空集合，遍历第一个集合，对于每个元素，在第二个集合中查找是否存在，如果不存在则插入到新集合中。

Node* difference(Node* set1, Node* set2) {
Node* newSet = NULL;
Node* cur1 = set1;
while (cur1 != NULL) {
if (findInSet(cur1->data, set2) == -1) {
insertToSet(cur1->data, newSet);
}
cur1 = cur1->next;
}
return newSet;
}

9. 输出集合

遍历链表，依次输出每个元素。

void print(Node* set) {
Node* cur = set;
while (cur != NULL) {
cout << cur->data << " ";
cur = cur->next;
}
cout << endl;
}