求集合（用单链表表示）的并、交和差运算

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

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; } 

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

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; } 

以上三个函数中都用到了引用参数，引用参数在C++里才有，所以源代码文件格式应为".cpp"。

与主函数相结合

#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); printf("求并集：\n"); flag = DispList(L3); flag = Intersection(L1, L2, L4); printf("求交集：\n"); flag = DispList(L4); flag = Difference(L1, L2, L5); printf("求差集：\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; } printf("\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; }