关于#c语言#的问题：求出A和B的差集A-B(由在A中出现而不在B中出现的元素所构成的集合）

Question

有两个存放整数的线性表A和B，链式存储，元素个数分别为m和n，表中元素单调递增。求出A和B的差集A-B(由在A中出现而不在B中出现的元素所构成的集合）。将差集保存在线性表A中，差集的元素保持原有的顺序。

Answer 1

两个线性表遍历逐个元素比较，A中元素不在B中的，就放入差集链表中。

代码如下：

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

struct DataSetQueue 
{
    double val;
    DataSetQueue* next;
};


//显示队列
void show(struct DataSetQueue* head)
{
    struct DataSetQueue* p = head;
    while(p)
    {
        printf("%g ",p->val);
        p = p->next;
    }
    printf("\n");
}


//创建队列
struct DataSetQueue* CreateQueue()
{
    struct DataSetQueue *head = (struct DataSetQueue*)malloc(sizeof(DataSetQueue));
    head->next =0;
    return head;
}

//复制队列
struct DataSetQueue* Copy(struct DataSetQueue* head)
{
    struct DataSetQueue* phead,*t,*p1,*p2;
    phead = CreateQueue();
    phead->val = head->val;
    phead->next = 0;

    p1 = phead;
    p2 = head->next;
    while(p2)
    {
        t = (struct DataSetQueue*)malloc(sizeof(DataSetQueue));
        t->next = 0;
        t->val = p2->val;
        p1->next = t;
        p1 = t;
        p2 = p2->next;
    }
    return phead;

}

//添加到队列
void Push(struct DataSetQueue* head,double v)
{
    struct DataSetQueue* p = head;
    struct DataSetQueue* t = (struct DataSetQueue*)malloc(sizeof(DataSetQueue));
    t->val = v;
    t->next = 0;
    while(p->next)
        p = p->next;
    p->next = t;
}


//第一个元素弹出队列
struct DataSetQueue* Pop(struct DataSetQueue* head)
{
    struct DataSetQueue* p = head;
    head = head->next;
    return p;
}

//释放空间
void Release(struct DataSetQueue* head)
{
    struct DataSetQueue* p = head;
    while(head)
    {
        p = head->next;
        free(head);
        head = p;
    }
}



//从队列中删除某个元素
struct DataSetQueue* isInAndDel(struct DataSetQueue* head,double v)
{
    struct DataSetQueue* p1;
    struct DataSetQueue* t;
    if(head == 0)
        return 0;
    if (head->val == v)
    {
        p1 = head;
        head = head->next;
        free(p1);
        return head;
    }
    p1 = head;
    while(p1->next)
    {
        t = p1->next;
        if(t->val == v)
        {
            p1->next = t->next;
            free(t);
            return head;
        }else
            p1 = p1->next;
    }
    return 0;
}



//求差在p1中，但不在p2中
struct DataSetQueue* Chaji(struct DataSetQueue* p1,struct DataSetQueue* p2)
{
    struct DataSetQueue* tmp;
    struct DataSetQueue* head = Copy(p1);
    struct DataSetQueue* t2 = p2;
    while(t2)
    {
        tmp = isInAndDel(head,t2->val);
        if(tmp)
            head = tmp;
        t2 = t2->next;
    }
    return head;
}


int main()
{
    int i,m,n;
    int data;
    struct DataSetQueue* h1,*h2,*cj;
    h1 = CreateQueue();
    h2 = CreateQueue();
    printf("请输入m和n：");
    scanf("%d %d",&m,&n);//读入m和n
    printf("请输入A中的%d个数据：",m);
    for (i=0;i<m;i++)
    {
        scanf("%d",&data);
        if(i==0)
            h1->val = data;
        else
            Push(h1,data);
    }

    printf("请输入B中的%d个数据：",n);
    for (i=0;i<n;i++)
    {
        scanf("%d",&data);
        if(i==0)
            h2->val = data;
        else
            Push(h2,data);
    }


    cj = Chaji(h1,h2);
    printf("集合1与集合2的差集:");
    show(cj);

    Release(h1);
    Release(h2);
    Release(cj);
    return 0;

}