c - 在链表中使用递归

Question

这里是新的。所以，我能够想出如何遍历 A 中的每个元素并将其与 B 中的一个元素进行比较。如果元素不匹配，则将元素存储到另一个列表中，并递归调用该函数到列表中的下一个节点A. 明显的问题是它会将 A 中的所有元素与 B 中的第一个元素进行比较。但是我在如何递归访问 B 中的下一个元素或节点以返回包含值的新集合方面遇到了困难集合 A 不在集合 B 中。

是的，列表已排序。

Node *diff(Node *a, Node *b) {

    Node *tmp;
    tmp = malloc(sizeof(Node));

    if ( (a == NULL) || (b == NULL) )   //Base case
            return NULL;

    if (a->val != b->val){
            tmp = a;
            tmp->next = sset_diff(a->next, b);
    }

    return tmp;


 return NULL;  //Placeholder
}

Answer 1

(特别是)在使用递归时，确定您的子任务很重要。在这里编写另一个函数来检查一个值是否是列表的成员是有意义的:

is_member(int val,Node *list) { //I'm assuming that it's a list of int
    if (list==NULL) return 0;
    if (list->val==val) return 1;
    return is_member(val,list->next);
}

之后，您可以轻松地创建 A 中不在 B 中的值的列表:

Node *diff(Node *a, Node *b) {
    if (a==NULL) return NULL; //the correct base case
    if (is_member(a->val,b)) return diff(a->next,b); //deal with one case
    Node *tmp=malloc(sizeof(Node)); //allocate it only now
    tmp->val=a->val; //assign to the value, not to the Node*
    tmp->next=diff(a->next,b); //the next elements
    return tmp;
    //there is not need to return NULL here
}