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

Question

编写程序，采用单链表表示集合（假设同一个结合中不存在重复的元素），将其按递增方式排序，构成有序单链表，并求这样的两个集合的并、交和差。
单链表结点类型定义：

typedef int ElemType;    //元素的数据类型

typedef struct LNode {
    ElemType data;        //结点的数据域
    struct LNode *next;    //指向后继结点
} LinkNode;             //单链表结点类型

函数接口定义：

//尾插法建立单链表,细节不表
void CreateListR(LinkNode *&L, ElemType a[], int n);

//输出线性表,细节不表
void DispList(LinkNode *L);

//求两个有序集合的并
void Union(LinkNode *A, LinkNode *B, LinkNode *&C);

//求两个有序集合的交
void InterSect(LinkNode *A, LinkNode *B, LinkNode *&C);

//求两个有序集合的差
void Subs(LinkNode *A, LinkNode *B, LinkNode *&C);

其中 L 和 A 、B、C都是带附加头结点的有序单链表的头指针。 数组a[] 存放创建有序单链表的元素，n为数组长度，其值不超过3000。
裁判测试程序样例：

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

typedef int ElemType;    //元素的数据类型

typedef struct LNode {
    ElemType data;        //结点的数据域
    struct LNode *next;    //指向后继结点
} LinkNode;                 //单链表结点类型

//尾插法建立单链表,细节不表
void CreateListR(LinkNode *&L, ElemType a[], int n);

//输出线性表,细节不表
void DispList(LinkNode *L);

//求两个有序集合的并
void Union(LinkNode *A, LinkNode *B, LinkNode *&C);

//求两个有序集合的交
void InterSect(LinkNode *A, LinkNode *B, LinkNode *&C);

//求两个有序集合的差
void Subs(LinkNode *A, LinkNode *B, LinkNode *&C);

int main() 
{
    LinkNode *A, *B, *C;
    int n, m;

    scanf("%d", &n);
    ElemType a[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &m);
    ElemType b[m];
    for (int i = 0; i < m; i++)
        scanf("%d", &b[i]);

    CreateListR(A, a, n);
    CreateListR(B, b, m);

    Union(A, B, C);
    printf("集合A与B的并: ");
    DispList(C);

    InterSect(A, B, C);
    printf("集合A与B的交: ");
    DispList(C);

    Subs(A, B, C);
    printf("集合A与B的差: ");
    DispList(C);

    return 1;
}

/* 请在下面填写答案 */

输入样例：
输入有4行。
第1行为单链表A的元素个数，接下来的一行为单链表A的元素，以空格分隔。
第3行为单链表B的元素个数，接下来的一行为单链表B的元素，以空格分隔。

5
1 2 3 4 5
3
2 4 6
输出样例：
输出有3行。
第1行为集合A与B的并；第2行为集合A与B的交；第3行为集合A与B的差。
元素之间以一个空格分隔，行尾无多余的空格。

集合A与B的并: 1 2 3 4 5 6
集合A与B的交: 2 4
集合A与B的差: 1 3 5
为什么我的代码老是显示段错误？求解答
a.cpp: In function ‘int main()’:
a.cpp:31:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);

//求两个有序集合的并
void Union(LinkNode *A, LinkNode *B, LinkNode *&C)
{
    C=(LinkNode*)malloc(sizeof(LinkNode));
    LinkNode *p1,*p2,*p3,*p;
    p1=A->next;
    p2=B->next;
    p3=C;
    while(p1&&p2)
    {
        if(p1->data<=p2->data)
        {
            p=(LinkNode*)malloc(sizeof(LinkNode));
            p->data=p1->data;
            p3->next=p;
            p3=p;
            p1=p1->next;
            if(p1->data==p2->data)
                p2=p2->next;
        }
        else
        {
            p=(LinkNode*)malloc(sizeof(LinkNode));
            p->data=p2->data;
            p3->next=p;
            p3=p;
            p2=p2->next;
        }
    }
    p3->next=p1?p1:p2;
}

//求两个有序集合的交
void InterSect(LinkNode *A, LinkNode *B, LinkNode *&C)
{
    C=(LinkNode*)malloc(sizeof(LinkNode));
    LinkNode *p1,*p2,*p3,*p;
    p1=A->next;
    p2=B->next;
    p3=C;
    while(p1&&p2)
    {
            if(p1->data>p2->data)
                p2=p2->next;
        else if(p1->data<p2->data)
            p1=p1->next;
        else
            {
                p=(LinkNode*)malloc(sizeof(LinkNode));
                p->data=p1->data;
                p3->next=p;
                p3=p;
                p1=p1->next;
                p2=p2->next;
            }
    }
    p3->next=NULL;
}
//求两个有序集合的差
void Subs(LinkNode *A, LinkNode *B, LinkNode *&C)
{
    C=(LinkNode*)malloc(sizeof(LinkNode));
    LinkNode *p1,*p2,*p3,*p;
    p1=A->next;
    p2=B->next;
    p3=C;
    if(p1->data<p2->data)
    {
            p=(LinkNode*)malloc(sizeof(LinkNode));
            p->data=p1->data;
            p3->next=p;
            p3=p;
            p1=p1->next;
    }
    else if(p1->data>p2->data)
        p2=p2->next;
    else {
        p1=p1->next;
        p2=p2->next;
    }
    if(p1)
        p3->next=p1;
    else p3->next=NULL;
}

Answer 1

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7790788