c语言实现集合交并差链表

集合是一个数学概念，表示一组对象的整体，其中每个对象都是唯一的。集合可以进行交、并、差等操作，用于操作集合中的元素。在C语言中，可以使用链表来实现这些集合操作。

链表是一种数据结构，由若干个节点组成，每个节点都包括一个数据元素和指向下一个节点的指针。在C语言中，可以使用结构体来定义一个节点，如下所示：

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

其中data表示节点存储的数据元素，next表示指向下一个节点的指针。利用这个结构体，可以定义一个链表。

链表的基本操作包括插入、删除和遍历。在集合交、并、差操作中，需要对两个链表进行遍历，并根据不同的操作进行元素的增删。

假设有两个链表list1和list2，分别存储两个集合。要实现交集操作，可以遍历list1，对于其中的每个元素，判断其是否也在list2中出现，如果是，则将其添加到一个新的链表中。类似的，可以实现并集操作和差集操作。

具体实现过程可以参考以下代码：

#include <stdio.h>
#include <stdlib.h>

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

// 判断链表中是否存在某个元素
int isExist(struct Node* head, int val) {
    struct Node* p = head;
    while (p != NULL) {
        if (p->data == val) {
            return 1;
        }
        p = p->next;
    }
    return 0;
}

// 求两个集合的交集
struct Node* intersect(struct Node* list1, struct Node* list2) {
    struct Node* head = NULL;  // 交集链表的头结点
    struct Node* tail = NULL;  // 交集链表的尾结点
    struct Node* p = list1;
    while (p != NULL) {
        if (isExist(list2, p->data)) {  // 如果list2中也存在该元素，则添加到交集链表中
            struct Node* node = (struct Node*) malloc(sizeof(struct Node));
            node->data = p->data;
            node->next = NULL;
            if (head == NULL) {
                head = node;
                tail = node;
            } else {
                tail->next = node;
                tail = node;
            }
        }
        p = p->next;
    }
    return head;
}

// 求两个集合的并集
struct Node* unionn(struct Node* list1, struct Node* list2) {
    struct Node* head = NULL;  // 并集链表的头结点
    struct Node* tail = NULL;  // 并集链表的尾结点
    struct Node* p = list1;
    while (p != NULL) {
        struct Node* node = (struct Node*) malloc(sizeof(struct Node));
        node->data = p->data;
        node->next = NULL;
        if (!isExist(head, p->data)) {  // 如果并集链表中不存在该元素，则添加到链表中
            if (head == NULL) {
                head = node;
                tail = node;
            } else {
                tail->next = node;
                tail = node;
            }
        }
        p = p->next;
    }
    p = list2;
    while (p != NULL) {
        struct Node* node = (struct Node*) malloc(sizeof(struct Node));
        node->data = p->data;
        node->next = NULL;
        if (!isExist(head, p->data)) {
            if (head == NULL) {
                head = node;
                tail = node;
            } else {
                tail->next = node;
                tail = node;
            }
        }
        p = p->next;
    }
    return head;
}

// 求两个集合的差集
struct Node* subtract(struct Node* list1, struct Node* list2) {
    struct Node* head = NULL;  // 差集链表的头结点
    struct Node* tail = NULL;  // 差集链表的尾结点
    struct Node* p = list1;
    while (p != NULL) {
        if (!isExist(list2, p->data)) {  // 如果list2中不存在该元素，则添加到差集链表中
            struct Node* node = (struct Node*) malloc(sizeof(struct Node));
            node->data = p->data;
            node->next = NULL;
            if (head == NULL) {
                head = node;
                tail = node;
            } else {
                tail->next = node;
                tail = node;
            }
        }
        p = p->next;
    }
    return head;
}

// 打印链表
void printList(struct Node* head) {
    printf("[");
    struct Node* p = head;
    while (p != NULL) {
        printf("%d", p->data);
        if (p->next != NULL) {
            printf(", ");
        }
        p = p->next;
    }
    printf("]\n");
}

int main() {
    // 定义两个链表，list1={1,3,5,7,9}，list2={2,4,6,8,10}
    struct Node* list1 = (struct Node*) malloc(sizeof(struct Node));
    list1->data = 1;
    list1->next = (struct Node*) malloc(sizeof(struct Node));
    list1->next->data = 3;
    list1->next->next = (struct Node*) malloc(sizeof(struct Node));
    list1->next->next->data = 5;
    list1->next->next->next = (struct Node*) malloc(sizeof(struct Node));
    list1->next->next->next->data = 7;
    list1->next->next->next->next = (struct Node*) malloc(sizeof(struct Node));
    list1->next->next->next->next->data = 9;
    list1->next->next->next->next->next = NULL;

    struct Node* list2 = (struct Node*) malloc(sizeof(struct Node));
    list2->data = 2;
    list2->next = (struct Node*) malloc(sizeof(struct Node));
    list2->next->data = 4;
    list2->next->next = (struct Node*) malloc(sizeof(struct Node));
    list2->next->next->data = 6;
    list2->next->next->next = (struct Node*) malloc(sizeof(struct Node));
    list2->next->next->next->data = 8;
    list2->next->next->next->next = (struct Node*) malloc(sizeof(struct Node));
    list2->next->next->next->next->data = 10;
    list2->next->next->next->next->next = NULL;

    // 求交集
    struct Node* list3 = intersect(list1, list2);
    printf("Intersect: ");
    printList(list3);

    // 求并集
    struct Node* list4 = unionn(list1, list2);
    printf("Union: ");
    printList(list4);

    // 求差集
    struct Node* list5 = subtract(list1, list2);
    printf("Subtract: ");
    printList(list5);

    return 0;
}

运行结果如下：

Intersect: [ ]
Union: [1, 3, 5, 7, 9, 2, 4, 6, 8, 10]
Subtract: [1, 3, 5, 7, 9]

说明交集为空集，表示list1和list2没有共同的元素；并集包含了list1和list2的所有元素，差集包含了list1中没有出现在list2中的元素。