已知两个链表A和B分别表示两个集合, 其元素递增排列. 设计算法求出两个集合A和B的差集(即仅由在A中出现而不在B中出现的元素所构成的集合), 结果存放在链表A中, 同时返回所求差集中元素的个数

r囧r小猫 2022-10-15 00:43 169阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    short InitHeadNode(struct Node* &, struct Node* &);
    short RearInsert(struct Node* &, struct Node* &, short);
    short GetListLength(struct Node* &);
    short IsElemIn(struct Node* &, short);
    short DeleteNodeIn1andIn2(struct Node* &, struct Node* &);
    void Traversal(struct Node* &);
    /* 链表结点定义 */
    struct Node
    {
        short data;
        struct Node *next;
    };
    int main()
    {
        struct Node *head1;
        struct Node *rear1;
        struct Node *head2;
        struct Node *rear2;
        /* 初始化1#链表的头结点 */
        if(InitHeadNode(head1, rear1) == -1)
        {
            /* 头结点申请失败, 程序直接结束 */
            exit(0);
        }
        short temp;
        /* 向链表中插入数据结点 */
        while(1)
        {
            while(scanf("%hd", &temp) != 1)
            {
                while(getchar() != '\n') ;
                printf("请输入合法数据.\n");
            }
            if(temp == -1)
            {
                break;
            }
            if(RearInsert(head1, rear1, temp) == -1)
            {
                /* 申请结点失败 */
                exit(0);
            }
        }
        /* 初始化2#链表的头结点 */
        if(InitHeadNode(head2, rear2) == -1)
        {
            /* 头结点申请失败, 程序直接结束 */
            exit(0);
        }
        /* 向链表中插入数据结点 */
        while(1)
        {
            while(scanf("%hd", &temp) != 1)
            {
                while(getchar() != '\n') ;
                printf("请输入合法数据.\n");
            }
            if(temp == -1)
            {
                break;
            }
            if(RearInsert(head2, rear2, temp) == -1)
            {
                /* 申请结点失败 */
                exit(0);
            }
        }
        /* 至此, A链表和B链表均已初始化 */
        printf("\nA链表中还剩%3hd个元素.\n", DeleteNodeIn1andIn2(head2, head1));
        Traversal(head1);
        /* */
        return 0;
    }
    /* 判断数据元素value是否在链表中 */
    short IsElemIn(struct Node* &head, short value)
    {
        struct Node *p = head -> next;
        while(p != NULL)
        {
            if(p -> data == value)
            {
                /* 找到数据元素value */
                return 1;
            }
            p = p -> next;
        }
        /* 未找到数据元素value */
        return -1;
    }
    /* 删除以下2#集合中的元素结点: 在2#集合中出现且也在1#集合中出现的元素结点 */
    short DeleteNodeIn1andIn2(struct Node* &head1, struct Node* &head2)
    {
        struct Node *p2 = head2 -> next;
        struct Node *q2 = head2;
        /* 删除在集合2中出现且也在集合1中出现的结点 */
        while(p2 != NULL)
        {
            if(IsElemIn(head1, p2 -> data) == 1)
            {
    
                /* 删除该结点 */
                q2 -> next = p2 -> next;
                free(p2);
                p2 = q2 -> next;
            }
            else
            {
                p2 = p2 -> next;
                q2 = q2 -> next;
            }
        }
        /* 返回经历删除操作后2#链表的表长 */
        return GetListLength(head2);
    }
    /* 遍历单链表并输出 */
    void Traversal(struct Node* &head)
    {
        struct Node *p = head -> next;
        while(p != NULL)
        {
            printf("%3hd", p -> data);
            p = p -> next;
        }
        putchar('\n');
    }
    /* 获取表长 */
    short GetListLength(struct Node* &head)
    {
        struct Node *p = head -> next;
        short length = 0;
        while(p != NULL)
        {
            length ++;
            p = p -> next;
        }
        return length;
    }
    /* 尾插法 */
    short RearInsert(struct Node* &head, struct Node* &rear, short value)
    {
        struct Node *p = (struct Node*)malloc(sizeof(struct Node));
        if(p != NULL)
        {
            /* 结点申请成功 */
            rear -> next = p;
            p -> next = NULL;
            p -> data = value;
            rear = p;
            return 1;
        }
        else
        {
            /* 结点申请失败 */
            return -1;
        }
    }
    /* 初始化头结点 */
    short InitHeadNode(struct Node* &head, struct Node* &rear)
    {
        struct Node *p = (struct Node*)malloc(sizeof(struct Node));
        if(p != NULL)
        {
            /* 头结点申请成功 */
            head = p;
            head -> data = 0;
            head -> next = NULL;
            rear = head;
            return 1;
        }
        else
        {
            /* 头结点申请失败 */
            return -1;
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70 3][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70]: /images/20221014/e2b217fac65d4f3bbbdbe25310e6e5da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70 1]: /images/20221014/d1ee4a028f854af5a290c618159e6135.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70 2]: /images/20221014/6d2e175c0e774d78ba8e59a7ac9ac994.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70 3]: /images/20221014/d1d6b330bd7f4b89baff5fc2c74250d2.png