c - 在C中设置链表的交集和差集

Question

我试图获取两个集合的交集和差异，每个集合都由这种形式的单链表表示

struct node{
    unsigned n;
    struct node *next;
};

我已经在之前的任务中编写了这个函数，它计算列表中的元素数量并确定列表中是否包含某个元素。

int cardinality(struct node *s){
    struct node *tmp = s;
    int count = 0;

    while(tmp != NULL){
    tmp = tmp->next;
    count++;
    }

    return count;
}

int contains(struct node *s, int v){ /* returns 0 if in list, 1 if not in list */
    struct node *tmp = s;
    int contains = 1;

    while(tmp->next != NULL){
    if(tmp->n == v){
        contains = 0;
        break;
        } else{
        if(tmp == NULL) break;
        tmp = tmp->next;
    }
    }
    return contains;
}

现在我必须编写以下函数，但我不知道该怎么做。 我是否应该循环遍历一个列表，并为列表中的每个元素循环遍历第二个列表以检查它是否包含在第二个列表中(差异)？对于这项任务来说，这似乎很复杂，必须有一种更简单的方法来完成此任务。 希望你能帮助我

void intersection(struct node *s1, struct node *s2, struct node **result){

}

void difference(struct node *s1, struct node *s2, struct node **result){

}

Answer 1

接下来实现这些:

// Copy one node s, giving the copy a NULL next pointer.
struct node *copy_one(struct node *s);

// Add the given node s to an existing list.
void add(struct node *s, struct node **existing);

它们有多种用途，但在这里您将编写它们:

add(copy_one(s), &existing_list);

建立你的结果。

现在交集的算法是:

set result empty
for all elements e in s1
   if e->val is contained in s2
       add a copy of e to result

对于差异s1 - s2，它是

set result empty
for all elements e in s1
   if e is _not_ contained in s2
       add a copy of e to result

我会让你算出 C。给你一个完整的答案没有任何乐趣。

请注意，选择链表来表示集合对于学习 C 和链表来说很好，但通常不是最佳选择，因为它会导致大集合的性能降低。