我试图得到两组分别由这种形式的单链表表示的交集和差值
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/