数据结构问题求两个集合的差?

作者站长头像
站长
· 阅读数 3
#include <stdio.h>
#include <stdlib.h>

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

Node* getNewLinklist(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = val;
    node->next = NULL;
    return node;
}

Node* insert(Node* head,int val) {
    Node* new_node = getNewLinklist(val);
    if (head == NULL) { 
        return new_node;
    }
    new_node->next = head;
    return new_node;
}


Node* compare(Node* A, Node* B) {
    Node new_nodeb;
    new_nodeb.next = B;
    Node* prevb = &new_nodeb,*tempor = prevb->next;
    while (tempor) {
        for (Node* p = A; p; p = p->next) {
            if (p->data == tempor->data) {
                prevb->next = tempor->next;
                
            }

        }
        prevb = tempor;
        tempor = tempor->next;
    }
    return new_nodeb.next;
}


int main() {
    Node* A = NULL,*B = NULL;
    int arr1[] = { 1,2,3,4,5 };
    int arr2[] = { 4,5,6,7,8 };
    for (int i = 0; i < 5; i++) {
        A = insert(A, arr1[i]);
        B = insert(B, arr2[i]);
    }
    Node* C = compare(A, B);
    for (Node* p = C; p; p = p->next) {
        printf("%d ",p->data);
    }
}

1.问题描述以单链表表示集合,求先后输入的两个集合的差。2.基本要求

输入集合A和集合B,计算集合A、B的差C并输出。

3.算法提示

假设两个已知集合A和B。根据集合运算的规则可知,集合A-B中包含所有属于集合A而不属于集合B的元素。因此,为了求A-B,需建立表示集合A 的单链表,然后对B中的每个元素X,在集合A的链表中进行查找,若存在和X相同的元素,则从该链表中删除。

运行结果的话只有5被删除了,而4并没有删除是什么原因数据结构问题求两个集合的差?对代码进行下面的修改后,代码运行反而不会出现结果了

while (tempor) {
    int k = 0;
    for (Node* p = A; p; p = p->next) {
        if (p->data == tempor->data) {
            prevb->next = tempor->next;
            k = 1;
        }
    }
    if (k == 0) {
        prevb = prevb->next;
        tempor = tempor->next;
    }    
    
}

数据结构问题求两个集合的差?

回复
1个回答
avatar
test
2024-06-25
    while (tempor) {
        for (Node* p = A; p; p = p->next) {
            if (p->data == tempor->data) {
                prevb->next = tempor->next;   
            }
        }
        /*
        prevb 应该为链表中 tempor 的前一个节点。
        但是如果 tempor 被删除了,tempor->next 还在链表中,tempor 本身已经不在链表中了。
        这时令 prevb = tempor ,那么 prevb 这个节点就已经不链表中了。所以通过
               prev->next = tempor->next 不能从链表中删除 tempor 。
        所以 5, 4 连续两个删除只有第一个成功了。
        */
        prevb = tempor;
        tempor = tempor->next;
    }
回复
likes
适合作为回答的
  • 经过验证的有效解决办法
  • 自己的经验指引,对解决问题有帮助
  • 遵循 Markdown 语法排版,代码语义正确
不该作为回答的
  • 询问内容细节或回复楼层
  • 与题目无关的内容
  • “赞”“顶”“同问”“看手册”“解决了没”等毫无意义的内容