我试图得到两组分别由这种形式的单链表表示的交集和差值

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

}

最佳答案

接下来实施这些:

// 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和链接列表,但通常不是最佳选择,因为这会导致大集合的性能降低。

关于c - 在C中使用链表设置交集和差值,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/20179688/

10-11 22:52
查看更多