时间戳

首页 > 解决方案 > 递归函数删除链表中字符的所有实例

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

问题描述

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

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

标签： c++linked-listnodes

解决方案

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

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

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

删除了字符 C的表单列表[HEAD, rest_of_list]等于删除 rest_of_list了字符 C 并且HEAD可选地预先添加到它前面。是否前置HEAD取决于它是否等于C.

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

递归部分正在C从rest_of_list. 请注意，递归发生在比输入短一个字符的字符串上。那挺好的！这意味着该算法正在从一个递归调用到下一个递归调用。

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

当输入列表为空时，不能包含C，所以返回空列表。

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

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

对于递归的情况，HEAD正如我们用英语写的那样，是list->dataC 中的。并且rest_of_list是list->next. 所以继续写：

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

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

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

剩下的情况是 wherehead 不等于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;
}

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

推荐阅读