0

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

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){

}
4

2 回答 2

0

接下来实施这些：

// 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 和链表来说很好，但通常不是最佳选择，因为它会导致大集合的性能下降。

于 2013-11-24T19:23:10.420 回答
0

我是否应该遍历一个列表并为列表中的每个元素循环遍历第二个列表以检查它是否包含在第二个列表中？

如果您要将您的集合表示为未排序的链表，是的。您可以使用更有效的数据结构和算法来实现集合操作（​​例如排序数组），但如果这是家庭作业，您可能会被链表困住。

对于这项任务来说，这似乎太复杂了，必须有一种更简单的方法来完成这项任务。

这是 C。您需要自己习惯处理大量低级细节，因为该语言没有提供太多内置数据结构和算法的方式。但是几个嵌套循环真的没什么大不了的。

于 2013-11-24T19:28:29.530 回答