Рекурсивная функция, удаляющая все экземпляры символа в связанном списке - PullRequest
Новая
       11

Рекурсивная функция, удаляющая все экземпляры символа в связанном списке

1 голос
/ 09 июня 2019

Я написал рекурсив для удаления узлов с определенным значением данных, однако он работает неправильно. 

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

Ответы [ 2 ]

2 голосов
/ 09 июня 2019

Я отвечу на это как учебное пособие, потому что почти все немного борются, когда учатся рекурсивному мышлению.

Обратите внимание, что, поскольку он использует цикл while, ответ @ Эдварда не является полностью рекурсивным.форма.

Когда вы учитесь, это всегда помогает сначала написать рекурсивное описание ответа на человеческом языке.Начиная с кода, внимание отвлекается от размышлений об алгоритме и до неважных деталей, таких как синтаксис и семантика указателей.На английском языке

Список формы [HEAD, rest_of_list] с удаленным символом C равен 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->data в C. И 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);

В остальном случае 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;
}

Я надеюсь, что это полезно для вас и других, пытающихся овладеть рекурсивным мышлением.

1 голос
/ 09 июня 2019

Изменить это: 

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

к этому: 

while(top && top->data == c){
    newTop = top->next;
    delete top;
    top = newTop;
}
newTop = top;

Таким образом, все последующие элементы, содержащие целевое значение, будут удалены перед переходом к следующему элементу.

Кроме того, эта функция могла бы использовать меньше памяти и быть быстрее, если бы она была написана итеративно, а не рекурсивно.

...