c++ - 递归函数删除链表中字符的所有实例

Question

我写了一个递归来删除具有特定数据值的节点，但是它不能正常工作。

Node * removeAll(Node *top, char c){
    if(top == NULL)
        return NULL;

    Node *newTop;
    if(top->data == c){
        newTop = top->next;
        delete top;
    }else{
        newTop = top;
    }

    newTop->next = removeAll(newTop->next,c);

    return newTop;
}

提供给函数的链表包含值 h e l l o 我希望输出的列表包含值 h e o，但它具有值 h e l o

Answer 1

我将作为教程来回答这个问题，因为几乎每个人在学习如何递归思考时都会遇到一些困难。

请注意，因为它使用了 while 循环，@Edward 的答案不是完全递归的形式。

当您学习时，首先用人类语言写出答案的递归描述总是有帮助的。从代码开始将注意力从算法的思考转移到不重要的细节，如语法和指针语义。英语，

A list of the form [HEAD, rest_of_list] with character C removed is equal to rest_of_list with character C removed and HEAD optionally pre-pended to it. Whether to prepend HEAD or not depends on whether it's equal to C.

这里的HEAD是一个字符，rest_of_list本身就是一个列表。

递归部分是从 rest_of_list 中删除 C。请注意，递归发生在比输入短一个字符的字符串上。那挺好的!这意味着算法正在从一个递归调用到下一个递归调用取得进展。

我们还需要描述递归停止的“基本情况”。在这里，由于列表从一个调用到下一个调用越来越短，因此尝试空列表是合乎逻辑的。英语，

When the input list is empty, it can't contain C, so return the empty list.

所以我们准备好编写代码了。首先是基本情况。您的实现很好。 NULL 指针是通常的 C 列表实现中的空列表。

Node *removeAll(Node *list, char c) {
  // Base case.
  if (list == NULL) return NULL;
  // Recursive case.
  // TODO: Complete me.
}

对于递归的情况，我们用英文写的HEAD是C中的list->data，而rest_of_list是list ->下一步。所以继续写吧:

  // Recursive case.
  char head = list->data;
  Node *rest = list->next;

递归case本身有2个case。如果 head 是 c，那么我们只返回 rest 并移除 c。

  if (c == head) return removeAll(rest, c);

剩下的情况是head不等于c。这里有一个选择。您需要一个节点来保存 c。您可以重新使用当前持有它的那个，这意味着您正在更改原始列表。或者您可以分配一个新节点，这意味着原始列表保持不变。在实际应用中，这个决定可能非常重要。假设您希望保持原始列表不变。前置是用

完成的

return allocateNewNode(head, removeAll(rest, c));

此处 allocateNewNode 为未用于其他列表的节点获取新内存。例如，它可以调用 malloc。

另一方面，如果您想更改输入列表(术语mutate 很常见)，则修改list 中的第一个节点。

list->next = removeAll(rest, c);
return list;

总的来说，变异的情况是:

Node *removeAll(Node *list, char c) {
  // Base case: on empty list, return empty list.
  if (list == NULL) return NULL;
  // Recursive cases. Extract head value and rest of list.
  char head = list->data;
  Node *rest = list->next;
  // If head is C, return rest with C removed.
  if (c == head) return removeAll(rest, c);
  // Otherwise prepend C to rest with C removed by mutating the first list node, 
  // which already contains head.
  list->next = removeAll(rest, c);
  return list;
}

我希望这对您和其他试图掌握递归思维窍门的人有所帮助。