Set intersection and difference with linked lists in C

Question

I'm trying to get the intersection and difference of two sets who are each represented by a singly-linked-list of this form

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

I already wrote this functions in the previous tasks which compute the number of elements in a list and determine if a certain element is contained in a list.

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;
}

Now I have to code the following functions but I dont know how to do it. Should I loop through one list and for every element in the list loop through the second list to check whether it is/is not(difference) contained in the second? That seems to complex for this task, there must be an easier way to do this. Hope you can help me

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

}

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

}

Answer 1

Implement these next:

// 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);

These are useful for many purposes, but here you'll be composing them:

add(copy_one(s), &existing_list);

to build up your result.

Now the algorithm for intersection is:

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

For difference s1 - s2, it's

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

I will let you work out the C. There's no fun in me giving you a complete answer.

Note that the choice of linked lists to represent sets is fine for learning about C and linked lists, but not often the best choice because it leads to slow performance for big sets.

Answer 2

Should I loop through one list and for every element in the list loop through the second list to check whether it is/is not(difference) contained in the second?

If you're going to represent your sets as unsorted linked lists, yes. There are more efficient data structures and algorithms you could be using to implement set operations (e.g. sorted arrays), but if this is homework, you're probably stuck with linked lists.

That seems too complex for this task, there must be an easier way to do this.

This is C. You'll need to get used to handling lots of low-level details yourself, because the language doesn't offer much in the way of built-in data structures and algorithms. But a couple of nested loops are really no big deal.